8.13 贝壳笔试统计+AK参考代码
2021-08-13 更新
考试时间 20:00 - 22:00，四道编程题。
前三题都比较简单，第四题直接递归把树转化为字符串，用 C++ 内存超限只过了90%多的数据，用Python直接ac了。开始以为子树是任意的子结构都行，实际上是包含该节点和所有的子节点。
回忆了下所有题的代码，作为参考：
第一题
vector<long long> solve(int n, long long m) {
// [0, n-1]，从 1 的位置开始洒，最后 a[0] 加 1,最后洒到的位置减去 1
long long div = m / (n - 1), mod = m % (n - 1);
vector<long long> ans(n);
for (int i = 1; i < n; ++i) {
ans[i] = (div + 1) / 2;
}
for (int i = n - 2; i >= 0; --i) {
ans[i] = div / 2;
}
int last = 0;
if (div & 1) {
if (mod == 0) {
last = n - 1;
} else {
for (int i = n - 2; i >= 0 && mod; --i, --mod) {
ans[i] += 1;
last = i;
}
}
} else {
if (mod == 0) {
last = 0;
} else {
for (int i = 1; i < n && mod; ++i, --mod) {
ans[i] += 1;
last = i;
}
}
}
ans[0] += 1;
ans[last] -= 1;
return ans;
} 第二题
string solve(string s, int k) {
// 每次删除 s 中最小的字符，共删除 k 次
// 笔试时我直接用的 set 做的，但是用位运算更优
int mask = 0;
for (char c : s) {
mask |= 1 << (c - 'a');
}
for (int i = 0; i < 26 && k; ++i) {
if (mask & (1 << i)) {
mask &= ~(1 << i);
k -= 1;
}
}
string ans;
for (char c : s) {
if (mask & (1 << (c - 'a'))) {
ans += c;
}
}
return ans;
} 第三题
long long solve(vector<int> &a, int t) {
int n = a.size();
long long ans = 0;
unordered_map<int, int> index;
int pre = 0;
for (int i = 0; i < n; ++i) {
int b = a[i] ^ t;
int k = index.count(b) ? index[b] + 1 : 0;
k = max(k, pre);
pre = k;
ans += i - k;
index[a[i]] = i;
}
return ans;
} 第四题
import sys
from collections import defaultdict
sys.setrecursionlimit(100005)
def solve(root):
pattern = defaultdict(int)
size = defaultdict(int)
def dfs(root):
if root is None:
return ("()", 0)
l_s, l_cnt = dfs(root.left)
r_s, r_cnt = dfs(root.right)
s = "(" + l_s + str(root.val) + r_s + ")"
cnt = 1 + l_cnt + r_cnt
pattern[s] += 1
size[s] = cnt
return (s, cnt)
dfs(root)
ans = 0
for k, v in pattern.items():
if v > 1:
ans = max(ans, size[k])
return ans
投递滴滴等公司10个岗位 >
