且听疯吟

leetcode biweekly contes 117

2023-11-19

leetcode biweekly contes 117

双周赛的题目质量太差了，全是概率题目， T4 题目太简单了。

100125. 给小朋友们分糖果 I

给你两个正整数 n 和 limit 。

请你将 n 颗糖果分给 3 位小朋友，确保没有任何小朋友得到超过 limit 颗糖果，请你返回满足此条件下的 总方案数 。

示例 1：

输入：n = 5, limit = 2
输出：3
解释：总共有 3 种方法分配 5 颗糖果，且每位小朋友的糖果数不超过 2 ：(1, 2, 2) ，(2, 1, 2) 和 (2, 2, 1) 。

示例 2：

输入：n = 3, limit = 3
输出：10
解释：总共有 10 种方法分配 3 颗糖果，且每位小朋友的糖果数不超过 3 ：(0, 0, 3) ，(0, 1, 2) ，(0, 2, 1) ，(0, 3, 0) ，(1, 0, 2) ，(1, 1, 1) ，(1, 2, 0) ，(2, 0, 1) ，(2, 1, 0) 和 (3, 0, 0) 。

提示：

  • 1 <= n <= 50
  • 1 <= limit <= 50

地址

https://leetcode.cn/contest/biweekly-contest-117/problems/distribute-candies-among-children-i/

题意

枚举

思路

  1. 题目看起来很难，实际比较简单，我们可以先给前两个小朋友分配 $x$ 个，最后一个小朋友可以分配的数量则为 $n-x$ 个，我们依次枚举前两个小朋友分配的数组 $x$，即可求出所有的分配方案。现在有 $x$ 个糖果分配给 $2$ 个小朋友，则实际分析如下：
    • $x < 2limit$，否则无论如何分配都无法满足要求；
    • 如果第一个小朋友分配 $i$ 个糖果，则一定满足 $x - i < limit$；
    • 如果 $x \le limit$，则此时一定有 $x+1$ 种分配方法，因此此时 $i \in[0,x]$；
    • 如果 $limit < x \le 2*limit$，则此时一定有 $2 * limit - i + 1$ 种分配方法，因此此时 $i \in[x - limit,limit]$；
    • 如果前两个小朋友分配的总的糖果数目确定，则第三个小朋友只能分配 $n-x$ 个糖果，此时需要满足 $n - x \le limit$ 即可；
  2. 复杂度分析：
  • 时间复杂度：$O(n)$，其中 $n$ 表示给定的 $n$ 的大小。
  • 空间复杂度：$O(1)$。

代码

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        if 3 * limit < n:
            return 0
        cnt = [0] * (n + 1)
        for i in range(min(n, 2 * limit) + 1):
            if i > limit:
                cnt[i] = 2 * limit - i + 1
            else:
                cnt[i] = i + 1
        return sum(cnt[i] for i in range(n + 1) if n - i <= limit)

2929. 给小朋友们分糖果 II

给你两个正整数 n 和 limit 。

请你将 n 颗糖果分给 3 位小朋友，确保没有任何小朋友得到超过 limit 颗糖果，请你返回满足此条件下的 总方案数 。

示例 1：

输入：n = 5, limit = 2
输出：3
解释：总共有 3 种方法分配 5 颗糖果，且每位小朋友的糖果数不超过 2 ：(1, 2, 2) ，(2, 1, 2) 和 (2, 2, 1) 。

示例 2：

输入：n = 3, limit = 3
输出：10
解释：总共有 10 种方法分配 3 颗糖果，且每位小朋友的糖果数不超过 3 ：(0, 0, 3) ，(0, 1, 2) ，(0, 2, 1) ，(0, 3, 0) ，(1, 0, 2) ，(1, 1, 1) ，(1, 2, 0) ，(2, 0, 1) ，(2, 1, 0) 和 (3, 0, 0) 。

提示：

  • 1 <= n <= 106
  • 1 <= limit <= 106

地址

https://leetcode.cn/contest/weekly-contest-370/problems/find-champion-ii/

题意

枚举

思路

  1. 题目看起来很难，实际比较简单，我们可以先给前两个小朋友分配 $x$ 个，最后一个小朋友可以分配的数量则为 $n-x$ 个，我们依次枚举前两个小朋友分配的数组 $x$，即可求出所有的分配方案。现在有 $x$ 个糖果分配给 $2$ 个小朋友，则实际分析如下：
    • $x < 2limit$，否则无论如何分配都无法满足要求；
    • 如果第一个小朋友分配 $i$ 个糖果，则一定满足 $x - i < limit$；
    • 如果 $x \le limit$，则此时一定有 $x+1$ 种分配方法，因此此时 $i \in[0,x]$；
    • 如果 $limit < x \le 2*limit$，则此时一定有 $2 * limit - i + 1$ 种分配方法，因此此时 $i \in[x - limit,limit]$；
    • 如果前两个小朋友分配的总的糖果数目确定，则第三个小朋友只能分配 $n-x$ 个糖果，此时需要满足 $n - x \le limit$ 即可；
  2. 复杂度分析：
  • 时间复杂度：$O(n)$，其中 $n$ 表示给定的 $n$ 的大小。
  • 空间复杂度：$O(1)$。

