LeetCode 第464场周赛第三天

1. 3658 奇数和与偶数和的最大公约数（欧几里得）

链接：题目链接
题解：

题解时间复杂度O(logmin(a, b))：

获得前n个奇、偶数的总和，由于数列为等差数列，等差数列和公式：(a1 + an) * n / 2），可以快速求和。
获取两个数字的最大公约数，用欧几里得算法可求得最大公约数，代码模版如下。

代码：

    class Solution {public int gcd(int a, int b) {return b != 0 ? gcd(b, a % b) : a;}public int gcdOfOddEvenSums(int n) {// 等差数列求和int sum1 = (1 + 2 * n - 1) * n / 2;int sum2 = (2 + 2 * n) * n / 2;return gcd(sum1, sum2);}
}

2. 3659 数组元素分组（抽屉原理）

链接：题目链接
题解：

题解时间复杂度O(n):

nums 中的每个元素必须被分配到恰好一个组中，每个组恰好k个不同的元素，说明 n * k = 数组长度，n为具体组数。
组数 = 数组长度 / k，如果某个数字重复次数 > 组数，那么肯定没办法满足每个组恰好k个不同的元素（抽屉原理），反之均可满足。

代码：

class Solution {public boolean partitionArray(int[] nums, int k) {int len = nums.length;if (len % k != 0) {return false;}int countLimit = len / k;Map<Integer, Integer> numCountMap = new HashMap<>();for (int num: nums) {numCountMap.put(num, numCountMap.getOrDefault(num, 0) + 1);}return numCountMap.values().stream().noneMatch(numCount -> numCount > countLimit);}
}

3. 3660 跳跃游戏 9（预处理单调栈二分解法）

链接：题目链接
题解：

背景：仅当 nums[j] < nums[i] 时，才允许跳跃到下标 j，其中 j > i。仅当 nums[j] > nums[i] 时，才允许跳跃到下标 j，其中 j < i。（一次跳跃中，往前跳，nums值必须严格大于; 往后跳，nums值必须严格小于）;
题解时间复杂度O(nlogn)：

对于第i个元素，如果能到达的最大值在左侧，那么一次跳跃即可（需要维护左侧最大值）。
对于第i个元素，如果能到达的最大值在右侧，首先往右跳跃到j位置，nums[j] < nums[i]的，所以nums[j]肯定不是i元素能到达的最大值，意味着还得从j下标往左跳，才有可能 num[j] > nums[i]。
注意：对于第i个元素，最大值在右侧还有一种跳跃方式。可能存在[30, 10, 35, 22] 这种情况，对于nums[1]来说，并不能直接跳到35去（因为nums[2、3] > nums[1]），但是有一条路线可以达到nums[3](1 -> 0 -> 3 -> 2)，(第2、3点)总结：对于最大值在右侧情况，nums[i]可以先跳到左侧最大值（nums[j] >= nums[i]），再往右侧跳（覆盖的范围更广）
因为要在logn级别找到 i右边元素到达的最大值，那么很自然想到了维护一个有序的列表，通过二分方式在logn时间复杂度找到右侧能到达的最大值。这里维护有序列表有个关键点：如果 2能到达x，3能达到x-1或者x，那么这个列表还有必要维护3这个元素吗？答案是不需要将3这个元素入队(因为能到达2的元素包含了能到达3的元素且 3能到达的最大值<=2能到达的最大值)，也就是单调栈思想
有序列表样例：[1 -> 10, 2 -> 12, 5 -> 15]，此时有序是指的nums[i]是递增的，且nums[i]能找到的最大值也是递增的。所以在二分查找的时候只需要找到小于nums[i]的第一个元素，再拿到它对应的最大值即可。
第i个元素能到达的最大值 = max(左侧最大值, 右侧最大值)

代码：

 class Solution {public int[] maxValue(int[] nums) {int len = nums.length;int[] leftMaxValues = new int[len];int maxValue = 0;for (int i = 0; i < len; ++ i) {maxValue = Math.max(maxValue, nums[i]);leftMaxValues[i] = maxValue;}int[] result = new int[len];TreeMap<Integer, Integer> map = new TreeMap<>();// 初始化result[len - 1] = leftMaxValues[len - 1];map.put(nums[len - 1], leftMaxValues[len - 1]);for (int i = len - 2; i >= 0; -- i) {// 获取右边最大值Map.Entry<Integer, Integer> entry = map.lowerEntry(leftMaxValues[i]);if (entry != null) {result[i] = entry.getValue();} else {result[i] = leftMaxValues[i];}// 维护mapInteger old = map.get(nums[i]);if (old == null || old < result[i]) {map.put(nums[i], result[i]);// 删除所有 "比nums[i]大，且 value <= result[0]" 的节点while (true) {Map.Entry<Integer, Integer> higher = map.higherEntry(nums[i]);if (higher != null && higher.getValue() <= result[i]) {map.remove(higher.getKey());} else break;}}}return result;}}

4. 3661 可以被机器人摧毁的最大墙壁数目（DP解法）

链接：题目链接
题解：

题解 时间复杂度O(nlogn)：

因为机器人会阻挡子弹的穿透，所以第i个机器人，最多穿透[i - 1, i + 1]下标的区域，那么也以为着第i个机器人只与第i-1、i+1个机器人有关系
robot、distance 为一组信息 walls为一组信息，两组信息分别排序（机器人跟相邻机器人有关系所以需要排序处理）
这里机器人只能往左往右发射，可以用f[i][j] i表示第i个机器人 j表示往左还是右设计 j为0 往左 j为1往右
dp转移方程式： f[i][1] = Math.max(f[i - 1][0], f[i - 1][1]) + i机器人往右打多少个墙； f[i][0] = Math.max(f[i - 1][0], f[i - 1][1]) + i机器人往左打多少个墙
打多少个墙？可以拿到机器人射击区间，因为墙列表也做了排序（是有序的），再通过二分计算能射击多少个墙
注意1：这里要注意i-1机器人往右，i机器人往左射击的情况，对射的情况（避免重复计算墙）
注意2：这里要考虑机器人与墙重合的情况，比如i机器人与墙重合，但是i-1机器人往右射击计算了该墙，但是i机器人射击又计算该墙的情况（又重复计算了），所以墙与机器人重合情况，该墙只让该机器人射击。（i-1机器人往右射击，区间从[nums[i-1], nums[i]] -> [nums[i-1], nums[i] -1)）

代码：

class Solution {class Pair implements Comparable<Pair>{private int robotIndex;private int distance;@Overridepublic int compareTo(Pair pair) {return robotIndex - pair.robotIndex;}public Pair(int robotIndex, int distance) {this.robotIndex = robotIndex;this.distance = distance;}}public int maxWalls(int[] robots, int[] distance, int[] walls) {int len = robots.length;List<Pair> pairs = new ArrayList<>(len);for (int i = 0; i < len; ++ i) {pairs.add(new Pair(robots[i], distance[i]));}Collections.sort(pairs);Arrays.sort(walls);int[][] f = new int[len + 1][2];for (int i = 1; i <= len; ++ i) {if (i == 1) {f[i][1] = caclSum(0, pairs, pairs.get(0).distance, walls, false, true);f[i][0] = caclSum(0, pairs, pairs.get(0).distance, walls, true, true);} else {f[i][1] = Math.max(f[i - 1][0], f[i - 1][1]) + caclSum(i - 1, pairs, pairs.get(i - 1).distance, walls, false, true);Pair pair = pairs.get(i - 1);Pair prePair = pairs.get(i - 2);if (pair.distance + prePair.distance >= pair.robotIndex - prePair.robotIndex) {f[i][0] = Math.max(f[i - 1][0] + caclSum(i - 1, pairs, pair.distance, walls, true, true), Math.max(f[i][0], Math.max(f[i - 2][0], f[i - 2][1]) + caclSum(i - 2, pairs, pair.distance + prePair.distance, walls, false, false)));} else {f[i][0] = Math.max(f[i - 1][1], f[i - 1][0]) + caclSum(i - 1, pairs, pair.distance, walls, true, true);}}}return Math.max(f[len][0], f[len][1]);}public int caclSum(int index, List<Pair> pairs, int distance, int[] walls, boolean left, boolean excludeNextIndex) {int l, r;if (left) {r = pairs.get(index).robotIndex;l = r - distance;if (index - 1 >= 0) {l = Math.max(l, pairs.get(index - 1).robotIndex + (excludeNextIndex ? 1 : 0));}} else {l = pairs.get(index).robotIndex;r = l + distance;if (index + 1 < pairs.size()) {r = Math.min(r, pairs.get(index + 1).robotIndex - (excludeNextIndex ? 1 : 0));}}int wallLIndex, wallRIndex;// 找到大于等于l的第一个下标int wallL = 0, wallR = walls.length - 1;while (wallL < wallR) {int mid = (wallL + wallR) >> 1;if (walls[mid] >= l) {wallR = mid;} else {wallL = mid + 1;}}wallLIndex = wallL;// 找到小于等于R的第一个下标wallL = 0;wallR = walls.length - 1;while (wallL < wallR) {int mid = (wallL + wallR + 1) >> 1;if (walls[mid] <= r) {wallL = mid;} else {wallR = mid - 1;}}wallRIndex = wallL;if (wallLIndex <= wallRIndex && walls[wallLIndex] >= l && walls[wallRIndex] <= r) {return wallRIndex - wallLIndex + 1;}return 0;}
}