且听疯吟

leetcode biweekly contest 132

2024-06-10

leetcode biweekly contest 132

t4 算是一个经典题目了，其余的题目都比较常规的题目。

3174. 清除数字

给你一个字符串 s 。

你的任务是重复以下操作删除 所有 数字字符：

  • 删除 第一个数字字符 以及它左边 最近 的 非数字 字符。

请你返回删除所有数字字符以后剩下的字符串。

示例 1：

输入：s = “abc”

输出：“abc”

解释：

字符串中没有数字。

示例 2：

输入：s = “cb34”

输出：“”

解释：

一开始，我们对 s[2] 执行操作，s 变为 "c4" 。

然后对 s[1] 执行操作，s 变为 "" 。

提示：

  • 1 <= s.length <= 100
  • s 只包含小写英文字母和数字字符。
  • 输入保证所有数字都可以按以上操作被删除。

地址

https://leetcode.cn/contest/biweekly-contest-132/problems/clear-digits/

题意

直接枚举

思路

  1. 直接模拟遍历字符串即可。
  2. 复杂度分析：
  • 时间复杂度：$O(n )$, 其中 $n$ 表示字符串的长度。
  • 空间复杂度：$O(1)$。

代码

class Solution:
    def clearDigits(self, s: str) -> str:
        res = []
        for c in s:
            if ord(c) >= ord('0') and ord(c) <= ord('9'):
                res.pop()
            else:
                res.append(c)
        return "".join(res)

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

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

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

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

比赛进行方式如下：

  • 队列中最前面两名玩家进行一场比赛，技能等级 更高 的玩家胜出。
  • 比赛后，获胜者保持在队列的开头，而失败者排到队列的末尾。

这个比赛的赢家是 第一位连续 赢下 k 场比赛的玩家。

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

示例 1：

输入：skills = [4,2,6,3,9], k = 2

输出：2

解释：

一开始，队列里的玩家为 [0,1,2,3,4] 。比赛过程如下：

  • 玩家 0 和 1 进行一场比赛，玩家 0 的技能等级高于玩家 1 ，玩家 0 胜出，队列变为 [0,2,3,4,1] 。
  • 玩家 0 和 2 进行一场比赛，玩家 2 的技能等级高于玩家 0 ，玩家 2 胜出，队列变为 [2,3,4,1,0] 。
  • 玩家 2 和 3 进行一场比赛，玩家 2 的技能等级高于玩家 3 ，玩家 2 胜出，队列变为 [2,4,1,0,3] 。

玩家 2 连续赢了 k = 2 场比赛，所以赢家是玩家 2 。

示例 2：

输入：skills = [2,5,4], k = 3

输出：1

解释：

一开始，队列里的玩家为 [0,1,2] 。比赛过程如下：

  • 玩家 0 和 1 进行一场比赛，玩家 1 的技能等级高于玩家 0 ，玩家 1 胜出，队列变为 [1,2,0] 。
  • 玩家 1 和 2 进行一场比赛，玩家 1 的技能等级高于玩家 2 ，玩家 1 胜出，队列变为 [1,0,2] 。
  • 玩家 1 和 0 进行一场比赛，玩家 1 的技能等级高于玩家 0 ，玩家 1 胜出，队列变为 [1,2,0] 。

玩家 1 连续赢了 k = 3 场比赛，所以赢家是玩家 1 。

提示：

  • n == skills.length
  • 2 <= n <= 105
  • 1 <= k <= 109
  • 1 <= skills[i] <= 106
  • skills 中的整数互不相同。

地址

https://leetcode.cn/contest/biweekly-contest-132/problems/find-the-first-player-to-win-k-games-in-a-row/

题意

贪心

思路

  1. 我们可以观察到，一旦当前玩家中的最大值参与比赛后则后续一直都会是他嬴，所以对于 $k >= n -1$ 时，直接返回数组中最大值的索引即可。实际分析每个人可以嬴的场次即等于：

    • $i$ 是否大于左边的最大值；
    • $i$ 右边第一个 $i$ 的元素；

    当然实际也不需要这么麻烦，直接开双端队列模拟，直到遇到最大值就结束即可。

  2. 复杂度分析：

  • 时间复杂度：$O(n )$，其中 $n$ 表示给定数组的长度。
  • 空间复杂度：$O(n)$。

