百度笔试20220913研发A卷 AK

百度笔试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写的代码 体验还好吧

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

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

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

#百度##笔试##23届秋招笔面经##百度23秋招笔试编程题有点儿简单啊#
全部评论
太强了
3 回复 分享
发布于 2022-09-13 21:05 北京
第一题我用滑动窗口 + 状态机,搞了一个小时,63%,看到你的答案我直接裂开。 第二题,我发现规律:只要总长度是奇数都一定能成功,只要总长度为偶数并且1的数量是奇数就总是失败,100%了。
2 回复 分享
发布于 2022-09-13 21:26 广东
请问为什么是从终点走向起点
2 回复 分享
发布于 2022-09-14 01:42 四川
牛客?为啥我是在赛码网,也没有监控手机?我考了个假的吗
1 回复 分享
发布于 2022-09-14 04:59 新加坡
同3道全AC,可惜选择题稀烂
1 回复 分享
发布于 2022-09-14 16:46 四川
点赞 回复 分享
发布于 2022-09-13 21:05 四川
我第三题双向搜没有超时但是有百分之30一直wa,到现在都不知道为什么
点赞 回复 分享
发布于 2022-09-14 14:13 上海
为啥你的单源最短路没有优化最小值的操作
点赞 回复 分享
发布于 2022-09-15 13:02 广东
兄弟,看我主页进群,从此秋招不迷路
点赞 回复 分享
发布于 2022-09-15 15:17 澳大利亚

相关推荐

牛客5655:其他公司的面试(事)吗
点赞 评论 收藏
分享
微风不断:兄弟,你把四旋翼都做出来了那个挺难的吧
点赞 评论 收藏
分享
14 47 评论
分享
牛客网
牛客企业服务