百度正式批笔经（研发A卷，算法题解+AK代码）
笔试：2022.09.13
岗位：c++研发工程师
时长：2小时（实际完成1小时）
在牛客上进行
经验教训：
一定要带好纸和笔！！！（全程无纸笔，只能痛苦乱答了）
单选题+多选题，八股知识
算法题
题目1
题面
判断一个长字符串，包含几个“baidu”型字符子串。”baidu”型字符串定义为，长度为5的字符串，任意两个字符不同，且第一第四位是辅音字母，另外三位是元音字母。字符串长度为20万。
思路
看清题意，暴力判断就行了
代码
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
string s;
bool check(const char &ch) {
if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u')
return true;
return false;
}
int main() {
cin >> s;
int n = s.size();
int ans = 0;
for (int i = 0; i < n - 4; ++i) {
bool flag = 1;
if (check(s[i]) || check(s[i+3]) || !check(s[i+1]) || !check(s[i+2]) || !check(s[i+4]))
continue;
for (int j = 0; j < 5; ++j)
for (int k = j + 1; k < 5; ++k)
if (s[i+j] == s[i+k])
flag = 0;
ans += flag;
}
cout << ans <<endl;
return 0;
}题目2
给q个字符串，每个字符串包含01。一个字符串能翻转任意次，每次翻转相邻两个数。求这q个字符串，能否变为全0或全1。字符串总长度20万。
思路
蛮有意思的题目，分享两个做法。
第一个做法：找规律
假设我们把所有相邻的1都变成0，其他1都是孤立的，可以全部交换到队列开头，那么只要判断奇偶，就知道是否能全部变成0。
做法很简单，只要对整个序列求一遍异或和即可。
（考场我只想到了这里，提交后只有10分）
但是这样可能有问题，比如010，它的最终答案是全1的，不能变成全0。
怎么办呢，把01交换，重新跑一遍。两次只要有一次是Yes，答案就是Yes。
第二个做法：动态规划
考虑到交换只能是相邻的，也就是我们当前是否交换只和上一个状态有关，很自然地想到用动态规划。
只有上一个状态，不好转移，还要考虑前面是变成了全0或者全1。
我设置了4个状态
f[i][0][0]表示最后一位为0，前面i-1位均为0，是否有解
f[i][0][1]表示最后一位为0，前面i-1位均为1，是否有解
f[i][1][0]表示最后一位为1，前面i-1位均为0，是否有解
f[i][1][1]表示最后一位为1，前面i-1位均为1，是否有解
每步的转移其实就两种情况，i翻转或者不翻转，所以有8个转移方程，具体看代码。
最终当f[n-1][0][0]为true，或者f[n-1][1][1]为true，即为Yes。
代码
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
string s;
bool f[200005][2][2];
int main() {
int q;
cin >> q;
while (q--) {
cin >> s;
int n = s.size();
if (s[0] == '0') {
f[0][0][0] = f[0][0][1] = true;
f[0][1][0] = f[0][1][1] = false;
}
else {
f[0][0][0] = f[0][0][1] = false;
f[0][1][0] = f[0][1][1] = true;
}
for (int i = 1; i < n; ++i) {
f[i][0][0] = f[i][0][1] = f[i][1][0] = f[i][1][1] = false;
if (s[i] == '0') {
f[i][0][0] |= f[i-1][0][0];
f[i][0][1] |= f[i-1][1][1];
f[i][1][0] |= f[i-1][1][0];
f[i][1][1] |= f[i-1][0][1];
}
else {
f[i][0][0] |= f[i-1][1][0];
f[i][0][1] |= f[i-1][0][1];
f[i][1][0] |= f[i-1][0][0];
f[i][1][1] |= f[i-1][1][1];
}
}
if (f[n-1][0][0] || f[n-1][1][1])
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}题目3
N*M的字符矩阵，包含red三个字母。有三条路是不能走的，”r->d”,”e->r”,”d->e”。求左上角到右下角的最段路。
思路
带障碍的，边权为1的最短路。
经典BFS（宽度优先搜索问题）
代码
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
int n, m;
char A[505][505];
int Q[2500005][2], dis[505][505];
const int fx[4] = {0, 1, -1, 0};
const int fy[4] = {1, 0, 0, -1};
int main() {
cin >> n >> m;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j) {
scanf(" %c", &A[i][j]);
dis[i][j] = 1e9;
}
int l = 0, r = 1;
Q[0][0] = 0, Q[0][1] = 0; dis[0][0] = 0;
while (l < r) {
for (int t = 0; t < 4; ++t) {
int ux = Q[l][0];
int uy = Q[l][1];
int tx = ux + fx[t];
int ty = uy + fy[t];
if (tx < 0 || tx >= n || ty < 0 || ty >= m)
continue;
if ((A[ux][uy] == 'r' && A[tx][ty] == 'd') ||
(A[ux][uy] == 'e' && A[tx][ty] == 'r') ||
(A[ux][uy] == 'd' && A[tx][ty] == 'e'))
continue;
if (dis[tx][ty] > dis[ux][uy] + 1) {
dis[tx][ty] = dis[ux][uy] + 1;
Q[r][0] = tx; Q[r][1] = ty;
r++;
}
}
l++;
}
if (dis[n-1][m-1] == 1e9)
cout << -1;
else
cout << dis[n-1][m-1];
return 0;
}八股完成总时长：20分钟；
算法题完成总时长：40分钟；
得分100+100+100=300。
算法不难，八股比较难。
希望百度还有HC给正式批的笔试同学哈哈～