代码

class Solution:
    def findWinningPlayer(self, skills: List[int], k: int) -> int:
        mx_i = 0
        win = -1  # 对于 skills[0] 来说，需要连续 k+1 个回合都是最大值
        for i, x in enumerate(skills):
            if x > skills[mx_i]:  # 新的最大值
                mx_i = i
                win = 0
            win += 1  # 获胜回合 +1
            if win == k:
                break
        return mx_i

3176. 求出最长好子序列 I

给你一个整数数组 nums 和一个 非负 整数 k 。如果一个整数序列 seq 满足在范围下标范围 [0, seq.length - 2] 中存在 不超过 k 个下标 i 满足 seq[i] != seq[i + 1] ，那么我们称这个整数序列为 好 序列。

请你返回 nums 中 好 子序列 的最长长度

示例 1：

输入：nums = [1,2,1,1,3], k = 2

输出：4

解释：

最长好子序列为 [***1***,***2***,***1\***,***1***,3] 。

示例 2：

输入：nums = [1,2,3,4,5,1], k = 0

输出：2

解释：

最长好子序列为 [***1\***,2,3,4,5,***1\***] 。

提示：

  • 1 <= nums.length <= 500
  • 1 <= nums[i] <= 109
  • 0 <= k <= min(nums.length, 25)

地址

https://leetcode.cn/contest/biweekly-contest-132/problems/find-the-maximum-length-of-a-good-subsequence-i/

题意

动态规划

思路

  1. 典型的动态规划，设 $dp[i][t]$ 表示以 $i$ 为结尾，且相邻下表不相等的个数为 $t$ 个的最大长度，此时我们考虑索引 $j$，则可以得到如下递推：

    • 如果 $nums[i] = nums[j]$, 此时可以得到 $dp[i][t] = \max(dp[i][t], dp[j][t] + 1)$;
    • 如果 $nums[i] \neq nums[j]$, 此时可以得到 $dp[i][t] = \max(dp[i][t], dp[j][t-1] + 1)$​;

    按照上述递推公式进行模拟即可得到，返回 $dp[i][t]$ 的最大值即可。

  2. 复杂度：

  • 时间复杂度：$O(k \times n^2)$，其中 $n$ 表示给定数组的长度，$k$ 为给定的整数；
  • 空间复杂度：$O(k \times n)$，其中 $n$ 表示给定数组的长度，$k$ 为给定的整数；

代码

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        res = 1
        dp = [[0] * (k + 1) for _ in range(n)]
        for i in range(n):
            dp[i][0] = 1
        for i in range(1, n):
            for j in range(i - 1, -1, -1):
                for t in range(0, k + 1):
                    if nums[i] == nums[j]:
                        dp[i][t] = max(dp[i][t], dp[j][t] + 1)
                    elif t > 0 and nums[i] != nums[j]:
                        dp[i][t] = max(dp[i][t], dp[j][t - 1] + 1)
                    res = max(res, dp[i][t])
        return res

3177. 求出最长好子序列 II

给你一个整数数组 nums 和一个 非负 整数 k 。如果一个整数序列 seq 满足在范围下标范围 [0, seq.length - 2] 中存在 不超过 k 个下标 i 满足 seq[i] != seq[i + 1] ，那么我们称这个整数序列为 好 序列。

请你返回 nums 中 好 子序列 的最长长度

示例 1：

输入：nums = [1,2,1,1,3], k = 2

输出：4

解释：

最长好子序列为 [***1***,***2***,***1\***,***1***,3] 。

示例 2：

输入：nums = [1,2,3,4,5,1], k = 0

输出：2

解释：

最长好子序列为 [***1\***,2,3,4,5,***1\***] 。

提示：

  • 1 <= nums.length <= 5 * 103
  • 1 <= nums[i] <= 109
  • 0 <= k <= min(50, nums.length)

地址

https://leetcode.cn/contest/biweekly-contest-132/problems/find-the-maximum-length-of-a-good-subsequence-ii/

