9.26 腾讯第三批后端开发笔试编程5道题(CPP版本)

1.所有因子间大于等于x(100%)
#include <bits/stdc++.h>

using namespace std;

int main () {
    int T;
    cin >> T;
    for (int p = 0; p < T; p++) {
        int x;
        cin >> x;
        //找两个比较质数乘一下,第一个要大于x,第二个要大于2x
        vector<bool> ok(30000, true);
        for (int i = 2; i <= x; i++) {
            int k = 1;
            while (k * i < 30000) {
                ok[k * i] = false;
                k++;
            }
        }
        long long num1 = x + 1;
        while (!ok[num1]) num1++;
        long long num2 = num1 + x;
        while (!ok[num2]) num2++;
        cout << num1 * num2 << endl;
    }
    return 0;
}
2.最大的跳跃积分(100%)
#include <bits/stdc++.h>

using namespace std;

int main () {
    int T;
    cin >> T;
    for (int p = 0; p < T; p++) {
        int n;
        cin >> n;
        vector<int> a(n, 0);
        vector<int> dp(n, 0);
        for (int i = 0; i < n; i++) cin >> a[i];
        int m = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (i + a[i] >= n) dp[i] = a[i];
            else dp[i] = a[i] + dp[i + a[i]];
            if (dp[i] > m) m = dp[i];
        }
        cout << m << endl;
    }
    return 0;
}
3.计算算式(100%)
#include <bits/stdc++.h>

using namespace std;

int main () {
    string input;
    stack<char> op;
    stack<long long> num;
    getline(cin, input);
    unordered_map<char, int> prio;
    prio['@'] = 1;
    prio['x'] = 2;
    prio['+'] = 3;
    //符号栈的量比数少1
    //符号栈按优先级处理单调排列,低优先级的放下面,同优先级从左到右那么遇到相同优先级符号压栈要先弹开符号处理计算
    string temp;
    for (const auto& c : input) {
        if (c <= '9' && c >= '0') {
            temp += c;
        } else {
            num.push(stoll(temp));
            temp.clear();
            if (op.empty()) {
                op.push(c);
            } else {
                while (!op.empty() && prio[c] >= prio[op.top()]) {
                    char opt = op.top();
                    long long b = num.top();
                    op.pop();
                    num.pop();
                    if (opt == '@') {
                        num.top() = num.top() | (num.top() + b);
                    } else if (opt == 'x') {
                        num.top() *= b;
                    } else if (opt == '+') {
                        num.top() += b;
                    }
                }
                op.push(c);
            }
        }
    }
    if (!temp.empty()) {
        num.push(stoll(temp));
        temp.clear();
    }
    while (!op.empty()) {
        char opt = op.top();
        long long b = num.top();
        op.pop();
        num.pop();
        if (opt == '@') {
            num.top() = num.top() | (num.top() + b);
        } else if (opt == 'x') {
            num.top() *= b;
        } else if (opt == '+') {
            num.top() += b;
        }
    }
    //数栈最后肯定只会剩一个的
    cout << num.top() << endl;
    return 0;
}
4.量子交换树枝(57%超时)
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 
     * @param root TreeNode类 指向量子树的根
     * @param b int整型vector<vector<>> 表示每次交换的两个子树
     * @return TreeNode类
     */
    TreeNode* solve(TreeNode* root, vector<vector<int> >& b) {
        // write code here
        //找到两个节点对应的祖先,带1的直接跳过,否则必有祖先
        for (const auto& item : b) {
            if (item[0] == 1 || item[1] == 1) continue;
            TreeNode* lf, *rf;
            //左f右t
            bool ld, rd;
            TreeNode* l, * r;
            lf = findNode(root, item[0], ld);
            rf = findNode(root, item[1], rd);
            
            if (ld) l = lf->right;
            else l = lf->left;
            if (rd) r = rf->right;
            else r = rf->left;
            
            if (judgeF(l, r)) continue;
            
            if (ld) lf->right = r;
            else lf->left = r;
            if (rd) rf->right = l;
            else rf->left = l;
        }
        return root;
    }
    
    bool judgeF(TreeNode* l, TreeNode* r) {
        bool ret = false;
        ret |= dfs(l, r);
        ret |= dfs(r, l);
        return ret;
    }
    
    bool dfs(TreeNode* base, TreeNode* target) {
        if (target == nullptr || base == nullptr) return false;
        if (base == target) return true;
        return dfs(base->left, target) || dfs(base->right, target);
    }

    TreeNode* findNode(TreeNode* root, int val, bool& d) {
        if (root == nullptr) return nullptr;
        if (root->left == nullptr && root->right == nullptr) return nullptr;
        if (root->left != nullptr && root->left->val == val) {d = false; return root;}
        if (root->right != nullptr && root->right->val == val) {d = true; return root;}
        TreeNode* temp = nullptr;
        if (root->left != nullptr) temp = findNode(root->left, val, d);
        if (temp != nullptr) return temp;
        if (root->right != nullptr) temp = findNode(root->right, val, d);
        if (temp != nullptr) return temp;
        return temp;
    }
};

5.开超市(没做了)


#秋招##腾讯##笔经##后端开发#
全部评论
第三题思路一样不知道为什么只a了10%
3 回复 分享
发布于 2021-09-26 23:19
路过补个4的AC
2 回复 分享
发布于 2021-09-26 22:58
楼主,第一题思路是怎么想的😂
1 回复 分享
发布于 2021-09-26 23:25
补个5题代码
1 回复 分享
发布于 2021-09-27 14:57
今天解锁了算式运算,平时都怕这种题,当然带括号的还不会做
点赞 回复 分享
发布于 2021-09-26 22:07
太强了
点赞 回复 分享
发布于 2021-09-26 22:31
有人a了第五道么,我感觉还是没啥思路
点赞 回复 分享
发布于 2021-09-26 22:45
第五题超市数就连通块数,然后处理连通块内最小距离和就好,但没来得及写完QAQ
点赞 回复 分享
发布于 2021-09-27 09:31
第4题给值和其节点、父节点做map就好,DFS序O(1)判断父子关系,O(1)交换。
点赞 回复 分享
发布于 2021-09-27 09:33
ac4题,然后笔试没了,这个怎么回事呀
点赞 回复 分享
发布于 2021-09-27 15:22

相关推荐

一个菜鸡罢了:哥们,感觉你的简历还是有点问题的,我提几点建议,看看能不能提供一点帮助 1. ”新余学院“别加粗,课程不清楚是否有必要写,感觉版面不如拿来写一下做过的事情,教育经历是你的弱势就尽量少写 2. “干部及社团经历”和“自我评价”删掉 3. 论文后面的“录用”和“小修”啥的都删掉,默认全录用,问了再说,反正小修毕业前肯定能发出来 4. 工作经验和研究成果没有体现你的个人贡献,着重包装一下个人贡献
点赞 评论 收藏
分享
20 55 评论
分享
牛客网
牛客企业服务