且听疯吟

leetcode weekly contest 411

2024-08-20

leetcode weekly contest 411

最近周赛难度确实加强了，不过还是好题目比较多，值得仔细思考。

3258. 统计满足 K 约束的子字符串数量 I

给你一个 二进制 字符串 s 和一个整数 k。

如果一个 二进制字符串 满足以下任一条件，则认为该字符串满足 k 约束：

  • 字符串中 0 的数量最多为 k。
  • 字符串中 1 的数量最多为 k。

返回一个整数，表示 s 的所有满足 k 约束 的子字符串的数量。

示例 1：

输入：s = “10101”, k = 1

输出：12

解释：

s 的所有子字符串中，除了 "1010"、"10101" 和 "0101" 外，其余子字符串都满足 k 约束。

示例 2：

输入：s = “1010101”, k = 2

输出：25

解释：

s 的所有子字符串中，除了长度大于 5 的子字符串外，其余子字符串都满足 k 约束。

示例 3：

输入：s = “11111”, k = 1

输出：15

解释：

s 的所有子字符串都满足 k 约束。

提示：

  • 1 <= s.length <= 50
  • 1 <= k <= s.length
  • s[i] 是 '0' 或 '1'。

地址

https://leetcode.cn/contest/weekly-contest-411/problems/count-substrings-that-satisfy-k-constraint-i/

题意

模拟

思路

  1. 直接模拟即可，由于题目要求子字符串中 $0,1$ 的数量至少有一个小于等于 $k$ 即满足 $k$ 约束，此时我们找到以 $i$ 为结尾的最长满足 $k$ 约束的字符串的长度 $m$ , 则此时以 $m$ 为结尾的$k$ 约束字符串数量即为 $m$ 个。
  2. 复杂度分析：
  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(1)$。

代码

class Solution:
    def countKConstraintSubstrings(self, s: str, k: int) -> int:
        cnt0, cnt1 = [], []
        res = 0
        for i, ch in enumerate(s):
            if ch == '0':
                cnt0.append(i)
            else:
                cnt1.append(i)
            pre0 = -1 if len(cnt0) <= k else cnt0[len(cnt0) - k - 1]
            pre1 = -1 if len(cnt1) <= k else cnt1[len(cnt1) - k - 1]
            res += i - min(pre0, pre1)
        return res

3259. 超级饮料的最大强化能量

来自未来的体育科学家给你两个整数数组 energyDrinkA 和 energyDrinkB，数组长度都等于 n。这两个数组分别代表 A、B 两种不同能量饮料每小时所能提供的强化能量。

你需要每小时饮用一种能量饮料来 最大化 你的总强化能量。然而，如果从一种能量饮料切换到另一种，你需要等待一小时来梳理身体的能量体系（在那个小时里你将不会获得任何强化能量）。

返回在接下来的 n 小时内你能获得的 最大 总强化能量。

注意 你可以选择从饮用任意一种能量饮料开始。

示例 1：

输入：energyDrinkA = [1,3,1], energyDrinkB = [3,1,1]

输出：5

解释：

要想获得 5 点强化能量，需要选择只饮用能量饮料 A（或者只饮用 B）。

示例 2：

输入：energyDrinkA = [4,1,1], energyDrinkB = [1,1,3]

输出：7

解释：

  • 第一个小时饮用能量饮料 A。
  • 切换到能量饮料 B ，在第二个小时无法获得强化能量。
  • 第三个小时饮用能量饮料 B ，并获得强化能量。

提示：

  • n == energyDrinkA.length == energyDrinkB.length
  • 3 <= n <= 105
  • 1 <= energyDrinkA[i], energyDrinkB[i] <= 105

地址

https://leetcode.cn/contest/weekly-contest-411/problems/maximum-energy-boost-from-two-drinks/

题意

动态规划

思路

  1. 仔细思考一些，题目本身就是简单的动态规划，设 $dp[i][0]$ 表示前 $i$ 个小时且最后饮用的为 $A$ 饮料的最大值，

    设 $dp[i][1]$ 表示前 $i$ 个小时且最后饮用的为 $B$ 饮料的最大值，此时我们可以得到结论如下：

    • 要么第 $i-1$ 个小时与第 $i$ 个小时喝的为同一种饮料，要么不同；

    • 此时如果第 $i$ 个小时喝的为 $A$ 饮料，则此时要么第 $i-1$ 个小时饮用的也为同样的 $A$ 饮料，要么第 $i-2$ 个小时饮用的为 $B$ 饮料，第 $i-1$ 个小时等待，此时可以得到递推公式如下：
      $$
      dp[i][0] = \max(dp[i-1][0], dp[i- 2][1]) + energyDrinkA[i]
      $$

    • 此时如果第 $i$ 个小时喝的为 $B$ 饮料，则此时要么第 $i-1$ 个小时饮用的也为同样的 $B$ 饮料，要么第 $i-2$ 个小时饮用的为 $A$ 饮料，第 $i-1$ 个小时等待，此时可以得到递推公式如下：
      $$
      dp[i][1] = \max(dp[i-1][1], dp[i- 2][0]) + energyDrinkB[i]
      $$

  2. 遵上我们可以知道最后一个小时一定会喝某种饮料，不存在最后一个小时等待的做法，因为如果最后一个小时做切换的话还不如利用这个一个小时来饮用同样的饮料即可。

  3. 复杂度分析：

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

代码

class Solution:
    def maxEnergyBoost(self, energyDrinkA: List[int], energyDrinkB: List[int]) -> int:
        n = len(energyDrinkA)
        dp = [[0, 0] for _ in range(n + 1)]
        for i, (x, y) in enumerate(zip(energyDrinkA, energyDrinkB)):
            dp[i + 1][0] = max(dp[i][0], dp[i- 1][1] if i >= 1 else 0) + x
            dp[i + 1][1] = max(dp[i][1], dp[i- 1][0] if i >= 1 else 0) + y
        return max(dp[n])

3260. 找出最大的 N 位 K 回文数

给你两个 正整数 n 和 k。

如果整数 x 满足以下全部条件，则该整数是一个 k 回文数：

  • x 是一个 回文数。
  • x 可以被 k 整除。

以字符串形式返回 最大的 n 位 k 回文数。

注意，该整数 不 含前导零。

示例 1：

输入： n = 3, k = 5

输出： “595”

解释：

595 是最大的 3 位 k 回文数。

示例 2：

输入： n = 1, k = 4

输出： “8”

解释：

1 位 k 回文数只有 4 和 8。

示例 3：

输入： n = 5, k = 6

输出： “89898”

提示：

  • 1 <= n <= 105
  • 1 <= k <= 9

3260. 找出最大的 N 位 K 回文数

给你两个 正整数 n 和 k。

如果整数 x 满足以下全部条件，则该整数是一个 k 回文数：

  • x 是一个 回文数。
  • x 可以被 k 整除。

以字符串形式返回 最大的 n 位 k 回文数。

注意，该整数 不 含前导零。

示例 1：

输入： n = 3, k = 5

输出： “595”

解释：

595 是最大的 3 位 k 回文数。

示例 2：

输入： n = 1, k = 4

输出： “8”

解释：

1 位 k 回文数只有 4 和 8。

示例 3：

输入： n = 5, k = 6

输出： “89898”

提示：

  • 1 <= n <= 105
  • 1 <= k <= 9

代码


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

Tags: 题解 力扣周赛赛
← leetcode biweekly contest 137 leetcode weekly contest 412 →

扫描二维码，分享此文章