LeetCode Contest 401

欢迎大家加QQ群：623375442，可以方便群里面交流。

100325. Find the Child Who Has the Ball After K Seconds

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

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

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

测试样例：

输入：1

输出：1

解释：5 [0, 1, 2]

解答：暴力模拟

class Solution {
    public int numberOfChild(int n, int k) {
        int dir = 1, cur = 0;
        for (int i = 0; i < k; ++i) {
            cur += dir;
            if (cur < 0 || cur >= n) {
                dir *= -1;
                cur += 2 * dir;
            }
        }
        return cur;
    }
}

100305. Find the N-th Value After K Seconds

给你两个整数 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] 的值。

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

测试样例：

输入：n = 4, k = 5

输出：56

解释：5 [1,6,21,56]

解答：暴力模拟。

class Solution {
    private static final int mod = 1_000_000_007;

    public int valueAfterKSeconds(int n, int k) {
        int[] arr = new int[n];
        Arrays.fill(arr, 1);
        for (int i = 0; i < k; ++i) {
            int[] nextArr = new int[n];
            int sum = 0;
            for (int j = 0; j < n; ++j) {
                sum = (sum + arr[j]) % mod;
                nextArr[j] = sum;
            }
            arr = nextArr;
        }
        return arr[arr.length - 1];
    }
}

100320. Maximum Total Reward Using Operations II

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

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

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

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

测试样例：

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

输出：4

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

解答：暴力递归，感觉会被rejudge

class Solution {
    private class Data {
        private int[] nums;
        private int ans, max;
        private boolean done;

        public Data(List<Integer> list) {
            nums = new int[list.size()];
            for(int i = 0;i < list.size(); i++){
                nums[i] = list.get(i);
            }
            ans = 0;
            max = nums[nums.length - 1];
            done = false;
        }
    }

    public int maxTotalReward(int[] rewardValues) {
        Arrays.sort(rewardValues);
        List<Integer> list = new ArrayList<>();
        int now = 0;
        int n = rewardValues.length;
        for(int i = 0; i < n; i++){
            if (rewardValues[i] > now){
                list.add(rewardValues[i]);
                now = rewardValues[i];
            }
        }
        Data data = new Data(list);
        dfs(0, data,0);
        return data.ans;
    }

    private void dfs(int startIndex, Data data, int sum){
        if (data.done) return;
        if (sum == data.max - 1){
            data.ans = data.max + sum;
            data.done = true;
            return;
        }
        if (sum >= data.max){
            data.ans = Math.max(data.ans, sum);
            return;
        }
        for (int i = startIndex; i < data.nums.length; i++){
            if (sum >= data.nums[i]) continue;
            dfs(i + 1, data,sum + data.nums[i]);
        }
    }
}