18-周赛353
卡在了T3，状态定义出现了偏差WA了
找出最大的可达成数字【LC2769】
给你两个整数
如果整数num和t。x可以在执行下述操作不超过t次的情况下变为与num相等，则称其为 可达成数字 ：
- 每次操作将
x的值增加或减少1，同时可以选择将num的值增加或减少1。
返回所有可达成数字中的最大值。可以证明至少存在一个可达成数字。
class Solution { public int theMaximumAchievableX(int num, int t) { return num + 2 * t; } }
达到末尾下标所需的最大跳跃次数【LC2770】
给你一个下标从 0 开始、由
n个整数组成的数组nums和一个整数target。你的初始位置在下标
0。在一步操作中，你可以从下标i跳跃到任意满足下述条件的下标j：
0 <= i < j < n
-target <= nums[j] - nums[i] <= target
返回到达下标 n - 1 处所需的 最大跳跃次数 。
如果无法到达下标 n - 1 ，返回 -1 。
class Solution { public int maximumJumps(int[] nums, int target) { // 最大跳跃次数：每次跳跃尽可能少跳 int n = nums.length; int[] dp = new int[n];// 跳跃至i时的最大次数 Arrays.fill(dp, -1); dp[0] = 0; for (int i = 1; i < n; i++){ // 向前搜索可以跳跃的最近位置 for (int j = 0; j < i; j++){ if (j >= 0 && Math.abs(nums[i] - nums[j]) <= target && dp[j] >= 0){ dp[i] = Math.max(dp[i], dp[j] + 1); } } } return dp[n - 1]; } }
构造最长非递减子数组【LC2771】
给你两个下标从 0 开始的整数数组
nums1和nums2，长度均为n。让我们定义另一个下标从 0 开始、长度为
n的整数数组，nums3。对于范围[0, n - 1]的每个下标i，你可以将nums1[i]或nums2[i]的值赋给nums3[i]。你的任务是使用最优策略为
nums3赋值，以最大化nums3中 最长非递减子数组 的长度。以整数形式表示并返回
nums3中 最长非递减 子数组的长度。注意：子数组 是数组中的一个连续非空元素序列。
- 错误思路
dp的同时稍微贪心了一下，比如根据大小判断应该取哪个nums… - 思路
每次选择的数可以是nums1，也可以是nums2，其前一个数字也有两种选择，因此需要定义两种状态记录以nums1/nums2[i]结尾的最长非递减 子数组的长度
- 状态定义：
class Solution { public int maxNonDecreasingLength(int[] nums1, int[] nums2) { int n = nums1.length; int[][] dp = new int[n][2]; dp[0][0] = 1; dp[0][1] = 1; int res = 1; for (int i = 1; i < n; i++){ dp[i][0] = 1; dp[i][1] = 1; if (nums1[i] >= nums1[i - 1]){ dp[i][0] = Math.max(dp[i - 1][0] + 1, dp[i][0]); } if (nums1[i] >= nums2[i - 1]){ dp[i][0] = Math.max(dp[i - 1][1] + 1, dp[i][0]); } if (nums2[i] >= nums1[i - 1]){ dp[i][1] = Math.max(dp[i - 1][0] + 1, dp[i][1]); } if (nums2[i] >= nums2[i - 1]){ dp[i][1] = Math.max(dp[i - 1][1] + 1, dp[i][1]); } res = Math.max(res, Math.max(dp[i][0], dp[i][1])); } return res; } }
使数组中的所有元素都等于零【LC2772】
给你一个下标从 0 开始的整数数组
nums和一个正整数k。你可以对数组执行下述操作 任意次 ：
- 从数组中选出长度为
k的 任一 子数组，并将子数组中每个元素都 减去1。如果你可以使数组中的所有元素都等于
0，返回true；否则，返回false。子数组 是数组中的一个非空连续元素序列。
边减边计算原值判断
- 思路
实现
在遍历的过程中，累加差分值，对变化后的数字进行判断，不满足要求则直接返回false
class Solution { public boolean checkArray(int[] nums, int k) { int n = nums.length, sumD = 0; var d = new int[n + 1]; for (int i = 0; i < n; i++) { sumD += d[i]; int x = nums[i]; x += sumD; if (x == 0) continue; // 无需操作 if (x < 0 || i + k > n) return false; // 无法操作 sumD -= x; // 直接加到 sumD 中nums[i] = d[0] + d[1] + d[i - 1] + d[i] d[i + k] += x; } return true; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/apply-operations-to-make-all-array-elements-equal-to-zero/solutions/2336744/chai-fen-shu-zu-pythonjavacgojs-by-endle-8qrt/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
减完后判断差分数组是否都为0
- 实现
- 如果操作后数组中所有值为0，那么差分数组中所有值为0
- 首先计算原数组的差分数组，对于差分数组中值大于0的每个位置，进行区间修改，最后判断差分数组中是否所有值为0
class Solution { public boolean checkArray(int[] nums, int k) { int n = nums.length; int[] d = new int[n + 1]; d[0] = nums[0]; // 计算差分数组 for (int i = 1; i < n; i++){ d[i] = nums[i] - nums[i - 1]; } // 从左到右对差分数组里的每个元素进行操作 for (int i = 0; i + k <= n; i++){ if (d[i] > 0){ d[i + k] += d[i]; d[i] = 0; }else if (d[i] < 0){ return false; } } // 检查差分数组中不能进行区间修改的元素是否均为 0 for (int i = n - k + 1; i < n; i++){ if (d[i] != 0){ return false; } } return true; } }
