腾讯笔试9.26 CPP代码 a4.4
我头文件都用的万能头文件#include<bits/stdc++.h>,所以下面代码都省略了
第一题主要是用素数筛
//任何两个因子相差都不小于x //三个质数相乘 int prime[50000]; //四个因数除去1和自己以外,找到两个满足题意的最小质数就ok了 int func(int x){ int i, j; for(i = 1 + x; i < 50000; i++){ if(prime[i] == 0){ break; } } for(j = i + x; j < 50000; j++){ if(prime[j] == 0) break; } return i * j; } int main(){ int T; cin >> T; //筛素数 memset(prime, 0, sizeof(prime)); prime[0] = 1; prime[2] = 0; for(int i = 2; i < 50000; i++){ if(prime[i] == 1) continue; for(int j = 2; j * i < 50000; j++){ prime[j * i] = 1; } } for(int i = 0; i < T; i++){ int k; cin >> k; cout<< func(k) << endl; } return 0; }
第二题可以从前往后跳可以看成从后往前的动态规划, 方便用i + a[i] 更新dp值
long maxScore(vector<int>& v){ int n = v.size(); vector<long> dp(n + 1, 0); long ans = LONG_MIN; for(int i = n - 1; i >= 0; i--){ if(i + v[i] >= n) dp[i] = v[i]; else dp[i] = max(dp[i], v[i] + dp[i + v[i]]); ans = ans > dp[i] ? ans : dp[i]; } return ans; } int main(){ int T; cin >> T; while(T--){ int n; cin >> n; vector<int> v(n); for(int i = 0; i < n; i++){ cin >> v[i]; } cout << maxScore(v) << endl; } return 0; }
第三题 我写的挺复杂, 就是用操作数栈和符号栈来模拟
+ * @ bool isNum(char c){ return c >= '0' && c <= '9'; } long answer(long a, long b, char op){ if(op == '+') return a + b; if(op == 'x') return a * b; return a | (a + b); } long long cal(string& str){ stack<long> st; stack<char> op; int curnum = 0; for(char& c : str){ if(isNum(c)){ curnum = curnum * 10 + c - '0'; continue; } st.push(curnum); if(c == '+'){ while(!op.empty()) { char cur = op.top(); op.pop(); long b = st.top(); st.pop(); long a = st.top(); st.pop(); long ans = answer(a, b, cur); st.push(ans); } } else if(c == 'x'){ while(!op.empty()){ if(op.top() == '+') break; char cur = op.top(); op.pop(); long b = st.top(); st.pop(); long a = st.top(); st.pop(); long ans = answer(a, b, cur); st.push(ans); } } else if(c == '@'){ while(!op.empty()){ if(op.top() == '+' || op.top() == 'x') break; char cur = op.top(); op.pop(); long b = st.top(); st.pop(); long a = st.top(); st.pop(); long ans = answer(a, b, cur); st.push(ans); } } op.push(c); //st.push(curnum); curnum = 0; } st.push(curnum); while(!op.empty()) { char cur = op.top(); op.pop(); long b = st.top(); st.pop(); long a = st.top(); st.pop(); long ans = answer(a, b, cur); st.push(ans); } return st.top(); } int main(){ string str; cin >> str; cout << cal(str) << endl; return 0; }
第四题 用hash来记录数与节点的映射关系, 再保存每个节点与它父亲的映射关系
class Solution { public: unordered_map<int, TreeNode*> mp; unordered_map<int, int> fa; bool judge(TreeNode* a, int val){ if(!a) return false; if(a -> val == val) return true; return judge(a -> left, val) || judge(a -> right, val); } bool isFather(TreeNode* a, TreeNode* b){ return judge(a, b -> val) || judge(b, a -> val); } void swap(vector<int>& v){ if(isFather(mp[v[0]], mp[v[1]])) return; TreeNode* a = mp[fa[v[0]]]; TreeNode* ason = mp[v[0]]; TreeNode* b = mp[fa[v[1]]]; TreeNode* bson = mp[v[1]]; //下面一大段其实就是交换a,b的孩子,只不过要讨论是左子树还是右子树 if(a -> left == ason && b -> left == bson){ a -> left = bson; fa[bson -> val] = a -> val; b -> left = ason; fa[ason -> val] = b -> val; } else if(a -> left == ason && b -> right == bson) { a->left = bson; fa[bson->val] = a->val; b->right = ason; fa[ason->val] = b->val; } else if(a -> right == ason && b -> left == bson) { a->right = bson; fa[bson->val] = a->val; b->left = ason; fa[ason->val] = b->val; } else if(a -> right == ason && b -> right == bson){ a -> right = bson; fa[bson -> val] = a -> val; b -> right = ason; fa[ason -> val] = b -> val; } } void dfs(TreeNode* root, int f){ if(!root) return; mp[root -> val] = root;//记录val和节点的映射关系 fa[root -> val] = f; //记录节点父亲 dfs(root -> left, root -> val); dfs(root -> right, root -> val); } TreeNode* solve(TreeNode* root, vector<vector<int> >& b) { // write code here dfs(root, -1); for(auto& v : b){ swap(v); } return root; } };第五题 只过了40% , 其实我测测试用例都没有对, 但是最后30s了就直接提交,发现过了40%,好像是有超时的原因,另外像测试用例没输出正确结果我也不知道为什么
这里面用到了一个dfs + bfs的思想, 就是限制超市的数量进行dfs
int N; char graph[55][55]; int houseNum = 0; int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; //判断当前所有房子是否都能到超市,把路径和加上, 如果有房子不能到就返回INT_MAX int judge(){ //如果每个房子都能到超市的话,就返回路径长度 if(houseNum == 0) return 0; int path = 0; queue<int> pos; int vis[55][55]; memset(vis, 0, sizeof(vis)); for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ if(graph[i][j] == 'o'){ pos.push(i * 100 + j); // 把超市加进来 vis[i][j] = 1; } } } int level = 1, cur = pos.size(), nc = 0; int houses = 0; while(!pos.empty()){ int tmp = pos.front(); pos.pop(); int x = tmp / 100, y = tmp % 100; cur--; for(int i = 0; i < 4; i++){ int nx = x + dx[i]; int ny = y + dy[i]; if(nx < 0 || ny < 0 || nx >= N || ny >= N || graph[nx][ny] == '*' || vis[nx][ny]){ continue; } vis[nx][ny] = 1; nc++; if(graph[nx][ny] == '#'){ path += level; houses++; } pos.push(nx * 100 + ny); } if(cur == 0){ level++; cur = nc; nc = 0; } } return houses == houseNum ? path : INT_MAX; } int ans = INT_MAX; int pa = INT_MAX; //在规定了超市个数up的情况下考虑每一个放置或者不放置超市 void dfs(int x, int y, int up){ if(up < 0) return; if(y == N){ y = 0; x++; } if(x == N) return; if(up == 0) { pa = min(pa, judge()); return; } if(graph[x][y] == '*'){ dfs(x, y + 1, up); } if(graph[x][y] == '.'){ dfs(x, y + 1, up); graph[x][y] = 'o'; dfs(x, y + 1, up - 1); graph[x][y] = '.'; } if(graph[x][y] == '#'){ dfs(x, y + 1, up); graph[x][y] = 'o'; houseNum--; dfs(x, y + 1, up - 1); houseNum++; graph[x][y] = '#'; } } vector<int> func(){ for(int i = 1; i <= houseNum; i++){ ans = INT_MAX; pa = INT_MAX; dfs(0, 0, i); if(pa != INT_MAX) return {i, pa - 1}; } return {houseNum, 0}; } int main(){ cin >> N; for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ cin >> graph[i][j]; if(graph[i][j] == '#') ++houseNum; } } vector<int> res = func(); cout << res[0] << " " << res[1] << endl; return 0; }