LeetCode Contest 333

6369. Left and Right Sum Differences

给你一个下标从 0 开始的整数数组 nums ，请你找出一个下标从 0 开始的整数数组 answer ，其中：

• answer.length == nums.length
• answer[i] = |leftSum[i] - rightSum[i]|

其中：

• leftSum[i] 是数组 nums 中下标 i 左侧元素之和。如果不存在对应的元素，leftSum[i] = 0 。
• rightSum[i] 是数组 nums 中下标 i 右侧元素之和。如果不存在对应的元素，rightSum[i] = 0 。
  返回数组 answer 。

测试样例

输入：nums = [10,4,8,3]

输出：[15,1,11,22]

解释：

数组 leftSum 为 [0,10,14,22] 且数组 rightSum 为 [15,11,3,0] 。
数组 answer 为 [|0 - 15|,|10 - 11|,|14 - 3|,|22 - 0|] = [15,1,11,22] 。

解答：这道题目按照题意，2个方向遍历一下数组，计算lestSum和rightSum，最后取绝对值之差即可

class Solution {
    public int[] leftRigthDifference(int[] nums) {
        int len = nums.length;
        int[] res = new int[len];
        for (int i = 1; i < nums.length; ++i) {
            res[i] = res[i - 1] + nums[i - 1];
        }

        int rightSum = 0;
        for (int i = nums.length - 2; i >= 0; --i) {
            rightSum += nums[i + 1];
            res[i] = Math.abs(res[i] - rightSum);
        }
        return res;
    }
}

6368. Find the Divisibility Array of a String

给你一个下标从 0 开始的字符串 word ，长度为 n ，由从 0 到 9 的数字组成。另给你一个正整数 m 。

word 的 可整除数组 div 是一个长度为 n 的整数数组，并满足：

• 如果 word[0,...,i] 所表示的 数值 能被 m 整除，div[i] = 1
• 否则，div[i] = 0

返回 word 的可整除数组。

测试样例：

输入：word = "998244353", m = 3

输出：[1,1,0,0,0,1,1,0,0]

解释：

仅有 4 个前缀可以被 3 整除："9"、"99"、"998244" 和 "9982443" 。

解答: 这道题目本质就是考一下mod，注意mod <= 10^9，安全一点用long记录前缀mod即可

class Solution {
    public int[] divisibilityArray(String word, int m) {
        int len = word.length();
        int[] res = new int[len];
        long cur = 0;
        for (int i = 0; i < word.length(); ++i) {
            int o = word.charAt(i) - '0';
            cur = (cur * 10 + o) % m;
            if (cur == 0) res[i] = 1;
        }
        return res;
    }
}

6367. Find the Maximum Number of Marked Indices

给你一个下标从 0 开始的整数数组 nums 。

一开始，所有下标都没有被标记。你可以执行以下操作任意次：

• 选择两个 互不相同且未标记 的下标 i 和 j ，满足 2 * nums[i] <= nums[j] ，标记下标 i 和 j 。

请你执行上述操作任意次，返回 nums 中最多可以标记的下标数目。

测试样例

输入：nums = [9,2,5,4]

输出：4

解释：

第一次操作中，选择 i = 3 和 j = 0 ，操作可以执行的原因是 2 nums[3] <= nums[0] ，标记下标 3 和 0 。
第二次操作中，选择 i = 1 和 j = 2 ，操作可以执行的原因是 2 nums[1] <= nums[2] ，标记下标 1 和 2 。
没有其他更多可执行的操作，所以答案为 4 。

解答：这道题目难度开始加大了。直接排序后使用贪婪是不行的。在我选的例子里面。如果直接贪婪，那么2 -> 4，但是9 < 2 * 5。得不到4这个结果。

这道题目需要用二分查找的思路。排序之后，如果能找到一个最佳前缀，且这个前缀和其对应的后缀都能满足2 * nums[i] <= nums[j]。使用折半搜索这个前缀

class Solution {
    public int maxNumOfMarkedIndices(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
        int st = 0, ed = len / 2;
        while (st < ed) {
            int mid = (st + ed + 1) / 2;
            if (isValid(nums, mid)) {
                st = mid;
            } else {
                ed = mid - 1;
            }
        }
        return st * 2;
    }

