百度笔试20220913 AK

第一题

给定一个字符串s，找出类似“baidu”的子串个数

类似“baidu”的子串是指：

• 子串的第一个和第四个字符为辅音
• 子串的其余字符为元音”aeiou”
• 不含重复字符

数据范围：len(s) < 2e6

Solution

由于给定了具体的位置，所以不好滑动窗口做

所以直接每五个字符check一下

s = input().strip()
n = len(s)
res = 0
mp = {v: i for i, v in enumerate("aeiou")}

def check(s):
    return (
        len(set(s)) == 5
        and all(x not in mp for x in (s[0], s[3]))
        and all(x in mp for x in (s[1], s[2], s[4]))
    )

for i in range(5, n + 1):
    if check(s[i - 5 : i]):
        # print(s[i - 5 : i])
        res += 1
print(res)

第二题

给定一个t，表示接下来有t行数据

给定一个01字符串s，对于每两个连续的子串，你可以把他们变成相反的子串

如 ”01“ 变成”10“ ，“00”变成”11“

如果能把s转换成所有字符相同的字符串，输出”Yes“；否则输出”No”

数据范围 len(s)<2e6

Solution

硬做就是了，要么变成全0，要么全1，两种都尝试一下

def f(s, c):
    n = len(s)
    for i in range(n - 1):
        if s[i] != c:
            s[i + 1] = c if s[i + 1] != c else s[i]
            s[i] = c
    return s[-1] == c

t = int(input())
for _ in range(t):
    s = list(input().strip())
    if f(s, "0") or f(s, "1"):
        print("Yes")
    else:
        print("No")

第三题

第一行输入n m (1<n,m<500)

n表示矩阵的行 m表示矩阵的列

接下来n行 输入一个长为m的”red”字符串

“red”字符串是指所有字符均为”r"或”e"或”d”

你可以在矩阵中上下左右移动

但是r不能移动到d e不能移动到r d不能移动到e

输出从左上角走到右下角最少需要多长时间

如无法到达输出-1

Solution

最近遇到好多这种题目 美团和华子都有类似的题 有点ptsd了

这种应该都是类似最短路径问题 注意需要从终点走向起点

from collections import deque

ban = "rderde"
mp = {}
for i in range(0, 5, 2):
    mp[ban[i + 1]] = ban[i]
n, m = map(int, input().split())
board = []
for _ in range(n):
    s = list(input().strip())
    board.append(s)

inf = 10 ** 9

q = deque([(n - 1, m - 1)])
g = [[inf] * m for _ in range(n)]
g[n - 1][m - 1] = 0
while q:
    x, y = q.popleft()
    for dx, dy in [(0, -1), (0, 1), (1, 0), (-1, 0)]:
        nx, ny = dx + x, dy + y
        if (
            0 <= nx < n
            and 0 <= ny < m
            and mp[board[x][y]] != board[nx][ny]
            and g[nx][ny] == inf
        ):
            g[nx][ny] = g[x][y] + 1
            q.append((nx, ny))

if g[0][0] == inf:
    print(-1)
else:
    print(g[0][0])

总结

这次面试是在牛客进行的 没想到居然还要监测手机

然后的话是在本地IDE写的代码 体验还好吧

编程题难度比较一般吧 我觉得更难的反而是那些选择题

真的是面面俱到 啥都有 看得我头疼 直接摆烂了

另外牛客能不能整个定时功能,每次写好了还要卡点发,好麻烦啊