Leetcode - 周赛401

目录

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

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

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

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

---

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

本题可以直接模拟，遇到 0 或 n - 1 下标，就反转一下。

代码如下：

class Solution {public int numberOfChild(int n, int k) {int i = 0, t = 1;while(k > 0){i += t;if(i == 0 || i == n-1){t *= -1;}k--;}return i;}
}

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

本题也是一道模拟题，对数组 a 不断的求前缀和，最后返回a[n-1].

代码如下：

class Solution {public int valueAfterKSeconds(int n, int k) {int MOD = (int)1e9 + 7;int[] a = new int[n];Arrays.fill(a, 1);while(k > 0){for(int i=1; i<n; i++){a[i] = (a[i] + a[i-1])%MOD;}k--;}return a[n-1];}
}

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

本题可以使用dfs中的选或不选来做，这里需要知道当前的下标 i ，以及前面所选的数的和 x，需要使用 x < rewardValues[i] 来判断该点能否选。（注意，题目对选择的下标没有进行限制，我们可以先将数组排序，这样就只需要向后遍历）

定义 dfs(i，x)：在[0，i)所选择的所有数的和为x时，[i，n]的最大总奖励。

• 选择 i 下标（必须先满足 x < rewardValues[i]），这时下一个状态就是 dfs(i+1，x+rewardValues[i])
• 不选 i 下标，下一个状态是 dfs(i+1, x)
• 结束条件，i == n，返回 0
• 返回两者的较大值

这里记忆化的时候只需要记录 x 就行，我们只需要关注在当前和为 x 时，能取到的最大值memo[x]，代码如下：

class Solution {public int maxTotalReward(int[] rewardValues) {Arrays.sort(rewardValues);memo = new int[4001];Arrays.fill(memo, -1);return dfs(0,0,rewardValues);}int[] memo;int dfs(int i, int x, int[] rewardValues){if(memo[x] != -1) return memo[x];if(i == rewardValues.length) return 0;int res = dfs(i+1, x, rewardValues);if(x < rewardValues[i]){res = Math.max(res, dfs(i+1, x+rewardValues[i], rewardValues)+rewardValues[i]);}return memo[x] = res;}
}

递推做法(0-1背包)

定义f[i][j]：能否从前 i 个数得到总奖励为 j

• 选（满足 j > rewardValues[i] && j-rewardValues[i] < rewardValues[i]），f [ i ][ j ] = f [ i-1 ][ j-rewardValues[i] ]
• 不选，f [ i ][ j ] = f [ i-1 ][ j ]
• f [ i ][ j ] = f [ i-1 ][ j ] || f [ i-1 ][ j-rewardValues[i] ]

class Solution {public int maxTotalReward(int[] rewardValues) {Arrays.sort(rewardValues);boolean[] f = new boolean[4001];int res  = 0;f[0] = true;for(int i=0; i<rewardValues.length; i++){for(int x=rewardValues[i]-1; x>=0; x--){f[x+rewardValues[i]] = f[x+rewardValues[i]] || f[x];res = Math.max(res,f[x+rewardValues[i]]?x+rewardValues[i]:res);}}return res;}
}

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

该问无法使用上述的做法，还需要进行优化，这里使用的是 bitset优化，它的原理就是直接使用二进制进行上述的或运算，这样就可以优化掉一层for循环。这里二进制位1-表示能得到当前数，0-表示不能得到当前数。代码如下：

//这里使用py是因为更加直接易懂
class Solution:def maxTotalReward(self, rewardValues: List[int]) -> int:f = 1for v in sorted(rewardValues):mask = (1 << v) - 1# t = (f & mask) << v : 表示如果选择v时，且 x < v 时， x + v 的所有能表示的值# f |= t : 为了计算不选择v时，x 的所有能表示的值f |= (f & mask) << vreturn f.bit_length() - 1//Java版
import java.math.BigInteger;class Solution {public int maxTotalReward(int[] rewardValues) {BigInteger f = BigInteger.ONE;for (int v : Arrays.stream(rewardValues).distinct().sorted().toArray()) {BigInteger mask = BigInteger.ONE.shiftLeft(v).subtract(BigInteger.ONE);f = f.or(f.and(mask).shiftLeft(v));}return f.bitLength() - 1;}
}