华为机试真题练习汇总（41~50）

题目来源：华为机试 - 牛客

标记 * 号的代表有难度的题目。

* HJ41 称砝码

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

注：称重重量包括 0

输入描述：
对于每组测试数据：
第一行：n — 砝码的种数(范围[1,10])
第二行：m1 m2 m3 … mn — 每种砝码的重量(范围[1,2000])
第三行：x1 x2 x3 … xn — 每种砝码对应的数量(范围[1,10])

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

代码 1：

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> weight(n), num(n);
    for (int i = 0; i < n; i++)
        cin >> weight[i];
    for (int i = 0; i < n; i++)
        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;
}
// 64 位输出请用 printf("%lld")

代码 2：

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    int max_weight = 0;
    vector<int> weight(n), num(n);
    for (int i = 0; i < n; i++)
        cin >> weight[i];
    for (int i = 0; i < n; i++) {
        cin >> num[i];
        max_weight += num[i] * weight[i];
    }

    // unordered_set<int> s;
    // s.insert(0);
    // for (int i = 0; i < n; i++)
    //     for (int j = 1; j <= num[i]; j++) {
    //         unordered_set<int> temp(s);
    //         for (auto it = temp.begin(); it != temp.end(); it++)
    //             s.insert(*it + weight[i]);
    //     }
    // cout << s.size() << endl;

    // dp[i]: 能否称出质量为 i 的砝码
    vector<bool> dp(max_weight + 1, false);
    // 初始化
    dp[0] = true;
    for (int i = 0; i < n; i++)
        for (int j = 1; j <= num[i]; j++)
            for (int k = max_weight; k >= weight[i]; k--)
                if (dp[k - weight[i]] == true)
                    dp[k] = true;

    int count = 0;
    for (int i = 0; i <= max_weight; i++)
        if (dp[i] == true)
            count++;

    cout << count << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

* HJ42 学英语

描述
Jessi初学英语，为了快速读出一串数字，编写程序将数字转换成英文：

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

下面再看几个数字例句：
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可加可不加，这个题目我们选择不加)
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

说明：
数字为正整数，不考虑小数，转化结果为英文小写；
保证输入的数据合法
关键字提示：and，billion，million，thousand，hundred。

代码 1：

#include <iostream>
#include <vector>
using namespace std;

vector<string> ones = { "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine" };
vector<string> tens = { "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen" };
vector<string> twenties = { "zero", "ten", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety" };
vector<string> hundreds = { "hundred", "thousand", "million", "billion" };
vector<int> ihundreds = { (int)1e2, (int)1e3, (int)1e6, (int)1e9, (int)1e12 };

string itostr(int n) {
    if (n <= 9)
        return ones[n];
    else if (n < 20)
        return tens[n % 10];
    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])
                return itostr(n / ihundreds[i]) + " "
                       + hundreds[i]
                       + (n % ihundreds[i] ? (i ? " " : " and ")
                          + itostr(n % ihundreds[i]) : "");
    }
    return "";
}

int main() {
    int n;
    cin>>n;
    cout<<itostr(n)<<endl;

    return 0;
}
// 64 位输出请用 printf("%lld")

代码 2：

#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;

    map<int, string> u10 = {
        {1, "one"},
        {2, "two"},
        {3, "three"},
        {4, "four"},
        {5, "five"},
        {6, "six"},
        {7, "seven"},
        {8, "eight"},
        {9, "nine"}
    };
    map<int, string> u20 = {
        {10, "ten"},
        {11, "eleven"},
        {12, "twelve"},
        {13, "thirteen"},
        {14, "fourteen"},
        {15, "fifteen"},
        {16, "sixteen"},
        {17, "seventeen"},
        {18, "eighteen"},
        {19, "nineteen"}
    };
    map<int, string> u100 = {
        {2, "twenty"},
        {3, "thirty"},
        {4, "forty"},
        {5, "fifty"},
        {6, "sixty"},
        {7, "seventy"},
        {8, "eighty"},
        {9, "ninety"}
    };

