leetcode weekly contest 401

t4 算是一个好题目，解法不常见，花了大概10分钟左右, AC 了前三题。

3178. 找出 K 秒后拿着球的孩子

给你两个 正整数 n 和 k。有 n 个编号从 0 到 n - 1 的孩子按顺序从左到右站成一队。

最初，编号为 0 的孩子拿着一个球，并且向右传球。每过一秒，拿着球的孩子就会将球传给他旁边的孩子。一旦球到达队列的 任一端 ，即编号为 0 的孩子或编号为 n - 1 的孩子处，传球方向就会 反转 。

返回 k 秒后接到球的孩子的编号。

示例 1：

输入：n = 3, k = 5

输出：1

解释：

示例 2：

输入：n = 5, k = 6

输出：2

解释：

示例 3：

输入：n = 4, k = 2

输出：2

解释：

提示：

• 2 <= n <= 50
• 1 <= k <= 50

地址

https://leetcode.cn/contest/weekly-contest-401/problems/find-the-child-who-has-the-ball-after-k-seconds/

题意

直接枚举

思路

1. 直接模拟即可，当然也可以用数学方法，每遍历一遍需要的时间为 $n - 1$，此时直接数学计算即可。
2. 复杂度分析：

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

代码

class Solution {
public:
    int numberOfChild(int n, int k) {
        int a = k / (n - 1);
        int b = k % (n - 1);
        if (a & 1) {
            return n - 1 - b;
        } else {
            return b;
        }
    }
};

3179. K 秒后第 N 个元素的值

给你两个整数 n 和 k。

最初，你有一个长度为 n 的整数数组 a，对所有 0 <= i <= n - 1，都有 a[i] = 1 。每过一秒，你会同时更新每个元素为其前面所有元素的和加上该元素本身。例如，一秒后，a[0] 保持不变，a[1] 变为 a[0] + a[1]，a[2] 变为 a[0] + a[1] + a[2]，以此类推。

返回 k 秒后 a[n - 1] 的值。

由于答案可能非常大，返回其对 109 + 7 取余 后的结果。

示例 1：

输入：n = 4, k = 5

输出：56

解释：

示例 2：

输入：n = 5, k = 3

输出：35

解释：

提示：

• 1 <= n, k <= 1000

地址

https://leetcode.cn/contest/weekly-contest-401/problems/maximum-total-reward-using-operations-i/

题意

前缀和，模拟

思路

1. 根据题意直接模拟即可，本质即为前 $k$ 次前缀和即可，非常简单。
2. 复杂度分析：

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

代码

class Solution:
    def valueAfterKSeconds(self, n: int, k: int) -> int:
        psum = [1] * n
        mod = 1e9 + 7
        for i in range(0, k):
            for j in range(1, n):
                psum[j] = (psum[j] + psum[j - 1]) % mod
        return int(psum[n - 1])

3180. 执行操作可获得的最大总奖励 I

给你一个整数数组 rewardValues，长度为 n，代表奖励的值。

最初，你的总奖励 x 为 0，所有下标都是 未标记 的。你可以执行以下操作 任意次 ：

• 从区间 [0, n - 1] 中选择一个 未标记 的下标 i。
• 如果 rewardValues[i] 大于 你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即 x = x + rewardValues[i]），并 标记 下标 i。

以整数形式返回执行最优操作能够获得的 最大 总奖励。

示例 1：

输入：rewardValues = [1,1,3,3]

输出：4

解释：

依次标记下标 0 和 2，总奖励为 4，这是可获得的最大值。

示例 2：

输入：rewardValues = [1,6,4,3,2]

输出：11

解释：

依次标记下标 0、2 和 1。总奖励为 11，这是可获得的最大值。

提示：

• 1 <= rewardValues.length <= 2000
• 1 <= rewardValues[i] <= 2000

地址

https://leetcode.cn/contest/weekly-contest-401/problems/maximum-total-reward-using-operations-i/

题意

动态规划, 背包

思路

1. 典型的动态规划，设 $dp[j]$ 表示当前是否可以取得最大值 $j$，此时遍历 $nums[i]$ 时，如果 $j \in [0,nums[i])$ 且满足 $dp[j] = 1$ ，此时一定可以取到 $dp[nums[i] + j]$，非常模板化的动态规划，最后返回可以取到的最大值即可。
2. 复杂度：

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

代码

class Solution:
    def maxTotalReward(self, rewardValues: List[int]) -> int:
        n = len(rewardValues)
        mx = max(rewardValues)
        dp = [0] * (2 * mx + 1)
        dp[0] = 1
        rewardValues.sort()
        for i, x in enumerate(rewardValues):
            for j in range(x):
                if (dp[j] > 0):
                    dp[j + x] = 1
        for i in range(2 * mx, -1, -1):
            if dp[i] > 0:
                return i
        return 0

3181. 执行操作可获得的最大总奖励 II

给你一个整数数组 rewardValues，长度为 n，代表奖励的值。

最初，你的总奖励 x 为 0，所有下标都是 未标记 的。你可以执行以下操作 任意次 ：

• 从区间 [0, n - 1] 中选择一个 未标记 的下标 i。
• 如果 rewardValues[i] 大于 你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即 x = x + rewardValues[i]），并 标记 下标 i。

以整数形式返回执行最优操作能够获得的 最大 总奖励。

示例 1：

输入：rewardValues = [1,1,3,3]

输出：4

解释：

依次标记下标 0 和 2，总奖励为 4，这是可获得的最大值。

示例 2：

输入：rewardValues = [1,6,4,3,2]

输出：11

解释：

依次标记下标 0、2 和 1。总奖励为 11，这是可获得的最大值。

提示：

• 1 <= rewardValues.length <= 5 * 104
• 1 <= rewardValues[i] <= 5 * 104

地址

https://leetcode.cn/contest/weekly-contest-401/problems/maximum-total-reward-using-operations-ii/

题意

动态规划，数位

思路

1. 同样的解法，然后用 bitset 优化，不过题目缺少太没有意思了，直到这个优化的话，题目就非常简单了。当然确实也是第一次在力扣碰到 bitset 优化的题目。如果可以用数据结构的话，题目本身就比较简单了。
2. 复杂度分析：

• 时间复杂度：$O(\dfrac {n \times U}{W} )$，其中 $n$ 表示给定数组的长度，$U$ 为给定的整数的最大元素；
• 空间复杂度：$O(U)$，其中 $n$ 表示给定数组的长度，$U$ 为给定的整数的最大元素；

代码

class Solution {
public:
    int maxTotalReward(vector<int>& rewardValues) {
        bitset<100001> cnt;
        int n = rewardValues.size();
        int maxVal = *max_element(rewardValues.begin(), rewardValues.end());
        set<int> nums(rewardValues.begin(), rewardValues.end());
        cnt.set(0);
        for (int x : nums) {
            int shift = cnt.size() - x;
            cnt |= (cnt << shift) >> (shift - x);
        }
        for (int i = 2 * maxVal - 1; i >= 0; i--) {
            if (cnt.test(i)) {
                return i;
            }
        }
        return -1;
    }
};

class Solution:
    def maxTotalReward(self, A: List[int]) -> int:
        b = 1
        for x in sorted(set(A)):
            b |= (b & ((1 << x) - 1)) << x
        return b.bit_length() - 1

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

• 关注我的博客: https://mike-box.github.io/

• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu

• 关注我的微信公众号: 哪些奋斗者