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-15 16:48 山东
厉害呀,大佬
1 回复 分享
发布于 2023-03-14 14:21 湖北
感谢大佬,学习了 回文子串构造 和树上DP
点赞 回复 分享
发布于 2023-04-07 19:54 辽宁
真强
点赞 回复 分享
发布于 2023-03-25 13:05 广东
感谢大佬,学习一下
点赞 回复 分享
发布于 2023-03-15 17:00 江西
太厉害啦
点赞 回复 分享
发布于 2023-03-15 15:15 湖北
大佬能说一下第三题思路吗,我小菜鸡看不懂
点赞 回复 分享
发布于 2023-03-14 09:29 江苏
mark
点赞 回复 分享
发布于 2023-03-14 06:52 重庆

相关推荐

来个大佬救一下,为上投了都是石沉大海了,没实习经历的话怕秋招直接进不了面。什么实习这么难找,基本
心态爆炸了:现在正式的岗位都少,实习基本不咋招的,除了大厂,中小企业其实没那么多岗位需求,就算是有,大多都是招一两个廉价劳动力,同时,他们也会希望你一来就能干活的,没时间培训你,就让你了解公司的项目,你了解完就可以开始干活。再者是,很多低质量的实习其实用处没有那么大的。我去年也是找实习找到破防,最后去了一家深圳的小公司实习,工作对我来说很简单,甚至不如我在学校做的项目,秋招的时候,这段实习经历也并没有帮上什么忙,投递简历,依旧非常低的回复率。低回复率是常态,尤其是找实习,找不到,那就把重心放在优化自己的简历和项目,多看八股文,锻炼自己的面试能力,多看别人的面经,自己模拟面试,等秋招的时候,只要有那么寥寥几次,好好抓住那几次机会。
点赞 评论 收藏
分享
榕城小榕树:1200单休,我去干点啥别的不好
点赞 评论 收藏
分享
05-29 09:02
门头沟学院 Java
点赞 评论 收藏
分享
评论
27
62
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务