Biweekly Contest 117

100127. Distribute Candies Among Children II

给你两个正整数 n 和 limit 。

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

测试样例：

输入：n = 5, limit = 2

输出：3

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

解答：第一题和第二题题目差不多，只是范围不一样。我就用第二题的解答了。这题就是锁住第一个人获取的糖果数，然后看后面两人有多少种可能。

class Solution {
    public long distributeCandies(int n, int limit) {
        int res = 0;
        for (int i = 0; i <= limit; ++i) {
            res += twoRemain(n - i, limit);
        }
        return res;
    }

    private int twoRemain(int remain, int limit) {
        if (remain < 0 || remain > 2 * limit) {
            return 0;
        } else if (remain <= limit) {
            return remain + 1;
        } else {
            return 2 * limit - remain + 1;
        }
    }
}

100126. Number of Strings Which Can Be Rearranged to Contain Substring

给你一个整数 n 。

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

比方说：

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

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

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

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

测试样例：

输入：n = 4

输出：12

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

解答：着实感觉这题是最难的。我只想到用动态规划。动态规划存在16个状态（注意有几个状态是不valid），分别是不存在lte，存在l，存在t，存在4，存在lt。。。然后转移计算各种可能接下来出现的可能。

class Solution {
    private static int mod = 1_000_000_007;
    private static int[] marked = {1, 2, 12};

    public int stringCount(int n) {
        if (n < 4) {
            return 0;
        }
        long[] dp = new long[16];
        dp[0] = 1;
        for (int i = 1; i <= n; ++i) {
            long[] nextDp = new long[16];
            nextDp[0] = mul(dp[0], 23);
            for (int j = 1; j < 16; ++j) {
                if (isValid(j)) {
                    nextDp[j] = mul(dp[j], 26 - mulNum(j));
                    if ((j & 1) != 0) {
                        nextDp[j] = add(nextDp[j], dp[j - 1]);
                    }
                    if ((j & 2) != 0) {
                        nextDp[j] = add(nextDp[j], dp[j - 2]);
                    }
                    if ((j & 8) != 0) {
                        nextDp[j] = add(nextDp[j], dp[j - 8]);
                    } else if ((j & 4) != 0) {
                        nextDp[j] = add(nextDp[j], dp[j - 4]);
                    }
                }
            }
            dp = nextDp;
        }
        return (int) dp[(1 << 4) - 1];
    }

    private boolean isValid(int key) {
        if ((key & 8) != 0) {
            return (key & 4) != 0;
        }
        return true;
    }

    private int mulNum(int key) {
        int res = 3;
        for (int n : marked) {
            if ((n & key) >= n) {
                --res;
            }
        }
        return res;
    }

    private long mul(long x, long y) {
        return (x * y) % mod;
    }

    private long add(long x, long y) {
        return (x + y) % mod;
    }

    private long minus(long x, long y) {
        return (x - y + mod) % mod;
    }
}

100043. Maximum Spending After Buying Items

给你一个下标从 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 件物品需要的 最大开销 。

测试样例

输入：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 件物品的最大总开销。

解答：这道题没啥难度，就是贪婪。获取当前最小值所在的队列，用户获取队列最小值，然后队列当前游标向前移动。

class Solution {
    public long maxSpending(int[][] values) {
        long res = 0, mul = 1;
        int len = values.length;
        int[] mem = new int[len];
        for (int i = 0; i < mem.length; ++i) {
            mem[i] = values[i].length - 1;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> (values[a][mem[a]] - values[b][mem[b]]));
        for (int i = 0; i < len; ++i) {
            if (mem[i] >= 0) {
                queue.add(i);
            }
        }
        while (!queue.isEmpty()) {
            int tmp = queue.poll();
            res += values[tmp][mem[tmp]] * mul;
            ++mul;
            mem[tmp] -= 1;
            if (mem[tmp] >= 0) {
                queue.add(tmp);
            }
        }
        return res;
    }
}