【2023-10-25】华为秋招笔试三道编程题解

恭喜发现宝藏！搜索公众号【TechGuide】回复公司名，解锁更多新鲜好文和互联网大厂的笔经面经。
作者@TechGuide【全网同名】

订阅专栏【进阶版】2023最新大厂笔试真题 & 题解，不容错过的宝藏资源！

第一题：简化版xml

题目描述

正常的xml样例如下：

<book>
<author>Cay s. Horstmann</author>
<isbn lang="CN">1234567</isbn>
<tags>
<tag>java</tag>
<tag>Network</tag>
</tags>
<pubDate/>
</book>

xml必须包含根节点，book就样例中的根节点。xml节点可以嵌套：如book和tags节点。

简化版xml节点满足如下条件：
1.节点的名称为单字符，如，不会出现
2.节点不带属性
3.节点不会出现
4.节点会出现带值情况如Value
5.xml节点包含值和包含子节点。只能二选一。

请计算给定简化版xml字符串中不合规的当前节点名称。不合规的当前节点：是指当前xml节点node1与下一个xml节点node2不匹配，则node1节点为当前节点。

题目保证输入的简化版xml，有且只有一个错误。

输入描述

简化版xml字符串，长度为小于1000.省略了样例中的换行符。

输出描述

输出给定简化版xml字符串中不合规的当前节点名称。

样例

输入

<a><b></a>

输出

b

思路

用栈来匹配XML节点的开始和结束标签，必须成对，否则抛出错误结点。本题欢迎给出更有代码。

代码

Java版本

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        solve();
    }

    public static void solve() {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        s = s.replace("<", " <").replace(">", "> ");
        s = s.trim();
        String[] arr = s.split(" ");

        Stack<String> stack = new Stack<>();

        for (String a : arr) {
            if (a.length() == 0) {
                continue;
            }
            if (a.startsWith("</")) {
                int cnt = 0;
                while (!stack.isEmpty() && !stack.peek().equals(a.replace("/", ""))) {
                    String tp = stack.pop();
                    if (tp.charAt(0) == '<') {
                        System.out.println(proce(tp));
                        return;
                    }
                    cnt++;
                }
                if (stack.peek().equals(a.replace("/", ""))) {
                    stack.pop();
                }
                if (cnt > 1) {
                    System.out.println(proce(a));
                    return;
                }
            } else {
                if (!stack.isEmpty() && stack.peek().charAt(0) != '<') {
                    System.out.println(proce(stack.get(stack.size() - 2)));
                    return;
                }
                stack.push(a);
            }
        }
    }

    private static String proce(String s) {
        return s.replace("<", "").replace("/", "").replace(">", "");
    }
}

// vx公众号关注TechGuide，代码可能需要少量调试。

CPP版本

#include <iostream>
#include <stack>
#include <vector>
#include <sstream>

using namespace std;

string proce(string s) {
    size_t pos = s.find('<');
    return s.substr(pos + 1, s.size() - pos - 2);
}

void solve() {
    string input;
    getline(cin, input);

    stringstream ss(input);
    string s;
    vector<string> arr;

    while (ss >> s) {
        arr.push_back(s);
    }

    stack<string> sk;

    for (const string &a : arr) {
        if (a.length() == 0) {
            continue;
        }
        if (a.substr(0, 2) == "</") {
            int cnt = 0;
            while (!sk.empty() && sk.top() != a.substr(2, a.size() - 3)) {
                string tp = sk.top();
                sk.pop();
                if (tp[0] == '<') {
                    cout << proce(tp) << endl;
                    return;
                }
                cnt++;
            }
            if (sk.top() == a.substr(2, a.size() - 3)) {
                sk.pop();
            }
            if (cnt > 1) {
                cout << proce(a) << endl;
                return;
            }
        } else {
            if (!sk.empty() && sk.top()[0] != '<') {
                cout << proce(sk.top()) << endl;
                return;
            }
            sk.push(a);
        }
    }
}

int main() {
    solve();
    return 0;
}

// vx公众号关注TechGuide，代码可能需要少量调试。

第二题：消息分发程序

题目描述

实习一个简易版的消息分发程序，客户端可以广播消息，可以订阅和取消订阅其他用户（默认订阅了自己）

