Daily question brushing record (III)

The first question is : Brackets

LeetCode: Interview questions 08.09. Brackets
describe :
Brackets . Design an algorithm , Print n All legal for parentheses （ for example , One to one correspondence between opening and closing ） Combine .
explain ： The solution set cannot contain duplicate subsets .
for example , give n = 3, The generated result is ：

[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

Their thinking :

Use backtracking here .
left Indicates the number of left parentheses . right Indicates the number of closing parentheses .
Build string , In case of disqualification, stop , Join if you meet the requirements list in
Pay attention to the pruning here ,

Code implementation :

class Solution {
    
    public List<String> generateParenthesis(int n) {
    
        List<String> res = new ArrayList<>();
        backstrack(res,"",n,n);
        return res;
    }

    public void backstrack(List<String> res,String str,int left,int right) {
    
    	//  prune 1 left  perhaps  right  Less than 0 The situation of 
        if(left < 0 || right < 0) return;
        //  prune 2 left > right The situation of 
        if(left > right) return;
        // left and right All for 0  At this point, the conditions are met 
        if(left == 0 && right == 0) {
    
            res.add(str);
            return;
        }
        backstrack(res,str+"(",left-1,right);
        backstrack(res,str+")",left,right-1);
    }
}

The second question is : COINS

LeetCode: Interview questions 08.11. COINS
describe :
COINS . An unlimited number of coins , The value of the currency is 25 branch 、10 branch 、5 Points and 1 branch , Write code to calculate n There are several ways of expression .( The result could be big , You need to model the results 1000000007)

Their thinking :

Dynamic planning ideas :

• state F(i) : Indicates the current round up i The way
• State transition equation : F(i) = (F(i) + F(i-coin)) %1000000007
• The initial state : F(0) = 1; Because it can be drawn out with coins .
• Return results : F(n)

here coins = { 1, 5, 10, 25 };
If I just walk through it , There will be repetition , for example 5 + 10 and 10 + 5
Avoid this situation , You can use small loops , Using only one coin per small cycle can avoid repetition .

Code implementation :

class Solution {
    
    public int waysToChange(int n) {
    
    	//  Current coin situation 
        int[] coins = {
    1,5,10,25};
        int[] dp = new int[n+1];
        //  for example  dp[1] = dp[1] + dp[0],  This means that the current coin can be used , Initialization is 1
        dp[0] = 1;
        //  The outer layer traverses this coins Array 
        for(int coin : coins) {
    
        	//  Inner layer   Traverse a coin 
            for(int i = coin;i <= n; i++) {
    
                dp[i] = (dp[i] + dp[i-coin]) % 1000000007;
            }
        }
        return dp[n];
    }
}

Third question : Morpheme phrase

LeetCode: Interview questions 10.02. Morpheme phrase
describe :
Write a method , Sort the string array , Put all the morphemes together . Morphemes refer to the same letters , But arrange different strings .

Their thinking :

1. Traverse , Let the traversed string be sorted , Add to HashMap in key Is the sorted string , value For one list
2. The sorted characters are the same , Join in the same list in
3. Add a new one if it is different list.
4. After the traversal , Put all the list Add them together

Code implementation :

class Solution {
    
    public List<List<String>> groupAnagrams(String[] strs) {
    
        List<List<String>> list = new ArrayList<>();
        Map<String,List<String>> map = new HashMap<>();
        for(String str : strs) {
    
        	//  Sort 
            char[] ch = str.toCharArray();
            Arrays.sort(ch);
            //  The sorted character array becomes a string 
            String s = new String(ch);
            if(!map.containsKey(s)) {
    
            // There is no such thing as the same key The situation of ,  You need to create a new list
                List<String> ret = new ArrayList<>();
                ret.add(str);
                map.put(s,ret);
            }else{
    
            // There is the same key The situation of ,  Need to get the previous list, Then add data 
                map.get(s).add(str);
            }
        }
        //  Use keySet The way to get key,  And then put all the value Values are added together .
        for(String key : map.keySet()) {
    
            list.add(map.get(key));
        }
        return list;
    }
}

Fourth question : Minimum difference

LeetCode: Interview questions 16.06. Minimum difference
describe :
Given two arrays of integers a and b, Calculate a pair of values with the absolute value of the minimum difference （ Take one value from each array ）, And return the difference of the logarithm

Their thinking :

1. Define two pointers , left right, Sort two arrays .
2. use ret Record the current a[left] - b[right] The difference between the
   If ret > 0, a[left]>b[right], let right++, In order to make b It's closer a Value
   If ret < 0, a[left]<b[right], let left++, In order to make a It's closer b Value
   Record The smallest ret

Code implementation :

class Solution {
    
    public int smallestDifference(int[] a, int[] b) {
    
       	//  Prioritize 
        Arrays.sort(a);
        Arrays.sort(b);
        //  Notice the overflow here 
        long min = Integer.MAX_VALUE;
        int left = 0;
        int right = 0;
        while(left < a.length && right < b.length) {
    
            // long  Prevent overflow 
            long ret = a[left] - b[right];
            //  Record minimum 
            min = Math.min(Math.abs(ret),min);
            //  Subtract the closer values 
            if(ret < 0) left++;
            else right++;
        }
        return (int)min;
    }
}

Fifth question : The first common ancestor

LeetCode: Interview questions 04.08. The first common ancestor
describe :
Design and implement an algorithm , Find the first common ancestor of two nodes in the binary tree . Do not store other nodes in another data structure . Be careful ： This is not necessarily a binary search tree .

for example , Given the following binary tree : root = [3,5,1,6,2,0,8,null,null,7,4]

Their thinking :

1. Possible situations :
   ①p and q There is a root node , Then the root node is the nearest common ancestor
   ②p and q Not under the same subtree , Then their father is the common ancestor
   ③p and q Under the same subtree
2. Recursive left and right subtrees
   ① Left and right subtrees are not empty , that root Is the common ancestor
   ② The left subtree is empty , The right subtree is not empty , Then the node found in the right tree is the common ancestor
   ③ The left subtree is not empty , The right subtree is empty , Then the node found in the left tree is the common ancestor

Code implementation :

class Solution {
    
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    
    	//  Situation 1 :  The root node is empty 
        if (root == null) return null;
        //  Situation two : p or q Root node 
        if (p == root || q == root) return root;
        //  Traverse the left and right subtrees 
        TreeNode leftNode = lowestCommonAncestor(root.left,p,q);
        TreeNode rightNode = lowestCommonAncestor(root.right,p,q);
        //  It's not empty. ,  that root Is the common ancestor 
        if(leftNode != null && rightNode != null) {
    
            return root;
        }
        //  The left subtree is empty ,  The node of the right tree is the common ancestor 
        if(leftNode == null){
    
            return rightNode;
        }
        //  The right subtree is empty ,  The node of the left tree is the common ancestor 
        if(rightNode == null) {
    
            return leftNode;
        }
        return null;
    }
}

Sixth question : Minimum height tree

LeetCode: Interview questions 04.02. Minimum height tree
describe :
Given an ordered array of integers , The elements are different and in ascending order , Write an algorithm , Create a minimum height binary search tree .

Their thinking :

1. Here we use the dichotomy method to segment , Every time you get a middle point , Then construct a node .
2. Then take a middle point on the left , Construct the left node , And then on the right, get a middle point , Construct the right node .
   

Code implementation :

class Solution {
    
    public TreeNode sortedArrayToBST(int[] nums) {
    
        return makeBST(nums,0,nums.length-1);
    }
    public TreeNode makeBST(int[] nums, int left, int right) {
    
        //  If left>right It's not legal 
        if (left > right) {
    
            return null;
        }
        //  Prevent overflow here ,  Use left+(right-left)/2
        int mid = left + (right - left) / 2;
        //  Construct a node 
        TreeNode node = new TreeNode(nums[mid]);
        //  Constructing left and right subtrees 
        node.left = makeBST(nums, left, mid - 1);
        node.right = makeBST(nums, mid+1, right);
        return node;
    }
}