9.13 百度研发A卷（baidu子串+01串+red矩阵）

一晚上2小时做了中兴、百度、微众银行，是真的累。。。百度的编程题总体难度一般，以下代码均为AC代码。

第一题：baidu子串

“baidu子串”是第1、4个字母为辅音，2、3、5个字母为元音，且这些字母全都不同的字符串。给定输入字符串，输出baidu子串（注：子串必须连续）的数量。

输入：

一个字符串

输出：

baidu子串的数量

解法：先把所有字母按照元音、辅音分开；然后遍历每个长度为5的子串，如果是“辅元元辅元”的形式，再检查它是否字母各异。

s = input()
y = ''
for c in s:
    if c in 'aeiou':
        y += '1'
    else:
        y += '0'
ans = 0
for i in range(len(s) - 4):
    if y[i:i+5] == '01101' and len(set(s[i:i+5])) == 5:
        ans += 1
print(ans)

第二题：01串

给定 0 和 1 组成的字符串，现在可以进行无限次操作，每次将连续2个字符取反。问是否可以将字符变成全部相同。

输入：

正整数n，接下来n行均是一个0、1组成的字符串

输出：

对于每一行，如果可以变成全部相同，输出“Yes”，否则输出“No”

解法：我们可以通过若干次操作，达到【同时翻转任意两个位置的字符】的效果。具体做法：要想交换第 i 和 j 位（i < j）的字符，只需要依次将 i 和 i+1、i+1和i+2、...、j-1和j交换即可。途中只有 i 和 j 两个数字反转了一次，其余数字反转了2次所以没有变化。

因此，只要字符串中0或1的数量为偶数即可。（我考试时提交的代码，判断的是字符串长度为奇数，或1数量为偶数，跟上述条件是等价的）

n = int(input())
for _ in range(n):
    s = input()
    if (len(s) & 1 == 1 or s.count('1') & 1 == 0):
        print('Yes')
    else:
        print('No')

第三题：矩阵行走

给定一个 m * n 的矩阵，每个元素为 'r' 'e' 'd' 之一。小红要从左上角走到右下角，并且不能从r走向d、从e走向r，从d走向e。最少需要多少步？如果无法到达输出-1。

输入：

正整数n，m，表示行数和列数

接下来n行均是一个'r' 'e' 'd'组成字符串，长度均为m

输出：

如果能到右下角，输出最少步数；如果不能，输出-1

网格类问题。按照题意，从左上角进行层序遍历，模拟即可。每遍历一层，计数器加1，最后若未到达则输出-1。

n, m = [int(x) for x in input().split()]
if m==n==1:
    print(0)
    exit(0)
g = []
for _ in range(n):
    g.append(list(input() + '0'))
g.append('0' * (m + 1))
ans = 0
layer = {(0,0)}
flag = True
while layer and flag:
    ans += 1
    nxt = set()
    for x, y in layer:
        for xx, yy in ((x+1, y), (x, y+1), (x-1, y), (x, y-1)):
            if g[x][y] == 'r' and g[xx][yy] in 're':
                nxt.add((xx, yy))
            if g[x][y] == 'e' and g[xx][yy] in 'de':
                nxt.add((xx, yy))
            if g[x][y] == 'd' and g[xx][yy] in 'rd':
                nxt.add((xx, yy))
        g[x][y] = '0'
    if (n-1, m-1) in nxt:
        print(ans)
        flag = False
    else:
        layer = nxt
if flag:
    print(-1)

求大佬点赞！！！