每一个客户端有一个ClientID，每一条消息都有一个MsgID。请实现如下方法。

指令按时间顺序输入，且客户端广播的消息都被系统记录不会消失，订阅生效后，能够查询到目标客户端的之前发送的消息。

输入描述

每行一条指令，每条指令包含指令名称和指令参数(可选)， 并中间用一个空格隔开，所有的指令满足如上规则，不用处理输入格式异常，其中ClientID满足O<=ClientID<=10000000，MsgID满足O<=MsgID<=100000000。

输出描述

每一行输入，对应一行输出，并用单个空格隔开消息。

样例

输入

Brocast 1 5
Brocast 2 6
GetMsg 2 10
Subcribe 2 1
GetMsg 2 10
GetMsg 3 5

输出

1
1
6
0
6 5
-1

思路

模拟。用哈希表来统计每一个id的订阅和发送的消息。

代码

Java版本

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<String> inputs = new ArrayList<>();
        Scanner scanner = new Scanner(System.in);

        while (true) {
            try {
                inputs.add(scanner.nextLine());
            } catch (Exception e) {
                break;
            }
        }

        Map<String, List<String>> sends = new HashMap<>();
        Map<String, List<String>> subs = new HashMap<>();
        int index = 0;

        for (String input : inputs) {
            String[] ops = input.split("\\s");

            if (!subs.containsKey(ops[1])) {
                subs.put(ops[1], new ArrayList<>(Collections.singletonList(ops[1])));
            }

            if ("Brocast".equals(ops[0])) {
                String cid = ops[1];
                String msg = ops[2];
                if (!sends.containsKey(cid)) {
                    sends.put(cid, new ArrayList<>());
                }
                sends.get(cid).add(msg + " " + index);
                System.out.println(sends.get(cid).size());
            } else if ("GetMsg".equals(ops[0])) {
                String cid = ops[1];
                int N = Integer.parseInt(ops[2]);
                List<String> msgs = new ArrayList<>();
                for (String s : subs.get(cid)) {
                    msgs.addAll(sends.getOrDefault(s, Collections.emptyList()));
                }
                if (msgs.isEmpty()) {
                    System.out.println(-1);
                    continue;
                }
                msgs.sort(Comparator.comparingInt(x -> Integer.parseInt(x.split(" ")[1])));

                List<String> res = new ArrayList<>();
                for (int i = 0; i < Math.min(N, msgs.size()); i++) {
                    res.add(msgs.get(i).split(" ")[0]);
                }
                System.out.println(String.join(" ", res));
            } else if ("Subscribe".equals(ops[0])) {
                String cid1 = ops[1];
                String cid2 = ops[2];

                if (cid1.equals(cid2)) {
                    System.out.println(2);
                    continue;
                }

                if (subs.get(cid1).contains(cid2)) {
                    System.out.println(1);
                    continue;
                }

                System.out.println(0);
                subs.get(cid1).add(cid2);
            } else if ("UnSubscribe".equals(ops[0])) {
                String cid1 = ops[1];
                String cid2 = ops[2];

                if (cid1.equals(cid2)) {
                    System.out.println(2);
                    continue;
                }

                if (!subs.get(cid1).contains(cid2)) {
                    System.out.println(1);
                    continue;
                }

                System.out.println(0);
                subs.get(cid1).remove(cid2);
            }

            index++;
        }
    }
}

// vx公众号关注TechGuide，代码可能需要少量调试。

