Leetcode question brushing (6)

Divide and conquer problem

The divide and conquer problem consists of “ branch ”（divide） and “ cure ”（conquer） Two parts , By dividing the original problem into subproblems , Then deal with the sub problems and merge them , So as to solve the original problem .
in addition , Top down divide and conquer can be compared with memoization combination , Avoid repeatedly traversing the same subproblem . If it is convenient to deduce , It can also be solved by bottom-up dynamic programming method .

241. DifferentWays to Add Parentheses (Medium)

Problem specification
Give you a string of numbers and operators expression , Combine numbers and operators according to different priorities , Calculate and return the results of all possible combinations . You can do it in any order Return to the answer .

I/o sample
Example 1：

Input ：expression = “2-1-1”
Output ：[0,2]
explain ：
((2-1)-1) = 0
(2-(1-1)) = 2

Example 2：

Input ：expression = “23-45”
Output ：[-34,-14,-10,-10,10]
explain ：
(2*(3-(45))) = -34
((23)-(45)) = -14
((2(3-4))5) = -10
(2((3-4)5)) = -10
(((23)-4)*5) = 10

Ideas
For an expression , It can be divided into two parts according to symbols . Solve the values of the two parts respectively , Then add, subtract and multiply the values of the two parts . Pay attention to the boundary conditions ： If there is no sign in an expression , Then add it directly to the result .

Code

class Solution {
    
    public List<Integer> diffWaysToCompute(String expression) {
    
        LinkedList<Integer> result = new LinkedList<>();
        for(int i=0;i<expression.length();i++){
    
            char c = expression.charAt(i);
            if(c=='+'||c=='-'||c=='*'){
    
                List<Integer> left_result = diffWaysToCompute(expression.substring(0,i)); //[0,i)
                List<Integer> right_result = diffWaysToCompute(expression.substring(i+1));//[i+1,length)
                for(int left:left_result){
    
                    for(int right:right_result){
    
                        if(c == '+')result.add(left+right);
                        if(c == '*')result.add(left*right);
                        if(c == '-')result.add(left-right);
                    }
                }
            }
            
        }
        // If expression There are only numbers in 
        if(result.isEmpty())result.add(Integer.valueOf(expression));
        return result;
    }
}

932. Beautiful Array (Medium)

Problem description
For some fixed N, If the array A Is an integer 1, 2, …, N The arrangement of components , bring ：
For each i < j, It doesn't exist k Satisfy i < k < j bring A[k] * 2 = A[i] + A[j].
So array A It's a beautiful array .
Given N, Returns any beautiful array A（ There is a guarantee that ）.

I/o sample
Example 1：

Input ：4
Output ：[2,1,4,3]

Example 2：

Input ：5
Output ：[3,1,2,5,4]

Ideas
According to the meaning of the topic, as long as you are not satisfied A[k] * 2 = A[i] + A[j] That is, a beautiful array , That is to say for 【1-n】 There may be many . Here we just need to find each n One of them is ok . Do not satisfy the above equation , It only needs A[i] and A[j] One is an even number and the other is an odd number .

about n Number , from 1 Start , Odd numbers have (n+1)/2 individual , Even numbers have n/2 individual
front (n+1)/2 A beautiful array of numbers is left
front n/2 individual The beautiful array of numbers is right
left*2-1 It's still a beautiful array （ Include 1 3 5 7…） Wonderful array
right*2 It is still a beautiful array （ Include 2 4 6 8…） I have a beautiful array
take left*2-1 and right*2 Put the left and right together ( The combination of odd beautiful array and even beautiful array is a beautiful array ), It just includes n Number , And it's a beautiful array .

Code

class Solution {
    
    public int[] beautifulArray(int n) {
    
        if(n==1) return new int[]{
    1};
        int[] left = beautifulArray((n+1)/2);
        int[] right = beautifulArray(n/2);
        int[] result = new int[n];
        int k = 0;
        for(int c:left){
    
            result[k++]=c*2-1;
        }
        for(int c:right){
    
            result[k++]=c*2;
        }
        return result;
    }
}

312. Burst Balloons (Hard)

Problem description
Yes n A balloon , The number is 0 To n - 1, Each balloon is marked with a number , There are arrays of these numbers nums in .

Now I ask you to prick all the balloons . Pierce the second i A balloon , You can get nums[i - 1] * nums[i] * nums[i + 1] Coin . there i - 1 and i + 1 For and on behalf of i The serial number of the two adjacent balloons . If i - 1 or i + 1 Beyond the bounds of the array , Then think of it as a number for 1 The balloon .

Find the maximum number of coins you can get .

I/o sample

Example 1：

Input ：nums = [3,1,5,8]
Output ：167
explain ：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 315 + 358 + 138 + 181 = 167

Example 2：

Input ：nums = [1,5]
Output ：10

Ideas
reference [email protected] Dog King
The balloon in this section is so long ：

Suppose this interval is an open interval , Leftmost index i, Rightmost index j, Here it is “ Open range ” It means that you can only poke i and j Between the balloons .
DP This is the idea , Just forget how you poked it in front , As long as the last balloon in this range is punctured , This is the last balloon to burst k. Suppose the last balloon that is popped is pink ,k It's the index of the pink balloon ：

Because it is the last one to be punctured , Only i and j 了 . therefore DP The state transition equation is only and i and j The number of positions is related to .
hypothesis dp[i][j] Open interval (i,j) The most gold coins you can get in a week , stay (i,j) The gold coins obtained by opening the interval can be obtained by dp[i][k] and dp[k][j] To transfer , Punctured at this time k The number of gold coins obtained is ：
dp[i][k]+val[i] * val[k] * val[j]+dp[k][j]
stay (i,j) Open interval can be selected k There are many , From optional k Select the maximum value in to update dp[i][j].

Code

class Solution {
    
    public int maxCoins(int[] nums) {
    
        int n = nums.length;
        //  Create an auxiliary array , And add... At the beginning and end 1, Easy to handle boundary conditions 
        int[] temp = new int[n+2];
        temp[0] = 1;
        temp[n+1] = 1;
        for(int i=0; i<n; i++){
    
            temp[i+1] = nums[i];
        }
        int m = n+2; // Indicates the length of the expanded array 
        int[][] dp = new int[m][m];
        // len Indicates the length of the open interval 
        for(int len=2; len<m; len++){
     // Traverse the length of each interval 
            // i Indicates the left end point of the open interval 
            for(int i=0; i<m-len; i++){
     // The section slides to the right 
                range_best(i,i+len,temp,dp); // Find the most gold coins in the current range 
            }
        }
        return dp[0][m-1];
    }

	// stay (i,j) The most gold coins in the open range 
    private void range_best(int i,int j,int[]nums,int[][]dp){
    
        int max = 0;
        for(int k=i+1;k<j;k++){
     //k Is interval (i,j) In the open section 
            int left = dp[i][k];
            int right = dp[k][j];
            max = Math.max(max,left+right+nums[i]*nums[k]*nums[j]);
        }
        dp[i][j]= max;
    }
}