324. 摆动排序 II / 剑指 Offer II 102. 加减的目标值

324. 摆动排序 II【中等题】【每日一题】

思路：

学习题解。
【Nick~Hot题】比较简单的双指针思路！

代码：

class Solution {
    
    public void wiggleSort(int[] nums) {
    
        int n = nums.length;
        //拷贝nums数组为copy
        int[] copy = Arrays.copyOf(nums,n);
        //对copy数组进行排序
        Arrays.sort(copy);
        //将copy数组分为两部分，左侧与右侧均依次递增(可能存在相等)，左侧全部小于右侧，定义left为左侧的右端点指针，right为右侧的右端点指针
        int left = (n - 1) / 2,right = n - 1;
        //将左侧和右侧元素均倒序排列，然后把元素交叉更新数组，偶数下标放置倒序的左侧元素，奇数下标放置倒序的右侧元素
        for (int i = 0; i < n; i++) {
    
            if (i % 2 == 0){
    
                //偶数下标放倒序的左侧元素
                nums[i] = copy[left--];
            }else {
    
                //奇数下标放倒序的右侧元素
                nums[i] = copy[right--];
            }
        }
    }
}

---

剑指 Offer II 102. 加减的目标值【中等题】

思路：【动态规划】

首先需要对题目重新建模处理，将问题转换为动态规划问题。
根据题解写出一阶dp和二阶dp如下。

代码：【二阶dp】

class Solution {
    
    public int findTargetSumWays(int[] nums, int target) {
    
        /** * 根据题解思路，需要先把这题的求解方向进行一下转换，然后使用动态规划求解。 * 设数组的元素和为sum，设元素前添加减号的元素的和为 neg ，那么其余添加加号的元素的和为 sum - neg，于是 * sum - neg - neg = target ==> neg = (sum-target)/2 * 由于数组中元素均为非负整数，所以 neg也必须为非负整数 于是 sum - target 必须是 非负偶数，如果这个条件不满足 则直接返回0，表示没有符合要求的表达式 * 排除特殊情况之后，由于 sum唯一，且可以求出来，target给定，于是问题就转换为 在数组中选择任意元素，求选择的元素和等于 sum-target的方案数 */
        int sum = Arrays.stream(nums).sum();
        if (sum - target < 0 || (sum - target) % 2 != 0){
    
            return 0;
        }
        int n = nums.length,neg = (sum - target) / 2;
        //定义dp数组 dp[i][j]表示 数组前i个元素 任意选取若干个元素和 为 j 的方案数
        int[][] dp = new int[n+1][neg+1];
        //边界条件 不选择元素，则元素和肯定为0，那么当要求的和为0时，这就是一种方案,当要求的和不为0时，没有方案符合要求 dp[0][j] = 0(j!=0) 保持默认值即可
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
    
            for (int j = 0; j <= neg; j++) {
    
                //如果 j >= nums[i-1] 那么当前这个元素nums[i-1] 可选可不选，两种情况都要考虑
                if (j >= nums[i-1]){
    
                    //不选 则当前方案数取决于 dp[i-1][j]
                    //选 则当前方案数取决于 dp[i-1][j-nums[i]]
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
                }else {
    
                    //如果 j < nums[i-1] 那么当前这个元素nums[i-1]一定不能选，因为选了和一定超过j
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        //dp[n][neg] 即为 数组全部元素 和为 neg的方案数
        return dp[n][neg];
    }
}

代码：【一阶dp】

class Solution {
    
    public int findTargetSumWays(int[] nums, int target) {
    
        /** * 根据题解思路，需要先把这题的求解方向进行一下转换，然后使用动态规划求解。 * 设数组的元素和为sum，设元素前添加减号的元素的和为 neg ，那么其余添加加号的元素的和为 sum - neg，于是 * sum - neg - neg = target ==> neg = (sum-target)/2 * 由于数组中元素均为非负整数，所以 neg也必须为非负整数 于是 sum - target 必须是 非负偶数，如果这个条件不满足 则直接返回0，表示没有符合要求的表达式 * 排除特殊情况之后，由于 sum唯一，且可以求出来，target给定，于是问题就转换为 在数组中选择任意元素，求选择的元素和等于 sum-target的方案数 */
        int sum = Arrays.stream(nums).sum();
        if (sum - target < 0 || (sum - target) % 2 != 0){
    
            return 0;
        }
        int n = nums.length,neg = (sum - target) / 2;
        //定义dp数组 dp[j]表示 数组前i(i根据实际情况动态调整，初始为0,然后从1开始逐渐递增)个元素 任取若干个元素的和为 j 的方案数
        int[] dp = new int[neg+1];
        //边界条件 和为 0 的前 0个元素的方案数为1
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
    //逐渐扩大可选元素窗口
            for (int j = neg; j >= nums[i]; j--) {
    
                //为了防止dp[j-nums[i]]在计算的时候被更新，于是倒序遍历dp数组
                //倒序遍历在 j == nums[i]截止是因为 j<nums[i]时，dp[j] = dp[j]
                //转移方程如下：
                dp[j] = dp[j] + dp[j-nums[i]];
            }
        }
        //循环结束时，i为n，所以此时的dp[neg]即为 数组全部元素 任取若干个元素的和为neg的方案数
        return dp[neg];
    }
}