Problem solving -- > online OJ (13)

1. The nearest common ancestor of a binary search tree （235）

Their thinking ：
1. First judgement p,q Whether it is the same node ;
2. secondly , Judge p,q Whether the node is the root node , If one of them is the root node , Just return to the root node directly ;
3. Judge p,q Location of nodes , The characteristics of binary search tree are ： Left < in < Right , Based on this ,p,q Whether the nodes are on the left or right side of the root node, or distributed on both sides of the root node , Make corresponding operation according to the judged result .
4. If left , Call directly recursively , The parameters that will be passed in , The root node is replaced by the left node of the root node , If right , Replace the root node with the right node of the root node . If it is distributed on the left and right sides of the root node , Just return to the root node directly .

class Solution {
    
      public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    
        if(p.val==q.val){
    
            return p;
        }
        if(root.val==p.val || root.val==q.val){
    
            return root;
        }
        if(p.val<root.val && q.val<root.val){
    
            return lowestCommonAncestor(root.left,p,q);
        }else if(p.val>root.val && q.val>root.val){
    
            return lowestCommonAncestor(root.right,p,q);
        }else{
    
            return root;
        }
    }
}

2. Invert the words in the string III(557)

Their thinking ：
Reverse the string , requirement , Break with a space , Each word is reversed independently , therefore , Solve this problem ：
First , You need to split this string with spaces , Split into an array of characters , Then reverse each word , After each word is reversed , Need to add a space . Last , Need to put stringBuilder Type into String type .

class Solution {
    
 public  static String reverseWords(String s) {
    
        String[] ret=s.split(" ");
        StringBuilder stringBuilder=new StringBuilder();
        for(int i=0;i<ret.length;i++){
    
           stringBuilder.append(reverse(ret[i]));
           if(i!=ret.length-1){
    
               stringBuilder.append(" ");
           }
        }
        return stringBuilder.toString();
    }
    public static String reverse(String s){
    
        StringBuilder stringBuilder=new StringBuilder(s);
        return stringBuilder.reverse().toString();

    }
}

3.Fizz Buzz(412)

class Solution {
    
   public List<String> fizzBuzz(int n) {
    
        List<String> list=new ArrayList<>();
        for(int i=1;i<=n;i++){
    
            if(i%3==0 && i%5==0){
    
                list.add("FizzBuzz");
            } else if(i%3==0){
    
                list.add("Fizz");
            }else if(i%5==0){
    
                list.add("Buzz");
            }else{
    
                list.add(i+"");
            }
        }
        return list;
    }
}

4.LRU cache (146)

Their thinking ：
1.LinkedHashMap: Hash table and linked list implementation Map Interface , With predictable iteration order . This implementation is different from HashMap, It maintains a running two-way linked list of all entries . This link list defines an iterative sort , It is usually to insert the key into the map （ Insertion order ） Order in . Please note that , If you re insert the key into the map , The insertion order is not affected . （A key k Re inserted into the map m If so m.containsKey(k) Will return true Call immediately before m.put(k, v) Called .）
2.
There are three parameters ： The first one means ： Initial capacity , The second represents the load factor , The third parameter ： If true： In accordance with Time access sequence , If false, Just insert the data elements in order .
3.
removeEldestEntry： When the number of data inserts is greater than capacity When , Will be accessed in chronological order , Delete the most recently accessed <key,value>.
4.
getOrDefault： If you find it key, Return its corresponding value , If not found , Go straight back to -1.

class LRUCache {
    
int capacity;
    LinkedHashMap<Integer,Integer> linkedHashMap;
    public LRUCache(int capacity) {
    
        this.capacity=capacity;
        linkedHashMap=new LinkedHashMap<Integer, Integer>(capacity,0.75f,true){
    
          @Override
          protected boolean removeEldestEntry(Map.Entry eldest){
    
              return size()>capacity;
          }
        };
    }

    public int get(int key) {
    
        return linkedHashMap.getOrDefault(key,-1);
    }

    public void put(int key, int value) {
    
        linkedHashMap.put(key,value);
    }
}

5. Sort list （148）

Their thinking ：
Solve by merging .
Split the linked list , And then merge .
The time complexity of the merging method :O(N*(log2 N)), Spatial complexity :O(N)

class Solution {
    
  public static ListNode sortList(ListNode head) {
    
       if(head ==null || head.next ==null){
    
           return head;
       }
       ListNode slow =head;
       ListNode fast =head.next;
       // Find the middle node of the linked list , The purpose is to divide the linked list into two .
       while(fast!=null && fast.next!=null){
    
           slow=slow.next;
           fast =fast.next.next;
       }
       ListNode newNode2=slow.next;
       slow.next =null;
       // Recursively call , The purpose is ： Constantly split the linked list , Until it is disassembled into nodes one by one 
       ListNode left = sortList(head);
       ListNode right =sortList(newNode2);
       // Link list splicing 
       //tempHead： As a temporary head node for splicing linked lists 
       ListNode tempHead =new ListNode(0);
       ListNode h=tempHead;
       // Implement linked list splicing 
       while(left!=null && right!=null){
    
           if(left.val<=right.val){
    
               h.next=left;
               left =left.next;
           }else{
    
               h.next=right;
               right=right.next;
           }
            h=h.next;
       }
       // When the left linked list is empty or the right linked list is empty , Connect the non empty linked list to h After node , then , Returns the next node of the temporary node .
       h.next=left!=null?left:right;
       return tempHead.next;
    }
}

