3.13百度后端笔试编程题

第一题

给定一个字符串,问是否可以排列为:Baidu

#include <iostream>
#include <map>
#include <string>

using namespace std;

bool solve() {
    string s; cin >> s;
    if(s.size() != 5) return false;
    
    map<char, int> mp;
    string Baidu = "Baidu";
    for(char c : s) mp[c] ++;
    for(char c : Baidu) if(mp[c] != 1) return false;
    
    return true;
}

int main() {
    int tt; cin >> tt;
    while(tt--) cout << (solve() ? "Yes" : "No") << '\n';
    
    return 0;
}

第二题

给定数字p,构造s使得s的子字符串为回文串的数目为p。(p<1e9,s.size() < 1e5);

#include <iostream>
#include <string>

using namespace std;

int main() {
    int x; cin >> x;
    
    string s, red = "red";
    
    int c = 0;
    while(x) {
        int sum = 0, i = 1;
        while(sum + i <= x) { // 构造连续相同的c
            sum += i, i++;
            s += red[c];
        }
        
        x -= sum, c = (c + 1) % 3;
    }
    cout << s;
    
    return 0;
}

第三题

给定一棵树,每个节点有蓝色和红色两种颜色,问:删除其中一条边,剩下两个联通块的色块的个数的差值,求所有差值的和;(n<2e5)

#include <iostream>
#include <vector>
#include <string>


using namespace std;
using ll = long long;
const int N = 200010;

int n;
string s;
vector<int> edge[N];
ll sum, ans, dp[N];

ll init(int x, int fa) {
    dp[x] = 1;
    for(int y : edge[x]) {
        if(y == fa) continue;
        
        dp[x] += init(y, x);
        // 如果子节点与父节点颜色相同,合并为一个块
        if(s[x] == s[y]) dp[x] --; 
    }
    return dp[x];
}

void dfs(int x, int fa) {
    for(int y : edge[x]) {
        if(y == fa) continue;
        dfs(y, x);
        ll son = dp[y];
        // 父亲节点所拥有的颜色块的数目为:总-儿子节点颜色块的数目+分割产生的一个颜色块
        ll father = sum - son + (s[x] == s[y]);
        
        ans += abs(father - son);
    }
}

int main() {
    cin >> n >> s;
    for(int i = 1; i < n; i++) {
        int x, y; cin >> x >> y;
        x--, y--;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    
    sum = init(0, -1);
    dfs(0, -1);
    cout << ans;
    
    return 0;
}

代码为回忆版本,非现场通过版本

#我的实习求职记录#
全部评论
大佬能说一下第二题思路吗,我小菜鸡看不懂
3 回复 分享
发布于 2023-03-14 11:26 北京
第三题没开longlong是过百分之十嘛
2 回复 分享
发布于 2023-03-14 15:39 浙江
厉害呀,大佬
1 回复 分享
发布于 2023-03-14 14:21 湖北
感谢大佬分享
1 回复 分享
发布于 2023-03-15 16:48 山东
mark
点赞 回复 分享
发布于 2023-03-14 06:52 重庆
大佬能说一下第三题思路吗,我小菜鸡看不懂
点赞 回复 分享
发布于 2023-03-14 09:29 江苏
太厉害啦
点赞 回复 分享
发布于 2023-03-15 15:15 湖北
感谢大佬,学习一下
点赞 回复 分享
发布于 2023-03-15 17:00 江西
真强
点赞 回复 分享
发布于 2023-03-25 13:05 广东
感谢大佬,学习了 回文子串构造 和树上DP
点赞 回复 分享
发布于 2023-04-07 19:54 辽宁

相关推荐

点赞 评论 收藏
分享
02-18 21:55
门头沟学院 Java
拍打星:谁说的,焦虑只是一种心理状态,啥都不干也可以焦虑,不如说很多人就是因为啥都不干才导致焦虑感加重
点赞 评论 收藏
分享
序&nbsp;朋友们,好久不见。&nbsp;笔者在过去消失的五个月里被困在情绪牢笼中过的相当煎熬,一度丢失自己,觉得整个世界都是昏暗的。&nbsp;庆幸的是靠着自己纯硬扛也是走出来了。表达欲再度回归,所以真的很开心还有机会能在再和大家见面。&nbsp;破碎秋招&nbsp;抑郁情绪的引爆点必然是秋招期间遭受的打击了,从去年九月份腾讯转正被告知失败之后就开始疯狂投递简历,每天都在经历:简历挂、一面挂、二面挂、三面挂、HR面挂,每天睁开眼就被无所适从的挫败感包围。&nbsp;秋招的特点是即便流程走到最后一步也不一定会&nbsp;offer,因为还需要进入大池子进行横向对比,俗称泡池子,而这一泡我的大多数面试流程到后面就没了后文,这一度让我感觉非常绝望。我深知自己学历并...
SoNiC_X:我已经工作快2年了,当时高考没考好没去到想去的学校,觉得天要塌了;校招找不到工作,觉得天要塌了;现在工作觉得看不到未来,觉得天要塌了;最近最大的感悟就是:天会一直塌,但是生活也会一直继续下去,还是要调整好自己的心态,不要因为一时的困难把自己困住,要记住完蛋的日子永远在后头
点赞 评论 收藏
分享
评论
27
62
分享

创作者周榜

更多
牛客网
牛客企业服务