522. longest special sequence II / Sword finger offer II 101 Split equal sum subset

522. The longest special sequence II【 Medium question 】【 A daily topic 】

Ideas ：【 enumeration 】

Procedures are written in code comments , Refer to the official solution . But my execution time is 2ms~

Code ：

class Solution {
    
    public int findLUSlength(String[] strs) {
    
        /** *  For a string in the string array  strs[i]  Come on   If a subsequence of it  sub  It's a special sequence , That is, it is not a subsequence of other strings in the array  *  So this string  strs[i] It is also a special sequence  *  prove ： Reduction to absurdity  *  hypothesis  sub  Is a special sequence , that  sub  It does not appear as a subsequence in any other string  *  So here you are  sub  Add any characters , It still doesn't appear in other strings as a subsequence  *  Because the topic requires finding the longest special sequence , So we just need to enumerate every string in the array , Filter out the longest string that matches the special sequence , That is, the longest special sequence we are looking for  *  So now the problem is reduced to two steps ： * 1. Traverse each string , Determine whether it is a special sequence  * 2. If the string meets the special sequence requirements , Update the longest special sequence length  max, The function finally returns  max *  For the first 1 Step by step , Can be converted to , Determine whether the current string is a subsequence of other strings in the array except itself , yes   It indicates that the current string is a special sequence , no   Is not a special sequence  */
        int max = -1,n = strs.length;
        // Double loop traversal string array , Screening strs[i] Whether it is a special sequence 
        for (int i = 0; i < n; i++) {
    
            boolean flag = true;
            for (int j = 0; j < n; j++) {
    
                if (i == j){
    
                    continue;
                }
                String s1 = strs[i],s2 = strs[j];
                int n1 = s1.length(),n2 = s2.length();
                //s1 Length ratio of s2 Also long ,s1 It can't be s2 The subsequence , Don't go on judging 
                if (n1 > n2){
    
                    continue;
                }else if (n1 == n2){
    
                    //s1 The length of s2 equal 
                    // If s1 And s2 Unequal , be s1 No s2 The subsequence 
                    // If s1 And s2 equal , be s1 yes s2 The subsequence , The location of the sign is flase, Inner layer for Loop exit 
                    if (s1.equals(s2)){
    
                        flag = false;
                        break;
                    }else {
    
                        continue;
                    }
                }
                // Judge s1 Whether it is s2 The subsequence ( here  n1 < n2)
                int p1 = 0,p2 = 0;
                while (p1 < n1 && p2 < n2){
    
                    // If p1 Character and p2 The characters are equal , be p1 And p2 Shift right 
                    if (s1.charAt(p1) == s2.charAt(p2)){
    
                        p1++;
                        p2++;
                    }else {
    
                        // otherwise , Only will p2 Move right 
                        p2++;
                    }
                }
                // If s1 End of normal traversal , explain s1 yes s2 The subsequence , The location of the sign is false, Inner layer for Loop exit 
                if (p1 == n1){
    
                    flag = false;
                    break;
                }
            }
            // After screening ,strs[i] Passed the test , It's a special sequence , Update the length of the longest special sequence 
            if (flag){
    
                max = Math.max(max,strs[i].length());
            }
        }
        return max;
    }
}

---

The finger of the sword Offer II 101. To divide into equal and subsets 【 Simple questions 】

Ideas ：【 Dynamic programming 】

First order dp And second order dp, Write according to the answer ~, This is a dynamic programming problem. I really didn't expect .

Code ：【 Second order dp】

class Solution {
    
    public boolean canPartition(int[] nums) {
    
        // It should be divided into two parts , Then the array length is at least 2,
        int n = nums.length;
        if (n < 2){
    
            return false;
        }
        // It should be divided into two parts of equal sum , The sum of each part must be half of the total , So you should first find the sum of the arrays sum, In this way, the goal and 
        int sum = 0,max = 0;
        for (int num : nums) {
    
            max = Math.max(max,num);
            sum += num;
        }
        // If sum Is odd , Then the array can not be divided into elements and equal parts 
        if(sum % 2 != 0){
    
            return false;
        }
        int target = sum / 2;
        //max > target, It is impossible to divide an array into elements and equal parts 
        if (max > target){
    
            return false;
        }
        //max == target  It must be divided into two parts ,max As part of , The rest of the elements are another part 
        if (max == target){
    
            return true;
        }

        // Definition dp Array  dp[i][j] Represents array subscript  [0,i)  Within the scope of , Select whether several elements can make elements and reach j  Then we just need to find dp[n-1][target] Is it true that will do 
        boolean[][] dp = new boolean[n][target+1];
        // The boundary conditions : j=0 when ,dp[i][0] = true ; i=0 when ,dp[0][nums[0]] = true.
        dp[0][nums[0]] = true;
        for (int i = 0; i < n; i++) {
    
            dp[i][0] = true;
        }
        for (int i = 1; i < n; i++) {
    
            for (int j = 1; j <= target; j++) {
    
                if (j >= nums[i]){
    
                    // No choice nums[i] Elements , be dp[i][j] Depending on  dp[i-1][j]
                    // choice  nums[i] Elements , be dp[i][j] Depending on  dp[i-1][j-nums[i]]
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];
                }else {
    
                    // because  j < nums[i]  It is impossible to choose nums[i] Elements 
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[n-1][target];
    }
}

Code ：【 First order dp】

class Solution {
    
    public boolean canPartition(int[] nums) {
    
        // It should be divided into two parts , Then the array length is at least 2,
        int n = nums.length;
        if (n < 2){
    
            return false;
        }
        // It should be divided into two parts of equal sum , The sum of each part must be half of the total , So you should first find the sum of the arrays sum, In this way, the goal and 
        int sum = 0,max = 0;
        for (int num : nums) {
    
            max = Math.max(max,num);
            sum += num;
        }
        // If sum Is odd , Then the array can not be divided into elements and equal parts 
        if(sum % 2 != 0){
    
            return false;
        }
        int target = sum / 2;
        //max > target, It is impossible to divide an array into elements and equal parts 
        if (max > target){
    
            return false;
        }
        //max == target  It must be divided into two parts ,max As part of , The rest of the elements are another part 
        if (max == target){
    
            return true;
        }
        // Definition dp Array  dp[j] Indicates that the current array is within the optional range , Select whether several elements can make elements and reach j, Then we find that when the optional range is the entire array ,dp[target] Is it true that will do 
        boolean[] dp = new boolean[target+1];
        // The boundary conditions ：j = 0  when , Must be  true
        dp[0] = true;
        for (int num : nums) {
    
            for (int j = target; j >= num; j--) {
    
                /*if (j >= nums[i]){ // choice nums[i] Elements , be dp[j] Depending on dp[j-nums[i]] // No choice nums[i] Elements , be dp[j] Immobility  dp[j] = dp[j] || dp[j-nums[i]]; }else { //j < nums[i] when , It is impossible to choose nums[i]  therefore  dp[j] Keep still  dp[j] = dp[j]; }  So the transfer equations are summarized as follows  */
                dp[j] = dp[j] || dp[j - num];
            }
        }
        return dp[target];
    }
}