6. Product maximum subarray (152)

Their thinking ：
The solution to this problem is ： Maximum product of continuous sequences .
Set up two temporary arrays , A maximum value for storing the results of each calculation , A minimum value for storing the results of each calculation , And then according to the maximum value of each calculation result, it will be continuously updated and replaced max.
Give an example of ：[-2,1,3,-4]
numsMax:[-2,1,3,24]
numsMin:[-2,-2,-6,-6]
max=24

class Solution {
    
       public static int maxProduct(int[] nums) {
    
        int length=nums.length;
        int[] numsMax=new int[length];
        int[] numsMin=new int[length];
        numsMax[0]=nums[0];
        numsMin[0]=nums[0];
        int max=numsMax[0];
        for(int i=1;i<nums.length;i++){
    
            numsMax[i]=Math.max(nums[i],Math.max(numsMax[i-1]*nums[i],numsMin[i-1]*nums[i]));
            numsMin[i]=Math.min(nums[i],Math.min(numsMax[i-1]*nums[i],numsMin[i-1]*nums[i]));
            max=Math.max(numsMax[i],max);
        }
        return max;
    }
}

7. raid homes and plunder houses (198)

Dynamic programming ,
Set up a dp Array , Here, the optimal value of each item is recorded ,
such as :[7,2,9,3,1]
dp[0]=7;
dp[1]=7;(dp[1]=Math.max(dp[0],nums[1]): And the reason for that is :dp The array represents the optimal value of each step , Only... Can be selected for 1 House No. and 2 House No , Our best choice is 1 House No );
dp[2]=16;Math.max(7,9+7)=16
dp[3]=16;Math.max(16,3+7)=16
dp[4]=17;Math.max(16,16+1)=17

class Solution {
    
 public static int rob(int[] nums) {
    
       if(nums.length==1){
    
            return nums[0];
        }
      int length=nums.length;
     int dp[]=new int[length];
     dp[0]=nums[0];
     dp[1]=Math.max(dp[0],nums[1]);
     for(int i=2;i<length;i++){
    
         dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
     }
     return dp[length-1];
    }
}

8. Number of Islands （200）

class Solution {
    
  public static int numIslands(char[][] grid) {
    
        int row=grid.length;
        int col=grid[0].length;
        int result=0;
        for(int i=0;i<row;i++){
    
            for(int j=0;j<col;j++){
    
                if(grid[i][j]=='1'){
    
                    result++;
                    dfs(grid,i,j);
                }
            }
        }
        return result;
    }
    public static void dfs(char[][] grid,int i,int j){
    
        if(i<0 || j<0 || i>=grid.length || j>=grid[0].length || grid[i][j]=='0'){
    
            return;
        }
        grid[i][j]='0';
        dfs(grid,i+1,j); // Next 
        dfs(grid,i-1,j); // On 
        dfs(grid,i,j-1); // Left 
        dfs(grid,i,j+1); // Right 
    }
}

9.Z Font conversion (6)

class Solution {
    
  public String convert(String s, int numRows) {
    
               StringBuilder[] stringBuilders=new StringBuilder[numRows];
        for(int i=0;i<stringBuilders.length;i++){
    
            stringBuilders[i]=new StringBuilder();
        }
       char[] temp=s.toCharArray();
        int length=s.length();
        for(int i=0;i<length;){
    
            for(int row=0;row<numRows&&i<length;row++){
    
                stringBuilders[row].append(temp[i]);
                i++;
            }
            for(int row=numRows-2;row>0&&i<length;row--){
    
                stringBuilders[row].append(temp[i]);
                i++;
            }
        }
        StringBuilder result=new StringBuilder();
        for(StringBuilder t:stringBuilders){
    
            result.append(t);
        }
        return result.toString();
    }
}

10. Construction of binary trees from traversal sequences of preorder and middle order （105）

class Solution {
    
  public TreeNode buildTree(int[] preorder, int[] inorder) {
    
        TreeNode root= createTree(preorder,0,inorder,0,inorder.length-1);
        return root;
    }
    public TreeNode createTree(int[] preorder,int rootIndex,int[] inorder,int left,int right){
    
        if(rootIndex>=preorder.length || left>right){
    
            return null;
        }
        TreeNode root=new TreeNode(preorder[rootIndex]);
        int i=0;
        for(;i<inorder.length;i++){
    
            if(root.val==inorder[i]){
    
                break;
            }
        }
        root.left=createTree(preorder,rootIndex+1,inorder,left,i-1);
        root.right=createTree(preorder,i+rootIndex-left+1,inorder,i+1,right);
        return root;
    }
}