腾讯客户端笔试

t1

删除链表中值为k的数

ListNode* deleteNode(ListNode* head, int k) {
        auto t = new ListNode(0);
        auto tmp = t;
        t->next = head;
        auto pre = t;
        while(head!=nullptr)
        {
            auto next = head->next;
            if(head->val == k) 
            {
                pre->next = next;
            }
            else
            pre = head;
            head = next;
        }
        return tmp->next;
    }

t2

给定二叉树，每个点价值是0或1，问从根节点到叶子节点组成的二进制数有多少个在l,r范围中

遍历往下走，大于r返回，最后看是不是大于等于l

 int number_of_different_plans(TreeNode* root, int l, int r) {
        // write code here
            int ans = 0;
        function<void(TreeNode*,int)> dfs = [&](TreeNode *rt, int x)
        {
            if(rt == nullptr) return;
            x = x * 2 + rt->val;
            if(x > r) return;
            if(rt ->left == nullptr && rt->right == nullptr)
            {
                if(x >= l) ans++;
                return;
            }
            // cout<<rt->val<<endl;
            dfs(rt->left, x), dfs(rt->right,x);

        };
        dfs(root, 0);
        return ans;
    }

t3

给定一颗树，每个节点右价值1或2，问有多少条简单路径价值为3，路径的价值是包含节点的价值，u->v,v->u只算一条

点数n满足1<=n<=1e5

存在三种路径，儿子->自己->父亲, 儿子->自己,儿子->自己->儿子,讨论一下即可

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >>n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; ++i) cin >>a[i];

    vector<vector<int>> h(n + 1);
    for(int i = 0, u, v; i < n - 1; ++i)
    {
        cin >>u >>v;
        h[u].push_back(v);
        h[v].push_back(u);
    }
    long long ans = 0;
    function<void(int,int)> dfs = [&](int u, int f)
    {
        if(f)
        {
            for(auto v : h[u])
            {
                if(v == f) continue;
                if(a[v] + a[u] + a[f] == 3) ans++;
            }
        }
        long long c = 0;
        for(auto v : h[u])
        {
            if(v == f) continue;
            if(a[v] + a[u] == 3) ans++;
            if(a[v] == 1) c++;
            dfs(v, u);
        }
        if(a[u] == 1) ans+=c * (c - 1)/2;
    };
    dfs(1, 0);
    cout<<ans<<endl;
}
// 64 位输出请用 printf("%lld")

t4

给定一颗树,问去掉一条边后生成的两个子树的直径的差值的绝对值最小是多少

点数n满足1<=n<=1e3

枚举每条边删除情况，模拟即可

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >>n;

    vector<vector<int>> h(n + 1);
    vector<pair<int,int>> p;
    for(int i = 0, u, v; i < n - 1; ++i)
    {
        cin >>u >>v;
        h[u].push_back(v);
        h[v].push_back(u);
        p.push_back({u, v});
    }

    int ans =n + 1;
     vector<int> dis(n + 1);
     auto tmp = dis;
    function<void(int,int,int)> dfs = [&](int u, int f,int t)
    {
        for(auto v : h[u])
        {
            if(v == f || v == t) continue;
            dis[v] = dis[u] + 1;
            dfs(v, u, t);
        }
    };
    auto get = [&](int a, int b)
    {
        dis = tmp;
       dfs(a, 0, b);
        int x = a;
        for(int i = 1; i <= n; ++i)
        {
            if(i != b && dis[i] > dis[x]) x = i;
        }
        // cout<<x<<endl;
        dis = tmp;
       dfs(x, 0, b);
        return *max_element(dis.begin(), dis.end());
    };
    for(auto [v, u] : p)
    {
        ans = min(ans, abs(get(v, u) - get(u, v)));
    }
    
    cout<<ans<<endl;
}
// 64 位输出请用 printf("%lld")

t5

给定一个n*m的矩阵，每个点有价值aij,以及颜色sij, 有两个人一起走，每次只能走右或者下，每个人只有点的颜色和自己颜色相同才能选这个点的价值，每个人也可以不选这个点，要求一个人不能连续选两次，问左上角一起走到右下角价值最大是多少

1<=n,m<=1e3

dp即可，记录每个点选不选然后分类讨论

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >>n >>m;
    vector a(n,vector(m, 0));
    vector dp(n,vector(m,vector(2,0ll)));
    for(auto &i : a) 
        for(auto &j : i)
            cin >>j;
    dp[0][0][0] = 0, dp[0][0][1] = a[0][0];
    vector<string> s(n);
    for(auto &i : s) cin >>i;
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0;j < m; ++j)
        {
            if(i)
            {
                if(s[i - 1][j]!=s[i][j])
                {
                    dp[i][j][0] = max(dp[i][j][0], max(dp[i - 1][j][1], dp[i - 1][j][0]));
                    dp[i][j][1] = max(dp[i][j][1], max(dp[i - 1][j][1], dp[i - 1][j][0]) + a[i][j]);
                }
                else
                {
                    dp[i][j][0] = max(dp[i][j][0], max(dp[i - 1][j][1], dp[i - 1][j][0]));
                    dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j][0] + a[i][j]);
                }
            }
            if(j)
            {
                if(s[i][j - 1]!=s[i][j])
                {
                    dp[i][j][0] = max(dp[i][j][0], max(dp[i][j - 1][1], dp[i][j - 1][0]));
                    dp[i][j][1] = max(dp[i][j][1], max(dp[i][j - 1][1], dp[i][j - 1][0]) + a[i][j]);
                }
                else
                {
                    dp[i][j][0] = max(dp[i][j][0], max(dp[i][j - 1][1], dp[i][j - 1][0]));
                    dp[i][j][1] = max(dp[i][j][1], dp[i][j - 1][0] + a[i][j]);
                }
            }
        }
    }
    cout<<max(dp[n - 1][m - 1][0], dp[n - 1][m - 1][1])<<endl;
}
// 64 位输出请用 printf("%lld")