笔试：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给正式批的笔试同学哈哈～