void getResult(vector<string>& result, int& num) {
    bool hundredSign = false;
    bool tenSign = false;
    if (num >= 100) {
        hundredSign = true;
        result.push_back(u10[num / 100]);
        result.push_back("hundred");
        num %= 100;
    }
    if (num >= 10) {
        tenSign = true;
        if (hundredSign) {
            result.push_back("and");
        }
        if (num <= 19) {
            result.push_back(u20[num]);
            num = 0;
        } else {
            result.push_back(u100[num / 10]);
            num %= 10;
        }
    }
    if (num > 0) {
        if (hundredSign && !tenSign) {
            result.push_back("and");
        }
        result.push_back(u10[num]);
    }
}

int main() {
    long num;
    cin >> num;

    vector<string> result;

    int numMillion = num / 1000000;
    if (numMillion > 0) {
        getResult(result, numMillion);
        result.push_back("million");
    }

    int numThousand = num % 1000000 / 1000;
    if (numThousand > 0) {
        getResult(result, numThousand);
        result.push_back("thousand");
    }

    int numOne = num % 1000000 % 1000;
    if (numOne > 0) {
        getResult(result, numOne);
    }

    for (auto s : result) {
        cout << s << " ";
    }
    cout << endl;

    return 0;
}

* HJ43 迷宫问题

描述
定义一个二维数组 N*M ，如 5 × 5 数组下所示：

int maze[5][5] = {
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,
};

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

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

输出描述：
左上角到右下角的最短路径，格式如样例所示。

代码：

#include <functional>
#include <iostream>
#include <vector>
using namespace std;

const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> grid[i][j];

    vector<pair<int, int>> res, path;
    function<void(int, int)> dfs = [&](int i, int j) {
        if (i < 0 || i >= n || j < 0 || j >= m)
            return;
        if (grid[i][j])
            return;

        path.push_back(make_pair(i, j)); // 记入路径
        grid[i][j] = 1;
        if (i == n - 1 && j == m - 1) {
            res = path;
            return;
        }
        // 四个方向搜索
        for (int k = 0; k < 4; k++)
            dfs(i + dx[k], j + dy[k]);
        // 回溯
        path.pop_back();
        grid[i][j] = 0;
    };

    dfs(0, 0);
    for (auto& p : res)
        cout << "(" << p.first << "," << p.second << ")" << endl;

    return 0;
}
// 64 位输出请用 printf("%lld")

* HJ44 Sudoku

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

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

输出描述：
完整的9X9盘面数组

代码：

#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) {
    // 如果已经递归到右下角，输出整个盘面，并置flag为true，结束递归
    if (n == 81) {
        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; // 列号

    // 如果当前位置为0，说明需要推算
    if (num[h][l] == 0) {
        // 枚举1-9的数字，判断哪个满足条件
        for (int i = 1; i <= 9; ++i) {
            num[h][l] = i;
            // 判断当前数字是否满足条件
            if (check(n)) {
                // 如果满足条件继续往下递归
                dfs(n + 1);
                // 如果flag为true表示整个盘面的递归结束了
                if (flag)
                    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];
        }
    }
    dfs(0); // 从左上角开始递归
    return 0;
}
// 64 位输出请用 printf("%lld")

HJ45 名字的漂亮度

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

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

本题含有多组数据。

输入描述：
第一行一个整数N，接下来N行每行一个字符串

输出描述：
每个字符串可能的最大漂亮程度

代码：

#include <functional>
#include <iostream>
#include <vector>
using namespace std;

int maxBeauty(const string& s) {
    vector<int> cnt(26, 0);
    for (const char& c : s)
        cnt[c - 'a']++;
    sort(cnt.begin(), cnt.end(), greater<>());
    int b = 26, sum = 0;
    for (int i = 0; i < 26; i++) {
        sum += cnt[i] * b;
        b--;
    }
    return sum;
}

