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

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

头像
南七技校 #秋招#
发布于 2021-09-26 22:05:35 APP内打开
赞 20 | 收藏 56 | 回复10 | 浏览3192
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.开超市(没做了)


10条回帖

回帖
加载中...
话题 回帖

相关热帖

笔经面经近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