CPP版本

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int main() {
    vector<string> inputs;
    string input;

    while (true) {
        try {
            getline(cin, input);
            inputs.push_back(input);
        } catch (exception &e) {
            break;
        }
    }

    map<string, vector<string>> sends;
    map<string, vector<string>> subs;
    int index = 0;

    for (const string &input : inputs) {
        stringstream ss(input);
        string ops[3];

        for (int i = 0; i < 3; i++) {
            ss >> ops[i];
        }

        if (subs.find(ops[1]) == subs.end()) {
            subs[ops[1]] = vector<string>{ops[1]};
        }

        if (ops[0] == "Brocast") {
            string cid = ops[1];
            string msg = ops[2];

            if (sends.find(cid) == sends.end()) {
                sends[cid] = vector<string>();
            }

            sends[cid].push_back(msg + " " + to_string(index));
            cout << sends[cid].size() << endl;
        } else if (ops[0] == "GetMsg") {
            string cid = ops[1];
            int N = stoi(ops[2]);

            vector<string> msgs;
            for (const string &s : subs[cid]) {
                auto it = sends.find(s);
                if (it != sends.end()) {
                    msgs.insert(msgs.end(), it->second.begin(), it->second.end());
                }
            }

            if (msgs.empty()) {
                cout << -1 << endl;
                continue;
            }

            sort(msgs.begin(), msgs.end(), [](const string &a, const string &b) {
                return stoi(a.substr(a.find(' ') + 1)) < stoi(b.substr(b.find(' ') + 1));
            });

            vector<string> res;
            for (int i = 0; i < min(N, (int)msgs.size()); i++) {
                res.push_back(msgs[i].substr(0, msgs[i].find(' ')));
            }

            cout << implode(" ", res) << endl;
        } else if (ops[0] == "Subscribe") {
            string cid1 = ops[1];
            string cid2 = ops[2];

            if (cid1 == cid2) {
                cout << 2 << endl;
                continue;
            }

            if (find(subs[cid1].begin(), subs[cid1].end(), cid2) != subs[cid1].end()) {
                cout << 1 << endl;
                continue;
            }

            cout << 0 << endl;
            subs[cid1].push_back(cid2);
        } else if (ops[0] == "UnSubscribe") {
            string cid1 = ops[1];
            string cid2 = ops[2];

            if (cid1 == cid2) {
                cout << 2 << endl;
                continue;
            }

            auto it = find(subs[cid1].begin(), subs[cid1].end(), cid2);

            if (it == subs[cid1].end()) {
                cout << 1 << endl;
                continue;
            }

            cout << 0 << endl;
            subs[cid1].erase(it);
        }

        index++;
    }

    return 0;
}

// vx公众号关注TechGuide，代码可能需要少量调试。

第三题：字母加法

题目描述

给你一个字母加法公式，形如“send”+“more”=“money”，公式左侧字符串“send”、“more”为加数和被加数，公式右侧字符“money”为加数和，满足以下规则： (1)公式中每个英文字母（均为小写字母）都代表一位数字(0~9)，且不同字母代表不同数字； (2)公式中每个字符串的第一个字母所代表的数字不为0，比如“send”的第一个字母不为0，“more”、“money”同理；

判断该字母公式是否成立，如果成立，返回公式右侧字符串加数和转换成数字对应的数值(如果存在多组解，返回最小的一组解) ;如果不成立，返回 -1。

输入描述

第一行为左侧加数和被加数的总个数N，范围为[2,6]

接下来N行为加数和被加数的字符串，每个字符串长度范围为[1,6]

最后一行为加数和的字符串，字符串长度范围为[1,7]

输出描述

有2种情况:

(1)如果字母公式成立，返回加数和转换成数字对应的数值

(2)如果字母公式不成立，返回-1

样例

输入

2
send
more
money

输出

10336

思路

dfs，枚举每个字母对应的数字，试出满足等式的条件，本代码效率不高，大家可以给出更有代码。

代码

