腾讯音乐娱乐集团2024暑期实习生招聘技术类岗位编程题合集
存一下代码emmm太久没写题手好生。用了3h左右，第五题没写出来，想复杂了。。。。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @return int整型
*/
int minCnt(string s) {
// write code here
int cnt = 0;
for (auto i : s) {
if (i == '1') cnt++;
}
return cnt - 1;
}
};
#include <queue>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param a int整型vector
* @param k int整型
* @param x int整型
* @return int整型
*/
int minMax(vector<int>& a, int k, int x) {
// write code here
priority_queue<int>q;
for (auto i : a) q.push(i);
while(k--) {
int tt = q.top();
q.pop();
tt -= x;
q.push(tt);
}
return q.top();
}
};
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型
* @param k int整型
* @return int整型
*/
const int N = 505, mod = 1e6;
typedef long long ll;
ll dp[N][28][2][2];
int numsOfStrings(int n, int k ) {
// write code here
//k-1个分隔点，每段长度至少为2，且相邻不同，26个字母
//dp[j][k][0/1]:到i为止划分的段数j,字母种类k,长度是否>=2,滚动数组
for (int ch = 0; ch < 26; ch++) {
dp[1][ch][0][1] = 1;
}
ll ans = 0;
for (int i = 2; i <= n; i++) {
int lst = (i - 1) & 1, cur = i & 1;
for (int j = 1; j <= k; j++) {
for (int ch = 0; ch < 26; ch++) {
dp[j][ch][1][cur] = dp[j][ch][0][cur] = 0;
}
for (int ch = 0; ch < 26; ch++) {
dp[j][ch][1][cur] += dp[j][ch][0][lst];
dp[j][ch][1][cur] %= mod;
dp[j][ch][1][cur] += dp[j][ch][1][lst];
dp[j][ch][1][cur] %= mod;
//不能划分->新启一段
for (int cc = 0; cc < 26; cc++) {
if (cc == ch) continue;
dp[j][ch][0][cur] += dp[j-1][cc][1][lst];
dp[j][ch][0][cur] %= mod;
}
}
}
if (i == n) {
for (int ch = 0; ch < 26; ch++) {
ans += dp[k][ch][1][n&1];
ans %= mod;
}
}
}
return ans % mod;
}
/**
* 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 a int整型vector
* @return TreeNode类vector
*/
map<int, int> dep;
map<int, vector<int>>idx;
map<int, TreeNode*>mp;
map<TreeNode*, TreeNode*>dadl, dadr;
int id = 0, mx = 0;
void dfs (TreeNode* p, int fa) {
int u = ++id;
// p->val = u;
mp[u] = p;
dep[u] = dep[fa] + 1;
mx = max(mx, dep[u]);
if (p->left != nullptr) dfs(p->left, u), dadl[p->left] = p;
if (p->right != nullptr) dfs(p->right, u), dadr[p->right] = p;
}
vector<TreeNode*> deleteLevel(TreeNode* root, vector<int>& a) {
// write code here
dfs(root, 0);
// for (int i = 1; i <= id; i++) cout << dep[i] << ' '; cout << endl;
for (int i = 1; i <= id; i++) idx[dep[i]].push_back(i);
// for (int i = 1; i <= mx; i++) {
// cout << i << ": ";
// for (auto j : idx[i]) cout << j << ' ';
// cout << endl;
// }
sort(a.begin(), a.end());
//谁删掉就保存子
vector<TreeNode*> rt;
set<int> st;
for (auto i : a) st.insert(i);
if (!st.count(1)) rt.push_back(root);
for (auto i : a) {
for (auto j : idx[i]) {
auto p = mp[j];
if (p->left != nullptr) {
if (!st.count(i + 1)) rt.push_back(p->left);
}
if (p->right != nullptr) {
if (!st.count(i + 1)) rt.push_back(p->right);
}
p->left = p->right = nullptr;
if (dadl[p] != nullptr) dadl[p]->left = nullptr;
if (dadr[p] != nullptr) dadr[p]->right = nullptr;
}
}
// for (auto i : rt) cout << i->val << ' ';
return rt;
}
};
这题写错了，想复杂了
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回值的树节点中val表示节点权值
* @param root TreeNode类 给定的初始树节点中的val表示节点编号
* @param op int整型vector<vector<>> op的组成为[[id,v],[id,v],[id,v],...]
* @return TreeNode类
*/
vector<int>v, sum;
map<int, int>idx;
void dfs (TreeNode *u) {
int x = u->val, id = idx[x];
u->val = sum[id];
if (u->left != nullptr) dfs(u->left);
if (u->right != nullptr) dfs(u->right);
}
TreeNode* xorTree(TreeNode* root, vector<vector<int> >& op) {
// write code here
// dfs (root);
v.push_back(0);
queue<TreeNode*>q;
q.push(root);
v.push_back(root->val);
while (!q.empty()) {
auto t = q.front();
q.pop();
// v.push_back(t->val);
// if (t->left == nullptr && t->right == nullptr) continue;
TreeNode *tmp;
if (t->left == nullptr && t->right == nullptr) {
TreeNode *t1, *t2;
q.push(t1), q.push(t2);
continue;
}
if (t->left != nullptr) q.push(t->left), v.push_back(t->left->val);
else v.push_back(0), q.push(tmp);
if (t->right != nullptr) q.push(t->right), v.push_back(t->right->val);
else v.push_back(0), q.push(tmp);
}
for (auto i : v) cout << i << ' ';
int n = v.size() - 1;
for (int i = 1; i <= n; i++) {
idx[v[i]] = i;
}
// for (auto i : idx) cout << i.first << ' ' << i.second << endl;
// cout << "---------\n";
for (int i = 0; i <= n + 2; i++) sum.push_back(0);
for (auto vi : op) {
int id = idx[vi[0]], val = vi[1];
// cout << id << ' ' << val << "-----------" << endl;
int step = 1, l = id, r = l + step - 1;
sum[l - 1] ^= val, sum[min(r, n)] ^= val;
// cout << l << ' ' << r << endl;
while (r <= n) {
step *= 2, l *= 2, r = l + step - 1;
if (l > n) break;
// cout << l << ' ' << r << endl;
sum[l - 1] ^= val, sum[min (r, n)] ^= val;
if (r > n) break;
}
// for (int i = 1; i <= n; i++) cout << sum[i] << ' ';
// cout << endl;
}
for (int i = n - 1; i >= 1; i--) {
sum[i] ^= sum[i+1];
}
// for (int i = 1; i <= n; i++) cout << sum[i] << ' ';
//转回去:层序遍历->treenode
dfs(root);
return root;
}
};
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param S string字符串
* @param k int整型
* @return int整型
*/
int howMany(string S, int k) {
// write code here
map<char, int> mp;
for (auto i : S) mp[i]++;
int cnt = 0;
for (auto i : mp) {
if (i.second >= k) cnt++;
}
return cnt;
}
};
#腾讯音乐26届实习#
哔哩哔哩公司福利 443人发布