    private boolean isValid(int[] nums, int mid) {
        int r = nums.length - 1, l = mid - 1;
        while (l >= 0) {
            if (nums[r] < nums[l] * 2) {
                return false;
            }
            --r; --l;
        }
        return true;
    }
}

6366. Minimum Time to Visit a Cell In a Grid

给你一个 m x n 的矩阵 grid ，每个元素都为 非负 整数，其中 grid[row][col] 表示可以访问格子 (row, col) 的 最早 时间。也就是说当你访问格子 (row, col) 时，最少已经经过的时间为 grid[row][col] 。

你从 最左上角 出发，出发时刻为 0 ，你必须一直移动到上下左右相邻四个格子中的 任意 一个格子（即不能停留在格子上）。每次移动都需要花费 1 单位时间。

请你返回 最早 到达右下角格子的时间，如果你无法到达右下角的格子，请你返回 -1 。

测试样例

输入：grid = [[0,1,3,2],[5,1,2,5],[4,3,8,6]]

输出：7

解释：

一条可行的路径为：

• 时刻 t = 0 ，我们在格子 (0,0) 。
• 时刻 t = 1 ，我们移动到格子 (0,1) ，可以移动的原因是 grid[0][1] <= 1 。
• 时刻 t = 2 ，我们移动到格子 (1,1) ，可以移动的原因是 grid[1][1] <= 2 。
• 时刻 t = 3 ，我们移动到格子 (1,2) ，可以移动的原因是 grid[1][2] <= 3 。
• 时刻 t = 4 ，我们移动到格子 (1,1) ，可以移动的原因是 grid[1][1] <= 4 。
• 时刻 t = 5 ，我们移动到格子 (1,2) ，可以移动的原因是 grid[1][2] <= 5 。
• 时刻 t = 6 ，我们移动到格子 (1,3) ，可以移动的原因是 grid[1][3] <= 6 。
• 时刻 t = 7 ，我们移动到格子 (2,3) ，可以移动的原因是 grid[2][3] <= 7 。

最终到达时刻为 7 。这是最早可以到达的时间。

解答：在图上上下左右搜索，寻找最短时间。那么很容易想到是BFS。但是这道题目是允许2个模块来回运动拖时间的，所以需要一点变形。

如果是用A -> B -> A来拖时间，那么达到A的时间奇偶性是不会发生变化的。所以BFS的数组改变一下，增加一个奇偶位判断即可。

class Solution {
    public static final int[] moves = {1,0,-1,0,1};

    public int minimumTime(int[][] grid) {
        if (grid[0][1] > 1 && grid[1][0] > 1) return -1;
        int m = grid.length, n = grid[0].length;

        int[][][] dp = new int[m][n][2];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int k = 0; k < 2; ++k) {
                    dp[i][j][k] = Integer.MAX_VALUE;
                }
            }
        }
        boolean[][][] isAdd = new boolean[m][n][2];

        dp[0][0][0] = 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0,0,0});
        isAdd[0][0][0] = true;

        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            isAdd[tmp[0]][tmp[1]][tmp[2]] = false;
            int oldTime = dp[tmp[0]][tmp[1]][tmp[2]] + 1;
            for (int i = 0; i < 4; ++i) {
                int xt = tmp[0] + moves[i], yt = tmp[1] + moves[i + 1];
                if (xt >= 0 && yt >= 0 && xt < m && yt < n) {
                    int nextTime = oldTime;
                    if (oldTime < grid[xt][yt]) {
                        nextTime = (grid[xt][yt] - oldTime) % 2 + grid[xt][yt];
                    }
                    int mod = nextTime % 2;
                    if (dp[xt][yt][mod] > nextTime) {
                        dp[xt][yt][mod] = nextTime;
                        if (!isAdd[xt][yt][mod]) {
                            isAdd[xt][yt][mod] = true;
                            queue.add(new int[]{xt, yt, mod});
                        }
                    }
                }
            }
        }
        int res = Math.min(dp[m - 1][n - 1][0], dp[m - 1][n - 1][1]);
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}