虾皮 10.26 笔试 AK

大数据开发工程师岗

笔试题型：单选 + 多选 + 三道编程题

编程题1：根据输入的数组构建二叉树，并输出层序遍历的结果

输入：{3,9,20,#,#,15,7}

输出：[[3],[9,20],[15,7]]

这道题就是建树麻烦点，层序遍历常规操作，注意格式就行。

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

struct Node {
    int value;
    Node* left;
    Node* right;
    Node(){};
    Node(int value = 0):value(value), left(nullptr), right(nullptr){}
};

Node* create(vector<string>& order, int pos) {
    if (pos >= order.size() || order[pos] == "#") return nullptr;
    Node* root = new Node(stoi(order[pos]));
    root->left = create(order, pos * 2 + 1);
    root->right = create(order, pos * 2 + 2);
    return root;
}

Node* createTree(vector<string>& order) {
    return create(order, 0);
}

void levelOrder(Node* root, string& ans) {
    queue<Node*> q;
    vector<vector<int>> result;
    if (root != nullptr) q.push(root);
    while (!q.empty()) {
        int size = q.size();
        vector<int> temp;
        while (size--) {
            Node* node = q.front();
            q.pop();
            temp.push_back(node->value);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        result.push_back(temp);
    }
    ans = "[";
    for (int i = 0; i < result.size(); i++) {
        ans += "[";
        for (int j = 0; j < result[i].size(); j++) {
            ans += to_string(result[i][j]);
            if (j < result[i].size() - 1) ans += ",";
        }
        ans += "]";
        if (i < result.size() - 1) ans += ",";
    }
    ans += "]";
}
int main() {
    string str;
    getline(cin, str);
    string temp = "";
    vector<string> order;
    for (int i = 1; i < str.size(); i++) {
        if (str[i] == ',' || str[i] == '}') {
            order.push_back(temp);
            temp = "";
        } else temp += str[i];
    }
    Node* root = createTree(order);
    string ans;
    levelOrder(root, ans);
    cout << ans << endl;
    return 0;
}

编程题2：字符串翻转（类似LeetCode151，相比之下更简单，不用考虑移除空格的操作）

class Solution {
public:
    void reverse(string& s, int left, int right) {
        for (;left < right; left++, right--) {
            swap(s[left], s[right]);
        }
    }
    /**
     * Note: 类名、方法名、参数名已经指定，请勿修改
     * @param originStr string字符串
     * @return string字符串
     */
    string ReverseString(string originStr) {
        int start = 0;
        for (int i = 0; i <= originStr.size(); i++) {
            if (originStr[i] == ' ' || i== originStr.size()) {
                reverse(originStr, start, i - 1);
                start = i + 1;
            }
        }
        return originStr;
    }
};

编程题3：大数乘法

class Solution {
public:
    void reverse(string &a) {
        for (int left = 0, right = a.size() - 1; left < right; left++, right--) {
            swap(a[left], a[right]);
        }
    }
    string multi(string a, int b) {
        string ans;
        int carry = 0; // 进位
        for (int i = 0; i < a.size(); i++) {
            carry +=  (a[i] - '0') * b;
            ans += to_string(carry % 10);
            carry /= 10;
        }
        while (carry != 0) {
            ans += to_string(carry % 10);
            carry /= 10;
        }
        return ans;
    }
    string add(string a, string b) {
        string ans;
        int carry = 0;  // 进位
        for (int i = 0; i < a.size() || i < b.size(); i++) {
            if (i < a.size()) carry += a[i] - '0';
            if (i < b.size()) carry += b[i] - '0';
            ans += to_string(carry % 10);
            carry /= 10;
        }
        if (carry != 0) {
            ans += to_string(carry % 10);
            carry /= 10;
        }
        return ans;

    }
    /**
     * Note: 类名、方法名、参数名已经指定，请勿修改
     * @param num1 string字符串
     * @param num2 string字符串
     * @return string字符串
     */
    string multiply(string num1, string num2) {
        reverse(num1);
        reverse(num2);
        string ans;
        if (num1.size() < num2.size()) swap(num1, num2);
        for (int i = 0; i < num2.size(); i++) {
            string temp = multi(num1, num2[i] - '0');
            reverse(temp);
            for (int j = 0; j < i; j++) temp += '0';
            reverse(temp);
            ans = add(ans, temp);
        }
        reverse(ans);
        return ans;
    }
};