题意

动态规划

思路

  1. 根据上诉的分析可以直到，设 $dp[i][t]$ 表示以 $i$ 为结尾，且相邻下标不相等的个数为 $t$ 个的最大长度，此时我们考虑索引 $j$，则可以得到如下递推：

    • 如果 $nums[i] = nums[j]$, 此时可以得到 $dp[i][t] = \max(dp[i][t], dp[j][t] + 1)$;
    • 如果 $nums[i] \neq nums[j]$, 此时可以得到 $dp[i][t] = \max(dp[i][t], dp[j][t-1] + 1)$​;

    按照上述递推公式进行模拟即可得到，返回 $dp[i][t]$​ 的最大值即可。

  2. 我们仔细分析一下，我们只需要找到相邻下标不相等的个数为 $t$ 个且结尾数字不同的两个最大长度即可，此时包含不相等相邻数组为 $t$ 的最大的两个长度分别为 $l_1,l_2$ ，结尾元素分别为 $s_1,s_2$，设以 $nums[i]$ 为结尾且相邻元素数目不同的为 $t$ 的最大长度为 $dp[nums[i]][t]$，此时假设遍历到元素 $nums[i]$ 时，此时可以得到：

    • 首先我们可以得到 $dp[nums[i]][t] = dp[nums[i]][t] + 1$, 此时 $nums[i]$ 可以直接连接在相同元素的后面；

    • 如果 $nums[i] \neq s_1, nums[i] \neq s_2$，此时可以得到此时 $nums[i]$ 可以连接 $s1,s2$ 的后面，此时 $dp[nums[i]][t] = \max(dp[s_1][t-1] + 1,dp[s_2][t-1] + 1)$, 同时根据比较大小来更新 $s_1,s_2$ 即可；

    • 如果 $nums[i] = s_1, nums[i] \neq s_2$，此时可以得到此时 $nums[i]$ 可以连接 $s2$ 的后面，此时 $dp[nums[i]][t] = \max(dp[s_2][t-1] + 1)$，此时不需要更新 $s_1,s_2$；

    • 如果 $nums[i] \neq s_1, nums[i] = s_2$，此时可以得到此时 $nums[i]$ 可以连接 $s1$ 的后面，此时 $dp[nums[i]][t] = \max(dp[s_1][t-1] + 1)$，此时不需要更新 $s_1,s_2$​；

    根据以上分析，写出动态规划即可。

  3. 复杂度分析：

  • 时间复杂度：$O(n \times k)$，其中 $n$ 表示给定数组的长度，$k$ 表示给定的元素；
  • 空间复杂度：$O(n \times k)$，其中 $n$ 表示给定数组的长度，$k$ 表示给定的元素；

代码

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = {}
        cnt = [[0] * 2 for _ in range(k + 1)]
        dp[0] = [0] * (k + 1)
        for i, x in enumerate(nums):
            if x not in dp:
                dp[x] = [0] * (k + 1)
            # add all equal
            for t in range(0, k + 1):
                dp[x][t] += 1
            # check not equal
            for t in range(1, k + 1):
                a, b = cnt[t - 1][0], cnt[t - 1][1]
                if a != x:
                    dp[x][t] = max(dp[x][t], dp[a][t - 1] + 1)
                if b != x:
                    dp[x][t] = max(dp[x][t], dp[b][t - 1] + 1)
   
            # update max
            for t in range(0, k + 1):
                a, b = cnt[t][0], cnt[t][1]
                if x == a or x == b:
                    if dp[a][t] < dp[b][t]:
                        cnt[t][0], cnt[t][1] = cnt[t][1], cnt[t][0]
                else:
                    if dp[x][t] > dp[a][t]:
                        cnt[t][0], cnt[t][1] = cnt[t][1], cnt[t][0]
                        cnt[t][0] = x
                    elif dp[x][t] > dp[b][t]:
                        cnt[t][1] = x
         
        return dp[cnt[k][0]][k]

欢迎关注和打赏，感谢支持！

Tags: 题解 力扣周赛赛
← leetcode weekly contest 397 leetcode weekly contest 401 →

扫描二维码，分享此文章