int main() {
    int n;
    cin >> n;
    string s;
    for (int i = 0; i < n; i++) {
        cin >> s;
        cout << maxBeauty(s) << endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

HJ46 截取字符串

描述
输入一个字符串和一个整数 k ，截取字符串的前k个字符并输出

输入描述：
1.输入待截取的字符串

2.输入一个正整数k，代表截取的长度

输出描述：
截取后的字符串

代码：

#include <iostream>
using namespace std;

int main() {
    string input;
    cin >> input;
    int k;
    cin >> k;
    cout << input.substr(0, k) << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

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

描述
输入一个单向链表和一个节点的值，从单向链表中删除等于该值的节点，删除后如果链表中无节点则返回空指针。

链表的值不能重复。

输入描述：
输入一行，有以下4个部分：
1 输入链表结点个数
2 输入头结点的值
3 按照格式插入各个结点
4 输入要删除的结点的值

输出描述：
输出一行
输出删除结点后的序列，每个数后都要加空格

代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> arr;
    int x;
    cin >> x;
    arr.push_back(x);
    for (int i = 1; i < n; i++) {
        int num, ins;
        // 在 ins 的后面插入 num
        cin >> num >> ins;
        auto it = find(arr.begin(), arr.end(), ins);
        if (it != arr.end())
            arr.insert(it + 1, num);
        else
            arr.push_back(num);
    }
    int del;
    cin >> del;
    arr.erase(find(arr.begin(), arr.end(), del));
    for (int& x : arr)
        cout << x << " ";
    return 0;
}
// 64 位输出请用 printf("%lld")

** HJ50 四则运算

描述
输入一个表达式（用字符串表示），求这个表达式的值。
保证字符串中的有效字符包括[‘0’-‘9’],‘+’,‘-’, ‘*’,‘/’ ,‘(’， ‘)’,‘[’, ‘]’,‘{’ ,‘}’。且表达式一定合法。

输入描述：
输入一个算术表达式

输出描述：
得到计算结果

代码：

#include <cctype>
#include <iostream>
#include <stack>
using namespace std;

void compute(stack<int>& ns, stack<char>& ops) {
    int num2 = ns.top();
    ns.pop();
    int num1 = ns.top();
    ns.pop();
    char op = ops.top();
    ops.pop();

    int res;
    switch (op) {
        case '+':
            res = num1 + num2;
            break;
        case '-':
            res = num1 - num2;
            break;
        case '*':
            res = num1 * num2;
            break;
        case '/':
            res = num1 / num2;
            break;
    }
    ns.push(res);
}

// 比较运算符优先级
bool priority(char m, char n) {
    if (m == '(') // 括号优先级最高
        return false;
    // 加减法小于乘除法
    else if ((m == '+' || m == '-') && (n == '*' || n == '/'))
        return false;
    return true;
}

int main() {
    string s;
    cin >> s;
    stack<int> ns;
    stack<char> ops;
    ops.push('(');
    s += ')';
    bool flag = false;
    for (int i = 0; i < s.length(); i++) {
        // 遇到左括号
        if (s[i] == '(' || s[i] == '[' || s[i] == '{')
            ops.push('(');
        // 遇到右括号
        else if (s[i] == ')' || s[i] == ']' || s[i] == '}') {
            // 弹出开始计算直到遇到左括号
            while (ops.top() != '(')
                compute(ns, ops);
            // 弹出左括号
            ops.pop();
        }
        // 遇到运算符
        else if (flag) {
            // 当s[i]的优先级小于等于栈顶符号优先级时，对栈顶进行一次计算，直到不符合条件
            while (priority(ops.top(), s[i]))
                compute(ns, ops);
            // 需要将当前运算符加入栈中等待运算
            ops.push(s[i]);
            flag = false;
        }
        // 遇到数字
        else {
            int j = i;
            if (s[j] == '-' || s[j] == '+')
                i++;
            while (isdigit(s[i]))
                i++;
            ns.push(stoi(s.substr(j, i - j)));
            i--;
            // 数字结束，下一次flag为true就是运算符了
            flag = true;
        }
    }
    cout << ns.top() << endl;

    return 0;
}
// 64 位输出请用 printf("%lld")