8.29小猿笔试

💻题目：选择10道（50分），编程3道（20,30,40）
选择题编程题整体来说不算难，AK的概率还是比较高的
❓第一题：比较简单的模拟题，统计词汇表中所有字母的个数，再挨个看每个单词能组成多少个就行
m = int(input())
for _ in range(m):
    _map = [0] * 26 # 统计词汇表中的字母个数
    s = input()
    for c in s: 
        idx = ord(c) - ord('a')
        _map[idx] += 1
        
    n = int(input())
    ss = list(input().split())
    max_cnt = 0
    for st in ss:
        map1 = [0] * 26 # 组成每个单词需要的字母个数
        cnt = 100000
        for c in st:
            idx = ord(c) - ord('a')
            map1[idx] += 1
            cnt = min(_map[idx] // map1[idx], cnt)
            if cnt < max_cnt:
                break
        max_cnt = max(max_cnt, cnt)
    print(max_cnt)
❓第二题：中等难度的动态规划，牛客上有一模一样的题：DP18 滑雪，简单来说就是从最低点（最高点也行）广搜递推dp，dp[i][j]表示从（i，j）开始的最大长度，搜索完一轮之后又从没找过的最低点开始搜索
from queue import PriorityQueue, Queue
n, m = map(int, input().split())
_map = []
que = PriorityQueue() # 从低到高排列
dp = [[0] * m for _ in range(n)] # dp[i][j]表示从（i，j）开始的最大长度
for i in range(n):
    nums = list(map(int, input().split()))
    _map.append(nums)
    for j in range(m):
        que.put((nums[j], i, j))
while not que.empty():
    num, x, y = que.get()
    if dp[x][y] == 0: # 从没搜索过的最小点开始广搜
        dp[x][y] = 1
        que2 = Queue()
        que2.put((x, y))
        while not que2.empty():
            x2, y2 = que2.get()
            if x2 > 0 and _map[x2-1][y2] > _map[x2][y2] and dp[x2-1][y2] < dp[x2][y2] + 1:
                que2.put((x2-1, y2))
                dp[x2 - 1][y2] = dp[x2][y2] + 1
            if x2 < n - 1 and _map[x2+1][y2] > _map[x2][y2] and dp[x2+1][y2] < dp[x2][y2] + 1:
                que2.put((x2+1, y2))
                dp[x2 + 1][y2] = dp[x2][y2] + 1
            if y2 > 0 and _map[x2][y2-1] > _map[x2][y2] and dp[x2][y2-1] < dp[x2][y2] + 1:
                que2.put((x2, y2-1))
                dp[x2][y2-1] = dp[x2][y2] + 1
            if y2 < m - 1 and _map[x2][y2+1] > _map[x2][y2] and dp[x2][y2+1] < dp[x2][y2] + 1:
                que2.put((x2, y2+1))
                dp[x2][y2+1] = dp[x2][y2] + 1
_max = 1
for _dp in dp:
    _max = max(_max, max(_dp))
print(_max)
❓第三题：中等难度的滑动窗口，要求找到最小的连续子数组，使得这个子数组中包含K的所有质因子，比如K=60，子数组里就要包含2,2,3,5
首先找到小于K的所有质数，在用滑动窗口做就可以了
我最后代码有点问题就过了20%，但思路应该没错
#秋招笔面试记录#