牛客网华为机试
上篇：算法|牛客网华为机试21-30C++

HJ41 称砝码

题目描述：

解题思路：
题解 | #称砝码#
解法：

#include<iostream>
#include<vector>
#include<unordered_set>
#include<algorithm>
using namespace std;int main(){int n;while(cin >> n){vector<int> weight(n);vector<int> num(n);for(int i = 0; i < n; i++) //输入n种砝码重量cin >> weight[i];for(int i = 0; i < n; i++) //输入n种砝码的数量cin >> num[i];unordered_set<int> s; //集合用于去重s.insert(0); //0也是一种for(int i = 0; i < n; i++){ //对于每一种砝码for(int j = 1; j <= num[i]; j++){ //用完之前数量之前unordered_set<int> temp(s);for(auto iter = temp.begin(); iter != temp.end(); iter++) //当前集合每个都可以加一次s.insert(*iter + weight[i]);}}cout << s.size() << endl; //最后集合的大小就是种类}return 0;
}

HJ42 学英语

题目描述：

解题思路：
暴力解。
解法：

#include<bits/stdc++.h> // 包含C++标准库的所有头文件
using namespace std; // 使用标准命名空间// 数组，用于存储1到9的英文单词
string ones[] = { "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine" };// 数组，用于存储10到19的英文单词
string tens[] = { "ten","eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen" };// 数组，用于存储20到90的英文单词（每十个一组）
string twenties[] = { "zero","ten","twenty","thirty","forty","fifty","sixty","seventy","eighty","ninety" };// 数组，用于存储"hundred", "thousand", "million", "billion"等单位的英文单词
string hundreds[] = { "hundred", "thousand", "million", "billion" };// 数组，用于存储与hundreds数组中单位对应的数值
int ihundreds[] = { (int)1e2, (int)1e3, (int)1e6, (int)1e9, (int)1e12 };// 函数，将整数n转换为英文单词表示
string itoe(long long n)
{// 如果n小于等于9，直接返回ones数组中对应的单词if (n<=9)return ones[n];// 如果n小于20，返回tens数组中对应的单词else if (n<20)return tens[n%10];// 如果n小于100，返回twenties数组中对应的单词，并根据个位数是否为0来决定是否添加个位数的单词else if (n<1e2)return twenties[n/10] + (n%10 ? " " + ones[n%10] : "");// 对于更大的数字，使用递归else {for (int i=0; i < 4; i++)// 找到当前数字所在的数量级if (n < ihundreds[i+1])// 递归调用itoe函数，并将结果与当前数量级的单位组合起来return itoe(n/ihundreds[i]) + " " + hundreds[i] // 如果不是最高数量级，并且当前数量级不为0，则添加"and"和当前数量级的数字+ (n%ihundreds[i] ? (i ? " ": " and ") + itoe(n%ihundreds[i]) : "");}return ""; // 如果数字为0，返回空字符串
}int main()
{long long n; // 用于存储输入的整数// 循环读取输入的整数，并输出其英文单词表示while (cin>>n)cout<<itoe(n)<<endl;
}

HJ43 迷宫问题

题目描述：

解题思路：
题解 | #迷宫问题#
“深度优先搜索一定要对递归过程有深入的理解，这样才能越做越顺，初做此类题型时不要盲目追求做题速度，多画一画递归树，了解了DFS运行机制以后，再去做同类题型就会得心应手。”
我讨厌动态规划。
解法：

#include <iostream>
#include <vector>
using namespace std;
int n, m;
vector<vector<int>> maze;
//当从（0，0）到（n-1，m-1）有多条通路时，best_path记录最小的temp_path
//本题只有一条通路，所以当到达（n-1，m-1）时，让 best_path=temp_path即可
vector<vector<int>> best_path;
vector<vector<int>> temp_path;void dfs(int i,int j){// 边界条件：（1）数组越界（2）“墙壁”或已走过if(i<0||i>=n||j<0||j>=m||maze[i][j]==1){return;}maze[i][j] = 1; //该位置已走过标记为1temp_path.push_back({i,j});if(i == n-1 && j == m-1){//走到终点// 多条路径时best_path记录最小的temp_path//if(temp_path.size()<best_path.size()||best_path.empty()){//    best_path = temp_path;//}// 本题只有一条通路，所以当到达（n-1,m-1）时，让best_path=temp_path即可best_path = temp_path;}dfs(i-1, j);//上dfs(i+1, j);//下dfs(i,j-1);//左dfs(i,j+1);//右maze[i][j]=0;//该结点走不通时，恢复原场面temp_path.pop_back();//从路径中删除节点
}int main() {while (cin>>n>>m) {maze = vector<vector<int>> (n,vector<int>(m,0));//设置地图大小并初始化//一次测试中多个案例一次输入时，每个案例执行完后将路径容器清空best_path.clear();temp_path.clear();for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>maze[i][j];}}dfs(0, 0);for(auto iter = best_path.begin();iter!=best_path.end();iter++)cout<<"("<<(*iter)[0]<<","<<(*iter)[1]<<")"<<endl;return 0;}
}

HJ44 Sudoku

题目描述：

解题思路：
题解 | #Sudoku#
解法：

#include <iostream>
using namespace std;
int num[9][9];  //用于保存9x9盘面
bool flag = false;//flag为true时表示推算完成，结束递归bool check(int n){  //判断当前位置的值是否满足条件int h = n / 9;  //行号int l = n % 9;  //列号for(int i=0;i<9;++i){//同一列中不能有重复if(i != h && num[i][l] == num[h][l]){return false;}}for(int j=0;j<9;++j){//同一行中不能有重复if( j != l && num[h][j] == num[h][l]){return false;}}for (int i = h / 3 * 3; i < h / 3 * 3 + 3; ++i) {//九宫格内不重复for(int j = l / 3 * 3;j < l / 3 * 3 + 3;++j){if((i != h || j != l) && num[i][j] == num[h][l]){return false;}}}return true;
}void dfs(int n){if(n == 81){//如果已经递归到右下角，输出整个盘面，并置flag为true，结束递归for(int i = 0;i < 9;++i){for(int j = 0;j < 8;++j){cout<<num[i][j]<<' ';}cout<<num[i][8]<<endl;}flag = true;return;}int h = n / 9;//行号int l = n % 9;//列号if(num[h][l] == 0){//如果当前位置为0，说明需要推算for(int i = 1;i <= 9;++i){//枚举1-9的数字，判断哪个满足条件num[h][l] = i;if(check(n)){   //判断当前数字是否满足条件dfs(n+1);   //如果满足条件继续往下递归if(flag){//如果flag为true表示整个盘面的递归结束了return;}}}num[h][l] = 0;//需要回溯，恢复num[h][l]的值为0}else{  // 当前位置不为0，往下一格递归dfs(n+1);}
}int main() {for (int i = 0; i< 9; ++i) {for (int j = 0; j < 9; ++j) {cin>>num[i][j];//输入9x9盘面}}dfs(0);//从左上角开始递归return 0;
}

HJ45 名字的漂亮度

题目描述：

解题思路：
题目的意思就是找出字符串出现次数最多的字母，从26开始赋值，依次递减，出现次数第二多的为25…最后计算漂亮度总和最高的。
解法：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {int d;while (cin >> d) {while (d--) {string s;cin >> s;// 初始化值为0的26个元素的动态数组 表示a-z出现的此时对应0-25vector<int>arr(26, 0);// 遍历每个字母for (int i = 0; i < s.size(); i++) {// 如果是小写字母减去a ++表示出现过的次数大写字母同理if (s[i] >= 'a' && s[i] <= 'z') {arr[s[i] - 'a']++;} else if (s[i] >= 'A' && s[i] <= 'Z') {arr[s[i] - 'A']++;}}// 根据出现过的次数从小到大排序sort(arr.begin(), arr.end());int res = 0;int k = 26;// 从出现次数最多的字母开始输出for (int i = 25; i >= 0; i--) {res += arr[i] * k;k--;}cout << res << endl;}}return 0;
}

HJ46 截取字符串

题目描述：

解题思路：
C++|string字符串操作(切割,是否包含某个子串)
string的substr()函数可以截取制定位置字符串。
解法：

#include <iostream>
using namespace std;int main() {string str;cin>>str;int num;cin>>num;cout<<str.substr(0,num);
}

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

题目描述：

解题思路：
用数组模拟链表。
解法：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main() {int n,head;while (cin>>n>>head) {vector<int> array;//用数组模拟链表array.push_back(head);//现将头元素放入for(int i=1;i<n;++i){//放入除头元素外其他元素int num,pos_num;//要插入的数和它要插入哪个数字后面cin>>num>>pos_num;  auto iter = find(array.begin(),array.end(),pos_num);//找到要插入后面的位置if(iter == array.end()) //结尾push_backarray.push_back(num);else//中间insertarray.insert(iter+1,num);}int remove;cin>>remove;array.erase(find(array.begin(),array.end(),remove));//找到要移除的数字的位置for(int i=0;i<array.size();++i){//输出cout<<array[i]<<" ";}}return 0;
}

HJ50 四则运算

题目描述：

解题思路：
题解 | #四则运算#
解法：

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

俺也不知道47、49去哪了，写着写着就没了，就像很多公司让等着等着就没信了。。。

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

题目描述：

解题思路：
题解 | #输出单向链表中倒数第k个结点#
解法：

#include<iostream>
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 = pHead;if(n < k) //长度过小，返回空链表return p = NULL;for(int i = 0; i < n - k; i++) //遍历n-k次p = p->next;return p;
}int main(){int n;while(cin >> n){ //输入nint val;cin >> val;ListNode *head = new ListNode(val); //链表第一个结点ListNode *p = head;for(int i = 1; i < n; i++){ //输入链表后续结点cin >> val;ListNode *q = new ListNode(val);p->next = q; //连接p = p->next;}int k;cin >> k; //输入kif(k == 0) //k等于0直接输出0cout << 0 << endl;else{p = FindKthToTail(head, k, n); //找到第k个结点if(p != NULL) //返回不为null才能输出cout << p->val << endl;}}return 0;
}

HJ52 计算字符串的编辑距离

题目描述：

解题思路：
题解 | #计算字符串的距离#
解法：

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>using namespace std;int main() {string str1, str2;while (cin >> str1 >> str2) {vector<vector<int>> dp(str1.size() + 1, vector<int>(str2.size() + 1, 0));for (int i = 1; i <= str2.size(); i++) dp[0][i] = i;//str1从0个字符变成str2的i个字符需要i个插入操作for (int i = 1; i <= str1.size(); i++) dp[i][0] = i;//str1从i个字符变成str2的0个字符也需要i个删除操作for(int i=1;i<=str1.size();i++){for (int j = 1; j <= str2.size(); j++) {int op1 = dp[i-1][j] + 1;//删除字符str1[i-1]int op2 = dp[i][j-1] + 1;//删除字符str2[j-1]int op3 = dp[i-1][j-1];//替换操作if(str1[i-1] != str2[j-1]){op3++;}dp[i][j] = min(min(op1, op2), op3);//替换操作和删除操作取最小}}cout << dp[str1.size()][str2.size()] << endl;}
}