算法|牛客网华为机试41-52C++

牛客网华为机试
上篇：算法|牛客网华为机试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; //该位置已走过标记为1
    temp_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-25
            vector<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_back
                array.push_back(num);
            else//中间insert
                array.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';//计算该部分数字总和 如果数字大于9
        else 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)//直到层数为0
                        break;
                }
                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){ //输入n
        int 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; //输入k
        if(k == 0) //k等于0直接输出0
            cout << 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;
    }
}