大数据开发工程师岗
笔试题型:单选 + 多选 + 三道编程题
编程题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; } };#虾皮笔试#