LeetCode-W117

Q1&Q2

100127. 给小朋友们分糖果

给你两个正整数 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

解法一

$O(n)$的思考方式

因为需要分给3个人，可以考虑先分一个人，然后计算剩下的糖果分给两个人的方案，考虑满足要求第一个人的糖果数量x,0 <= x <= min(limit, n),则剩下的两个人分的糖果数量k为max(0, n - limit) <= k <= n,若k <= limit则有k + 1种方案,若k > limit,则有(limit - (k - limit) + 1)种方案

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        ans = 0
        for i in range(max(0, n - limit), n + 1):
            if i > limit * 2:
                return ans
            if limit >= i:
                ans += i + 1
            else:
                ans += limit - (i - limit) + 1
        return ans

解法二

$O(1)$的思考方式

正难则反,计算全部的方案数再减去不符合的方案数，用隔板法计算n个糖果分给x个人有多少种方案的公式为C(n-1, x - 1),但本题要求可以分0个，可以假设确保每人至少一个，那么总糖果数就为n + 3个，这样就可以继续套公式了，本题的公式就为C(n + 2, 2)。利用容斥原理计算有多少个不符合(不符合一个 - 不符合两个 + 不符合三个)

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        def c(x: int) -> int:
            return 0 if x < 0 else x * (x - 1) // 2

        return c(n + 2) - 3 * c(n - limit + 1) + 3 * c(n - 2 * limit) - c(n - 3 * limit - 1)

Q3

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

给你一个整数 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

解法一

容斥原理。正难则反,计算出全部方案减去不符合的方案。利用容斥原理计算不符合的方案。

class Solution:
    def stringCount(self, n: int) -> int:

        mod = 10 ** 9 + 7

        s = pow(26, n, mod)

        """
        一个不符合类型
        """
        no_l = pow(25, n, mod)
        no_t = pow(25, n, mod)
        no_e_or_ee = pow(25, n, mod) + n * pow(25, n - 1, mod)

        """
        两个不符合
        """
        no_lt = pow(24, n, mod)
        no_le = pow(24, n, mod) + n * pow(24, n - 1, mod)
        no_te = pow(24, n, mod) + n * pow(24, n - 1, mod)

        """
        三个不符合
        """
        no_let = pow(23, n, mod) + n * pow(23, n - 1, mod)

        return (s - (no_l + no_t + no_e_or_ee) + (no_lt + no_le + no_te) - no_let) % mod

解法二

将题目意思转换下: n次选择的机会每次选择的包含26个字母，其中包含1个l,1个t,2个e的方案,可以使用状压DP来解决本问题，选择1个t和两个t的效果是一样的，因此可以进一步压缩状态。

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



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

Q4

100043. 购买物品的最大开销

给你一个下标从 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] 按照非递增顺序排序。

解法一

多路归并(归并排序)

贪心思想，从大的开始反着选，谁大就选谁，用堆模拟即可。

class Solution:
    def maxSpending(self, values: List[List[int]]) -> int:
        heap = []

        n, m = len(values), len(values[0])
        for i in range(n):
            heap.append((-values[i][0], i, 0))

        heapify(heap)
        ans = 0
        for i in range(n * m, 0, -1):
            poll = heappop(heap)
            v, x, y = poll[0], poll[1], poll[2]
            ans += -i * v
            if y < m - 1: heappush(heap, (-values[x][y + 1], x, y + 1))
        return ans