腾讯笔试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;
}




#腾讯笔试##笔试题目##秋招#
全部评论
最后一个题可以在一个联通快里同时bfs,把联通快覆盖的最后一个点就是最终超市选择的点,不过这个距离可以公式求得,就是任意两点的距离和
1 回复 分享
发布于 2021-09-27 10:35
头文件是#include<bits/stdc++.h> 反正牛客上是可以用这个万能头文件的
1 回复 分享
发布于 2021-09-26 23:24
楼主,第一题的算法正确性应该怎么证明呢
点赞 回复 分享
发布于 2021-09-28 21:11
这个代码写的真的好,赞赞赞
点赞 回复 分享
发布于 2021-09-28 20:30
问一下第二题为什么深度遍历不能ac呢。
点赞 回复 分享
发布于 2021-09-27 10:34
第一题和第三题一样的方法却没有ac
点赞 回复 分享
发布于 2021-09-27 10:17
请问第二题为什么是dp[i] = max(dp[i], v[i] + dp[i + v[i]]);
点赞 回复 分享
发布于 2021-09-27 00:13
tql,第一题都不会😂
点赞 回复 分享
发布于 2021-09-26 22:24

相关推荐

面试官人很好,态度和蔼可亲,没答出来时也会引导你去思考。由于是晚上面的,导致我白天一天都有点紧张,面的时候状态也不是很好,正常可能面试官提问完应该思考几秒再答,而我就像抢答一样一口气把所有会的都说出来,这样就导致逻辑比较混乱,东一句西一句的。首先是自我介绍,先把会的技术大致讲一下,由于我八股背的多所以着重讲了一下,Java,go,jvm,MySQL,Redis,计网,操作系统这些,然后一小部分闲聊,然后先问了一下项目,面试官问我这个项目是否落实之类的,直接坦言说是写的练手的,包括之前也写过IM通讯,外卖之类的。然后面试官就把提问的重点放在了八股上。先问了Java:类加载器(答:3种+自定义类加载器、tomcat、原因+双亲委派+好处)JVM参数(答:xmx,xms,newsize这些,问我是如何设定的,我回答是把内存分一半给堆,再把堆分一半给新生代,这方面确实不太了解)然后问了一下并发相关的:线程池(答:线程池的7个参数(忘了线程工厂和阻塞时间了),3个重要参数,还有线程如何启用,为什么要设计最大线程数之类的,提到Java栈默认分配1MB运行时不可以更改)AQS(答:先讲clh是自旋锁+list,然后是AQS在这个基础上做的两个优化,然后举了一下reentrantlock根据state如何获取资源)CAS(答:使用三个字段,aba问题,然后将通常搭配自旋锁实现,面试官问通常会自旋多少次,这个不太了解,答的100,然后问100次大概多少秒,回答微秒级,然后面试官讲了一下怎么做资源可能没用完,意识到可能还需要进行阻塞操作)然后考虑一下Linux命令(top,ps,如何使用管道符过滤线程和使用Linux启动线程没答出来)然后问Redis:持久化机制(答:三种aof,rdb,混合,aof的三个参数刷盘策略,rdb以快照保存,使用bgsave会使用子线程来保存不会阻塞,而aof虽然会阻塞但是只在写完数据后追加一条命令,不会太影响,然后是他俩的优缺点,还有混合是怎么保存数据的)集群模式(答:三种,主从复制到缺点再到哨兵机制,正常使用三个哨兵互相监督,主节点挂了投票选主哨兵然后选主节点,然后额外讲一下脑裂的问题,主节点进行数据更新然后把命令写入aof来同步从节点,最后cluster集群,如何实现,使用16383个哈希槽(艹答成16384了),先根据哈希码取余,再根据节点数取余决定放在哪个节点上,然后问了一下我会怎么选集群模式,首先是cluster的问题,会让管道操作之类的失效,然后哨兵会导致整个集群结构变得复杂,使用小项目可能会考虑哨兵,大的考虑cluster,然后考了一下cluster如果一个节点挂了怎么办,根据节点数重新取余然后数据转移,面试官说这么转移比较慢,有没有别的办法,我隐约记得使用一个类似环形数组的方式,想不起来了)然后考了一下MySQL的b+树(这方面的知识点太多了,导致我什么都想讲逻辑就比较乱,讲了一下聚簇索引,树的叶子节点对应着一张页16KB,MySQL有一个区的概念,把这些页放在同一个区中,这样叶子节点的双向链表遍历时速度更快,然后b+树的扇出比较大(非常二,说成扇度之类的,面试官以为说的是扇区)这样层数就比较小,一行1kb数据的话3层可以放心2000w数据)其他的暂时想不起来了算法是lru,面试官问要不要提示,我说写个,然后写了10分钟左右,说大概写好了,但是面试官指出了2个小错误,第一个马上就改回来了,第二个一直没看出来(大脑这时候已经停止工作了)反问:问学习建议,说根据实际的项目进行深入,考虑应该怎么做,还问了一下组里面是做Java的吗?面试官说他是做go的,组里什么语言都有,语言影响不大,连忙补充了一句我对go的底层有深入源码的学习)结束。总体感觉答得不太好,没有太体现出深度,细节也不够全面。
下一个更好呗:佬,我投完云智一直没消息,多久约的一面啊
查看14道真题和解析
点赞 评论 收藏
分享
评论
10
29
分享

创作者周榜

更多
牛客网
牛客企业服务