代码

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        if 3 * limit < n:
            return 0
        cnt = [0] * (n + 1)
        for i in range(min(n, 2 * limit) + 1):
            if i > limit:
                cnt[i] = 2 * limit - i + 1
            else:
                cnt[i] = i + 1
        return sum(cnt[i] for i in range(n + 1) if n - i <= limit)

2930. 重新排列后包含指定子字符串的字符串数目

给你一个整数 n 。

如果一个字符串 s 只包含小写英文字母，且 将 s 的字符重新排列后，新字符串包含 子字符串 "leet" ，那么我们称字符串 s 是一个 好 字符串。

比方说：

  • 字符串 "lteer" 是好字符串，因为重新排列后可以得到 "leetr" 。
  • "letl" 不是好字符串，因为无法重新排列并得到子字符串 "leet" 。

请你返回长度为 n 的好字符串 总 数目。

由于答案可能很大，将答案对 109 + 7 取余 后返回。

子字符串 是一个字符串中一段连续的字符序列。

示例 1：

输入：n = 4
输出：12
解释：总共有 12 个字符串重新排列后包含子字符串 "leet" ："eelt" ，"eetl" ，"elet" ，"elte" ，"etel" ，"etle" ，"leet" ，"lete" ，"ltee" ，"teel" ，"tele" 和 "tlee" 。

示例 2：

输入：n = 10
输出：83943898
解释：长度为 10 的字符串重新排列后包含子字符串 "leet" 的方案数为 526083947580 。所以答案为 526083947580 % (109 + 7) = 83943898 。

提示：

  • 1 <= n <= 105

地址

https://leetcode.cn/contest/biweekly-contest-117/problems/number-of-strings-which-can-be-rearranged-to-contain-substring/

题意

数论或者动态规划，容斥定理

思路

  1. 题目是个好题目，最近的第三题难度越来越高了，可以用动态规划，但时几个状态转移还是稍显复杂，我们可以使用容斥定理：

  • 不包含 $\text{l}$ 的字符串数目为 $25^n$；

  • 不包含 $\text{t}$ 的数目为 $25^n$；

  • 不包含 $\text{ee}$ 的数目为 $25^n + n * 25^{n-1} = (25 + n)\times 25^{n-1}$；
    再计算三者存在重合的地方：

  • 不包含 $\text{l,t}$ 的字符串数目为 $24^n$;

  • 不包含 $\text{l,ee}$ 的字符串数目为 $24^n + n\times24^{n-1}$；

  • 不包含 $\text{t,ee}$ 的字符串数目为 $24^n + n\times24^{n-1}$；

  • 不包含 $\text{l, t,ee}$ 的字符串数目为 $23^n + n\times23^{n-1}$；
    根据容斥定理可以知道不包含 $\text{leet}$ 的字符串数目为：
    $$
    T = 25^n + $25^n + (25^n + n * 25^{n-1}) - 24^{n} - (24^n + n\times24^{n-1}) - (24^n + n\times24^{n-1}) + 23^n + n\times23^{n-1} \
    = 3\times 25^n + n\times 25^{n-1} - 3 \times 24^{n} - 2n\times 24^{n-1} + 23^n + n\times 23^{n-1}
    $$
    此时可以知道字符串的总数目为 $26^n$，则含有 $leet$ 的字符串的数目为 $26^n - T$;

  • 时间复杂度：$O(\log n)$，其中$n$ 表示整数；

  • 空间复杂度：$O(1)$；

代码

class Solution:
    def stringCount(self, n: int) -> int:
        MOD = 10**9 + 7
        return (MOD + pow(26, n, MOD) - pow(25, n - 1, MOD) * (75 + n) + pow(24, n - 1, MOD) * (72 + 2 * n) - pow(23, n - 1, MOD) * (n + 23)) % MOD

@cache
def dfs(i: int, L: int, t: int, e: int) -> int:
    if i == 0:
        return 1 if L == t == e == 0 else 0
    res = dfs(i - 1, 0, t, e)
    res += dfs(i - 1, L, 0, e)
    res += dfs(i - 1, L, t, max(e - 1, 0))
    res += dfs(i - 1, L, t, e) * 23
    return res % (10 ** 9 + 7)

