热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

华为机考108题(c++)(4151)

HJ41称砝码描述现有n种砝码,重量互不相等,分别为m1,m2,m3…mn;每种砝码对应的数量为x1,x2,x3xn。现在要用这
HJ41 称砝码

描述

现有n种砝码,重量互不相等,分别为 m1,m2,m3…mn ;
每种砝码对应的数量为 x1,x2,x3...xn 。现在要用这些砝码去称物体的重量(放在同一侧),问能称出多少种不同的重量。

注:

称重重量包括 0

数据范围:每组输入数据满足 1≤n≤10 , 1≤mi​≤2000 , 1≤xi​≤10

输入描述:

对于每组测试数据:
第一行:n --- 砝码的种数(范围[1,10])
第二行:m1 m2 m3 ... mn --- 每种砝码的重量(范围[1,2000])
第三行:x1 x2 x3 .... xn --- 每种砝码对应的数量(范围[1,10])

输出描述:

利用给定的砝码可以称出的不同的重量数

方法一:集合

#include
#include
#include
#include
using namespace std;int main(){int n;while(cin >> n){vector weight(n);vector num(n);for(int i &#61; 0; i > weight[i];for(int i &#61; 0; i > num[i];unordered_set s; //集合用于去重s.insert(0); //0也是一种for(int i &#61; 0; i temp(s);for(auto iter &#61; temp.begin(); iter !&#61; temp.end(); iter&#43;&#43;) //当前集合每个都可以加一次s.insert(*iter &#43; weight[i]);}}cout <}

方法二&#xff1a;动态规划

#include
#include
#include
using namespace std;int main(){int n;while(cin >> n){vector weight(n);vector num(n);int sum &#61; 0;for(int i &#61; 0; i > weight[i];for(int i &#61; 0; i > num[i];sum &#43;&#61; num[i] * weight[i]; //砝码总重量}vector dp(sum &#43; 1, false); //记录0到sum是否可行dp[0] &#61; true;for(int i &#61; 0; i &#61; weight[i]; k--) //每次剩余的每个都可以添加if(dp[k - weight[i]])dp[k] &#61; 1;}}int count &#61; 0;for(int i &#61; 0; i <&#61; sum; i&#43;&#43;) //找到为1的就是可以组成的质量&#xff0c;计数if(dp[i])count&#43;&#43;;cout <}

 HJ42 学英语

描述

Jessi初学英语&#xff0c;为了快速读出一串数字&#xff0c;编写程序将数字转换成英文&#xff1a;

具体规则如下:
1.在英语读法中三位数字看成一整体&#xff0c;后面再加一个计数单位。从最右边往左数&#xff0c;三位一单位&#xff0c;例如12,345 等
2.每三位数后记得带上计数单位 分别是thousand, million, billion.
3.公式&#xff1a;百万以下千以上的数 X thousand X, 10亿以下百万以上的数&#xff1a;X million X thousand X, 10 亿以上的数&#xff1a;X billion X million X thousand X. 每个X分别代表三位数或两位数或一位数。
4.在英式英语中百位数和十位数之间要加and&#xff0c;美式英语中则会省略&#xff0c;我们这个题目采用加上and&#xff0c;百分位为零的话&#xff0c;这道题目我们省略and
下面再看几个数字例句&#xff1a;

22: twenty two

100:  one hundred

145:  one hundred and forty five
1,234:  one thousand two hundred and thirty four
8,088:  eight thousand (and) eighty eight (注:这个and可加可不加&#xff0c;这个题目我们选择不加)
486,669:  four hundred and eighty six thousand six hundred and sixty nine
1,652,510:  one million six hundred and fifty two thousand five hundred and ten
说明&#xff1a;
数字为正整数&#xff0c;不考虑小数&#xff0c;转化结果为英文小写&#xff1b;
保证输入的数据合法

关键字提示&#xff1a;and&#xff0c;billion&#xff0c;million&#xff0c;thousand&#xff0c;hundred。

数据范围&#xff1a;1≤n≤2000000 

输入描述&#xff1a;

输入一个long型整数

输出描述&#xff1a;

输出相应的英文写法

方法一&#xff1a;

#include
#include using namespace std;const string ones[] &#61; { "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine" };
const string tens[] &#61; { "ten","eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen" };
const string twenties[] &#61; { "zero","ten","twenty","thirty","forty","fifty","sixty","seventy","eighty","ninety" };
const int ihundreds[] &#61; { (int)1e2, (int)1e3, (int)1e6, (int)1e9, (int)1e12 };
const string hundreds[] &#61; { "hundred", "thousand", "million", "billion" };string itoe(long long n){if (0<&#61;n && n<&#61;9){//个位数&#xff0c;直接输出return ones[n];}if (10<&#61;n && n<20){//十位数&#xff0c;直接输出return tens[n%10];}if (20<&#61;n && n<1e2){//20-100return twenties[n/10] &#43; (n%10 ? " " &#43; ones[n%10] : "");}for (int i&#61;0; i <4; i&#43;&#43;){//大于100if (n }int main(){long long n;while (cin>>n){cout<}

方法二&#xff1a;模拟

#include
#include
#include
#include using namespace std;const vector num1 &#61; {"", "thousand", "million", "billion"};
const vector num2 &#61; {"", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
const vector num3 &#61; {"", "", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"};
const vector num4 &#61; {"ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"};int main(){long n;while(cin >> n){vector res;string s &#61; to_string(n);vector v;int i &#61; s.size() - 1;//此时i指向数字的最低位while(i >&#61; 0){//从低位开始每三位划分int j &#61; i;while(j > 0 && i - j <2) j--;v.push_back(s.substr(j, i - j &#43; 1));i &#61; j - 1;}reverse(v.begin(), v.end());for(int i &#61; 0; i }

HJ43 迷宫问题

描述

定义一个二维数组 N*M &#xff0c;如 5 × 5 数组下所示&#xff1a;


int maze[5][5] &#61; {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};


它表示一个迷宫&#xff0c;其中的1表示墙壁&#xff0c;0表示可以走的路&#xff0c;只能横着走或竖着走&#xff0c;不能斜着走&#xff0c;要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。

数据范围&#xff1a; 2≤n,m≤10  &#xff0c; 输入的内容只包含 0≤val≤1 

输入描述&#xff1a;

输入两个整数&#xff0c;分别表示二维数组的行数&#xff0c;列数。再输入相应的数组&#xff0c;其中的1表示墙壁&#xff0c;0表示可以走的路。数据保证有唯一解,不考虑有多解的情况&#xff0c;即迷宫只有一条通道。

输出描述&#xff1a;

左上角到右下角的最短路径&#xff0c;格式如样例所示。

方法一&#xff1a;dfs递归&#43;回溯

#include
#include
using namespace std;vector > res;
void dfs(vector>& matrix, int n, int m, int i, int j, vector>& paths){paths.push_back(make_pair(i, j)); //记入路径matrix[i][j] &#61; 1; //经过部分设置为1&#xff0c;表示后续不能经过if(i &#61;&#61; n - 1 && j &#61;&#61; m - 1){ //到达终点res &#61; paths;return;}//四个方向搜索if(i &#43; 1 &#61; 0 && matrix[i - 1][j] &#61;&#61; 0)dfs(matrix, n, m, i - 1, j, paths);if(j - 1 >&#61; 0 && matrix[i][j - 1] &#61;&#61; 0)dfs(matrix, n, m, i, j - 1, paths);paths.pop_back(); //回溯matrix[i][j] &#61; 0;
}
int main(){int n, m;while(cin >> n >> m){vector > matrix(n, vector(m, 0));for(int i &#61; 0; i > matrix[i][j];vector > paths; //记录临时路径dfs(matrix, n, m, 0, 0, paths); //dfs遍历矩阵for(int i &#61; 0; i }

方法二&#xff1a;dfs非递归&#43;逆向搜索


#include
#include
#include
using namespace std;int main(){int n, m;int direct[4][2] &#61; {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};while(cin >> n >> m){vector > matrix(n &#43; 1, vector(m &#43; 1, 0)); for(int i &#61; 1; i <&#61; n; i&#43;&#43;)for(int j &#61; 1; j <&#61; m; j&#43;&#43;) //输入迷宫矩阵cin >> matrix[i][j];stack > s; //记录深度优先的栈s.push(make_pair(1, 1)); //第一个结点入栈matrix[1][1] &#61; 1;vector > res;while(!s.empty()){auto p &#61; s.top();s.pop();for(int i &#61; 0; i <4; i&#43;&#43;){ //四个方向int x &#61; p.first &#43; direct[i][0];int y &#61; p.second &#43; direct[i][1];if(x > 0 && y > 0 && x <&#61; n && y <&#61; m && matrix[x][y] &#61;&#61; 0){ //确保不越界再看是否为0matrix[x][y] &#61; p.first * 100 &#43; p.second; //修改矩阵为前一个的坐标&#xff0c;百位为i&#xff0c;个位为jif(x &#61;&#61; n && y &#61;&#61; m) //到达终点break;s.push(make_pair(x, y));}}}int i &#61; n;int j &#61; m;while(matrix[i][j] !&#61; 1){ //直到遇到起点res.push_back(make_pair(i, j)); //从终点逆向添加int temp &#61; matrix[i][j];i &#61; temp / 100;j &#61; temp % 100;}res.push_back(make_pair(1, 1)); //添加起点for(int i &#61; res.size() - 1; i >&#61; 0; i--) //反向输出路径cout <<"(" <}

 方法三&#xff1a;BFS

#include using namespace std;
int a[15][15],vis[15][15];
int b[4][2]&#61;{{-1,0},{0,1},{1,0},{0,-1}};//上下左右四个方向
pair fa[15][15];//记录当前下标的父亲下标void dfs(int x,int y){//dfs打印路径if(x&#61;&#61;0&&y&#61;&#61;0)//如果到达左上角&#xff0c;则退出return;auto t&#61;fa[x][y];dfs(t.first,t.second);printf("(%d,%d)\n",x,y);
}
int main(){int n,m;while(cin >> n >> m){for(int i&#61;0;i> a[i][j];//输入迷宫memset(vis,0,sizeof(vis));memset(fa,0,sizeof(fa));queue> q;//队列q.push({0,0});//左上角坐标入队列vis[0][0]&#61;1;while(!q.empty()){auto u&#61;q.front();q.pop();if(u.first&#61;&#61;n-1&&u.second&#61;&#61;m-1){break;}for(int i&#61;0;i<4;i&#43;&#43;){//遍历四个方向int nx&#61;u.first&#43;b[i][0],ny&#61;u.second&#43;b[i][1];if(nx<0||nx>&#61;n||ny<0||ny>&#61;m)continue;if(vis[nx][ny]&#61;&#61;0&&a[nx][ny]&#61;&#61;0){//如果当前坐标未访问过并且可以走&#xff0c;则入队列&#xff0c;并且当前坐标指定父亲坐标fa[nx][ny]&#61;{u.first,u.second};q.push({nx,ny});vis[nx][ny]&#61;1;}}}printf("(%d,%d)\n",0,0);dfs(n-1,m-1);}return 0;
}

HJ44 Sudoku

描述

问题描述&#xff1a;数独&#xff08;Sudoku&#xff09;是一款大众喜爱的数字逻辑游戏。玩家需要根据9X9盘面上的已知数字&#xff0c;推算出所有剩余空格的数字&#xff0c;并且满足每一行、每一列、每一个3X3粗线宫内的数字均含1-9&#xff0c;并且不重复。

例如&#xff1a;

输入

输出

数据范围&#xff1a;输入一个 9*9 的矩阵

输入描述&#xff1a;

包含已知数字的9X9盘面数组[空缺位以数字0表示]

输出描述&#xff1a;

完整的9X9盘面数组

方法一&#xff1a;递归

#include using namespace std;int num[9][9];//用于保存9x9盘面
bool flag &#61; false;//flag为true时表示推算完成&#xff0c;结束递归bool check(int n){//判断当前位置的值是否满足条件int h &#61; n / 9;//行号int l &#61; n % 9;//列号for (int i &#61; 0; i <9; &#43;&#43;i){//同一列中不能有重复if (i !&#61; h && num[i][l] &#61;&#61; num[h][l]){return false;}}for (int j &#61; 0; j <9; &#43;&#43;j){//同一行中不能有重复if (j !&#61; l && num[h][j] &#61;&#61; num[h][l]){return false;}}for (int i &#61; h / 3 * 3; i }void dfs(int n)
{if (n &#61;&#61; 81){//如果已经递归到右下角&#xff0c;输出整个盘面&#xff0c;并置flag为true&#xff0c;结束递归for (int i &#61; 0; i <9; &#43;&#43;i){for (int j &#61; 0; j <8; &#43;&#43;j){cout <}int main()
{for (int i &#61; 0; i <9; &#43;&#43;i){for (int j &#61; 0; j <9; &#43;&#43;j){cin >> num[i][j];//输入9x9盘面}}dfs(0);//从左上角开始递归return 0;
}

方法二&#xff1a;

#include using namespace std;int num[9][9];//用于保存9x9盘面
int row[9][9]&#61;{0};
int col[9][9]&#61;{0};
int block[3][3][9]&#61;{0};
bool flag &#61; false;//flag为true时表示推算完成&#xff0c;结束递归bool check(int n,int num){//判断当前位置的值是否满足条件int h &#61; n / 9;//行号int l &#61; n % 9;//列号if(row[h][num-1] &#61;&#61; 1||col[l][num-1] &#61;&#61; 1|| block[h/3][l/3][num-1]&#61;&#61;1){return false;}return true;
}void dfs(int n){if (n &#61;&#61; 81){//如果已经递归到右下角&#xff0c;输出整个盘面&#xff0c;并置flag为true&#xff0c;结束递归for (int i &#61; 0; i <9; &#43;&#43;i){for (int j &#61; 0; j <8; &#43;&#43;j){cout <}int main()
{for (int i &#61; 0; i <9; &#43;&#43;i){for (int j &#61; 0; j <9; &#43;&#43;j){int temp;cin >> num[i][j];//输入9x9盘面temp &#61; num[i][j];if(temp!&#61;0){//记录每行、每列、每九宫格值的信息row[i][temp-1] &#61; 1;col[j][temp-1] &#61; 1;block[i/3][j/3][temp-1] &#61; 1;}}}dfs(0);//从左上角开始递归return 0;
}

方法二&#xff1a;递归空间优化&#xff08;位运算&#xff09;


#include
#include
using namespace std;vector > sudoku(9, vector(9, 0)); //记录数独矩阵
vector col(9, 0); //用数字记录每列1-9是否有被使用过
vector row(9, 0); //用数字记录每行1-9是否有被使用过
vector > block(3, vector(3, 0)); //用数字记录每个方块1-9是否有被使用过
vector > space; //记录空缺的位置void flip(int i, int j, int num){ //将第num位由0变成1或者由1变回0row[i] ^&#61; (1 <}void dfs(int pos, bool& valid){ //dfs搜索每一种情况if(pos &#61;&#61; space.size()){ //填充到空缺结尾&#xff0c;结束valid &#61; true;return;}auto p &#61; space[pos];for(int i &#61; 0; i <9 && !valid; i&#43;&#43;){ //遍历1-9&#xff0c;尝试每个数字int mask &#61; 1 <}int main(){for(int i &#61; 0; i <9; i&#43;&#43;)for(int j &#61; 0; j <9; j&#43;&#43;){ //输入矩阵cin >> sudoku[i][j];if(sudoku[i][j] &#61;&#61; 0) //如果缺少&#xff0c;坐标加入缺少的数组space.push_back(make_pair(i, j));else{ //否则行列块都记录这个数字出现过了int num &#61; sudoku[i][j];flip(i, j, num - 1);}}bool valid &#61; false;dfs(0, valid);for(int i &#61; 0; i <9; i&#43;&#43;){ //输出for(int j &#61; 0; j <9; j&#43;&#43;){cout <}

 HJ45 名字的漂亮度

描述

给出一个字符串&#xff0c;该字符串仅由小写字母组成&#xff0c;定义这个字符串的“漂亮度”是其所有字母“漂亮度”的总和。
每个字母都有一个“漂亮度”&#xff0c;范围在1到26之间。没有任何两个不同字母拥有相同的“漂亮度”。字母忽略大小写。

给出多个字符串&#xff0c;计算每个字符串最大可能的“漂亮度”。

本题含有多组数据。

数据范围&#xff1a;输入的名字长度满足 1≤n≤10000 

输入描述&#xff1a;

第一行一个整数N&#xff0c;接下来N行每行一个字符串

输出描述&#xff1a;

每个字符串可能的最大漂亮程度

/*
解题思路&#xff1a;笨方法——用「钱」式思维来思考
名字的漂亮度&#xff0c;其实就是比谁的名字更值钱&#xff01;
我们将名字的字母对应的「数字」作为它的价钱&#xff0c;
比如 26 最高&#xff0c;1 则最低&#xff0c;按大小顺序排布。
那么&#xff0c;我们要得到名字的最大可能「漂亮度」&#xff0c;
就要使得&#xff0c;越高频出现的字母&#xff0c;价钱越高。
Better than OK? 来&#xff01;我们一起开始写代码&#xff01;
*/
#include
#include
using namespace std;
//计算名字的最大可能漂亮度&#xff08;最高价钱&#xff09;的函数接口
int MostValuableName (string Name) {int Alphabet[26] &#61; {0}; //初始化一个数组&#xff0c;用于记录名字中不同字母出现的次数int Price[26] &#61; {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26}; //初始化一个价钱表int MostValuable &#61; 0; //初始化名字的最高价钱for (int i &#61; 0; i &#61; &#39;A&#39; && Name[i] <&#61; &#39;Z&#39;) {Alphabet[Name[i] - &#39;A&#39;] &#43;&#61; 1; //累加字母的出现次数}//小写字母的情况else if (Name[i] >&#61; &#39;a&#39; && Name[i] <&#61; &#39;z&#39;) {Alphabet[Name[i] - &#39;a&#39;] &#43;&#61; 1; //累加字母的出现次数}}sort(Alphabet, Alphabet &#43; 26);for (int i &#61; 0; i <26; i&#43;&#43;) {MostValuable &#43;&#61; Alphabet[i] * Price[i]; //依次取高频字母&#xff0c;对应地&#xff0c;依次取高价钱&#xff1b;//正所谓「好货不便宜&#xff0c;便宜无好货」&#xff0c;哦&#xff0c;好像不对&#xff0c;//应该是卖得越多的货的价钱越高&#xff0c;就越赚钱&#xff01;&#xff01;&#xff01;}return MostValuable; //返回一个名字的最大可能价钱&#xff08;即漂亮度&#xff09;
}
//计算多个名字的最大可能漂亮度&#xff08;最高价钱&#xff09;的函数接口
int MaximumPriceOfName (int Number) {string Name; //字符串形式的名字for (int i &#61; 0; i > Name; //输入名字cout <}
//主函数
int main () {int N; //需要计算最大可能漂亮的名字个数while (cin >> N) {MaximumPriceOfName (N); //输出多个名字的最大可能漂亮度}return 0;
}

HJ46 截取字符串 

描述

输入一个字符串和一个整数 k &#xff0c;截取字符串的前k个字符并输出

数据范围&#xff1a;字符串长度满足 1≤n≤1000  &#xff0c; 1≤k≤n 

输入描述&#xff1a;

1.输入待截取的字符串

2.输入一个正整数k&#xff0c;代表截取的长度

输出描述&#xff1a;

截取后的字符串

方法一&#xff1a;substr&#xff08;&#xff09;

#include
#include using namespace std;int main()
{string str;int k;while(cin>>str>>k){//输入字符串和kstring sub_str &#61; str.substr(0,k);cout<}

方法二&#xff1a;遍历

#include
#include using namespace std;int main()
{string str;int k;while(cin>>str>>k){//输入字符串和kfor(int i &#61; 0;i }

HJ48 从单向链表中删除指定值的节点

 方法一&#xff1a;数组模拟

#include
#include
#include
using namespace std;int main(){int n, head;while(cin >> n >> head){vector array; //用数组模拟链表array.push_back(head);for(int i &#61; 1; i > num >> pos_num; //输入要插入的数和它要插入哪个数字后面auto iter &#61; find(array.begin(), array.end(), pos_num); //找到要插入后面你的那个位置if(iter &#61;&#61; array.end()) //结尾push_backarray.push_back(num);else //中间insertarray.insert(iter &#43; 1, num);}int remove;cin >> remove;array.erase(find(array.begin(), array.end(), remove)); //找到要移除的数字的位置for(int i &#61; 0; i }

方法二&#xff1a;链表

#include
#include
#include
using namespace std;struct node{ //链表结点int val;struct node* next &#61; NULL;
};int main(){int n, val;while(cin >> n >> val){node* head &#61; new node; //头结点head->val &#61; val;for(int i &#61; 1; i > cur >> pre;node* p &#61; new node; //添加这个结点p->val &#61; cur;node* q &#61; head;while(q->val !&#61; pre) //找到前序结点q &#61; q->next;p->next &#61; q->next; //断开q->next &#61; p; //插入}int remove;cin >> remove;node* p &#61; head;while(p !&#61; NULL){if(p->val !&#61; remove) //不输出remove&#xff0c;其他都输出cout <val <<" ";p &#61; p->next;}cout <}

HJ50 四则运算

描述

输入一个表达式&#xff08;用字符串表示&#xff09;&#xff0c;求这个表达式的值。

保证字符串中的有效字符包括[‘0’-‘9’],‘&#43;’,‘-’, ‘*’,‘/’ ,‘(’&#xff0c; ‘)’,‘[’, ‘]’,‘{’ ,‘}’。且表达式一定合法。

数据范围&#xff1a;表达式计算结果和过程中满足 ∣val∣≤1000  &#xff0c;字符串长度满足 1≤n≤1000 

输入描述&#xff1a;

输入一个算术表达式

输出描述&#xff1a;

得到计算结果

方法一&#xff1a;递归

#include
#include
#include
using namespace std;int compute(string& s, int left, int right){char op &#61; &#39;&#43;&#39;; //默认加开始int num &#61; 0;vector st;for(int i &#61; left; i <&#61; right; i&#43;&#43;){if(isdigit(s[i])) //数字num &#61; num * 10 &#43; s[i] - &#39;0&#39;; //计算该部分数字总和if(s[i] &#61;&#61; &#39;{&#39; || s[i] &#61;&#61; &#39;[&#39; || s[i] &#61;&#61; &#39;(&#39;){ //进入左括号int layer &#61; 0; //统计左括号层数int j &#61; i;while(j <&#61; right){ //遍历到右边if(s[j] &#61;&#61; &#39;{&#39; || s[j] &#61;&#61; &#39;[&#39; || s[j] &#61;&#61; &#39;(&#39;)layer&#43;&#43;; //遇到左括号&#xff0c;层数累加else if(s[j] &#61;&#61; &#39;}&#39; || s[j] &#61;&#61; &#39;]&#39; || s[j] &#61;&#61; &#39;)&#39;){layer--; //遇到右括号层数递减if(layer &#61;&#61; 0) //直到层数为0break;}j&#43;&#43;;}num &#61; compute(s, i &#43; 1, j - 1); //递归计算括号中的部分i &#61; j &#43; 1;}if(!isdigit(s[i]) || i &#61;&#61; right){ //遇到运算符或者结尾switch(op){ //根据运算符开始计算case &#39;&#43;&#39;: st.push_back(num); break; //加减法加入到末尾case &#39;-&#39;: st.push_back(-num); break;case &#39;*&#39;: st.back() *&#61; num; break; //乘除法与末尾计算case &#39;/&#39;: st.back() /&#61; num; break;}op &#61; s[i]; //修改为下一次的运算符num &#61; 0;}}int res &#61; 0; for(int x : st) //累加和res &#43;&#61; x;return res;
}
int main(){string s;while(cin >> s){cout <}

 方法二&#xff1a;双栈法

#include
#include
using namespace std;void compute(stack& st1, stack& st2){ //根据栈顶运算符弹出栈顶两个元素进行运算int b &#61; st1.top();st1.pop();int a &#61; st1.top();st1.pop();char op &#61; st2.top(); //栈顶运算符st2.pop();if(op &#61;&#61; &#39;&#43;&#39;) a &#61; a &#43; b; //加else if(op &#61;&#61; &#39;-&#39;) a &#61; a - b; //减else if(op &#61;&#61; &#39;*&#39;) a &#61; a * b; //乘else if(op &#61;&#61; &#39;/&#39;) a &#61; a / b; //除st1.push(a);
}bool priority(char m, char n){ //比较运算符优先级if(m &#61;&#61; &#39;(&#39;) //括号优先级最高return false;else if((m &#61;&#61; &#39;&#43;&#39; || m &#61;&#61; &#39;-&#39;) && (n &#61;&#61; &#39;*&#39; || n &#61;&#61; &#39;/&#39;)) //加减法小于乘除法return false;return true;
}
int main(){string s;while(cin >> s){stack st1; //记录运算数字stack st2; //记录运算符st2.push(&#39;(&#39;); //整个运算式添加括号s &#43;&#61; &#39;)&#39;;bool flag &#61; false;for(int i &#61; 0; i }

 HJ51 输出单向链表中倒数第k个结点

描述

输入一个单向链表&#xff0c;输出该链表中倒数第k个结点&#xff0c;链表的倒数第1个结点为链表的尾指针。

链表结点定义如下&#xff1a;

struct ListNode
{int m_nKey;ListNode* m_pNext;
};

正常返回倒数第k个结点指针&#xff0c;异常返回空指针.

要求&#xff1a;

(1)正序构建链表;

(2)构建后要忘记链表长度。

数据范围&#xff1a;链表长度满足 1≤n≤1000  &#xff0c;k≤n  &#xff0c;链表中数据满足0≤val≤10000 

本题有多组样例输入。

输入描述&#xff1a;

输入说明
1 输入链表结点个数
2 输入链表的值
3 输入k的值

输出描述&#xff1a;

输出一个整数

方法一&#xff1a;根据长度找倒数k

#include
using namespace std;struct ListNode{ //链表结点int val;ListNode* next;ListNode(int x) : val(x), next(NULL){} //初始化
};
ListNode* FindKthToTail(ListNode* pHead, int k, int n) { //找到链表倒数第k个结点ListNode* p &#61; pHead;if(n next;return p;
}int main(){int n;while(cin >> n){ //输入nint val;cin >> val;ListNode *head &#61; new ListNode(val); //链表第一个结点ListNode *p &#61; head;for(int i &#61; 1; i > val;ListNode *q &#61; new ListNode(val);p->next &#61; q; //连接p &#61; p->next;}int k;cin >> k; //输入kif(k &#61;&#61; 0) //k等于0直接输出0cout <<0 <val <}

 方法二&#xff1a;快慢双指针

#include
using namespace std;struct ListNode{ //链表结点int val;ListNode* next;ListNode(int x) : val(x), next(NULL){} //初始化
};
ListNode* FindKthToTail(ListNode* pHead, int k) {//找到链表倒数第k个结点int n &#61; 0;ListNode* fast &#61; pHead;ListNode* slow &#61; pHead;for(int i &#61; 0; i next;else //达不到k步说明链表过短&#xff0c;返回空链表return slow &#61; NULL;}while(fast !&#61; NULL){ //快慢指针同步&#xff0c;快指针先到底&#xff0c;慢指针指向倒数第k个fast &#61; fast->next;slow &#61; slow->next;}return slow;
}int main(){int n;while(cin >> n){ //输入nint val;cin >> val;ListNode *head &#61; new ListNode(val); //链表第一个结点ListNode *p &#61; head;for(int i &#61; 1; i > val;ListNode *q &#61; new ListNode(val);p->next &#61; q; //连接p &#61; p->next;}int k;cin >> k; //输入kif(k &#61;&#61; 0) //k等于0直接输出0cout <<0 <val <}


推荐阅读
  • Ihavetwomethodsofgeneratingmdistinctrandomnumbersintherange[0..n-1]我有两种方法在范围[0.n-1]中生 ... [详细]
  • 本文介绍如何使用 Python 的 DOM 和 SAX 方法解析 XML 文件,并通过示例展示了如何动态创建数据库表和处理大量数据的实时插入。 ... [详细]
  • 在2019年寒假强化训练中,我们深入探讨了二分算法的理论与实践应用。问题A聚焦于使用递归方法实现二分查找。具体而言,给定一个已按升序排列且无重复元素的数组,用户需从键盘输入一个数值X,通过二分查找法判断该数值是否存在于数组中。输入的第一行为一个正整数,表示数组的长度。这一训练不仅强化了对递归算法的理解,还提升了实际编程能力。 ... [详细]
  • 零拷贝技术是提高I/O性能的重要手段,常用于Java NIO、Netty、Kafka等框架中。本文将详细解析零拷贝技术的原理及其应用。 ... [详细]
  • 单片微机原理P3:80C51外部拓展系统
      外部拓展其实是个相对来说很好玩的章节,可以真正开始用单片机写程序了,比较重要的是外部存储器拓展,81C55拓展,矩阵键盘,动态显示,DAC和ADC。0.IO接口电路概念与存 ... [详细]
  • 重要知识点有:函数参数默许值、盈余参数、扩大运算符、new.target属性、块级函数、箭头函数以及尾挪用优化《深切明白ES6》笔记目次函数的默许参数在ES5中,我们给函数传参数, ... [详细]
  • 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4277。作者:Bob Lee,日期:2012年9月15日。题目描述:给定n个木棍,求可以组成的不同三角形的数量,最多15根木棍。 ... [详细]
  • MySQL Decimal 类型的最大值解析及其在数据处理中的应用艺术
    在关系型数据库中,表的设计与SQL语句的编写对性能的影响至关重要,甚至可占到90%以上。本文将重点探讨MySQL中Decimal类型的最大值及其在数据处理中的应用技巧,通过实例分析和优化建议,帮助读者深入理解并掌握这一重要知识点。 ... [详细]
  • PTArchiver工作原理详解与应用分析
    PTArchiver工作原理及其应用分析本文详细解析了PTArchiver的工作机制,探讨了其在数据归档和管理中的应用。PTArchiver通过高效的压缩算法和灵活的存储策略,实现了对大规模数据的高效管理和长期保存。文章还介绍了其在企业级数据备份、历史数据迁移等场景中的实际应用案例,为用户提供了实用的操作建议和技术支持。 ... [详细]
  • 深入解析C语言中结构体的内存对齐机制及其优化方法
    为了提高CPU访问效率,C语言中的结构体成员在内存中遵循特定的对齐规则。本文详细解析了这些对齐机制,并探讨了如何通过合理的布局和编译器选项来优化结构体的内存使用,从而提升程序性能。 ... [详细]
  • 在《Linux高性能服务器编程》一书中,第3.2节深入探讨了TCP报头的结构与功能。TCP报头是每个TCP数据段中不可或缺的部分,它不仅包含了源端口和目的端口的信息,还负责管理TCP连接的状态和控制。本节内容详尽地解析了TCP报头的各项字段及其作用,为读者提供了深入理解TCP协议的基础。 ... [详细]
  • Java Socket 关键参数详解与优化建议
    Java Socket 的 API 虽然被广泛使用,但其关键参数的用途却鲜为人知。本文详细解析了 Java Socket 中的重要参数,如 backlog 参数,它用于控制服务器等待连接请求的队列长度。此外,还探讨了其他参数如 SO_TIMEOUT、SO_REUSEADDR 等的配置方法及其对性能的影响,并提供了优化建议,帮助开发者提升网络通信的稳定性和效率。 ... [详细]
  • Python多线程编程技巧与实战应用详解 ... [详细]
  • C++ 异步编程中获取线程执行结果的方法与技巧及其在前端开发中的应用探讨
    本文探讨了C++异步编程中获取线程执行结果的方法与技巧,并深入分析了这些技术在前端开发中的应用。通过对比不同的异步编程模型,本文详细介绍了如何高效地处理多线程任务,确保程序的稳定性和性能。同时,文章还结合实际案例,展示了这些方法在前端异步编程中的具体实现和优化策略。 ... [详细]
  • 经过两天的努力,终于成功解决了半平面交模板题POJ3335的问题。原来是在`OnLeft`函数中漏掉了关键的等于号。通过这次训练,不仅加深了对半平面交算法的理解,还提升了调试和代码实现的能力。未来将继续深入研究计算几何的其他核心问题,进一步巩固和拓展相关知识。 ... [详细]
author-avatar
宝贝小左手很开心
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有