腾讯客户端笔试
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")