Java版本

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        scanner.nextLine(); // Consume the newline character

        List<String> words = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            words.add(scanner.nextLine());
        }

        String result = scanner.nextLine();

        isSolvable(words, result);
    }

    private static void isSolvable(List<String> words, String result) {
        if (result.length() == 1) {
            System.out.println(0);  // Single-digit result, no solution possible
            return;
        }

        Map<Character, Integer> dct = new HashMap<>();

        for (String word : words) {
            int k = word.length();
            for (int i = 0; i < k; i++) {
                dct.put(word.charAt(i), dct.getOrDefault(word.charAt(i), 0) + (int) Math.pow(10, k - i - 1));
            }
        }

        int n = result.length();

        for (int i = 0; i < n; i++) {
            char c = result.charAt(i);
            dct.put(c, dct.getOrDefault(c, 0) - (int) Math.pow(10, n - i - 1));
        }

        List<int[]> lst = new ArrayList<>();

        for (Map.Entry<Character, Integer> entry : dct.entrySet()) {
            lst.add(new int[]{entry.getValue(), entry.getKey()});
        }

        lst.sort((a, b) -> Integer.compare(Math.abs(b[0]), Math.abs(a[0])));

        int m = lst.size();
        Map<Character, Integer> mapper = new HashMap<>();

        for (int i = 0; i < m; i++) {
            mapper.put((char) lst.get(i)[1], i);
        }

        int[] mapping = new int[m];
        Arrays.fill(mapping, -1);

        List<Integer> ans = new ArrayList<>();

        dfs(0, 0, lst, mapping, ans, result, mapper, words);

        if (!ans.isEmpty()) {
            StringBuilder resultStr = new StringBuilder();
            for (int r : ans) {
                resultStr.append(r);
            }
            System.out.println(resultStr);
        } else {
            System.out.println(-1);
        }
    }

    private static void dfs(int preSum, int ind, List<int[]> lst, int[] mapping, List<Integer> ans, String result,
                            Map<Character, Integer> mapper, List<String> words) {
        if (!ans.isEmpty()) {
            return;
        }

        if (ind == lst.size()) {
            if (preSum == 0 && check(lst, mapping, result, mapper, words)) {
                for (int r : mapping) {
                    ans.add(r);
                }
            }
            return;
        }

        for (int num = 0; num < 10; num++) {
            if (!mapper.containsValue(num)) {
                List<Integer> rest = new ArrayList<>();
                for (int j = 0; j < 10; j++) {
                    if (!mapper.containsValue(j) && j != num) {
                        rest.add(j);
                    }
                }
                rest.sort(Integer::compareTo);

                List<Integer> pos = new ArrayList<>();
                List<Integer> neg = new ArrayList<>();

                for (int r = 1; r < lst.size() - ind; r++) {
                    int[] ls = lst.get(ind + r);
                    if (ls[0] > 0) {
                        pos.add(ls[0]);
                    } else {
                        neg.add(ls[0]);
                    }
                }

                int[] postCeilFloor = computeCeilFloor(rest, pos, neg);

                int postCeil = postCeilFloor[0];
                int postFloor = postCeilFloor[1];

                if (-postCeil <= preSum + lst.get(ind)[0] * num && preSum + lst.get(ind)[0] * num <= -postFloor) {
                    mapping[ind] = num;
                    dfs(preSum + lst.get(ind)[0] * num, ind + 1, lst, mapping, ans, result, mapper, words);
                    mapping[ind] = -1;
                }
            }
        }
    }

    private static int[] computeCeilFloor(List<Integer> rest, List<Integer> pos, List<Integer> neg) {
        int postCeil = 0;
        for (int r = 0; r < neg.size(); r++) {
            postCeil += rest.get(r) * neg.get(r);
        }

        for (int r = 0; r < pos.size(); r++) {
            postCeil += rest.get(rest.size() - r - 1) * pos.get(r);
        }

        int postFloor = 0;
        for (int r = 0; r < pos.size(); r++) {
            postFloor += rest.get(r) * pos.get(r);
        }

        for (int r = 0; r < neg.size(); r++) {
            postFloor += rest.get(rest.size() - r - 1) * neg.get(r);
        }

        return new int[]{postCeil, postFloor};
    }

    private static boolean check(List<int[]> lst, int[] mapping, String result, Map<Character, Integer> mapper,
                                 List<String> words) {
        Map<Character, Integer> mapNum = new HashMap<>();
        for (int c = 0; c < lst.size(); c++) {
            mapNum.put((char) lst.get(c)[1], mapping[c]);
        }

        for (String word : words) {
            if (word.length() >= 2) {
                char firstChar = word.charAt(0);
                if (mapNum.containsKey(firstChar) && mapNum.get(firstChar) == 0) {
                    return false;
                }

                if (!mapNum.containsKey(firstChar) && lst.size() == 9 && !mappingContainsZero(mapping)) {
                    return false;
                }
            }
        }

        return true;
    }

    private static boolean mappingContainsZero(int[] mapping) {
        for (int value : mapping) {
            if (value == 0) {
                return true;
            }
        }
        return false;
    }
}

// vx公众号关注TechGuide，代码可能需要少量调试。