324. swing sort II / Sword finger offer II 102 Target value of addition and subtraction

324. Swing sort II【 Medium question 】【 A daily topic 】

Ideas ：

Learning problem solving .
【Nick~Hot topic 】 Relatively simple double pointer idea ！

Code ：

class Solution {
    
    public void wiggleSort(int[] nums) {
    
        int n = nums.length;
        // Copy nums The array is copy
        int[] copy = Arrays.copyOf(nums,n);
        // Yes copy Array to sort 
        Arrays.sort(copy);
        // take copy The array is divided into two parts , Both the left side and the right side increase in turn ( Possible equality ), The left side is all smaller than the right side , Definition left Is the right endpoint pointer on the left ,right Is the right endpoint pointer on the right 
        int left = (n - 1) / 2,right = n - 1;
        // Arrange the left and right elements in reverse order , Then cross update the elements of the array , Even subscripts place the left elements in reverse order , Odd subscripts place the right elements in reverse order 
        for (int i = 0; i < n; i++) {
    
            if (i % 2 == 0){
    
                // Even subscripts are placed in reverse order on the left element 
                nums[i] = copy[left--];
            }else {
    
                // Odd subscripts are placed in reverse order on the right element 
                nums[i] = copy[right--];
            }
        }
    }
}

---

The finger of the sword Offer II 102. The target value of addition and subtraction 【 Medium question 】

Ideas ：【 Dynamic programming 】

First of all, we need to re model the problem , Transform the problem into a dynamic programming problem .
Write the first order according to the solution dp And second order dp as follows .

Code ：【 Second order dp】

class Solution {
    
    public int findTargetSumWays(int[] nums, int target) {
    
        /** *  According to the solution to the problem , We need to change the direction of solving this problem first , Then use dynamic programming to solve . *  Set the sum of the elements of the array to sum, Set the sum of the elements with a minus sign before the element to  neg , Then the sum of the other elements with the plus sign is  sum - neg, therefore  * sum - neg - neg = target ==> neg = (sum-target)/2 *  Because the elements in the array are non negative integers , therefore  neg Must also be a non negative integer   therefore  sum - target  Must be   Nonnegative even number , If this condition is not satisfied   Then return directly 0, Indicates that there is no expression that meets the requirements  *  After excluding special circumstances , because  sum only , And you can find out ,target Given , So the question turns to   Select any element in the array , Find the sum of the selected elements equal to  sum-target Number of alternatives  */
        int sum = Arrays.stream(nums).sum();
        if (sum - target < 0 || (sum - target) % 2 != 0){
    
            return 0;
        }
        int n = nums.length,neg = (sum - target) / 2;
        // Definition dp Array  dp[i][j] Express   Before the array i Elements   Select any number of elements and   by  j  Number of alternatives 
        int[][] dp = new int[n+1][neg+1];
        // The boundary conditions   Don't select element , Then the element and must be 0, Then when the required sum is 0 when , This is a plan , When required and not for 0 when , No scheme meets the requirements  dp[0][j] = 0(j!=0)  Keep the default value 
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
    
            for (int j = 0; j <= neg; j++) {
    
                // If  j >= nums[i-1]  So the current element nums[i-1]  No choice , Both cases should be considered 
                if (j >= nums[i-1]){
    
                    // No election   The current number of schemes depends on  dp[i-1][j]
                    // choose   The current number of schemes depends on  dp[i-1][j-nums[i]]
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
                }else {
    
                    // If  j < nums[i-1]  So the current element nums[i-1] You must not choose , Because I have chosen and must surpass j
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        //dp[n][neg]  That is to say   All elements of the array   And for  neg Number of alternatives 
        return dp[n][neg];
    }
}

Code ：【 First order dp】

class Solution {
    
    public int findTargetSumWays(int[] nums, int target) {
    
        /** *  According to the solution to the problem , We need to change the direction of solving this problem first , Then use dynamic programming to solve . *  Set the sum of the elements of the array to sum, Set the sum of the elements with a minus sign before the element to  neg , Then the sum of the other elements with the plus sign is  sum - neg, therefore  * sum - neg - neg = target ==> neg = (sum-target)/2 *  Because the elements in the array are non negative integers , therefore  neg Must also be a non negative integer   therefore  sum - target  Must be   Nonnegative even number , If this condition is not satisfied   Then return directly 0, Indicates that there is no expression that meets the requirements  *  After excluding special circumstances , because  sum only , And you can find out ,target Given , So the question turns to   Select any element in the array , Find the sum of the selected elements equal to  sum-target Number of alternatives  */
        int sum = Arrays.stream(nums).sum();
        if (sum - target < 0 || (sum - target) % 2 != 0){
    
            return 0;
        }
        int n = nums.length,neg = (sum - target) / 2;
        // Definition dp Array  dp[j] Express   Before the array i(i Dynamically adjust according to the actual situation , For the initial 0, And then from 1 Gradually increasing ) Elements   Take the sum of any number of elements as  j  Number of alternatives 
        int[] dp = new int[neg+1];
        // The boundary conditions   And for  0  Before  0 The number of schemes with elements is 1
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
    // Gradually expand the window of optional elements 
            for (int j = neg; j >= nums[i]; j--) {
    
                // In order to prevent dp[j-nums[i]] It is updated during calculation , So we traverse in reverse order dp Array 
                // Traversal in reverse order  j == nums[i] The deadline is because  j<nums[i] when ,dp[j] = dp[j]
                // The transfer equation is as follows ：
                dp[j] = dp[j] + dp[j-nums[i]];
            }
        }
        // At the end of the loop ,i by n, So at this time dp[neg] That is to say   All elements of the array   Take the sum of any number of elements as neg Number of alternatives 
        return dp[neg];
    }
}