链接:LeetCode
[Leetcode]6451. 找出最大的可达成数字
给你两个整数 num 和 t 。
如果整数 x 可以在执行下述操作不超过 t 次的情况下变为与 num 相等,则称其为 可达成数字 :
- 每次操作将 x 的值增加或减少 1 ,同时可以选择将 num 的值增加或减少 1 。
返回所有可达成数字中的最大值。可以证明至少存在一个可达成数字。
class Solution {
public int theMaximumAchievableX(int num, int t) {
return num + 2* t;
}
}
[Leetcode]2770. 达到末尾下标所需的最大跳跃次数
给你一个下标从 0 开始、由 n 个整数组成的数组 nums 和一个整数 target 。
你的初始位置在下标 0 。在一步操作中,你可以从下标 i 跳跃到任意满足下述条件的下标 j :
- 0 <= i < j < n
- -target <= nums[j] - nums[i] <= target
返回到达下标 n - 1 处所需的 最大跳跃次数 。
如果无法到达下标 n - 1 ,返回 -1 。
动态规划:dp数组存储最大跳跃次数
对于当前i,寻找满足abs(nums[i] - nums[j]) <= target的所有j (0 <= j < i)
若存在这种j,找到其中dp[j]值最大的max
\(dp[i] = max + 1\)
否则
\(dp[i] = -1\)
class Solution {
public int maximumJumps(int[] nums, int target) {
int res = 0, n=nums.length;
int[] dp = new int[n];
for(int i=1;i<n;++i) {
dp[i] = -1;
for(int j=0;j<i;++j) {
int diff = nums[j] - nums[i];
if(diff >= -target && diff <= target) {
if(j == 0 || dp[j] > 0) dp[i] = Math.max(dp[i], dp[j]+1);
}
}
}
return dp[n-1];
}
}
[Leetcode]2741. 特别的排列
- 构造最长非递减子数组
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ,长度均为 n 。
让我们定义另一个下标从 0 开始、长度为 n 的整数数组,nums3 。对于范围 [0, n - 1] 的每个下标 i ,你可以将 nums1[i] 或 nums2[i] 的值赋给 nums3[i] 。
你的任务是使用最优策略为 nums3 赋值,以最大化 nums3 中 最长非递减子数组 的长度。
以整数形式表示并返回 nums3 中 最长非递减 子数组的长度。
注意:子数组 是数组中的一个连续非空元素序列。
动态规划.
class Solution {
public int maxNonDecreasingLength(int[] nums1, int[] nums2) {
int res = 1, n = nums1.length;
int[][] dp = new int[n][2];
dp[0][0] = 1;
dp[0][1] = 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][0], dp[i-1][0]+1);
if(nums1[i] >= nums2[i-1]) dp[i][0] = Math.max(dp[i][0], dp[i-1][1]+1);
if(nums2[i] >= nums1[i-1]) dp[i][1] = Math.max(dp[i][1], dp[i-1][0]+1);
if(nums2[i] >= nums2[i-1]) dp[i][1] = Math.max(dp[i][1], dp[i-1][1]+1);
res = Math.max(res, dp[i][0]);
res = Math.max(res, dp[i][1]);
}
return res;
}
}
[Leetcode]2772. 使数组中的所有元素都等于零
给你一个下标从 0 开始的整数数组 nums 和一个正整数 k 。
你可以对数组执行下述操作 任意次 :
- 从数组中选出长度为 k 的 任一 子数组,并将子数组中每个元素都 减去 1 。
如果你可以使数组中的所有元素都等于 0 ,返回 true ;否则,返回 false 。
子数组 是数组中的一个非空连续元素序列。
差分数组 & 贪心。
令 \(f(i)=a_i-a_{i-1}\),特别的,\(f(0)=a_0\), \(f(n)=−a_{n-1}\) 。数组 f 称为原数组的差分数组。
可以发现,差分数组具有以下性质:
- 原数组中所有元素都等于零,等价于差分数组中所有元素都等于零。
- 如果我们将原数组中以\(a_i\)为开头且长度为 \(k\) 的子数组中每个元素 −1,等价于 \(f(i)−1\),\(f(i+k)+1\)。这样我们就将子数组的运算转化为了单个元素的运算。
class Solution {
public boolean checkArray(int[] nums, int k) {
int n = nums.length;
int[] f = new int[n+1];
f[0] = nums[0];
f[n] = -nums[n-1];
for(int i=1;i<n;++i) {
f[i] = nums[i] - nums[i-1];
}
for(int i=0;i<=n-k;++i) {
if(f[i] < 0) return false;
if(f[i] > 0) {
f[i+k] += f[i];
f[i] -= f[i];
}
}
for(int i=0;i<=n;++i) if(f[i] != 0) return false;
return true;
}
}
参考:LeetCode
- Leetcode Contest Weekly 351leetcode contest weekly 351 leetcode contest weekly 361 leetcode contest weekly 355 leetcode contest weekly 365 leetcode contest weekly 367 leetcode contest weekly 368 leetcode contest weekly 350 leetcode contest weekly 339 leetcode contest weekly 364 leetcode contest weekly 359