算法题记录 24

2070.每一个查询的最大美丽值（1724）

给你一个二维整数数组 items ，其中 items[i] = [pricei, beautyi] 分别表示每一个物品的 价格 和 美丽值 。

同时给你一个下标从 0 开始的整数数组 queries 。对于每个查询 queries[j] ，你想求出价格小于等于 queries[j] 的物品中，最大的美丽值 是多少。如果不存在符合条件的物品，那么查询的结果为 0 。

请你返回一个长度与 queries 相同的数组 answer，其中 answer[j]是第 j 个查询的答案。

涉及知识点

前缀，二分

解决思路

很简单的题，按price从小到大排序，原地记录每个price对应的之前所有的beauty的最大值，然后我们拿query对price二分查找找到提前算出的beauty即可。

class Solution:
    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
        b=[[0,-inf] for _ in range(len(items))]
        items.sort(key=lambda x:x[0])
        answer=[]
        for i in range(len(items)):
            b[i][0]=items[i][0]
            b[i][1]=max(b[i-1][1],items[i][1])
        for each in queries:
            if each <b[0][0]:
                answer.append(0)
                continue
            index1=bisect_right(b,each,key=lambda b:b[0])-1
            answer.append(b[index1][1])
        return answer

3175.找到连续赢K场比赛的第一位玩家（1724）

有 n 位玩家在进行比赛，玩家编号依次为 0 到 n - 1 。

给你一个长度为 n 的整数数组 skills 和一个 正 整数 k ，其中 skills[i] 是第 i 位玩家的技能等级。skills 中所有整数 互不相同 。

所有玩家从编号 0 到 n - 1 排成一列。

比赛进行方式如下：

队列中最前面两名玩家进行一场比赛，技能等级 更高 的玩家胜出。
比赛后，获胜者保持在队列的开头，而失败者排到队列的末尾。
这个比赛的赢家是 第一位连续 赢下 k 场比赛的玩家。

请你返回这个比赛的赢家编号。

涉及知识点

脑筋急转弯

解决思路

如果按题意用队列去模拟，会发现超时，并且代码编写很耗时间。但是我们仔细想想会发现如果所有值都没满足k，那我们此时拿到手去比较的数一定是整个列表的最大值，此时他会一直赢下去。那么我们只需要记录连胜即可，如果一个数在连胜我们观察它是否会满足k，如果输了我们就更新“最大下标”，连胜数清零，拿新的较大值去进行连胜判断。

class Solution:
    def findWinningPlayer(self, skills: List[int], k: int) -> int:
        max_i = win = 0
        for i in range(1, len(skills)):
            if skills[i] > skills[max_i]:  # 打擂台，发现新的最大值
                max_i = i
                win = 0
            win += 1  # 获胜回合 +1
            if win == k:  # 连续赢下 k 场比赛
                break
        # 如果 k 很大，那么 max_i 就是 skills 最大值的下标，毕竟最大值会一直赢下去
        return max_i

3191.使二进制数组全部等于1的最少操作次数1（1312）

有 n 位玩家在进行比赛，玩家编号依次为 0 到 n - 1 。

给你一个长度为 n 的整数数组 skills 和一个 正 整数 k ，其中 skills[i] 是第 i 位玩家的技能等级。skills 中所有整数 互不相同 。

所有玩家从编号 0 到 n - 1 排成一列。

比赛进行方式如下：

队列中最前面两名玩家进行一场比赛，技能等级 更高 的玩家胜出。
比赛后，获胜者保持在队列的开头，而失败者排到队列的末尾。
这个比赛的赢家是 第一位连续 赢下 k 场比赛的玩家。

请你返回这个比赛的赢家编号。

涉及知识点

数学

解决思路

难度只有1312挺意外，其实这题需要数学直觉。我们发现假如存在某种翻转策略，这种策略跟翻转的先后顺序是无关的，只跟哪些i,i+1,i+2下标的数要翻转有关，并且，最优策略下i,i+1,i+2要么操作一次，要么不操作，因为如果操作2次相当于没操作，操作次数凭空增加了。所以我们可以从左往右依次模拟，像背包问题一样，考虑i是操作还是不操作即可。如果i=0，那我们必须操作。

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        ans = 0
        for i in range(len(nums) - 2):
            if nums[i] == 0:  # 必须操作
                nums[i + 1] ^= 1
                nums[i + 2] ^= 1
                ans += 1
        return ans if nums[-2] and nums[-1] else -1

935.骑士拨号器（1690）

象棋骑士有一个独特的移动方式，它可以垂直移动两个方格，水平移动一个方格，或者水平移动两个方格，垂直移动一个方格(两者都形成一个 L 的形状)。
我们有一个象棋骑士和一个电话垫，如下所示，骑士只能站在一个数字单元格上(即蓝色单元格)。
给定一个整数 n，返回我们可以拨多少个长度为 n 的不同电话号码。

你可以将骑士放置在任何数字单元格上，然后你应该执行 n - 1 次移动来获得长度为 n 的号码。所有的跳跃应该是有效的骑士跳跃。

因为答案可能很大，所以输出答案模 109 + 7.

涉及知识点

动态规划

解决思路

很容易想到动态规划，因为如果n=3，我们从1开始，可以到6、8，接下来的问题就变为从6、8分别开始，n=2的问题。

i：还需要移动 i 步。
j：马在单元格 j 上。

MOD = 1_000_000_007
NEXT = (4, 6), (6, 8), (7, 9), (4, 8), (0, 3, 9), (), (0, 1, 7), (2, 6), (1, 3), (2, 4)

@cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
def dfs(i: int, j: int) -> int:
    if i == 0:
        return 1
    return sum(dfs(i - 1, k) for k in NEXT[j]) % MOD

class Solution:
    def knightDialer(self, n: int) -> int:
        if n == 1:
            return 10
        return (sum(dfs(n - 1, j) for j in range(10))) % MOD

声明

题目均来源于leetcode公开题库，部分方法解析来源于高赞题解，如有不妥请联系。