2024-03-16 16:57 电子科技大学 C++
关注
饿了么笔试
1. 利用哈希存储x1和x2的出现次数，y1和y2同理，如果x1出现一次，答案为x1，x2同理，y同理
2. 前缀和+字符统计，根据count[26]判断是否可以变成回文字符串，如果出现count[k]为奇数的个数大于等于2则不是回文
3. dfs，注意叶子节点的奇数权值和偶数权值个数的初始化
代码
pair<int, int> dfs(int u)
{
st[u] = true;
int odd = 0, even = 0;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (st[j]) continue;
pair<int, int> s = dfs(j);
if (w[i] % 2)
{
ans += (s.second + 1) * odd;
ans += (s.first) * odd;
ans += s.first;
even += s.first;
odd += s.second + 1;
}
else
{
ans += (s.second + 1) * even;
ans += (s.first) & odd;
even += s.second + 1;
ans += s.second + 1;
odd += s.first ;
}
}
return {odd, even};
}
2. 前缀和+字符统计，根据count[26]判断是否可以变成回文字符串，如果出现count[k]为奇数的个数大于等于2则不是回文
3. dfs，注意叶子节点的奇数权值和偶数权值个数的初始化
代码
pair<int, int> dfs(int u)
{
st[u] = true;
int odd = 0, even = 0;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (st[j]) continue;
pair<int, int> s = dfs(j);
if (w[i] % 2)
{
ans += (s.second + 1) * odd;
ans += (s.first) * odd;
ans += s.first;
even += s.first;
odd += s.second + 1;
}
else
{
ans += (s.second + 1) * even;
ans += (s.first) & odd;
even += s.second + 1;
ans += s.second + 1;
odd += s.first ;
}
}
return {odd, even};
}
全部评论
寄来寄去
深圳技师学院 后端工程师
佬还记得第三题题目是啥吗
相关推荐
点赞 评论 收藏
分享
01-12 17:45
门头沟学院 Java 点赞 评论 收藏
分享