9.26 腾讯后台笔试题解
第一题：质数 + 贪心
第二题AC：
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
vector<int> v(n, -1);
int ans = 0;
for (int start = 0; start < n; ++start) {
int sum = 0;
int cur = start;
if (v[cur] > sum) continue;
// 之前跳过了肯定是不用看了
while (cur < n) {
sum += a[cur];
if (v[cur] > sum) {
break;
}
v[cur] = sum;
cur += a[cur];
}
ans = max(ans, sum);
}
cout << ans << endl;
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
inline bool isDigit(char c) {
return c <= '9' && c >= '0';
}
inline bool great(char a, char b) {
int p, q;
switch(a) {
case '+' : p = 0; break;
case 'x' : p = 1; break;
case '@' : p = 2; break;
}
switch(b) {
case '+' : q = 0; break;
case 'x' : q = 1; break;
case '@' : q = 2; break;
}
return p > q;
}
// 看样子第一题有坑啊，这居然都发公告了
long long cal(long long a, long long b, char o) {
switch(o) {
case '+' : return a + b;
case 'x' : return a * b;
case '@' : return a | (a + b);
}
return -1;
}
int main() {
// 还是首先认真审题好吧
// + 加法
// x 乘法
// 新定义运算是吧
// a @ b = a | (a + b)
// 优先级 @ > x > +
// 同优先级是从左到右
// 开long long
// 注意是没有括号的
string s;
cin >> s;
// 数值直接压栈，然后看操作符号，如果栈顶的优先级比自己低，压栈，比自己高，弹出
stack<char> oper;
stack<long long> nums;
int n = s.length();
for (int i = 0; i < n; ) {
char c = s[i];
if (isDigit(c)) {
long long num = c - '0';
i++;
c = s[i];
while (isDigit(c) && i < n) {
num = num * 10LL + (c - '0');
i++;
c = s[i];
}
nums.push(num);
} else {
// 说明是操作符，看情况来了
i++; // 别忘了这一步
// 应该先验证正确性的好吧
while (true) {
if (oper.empty()) {
oper.push(c);
break;
} else {
char o = oper.top();
// 如果c的优先级比栈顶高，压栈
if (great(c, o)) {
oper.push(c);
break;
} else {
oper.pop();
long long b = nums.top();
nums.pop();
long long a = nums.top();
nums.pop();
long long t = cal(a, b, o);
nums.push(t);
}
}
}
}
}
while (!oper.empty()) {
char o = oper.top();
oper.pop();
long long b = nums.top();
nums.pop();
long long a = nums.top();
nums.pop();
long long t = cal(a, b, o);
nums.push(t);
}
cout << nums.top();
return 0;
}
第四题AC：二叉树
#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
private:
// 应该还要记录左右信息, 0 左 1 右
// 不用，反而麻烦，之后判断一下就是
unordered_map<int, TreeNode*> pa;
unordered_map<int, TreeNode*> node;
private:
TreeNode* lca(TreeNode* root, TreeNode* p, TreeNode* q) {
// 如果在一左一右找到了结点，那么就是这个根结点咯，如果不是
if (root == nullptr || root == p || root == q) return root;
TreeNode* left = lca(root->left , p, q);
TreeNode* right = lca(root->right, p , q);
if (!left && !right) return nullptr;
if (left && !right) return left;
if (!left && right) return right;
else return root;
}
// 建立父亲结点hash和自己的hash，之后动态改变，可能稍微有点麻烦
void dfs(TreeNode* root) {
node[root->val] = root;
if (root->left) {
pa[root->left->val] = root;
dfs(root->left);
}
if (root->right) {
pa[root->right->val] = root;
dfs(root->right);
}
}
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param root TreeNode类 指向量子树的根
* @param b int整型vector<vector<>> 表示每次交换的两个子树
* @return TreeNode类
*/
TreeNode* solve(TreeNode* root, vector<vector<int> >& b) {
// write code here
// 这道题一定要小心审题，看样子是有诈的
// 某些时刻会有两子树交换位置，
// 假设x和y交换律位置，x的父亲fa[x], y 父亲fa[y]
// x 与 fa[x] 边断开， y 与 fa[y] 间的边会断开
// 然后 x 连 fa[y], 同理
// !!!!!!!!!!! 可能有不合法的情况，这种情况忽略此次交换，那么还得有机制能够达到这种方式
// 这道题抽象为找最临近父节点的问题就是了
// 树的编号是1 - n 的整数并且互不相同， 找到相应的结点也是个问题，unoreder_map好啦，
// 先遍历一遍树并且建立树，之后就lucky了
dfs(root);
for (const vector<int>& a : b) {
int p = a[0], q = a[1];
TreeNode* tp = node[p];
TreeNode* tq = node[q];
TreeNode* lcap = lca(root, tp, tq);
// cout << lcap->val;
// 不合法食大便啦
if (lcap == tq || lcap == tp)
continue;
TreeNode* pp = pa[p];
TreeNode* pq = pa[q];
TreeNode* pl = pp->left;
TreeNode* pr = pp->right;
TreeNode* ql = pq->left;
TreeNode* qr = pq->right;
if (pl == tp) {
pp->left = tq;
} else if (pr == tp) {
pp->right = tq;
}
pa[q] = pp;
if (ql == tq) {
pq->left = tp;
} else if (qr == tq) {
pq->right = tp;
}
pa[p] = pq;
}
return root;
}
};
int main() {
TreeNode* p1= new TreeNode(1);
TreeNode* p2= new TreeNode(2);
TreeNode* p3= new TreeNode(3);
TreeNode* p4= new TreeNode(4);
TreeNode* p5= new TreeNode(5);
TreeNode* p6= new TreeNode(6);
TreeNode* p7= new TreeNode(7);
p1->left = p2;
p1->right = p3;
p2->left = p4;
p2->right = p5;
p3->left = p6;
p3->right = p7;
vector<vector<int>> vec;
vec.push_back({1, 2});
vec.push_back({2, 3});
Solution().solve(p1, vec);
}
第五题：图论，没来得及做
查看5道真题和解析