class Solution:
    def stringCount(self, n: int) -> int:
        return dfs(n, 1, 1, 2)

2931. 购买物品的最大开销

给你一个下标从 0 开始大小为 m * n 的整数矩阵 values ，表示 m 个不同商店里 m * n 件不同的物品。每个商店有 n 件物品，第 i 个商店的第 j 件物品的价值为 values[i][j] 。除此以外，第 i 个商店的物品已经按照价值非递增排好序了，也就是说对于所有 0 <= j < n - 1 都有 values[i][j] >= values[i][j + 1] 。

每一天，你可以在一个商店里购买一件物品。具体来说，在第 d 天，你可以：

  • 选择商店 i 。
  • 购买数组中最右边的物品 j ，开销为 values[i][j] * d 。换句话说，选择该商店中还没购买过的物品中最大的下标 j ，并且花费 values[i][j] * d 去购买。

注意，所有物品都视为不同的物品。比方说如果你已经从商店 1 购买了物品 0 ，你还可以在别的商店里购买其他商店的物品 0 。

请你返回购买所有 m * n 件物品需要的 最大开销 。

示例 1：

输入：values = [[8,5,2],[6,4,1],[9,7,3]]
输出：285
解释：第一天，从商店 1 购买物品 2 ，开销为 values[1][2] * 1 = 1 。
第二天，从商店 0 购买物品 2 ，开销为 values[0][2] * 2 = 4 。
第三天，从商店 2 购买物品 2 ，开销为 values[2][2] * 3 = 9 。
第四天，从商店 1 购买物品 1 ，开销为 values[1][1] * 4 = 16 。
第五天，从商店 0 购买物品 1 ，开销为 values[0][1] * 5 = 25 。
第六天，从商店 1 购买物品 0 ，开销为 values[1][0] * 6 = 36 。
第七天，从商店 2 购买物品 1 ，开销为 values[2][1] * 7 = 49 。
第八天，从商店 0 购买物品 0 ，开销为 values[0][0] * 8 = 64 。
第九天，从商店 2 购买物品 0 ，开销为 values[2][0] * 9 = 81 。
所以总开销为 285 。
285 是购买所有 m * n 件物品的最大总开销。

示例 2：

输入：values = [[10,8,6,4,2],[9,7,5,3,2]]
输出：386
解释：第一天，从商店 0 购买物品 4 ，开销为 values[0][4] * 1 = 2 。
第二天，从商店 1 购买物品 4 ，开销为 values[1][4] * 2 = 4 。
第三天，从商店 1 购买物品 3 ，开销为 values[1][3] * 3 = 9 。
第四天，从商店 0 购买物品 3 ，开销为 values[0][3] * 4 = 16 。
第五天，从商店 1 购买物品 2 ，开销为 values[1][2] * 5 = 25 。
第六天，从商店 0 购买物品 2 ，开销为 values[0][2] * 6 = 36 。
第七天，从商店 1 购买物品 1 ，开销为 values[1][1] * 7 = 49 。
第八天，从商店 0 购买物品 1 ，开销为 values[0][1] * 8 = 64 。
第九天，从商店 1 购买物品 0 ，开销为 values[1][0] * 9 = 81 。
第十天，从商店 0 购买物品 0 ，开销为 values[0][0] * 10 = 100 。
所以总开销为 386 。
386 是购买所有 m * n 件物品的最大总开销。

提示：

  • 1 <= m == values.length <= 10
  • 1 <= n == values[i].length <= 104
  • 1 <= values[i][j] <= 106
  • values[i] 按照非递增顺序排序。

https://leetcode.cn/contest/biweekly-contest-117/problems/maximum-spending-after-buying-items/

题意

排序或者优先队列，贪心算法

思路

  1. 典型的贪心算法，首先对于越小的值我们应该尽可能的赋给其最小的权值，对于越大的值应该赋给其越大的权值。由于矩阵中的每一行均已经有序，我们可以直接按照从小到大的顺序从矩阵中取出所有的元素，因此我们直接将矩阵中所有的元素排序，然后求和即可。

  2. 复杂度分析：

  • 时间复杂度：$O(nm \log nm)$，其中 $n$ 表示矩阵的行数，$m$ 表示矩阵的列数;
  • 空间复杂度：$O(\log mn)$，其中 $n$ 表示矩阵的行数，$m$ 表示矩阵的列数;

代码

class Solution:
    def maxSpending(self, values: List[List[int]]) -> int:
        nums = []
        for i in range(len(values)):
            for j in range(len(values[0])):
                nums.append(values[i][j])
        nums.sort()
        return sum((i + 1) * nums[i] for i in range(len(nums)))

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

Tags: 题解 力扣周赛赛
← leetcode weekly contes 372 leetcode contest 375 →

扫描二维码，分享此文章