[Leetcode Weekly Contest]351

链接：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. 特别的排列

2771. 构造最长非递减子数组
      给你两个下标从 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