9.1B站笔试

试卷为算法/研发工程师（推荐搜索/AI/数据平台方向）

14个选择占比70分！！！！2个编程各15分，这选择看的我人都傻了。。。

选择题：

种类繁多，包括了散列表，树的后序遍历，栈数据结构，TCP，算法时间复杂度考察，快排/插入排序/堆排序/冒泡排序的稳定性、平均时间复杂度、最坏时间复杂度，BFS遍历图，二叉搜索，操作系统等。

编程题：

1. 序列中只包含数字和字母，判断是否有长度大于3的单调递增或者递减的数字序列，比较简单都通过了

思路：用一个字典每次把序列中的所有数字序列取出来，同时存储的有长度。再遍历字典判断即可。

2. 只包含(、)的序列，输出合法最长的前缀长度。这里我没有太懂前缀的意思，可能是必须从第一个字符开始算起吧。。。合法即为可以组成一对括号，)()(这种就不算合法。

思路：用dp+stack，stack保证合法性，遇到(入栈，遇到)出栈计算长度。当栈为空的时候dp(i)的值为length或者dp[i-2]+length，最后返回max(dp)。

但是只通过了40%的用例，只能说这个前缀这里搞得有点不太清楚。。。时间也不太够了。

总结为B站的选择题考察的基础很多，编程题不算很难大概也就是easy to medium的难度。

最后求笔试通过~~~

第一题Python：

def password(s):
    s += '*'
    n = len(s)
    dic = {}
    digit = ""
    cnt = 0
    for i in range(n):
        if s[i].isdigit():
            digit += s[i]
            cnt += 1
        elif digit != "":
            dic[digit] = cnt
            cnt = 0
            digit = ""
    for k, v in dic.items():
        if v < 3:
            continue
        else:
            flag = True
            length = len(k)
            if int(k[0]) < int(k[-1]):
                for i in range(1, length):
                    if int(k[i]) != int(k[i - 1]) + 1:
                        flag = False
                        break
                if flag:
                    return True
                else:
                    continue
            else:
                for i in range(1, length):
                    if int(k[i]) != int(k[i - 1]) - 1:
                        flag = False
                        break
                if flag:
                    return True
                else:
                    continue
    return False


t = int(input().strip())
for i in range(t):
    string = input().strip()
    res = password(string)
    if res:
        print("yes")
    else:
        print("no")

#b站笔试##笔试##bilibili笔试##B站#