腾讯笔试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;
} 
查看14道真题和解析