587. Install fence / Sword finger offer II 014 Anagrams in strings

587. Install fence 【 Difficult questions 】【 A daily topic 】

Ideas ：

Look at the solution directly , Understood for a long time ~ It's in the notes , I hope I can remember how to understand it today when I see it next time …

Code ：

class Solution {
    
    public int[][] outerTrees(int[][] trees) {
    
        int n = trees.length;
        if (n < 4){
    // Tree less than 4 when , All the trees are at the boundary , Must be surrounded , So go straight back to trees
            return trees;
        }
        // Yes trees According to the first  x  Coordinate ordering ,x Press... When the coordinates are equal  y  Coordinate ordering  ( In ascending order )
        Arrays.sort(trees,(a,b)->(a[0] == b[0] ? a[1]-b[1] : a[0]-b[0]));
        int tp = 0;//tp Indicates the subscript of the element at the top of the stack 
        int[] stk = new int[n+10];// adopt stk Array to achieve stack function ,stk What's in it tree stay trees Subscript in 
        boolean[] vis = new boolean[n+10];//vis Array is used to mark whether the tree at the current position needs to be at the boundary , That is, whether it is necessary to use 
        stk[++tp] = 0;// Push the first... Into the stack tree,tp For now 1
        //trees After the array is ordered , first tree Must be on the border , So from the first 2 individual tree To traverse the 
        // Draw the first part of the convex hull , That is, the lower half （ With trees The left and right end lines are bounded ）
        for (int i = 1; i < n; i++) {
    // Traverse all in order tree
            int[] c = trees[i];// use c Represents the coordinates of the current tree 
            while (tp >= 2){
    // When there are more than two elements in the stack , You need to judge whether the current tree is at the boundary 
                // Take out the coordinates of the stack top tree  b, And the coordinates of the last tree at the top of the stack  a
                int[] a = trees[stk[tp-1]], b = trees[stk[tp]];
                // Judgment vector ac Whether in ab On the left 
                if (getArea(a,b,c) < 0){
    
                    //ac stay ab On the right , It means that c More in line with the boundary conditions , Need to be abandoned b node 
                    // So the top node of the stack  b  abandoned , That is to say vis In the corresponding  b  The subscript position of is set to false, At the same time, the subscript at the top of the stack decreases automatically 1, Indicates that the stack top subscript is removed 
                    vis[stk[tp--]] = false;
                }else {
    
                    //ac stay ab On the left , So exit while Loop processing can push the current tree onto the stack 
                    break;
                }
            }
            stk[++tp] = i;// Push the subscript of the current tree into the stack 
            vis[i] = true;// Mark that the current tree has been selected as the boundary 
        }
        int size = tp;// Record that the first part of the convex hull already has several trees 
        // Draw the second part of the convex hull , That is, the upper half of the convex hull 
        for (int i = n-1; i >= 0 ; i--) {
    
            if (vis[i]){
    // If the current tree is already in use , Then directly judge the next tree 
                continue;
            }
            int[] c = trees[i];// Take out the currently traversed tree 
            while (tp > size){
    // When the number of elements in the stack is greater than the number of convex hulls in the first part 
                // Take out the top element of the stack  b  and   The previous element of the top element of the stack  a
                int[] a = trees[stk[tp-1]],b = trees[stk[tp]];
                // Judgment vector ac Is it in a vector ab On the left 
                if (getArea(a,b,c) < 0){
    
                    // If ac stay ab On the right , Then put an element on the top of the stack   abandoned 
                    vis[stk[tp--]] = false;
                }else {
    
                    // If ac stay ab On the left , So exit while loop , Push the current tree onto the stack 
                    break;
                }
            }
            stk[++tp] = i;// Subscript the current tree i Push to stack 
            vis[i] = true;// Mark the current tree as used 
        }
        int[][] ans = new int[tp-1][2];
        for (int i = 1; i < tp; i++) {
    
            ans[i-1] = trees[stk[i]];// The corresponding elements in the stack trees Middle tree deposit ans The number returns 
        }
        return ans;
    }
    public int[] subtraction(int[] a,int[] b){
    // Two dimensional vector subtraction 
        return new int[]{
    a[0]-b[0],a[1]-b[1]};
    }
    public double cross(int[] a,int[] b){
    // Two dimensional vector cross product 
        return a[0]*b[1]-a[1]*b[0];// The result is greater than 0 It's a vector b In vector a left , The result is less than 0 It's a vector b In vector a On the right side 
    }
    public double getArea(int[] a,int[] b,int[] c){
    // Calculate the vector ab Into a vector ac In the process of 
        // The result is greater than 0 It's a vector ac In vector ab left , The result is less than 0 It's a vector ac In vector ab On the right side 
        return cross(subtraction(b,a),subtraction(c,a));
    }
}

The finger of the sword Offer II 014. An anamorphic word in a string 【 Medium question 】

Ideas ：

Statistics s1 The number of occurrences of each character in the , Use a length and s1 Equal sliding windows frame s2, Count the number of occurrences of each character in the window , If s1 The number of occurrences of Chinese characters is the same as s2 The number of characters in the sliding window is the same , So expressed s2 contain s1 An anamorphic word of .
When the window slides , Reduce the number of characters on the left side of the window by 1, Increase the number of characters on the right side of the window by 1 You can update the character count in the window , Instead of re counting the number of characters in the whole window .

Code ;

class Solution {
    
    public boolean checkInclusion(String s1, String s2) {
    
        int n1 = s1.length(),n2 = s2.length();
        if (n1 > n2){
    
            return false;
        }
        int[] cnt1 = new int[26],cnt2 = new int[26];
        char[] chars1 = s1.toCharArray(),chars2 = s2.toCharArray();
        for (char c : chars1) {
    // Statistics string s1 The number of characters in the 
            cnt1[c-'a']++;
        }
        for (int i = 0; i < n1; i++) {
    // Statistics string s2 front n1 The number of characters in each character 
            cnt2[chars2[i]-'a']++;
        }
        if (Arrays.equals(cnt1,cnt2)){
    
            return true;
        }
        for (int i = 1; i < n2-n1+1; i++) {
    
            cnt2[chars2[i-1]-'a']--;// Reduce the number of characters at the left end of the current window by 1
            cnt2[chars2[i+n1-1]-'a']++;// Add... To the number of characters at the right end of the current window 1
            if (Arrays.equals(cnt1,cnt2)){
    
                return true;
            }
        }
        return false;
    }
}