华为机考108题（c++）（4151）

描述

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

注&＃xff1a;

称重重量包括 0

数据范围&＃xff1a;每组输入数据满足 1≤n≤10 &＃xff0c; 1≤mi​≤2000 &＃xff0c; 1≤xi​≤10

输入描述&＃xff1a;

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

输出描述&＃xff1a;

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

方法一&＃xff1a;集合

#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 <}