字节跳动 Byte camp 2020 第二轮 笔试题 题解
## T1 Easy
直接双指针一下,判断一下即可
直接双指针一下,判断一下即可
#include <iostream> #include <cstring> #include <vector> #include <unordered_map> using namespace std; string input; bool validNumber(const string& str, int i, int j) { for (int k = i; k <= j; k++) { if (!(str[k] >= '0' && str[k] <= '9')) return false; } return true; } bool validDate(int y, int m, int d) { const bool isRunnian = (y == 2004 || y == 2008 || y == 2012 || y == 2016 || y == 2020); int months[] = {0, 31, isRunnian?29:28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; return d >= 1 && d <= months[m]; } int main() { cin >> input; unordered_map<string, int> validmap; for (int l = 0, r = 9; r < input.size(); l++, r++) { string cur = input.substr(l, 10); if (cur[2] == cur[5] && cur[2] == '-' && validNumber(cur, 0, 1) && validNumber(cur, 3, 4) && validNumber(cur, 6, 9)) { int d = stoi(cur.substr(0, 2)); int m = stoi(cur.substr(3, 2)); int y = stoi(cur.substr(6, 4)); if (y < 2001 || y > 2020) continue; if (m <= 0 || m >= 13) continue; if (!validDate(y, m, d)) continue; validmap[cur]++; } } string answer; int mx = 0; for (auto& p : validmap) { if (p.second > mx) { mx = p.second; answer = p.first; } } cout << answer << endl; return 0; }
## T2 Medium
IPv4 最长前缀匹配原则,ipv4字符串手写一个转化为 `uint32_t` 的函数,手写一个 `ipv4 cidr` 解析器。然后位运算、用一个哈希维护即可
#include <iostream> #include <cstring> #include <vector> #include <unordered_map> using namespace std; unordered_map<int, int> ips[35]; pair<uint32_t, uint32_t> parseip(const string& ip) { uint32_t answer = 0, seg = 31; uint32_t cur_ips[4] = {0}; string tmp; int ids = 0, have_seg = 0; for (int i = 0; i < ip.size(); i++) { if (ip[i] >= '0' && ip[i] <= '9') { tmp += ip[i]; } else if (ip[i] == '.') { cur_ips[ids++] = stoi(tmp); tmp.clear(); } else if (ip[i] == '/') { cur_ips[ids++] = stoi(tmp); tmp.clear(); have_seg = true; } } if (!tmp.empty()) { if (have_seg) { seg = stoi(tmp); } else { cur_ips[ids] = stoi(tmp); } } answer |= cur_ips[3]; answer |= cur_ips[2] << 8u; answer |= cur_ips[1] << 16u; answer |= cur_ips[0] << 24u; return {answer, seg}; } uint32_t make_mask(int seg) { uint32_t answer = 0; for (int i = 31, j = 0; i >= 0 && j < seg; i--, j++) { answer |= 1u << i; } return answer; } int query(const string& _ip) { uint32_t ip, seg; tie(ip, seg) = parseip(_ip); for (int i = 31; i >= 0; i--) { const uint32_t mask = make_mask(i + 1); if (ips[i].count(ip & mask)) { return ips[i][ip & mask]; } } return -1; } void inc(const string& _ip, int id) { uint32_t ip, seg, mask; tie(ip, seg) = parseip(_ip); mask = make_mask(seg); ip &= mask; ips[seg - 1][ip] = id; } int main() { int n, m; cin >> n >> m; for (int i = 0; i < n; i++) { int id; string _ip; cin >> id >> _ip; inc(_ip, id); } for (int i = 0; i < m; i++) { string _ip; cin >> _ip; cout << query(_ip) << endl; } return 0; }
## T3 Medium
博弈论:A 和 B 轮流取数,一共有 n 个物品,A 是先手,先手第一次可以取 [1, n - 1] 个物品。后续游戏,每个人至少取一个数,最多取前一个人取数的二倍,先取完者胜,都采取最优策略。给定 t 次独立游戏,问 A 获胜的次数是多少?
n 的数据到 1e9
打表发现是斐波那契数列,O(log(1e9)) 预处理,用哈希表维护,O(1) 查询
#include <iostream> #include <cstring> #include <vector> #include <unordered_set> using namespace std; const int MAX = 1e9; unordered_set<long long> invalid; void prepare() { long long a = 1, b = 1; while (b <= MAX) { long long lst = a; a = b; b = a + lst; invalid.insert(b); } } int main() { prepare(); int t; cin >> t; int answer = 0; for (int i = 0; i < t; i++) { int cur; cin >> cur; if (!invalid.count(cur)) answer++; } cout << answer << endl; return 0; }
## T4 Medium
1、构建表达式树
2、dfs一遍,重新计算 id
3、dfs一遍,生成结果
复杂度 O(N),这里我偷懒了,没有 delete 释放空间
#include <iostream> #include <cstring> #include <vector> #include <unordered_map> using namespace std; class TreeNode { public: TreeNode *left, *right, *memo; int id = -1; char val; TreeNode() : left(nullptr), right(nullptr), val(0), memo(nullptr) {}; }; bool isSymbol(char ch) { return ch == '+' || ch == '-' || ch == '*' || ch == '/'; } unordered_map<string, TreeNode*> memo; int id = 1, stridx = 0; pair<TreeNode*, string> build(const string& str) { if (stridx == str.size()) { return {nullptr, ""}; } if (str[stridx] == '(' || str[stridx] == ')' || str[stridx] == ',') { TreeNode* u; string x = string{str[stridx]}; string buffer; stridx++; tie(u, buffer) = build(str); return {u, x + buffer}; } TreeNode* u = new TreeNode(); u->id = id++; u->val = str[stridx]; string expr = {str[stridx]}; const bool iss = isSymbol(str[stridx]); stridx++; if (iss) { string exprl, exprr; tie(u->left, exprl) = build(str); tie(u->right, exprr) = build(str); expr += "(" + exprl + "," + exprr + ")"; } if (memo.count(expr)) { u->memo = memo[expr]; } else { memo[expr] = u; } return {u, expr}; } void reid(TreeNode* u) { if (u == nullptr) return; if (!u->memo) u->id = id++; if (u->left) reid(u->left); if (u->right) reid(u->right); } string traverse(TreeNode* u) { if (u == nullptr) return ""; if (u->memo != nullptr) { return to_string(u->memo->id); } string answer = {u->val}; if (isSymbol(u->val)) { answer += "(" + traverse(u->left) + "," + traverse(u->right) + ")"; } return move(answer); } int main() { // freopen("test.in", "r", stdin); // freopen("test.out", "w", stdout); int t; cin >> t; for (int i = 0; i < t; i++) { string exp; cin >> exp; id = 1; stridx = 0; memo.clear(); TreeNode* root = build(exp).first; id = 1; reid(root); cout << traverse(root) << endl; } return 0; }