算法日常

[ZhangHanwen96]

• 03/07

  • 用post order遍历获得的array重建二叉树
  • 字节面试题-子串问题

• 03/08

  • Longest Common Subsequence
  • Longest Common Substring
  • Longest Palindromic Substring
  • Longest Increasing Subsequence()
  • Container With Most Water
  • leetcode 79、剑12 - 矩阵中的路径

• 03/10

  • 62. 不同路径
  • 63. 不同路径II
  • 980. 不同路径III
  • 680. 验证回文字符串 II

• 03/11

  • [42 接雨水]
  • 股票I
  • 股票II

• 03.12

  • [ ]
  • 232. 用栈实现队列
  • 翻转二叉树
  • [全排列(#全排列)
  • 78 子集
  • 排序链表
  • 23. 合并K个升序链表

• 3.13

  • 34. 在排序数组中查找元素的第一个和最后一个位置
  • 695. 岛屿的最大面积

• 3.15
  - 236 二叉树的最近公共祖先
  - 22 括号生成
  - 104 二叉树最大深度

• 3.17

  • 螺旋矩阵
  • 二叉树的右视图

• 3.19

  • 二叉树的镜像

用post order遍历获得的array重建二叉树

Link

public static Node process1(int[] postArr, int L, int R) {
    if(L > R) {
        return null;
    }
    Node head = new Node(postArr[R]);
    if(L == R) return head;

    int M = L - 1;
    for(int i = 0; i < R; i ++) {
        if(postArr[i] < postArr[R]) {
            M = i;
        }
    }

    head.left = process1(postArr, L, M);
    head.right = process1(postArr, M+1, R-1);

    return head
}

// 更容易理解的分类判断
public static Node process3(int[] postArr, int L, int R) {
    if(L > R) {
        return null;
    }
    Node head = new Node(postArr[R]);
    if(L == R) return head;

    int M = -1;
    for(int i = 0; i < R; i ++) {
        if(postArr[i] < postArr[R]) {
            M = i;
        }
    }

    if(M == -1) {
        head.right = process3(postArr, L, R-1);
    } else if(M == R - 1) {
        head.left = process3(postArr, L, R - 1);
    } else {
        head.left = process3(postArr, L, M);
        head.right = process3(postArr, M+1, R-1);
    }

    return head
}

// 利用二分法寻找M
public static Node process2(int[] postArr, int L, int R) {
    if(L > R) {
        return null;
    }
    Node head = new Node(postArr[R]);
    if(L == R) return head;

    int M = L - 1;
    //二分
    int left = L;
    int right = R - 1;
    while(left <= right) {
        int mid = left + ((right - left) >> 1);
        if(postArr[mid] < postArr[R]) {
            M = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    head.left = process1(postArr, L, M);
    head.right = process1(postArr, M+1, R-1);

    return head
}

For test only, generate random BST

public static Node generateRandomBST(int min, int max, int N) {
    if(min > max) return null;
    return createTree(min, max, level, N);
}

public static Node createTree(int min, int max, int level, int N) {
    if(min > max || level > N) {
        return null;
    }
    Node head = new Node(random(min, max));
    head.left = createTree(min, head.value - 1, level +1, N);
    head.right = createTree(head.value + 1, max, level +1, N);

    return head;
}

public static int random(int min, int max) {
    return min + (int) (Math.random() * (max - min + 1));
}

字节面试题-子串问题

'acdbsgee' 里包含 'adcb' 顺序不重要

// 暴力循环方法
public static int contain(String s, String a) {
    if(s == null || a == null || s.length() < a.length()) {
        return -1;
    }

    char[] str = s.toCharArray();
    char[] aim = a.toCharArray();

    for(int i = 0; i <= str.length - aim.length; i ++) {
        if(isCountEqual(str, aim, i)) {
            return i;
        }
    }
}

public static Boolean isCountEqual(char[] str, char[] aim, int L) {
    int[] count = new int[256];
    for(char c : aim) {
        count[c]++;
    }

    for(int i = 0; i < aim.length; i++) {
        if(-- count[str[i+L]] < 0) {
            return false;
        }
    }

    return true;
}


public static int contain2(String s, String a) {
    char[] aim = a.toCharArray();
    char[] str = s.toCharArray();
    int[] count = new int[256];

    for(char c : aim) {
        count[c]++;
    }

    int M = aim.length;
    int inValidtimes = 0;
    int R = 0;

    for(; R < M; R ++) {
        if(-- count[R] < 0) {
            inValidtimes ++;
        }
    }

    for(; R < str.length; R++) {
        if(inValidtimes == 0) {
            return R - M;
        }

        if(--count[R] < 0 ) {
            inValidtimes ++;
        }

        if(count[R-M]++ < 0) {
            inValidtimes --;
        }
    }

    return inValidtimes == 0 ? R - M : -1;
}

LC substring

public static String LCS(String s1, String s2) {
    int len1 = s1.length();
    int len2 = s2.length();

    int[][] dp = new int[len1][len2]
    int lastI = 0;
    int maxLen = 0;

    for(int i = 0; i <= len1; i++) {
        for(int j = 0; j <= len2; j++) {
            if((i==0 || j==0)) dp[i][j] = 0;
            else if(s1.charAt(i-1) == s2.charAt(j-1)) {
                dp[i][j] = d[i-1][j-1] +1;
                if(dp[i][j] > maxLen) {
                    maxLen = dp[i][j];
                    lastI = i;
                }
            }
        }
    }

    if(maxLen == 0) return "-1";
    return s1.substring(lastI - maxLen, lastI + 1);
}

LC subsequence

public static int LCS2(String s1, String s2) {
    int len1 = s1.length();
    int len2 = s2.length();

    int[][] dp = new int[len1+1][len2+1];

    
    for(int i = 0; i <= len1; i++) {
        for(int j = 0; j <= len2; j++) {
            if((i==0 || j==0)) dp[i][j] = 0;
            else if(s1.charAt(i-1) == s2.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1] +1;
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }

    return dp[len1][len2];
}

Longest Palindromic Substring

public String LP(String s) {
    if(s == null || s.length() == 0) {
        return "";
    }
    int len = s.length();
    int start = 0, end = 0, max = 0;
    boolean[][] dp = new boolean[len][len];

    for(int i = 0; i < len; i++) {
        for(int j = 0; j <=i; j++) {
            if(s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j-1][i-1])) {
                dp[j][i] = true;
            }
            if(dp[j][i] && max < i - j + 1) {
                max = i - j + 1;
                start = j;
                end = i;
            }
        }
    }

    return s.substring(start,  end + 1);
}

Longest Increasing Subsequence

 public int lengthOfLIS(int[] nums) {
        if(nums.length==1){
            return nums.length;
        }
        
        int[] a = new int[nums.length];
        int ans = 0;
      
        for(int i = 0; i < a.length; ++i){
            a[i] = 1; 
        }
        
        for(int i = 1; i < a.length; ++i){
            for(int j = 0; j < i; ++j){
                if(nums[j] < nums[i]){
                    
                    a[i] = Math.max(a[j]+1, a[i]);
                }
            }
            ans = Math.max(ans, a[i]);
        }
        return ans;
        
    }

Container With Most Water

// 用双指针，因为装水的瓶颈在height最低的那个木板，所以每次按最低的算
    public int maxArea(int[] height) {
        int ans = 0;
        
        int i = 0, j = height.length-1;
        
        while(i < j) {
            ans = Math.max(ans, Math.min(height[i], height[j]) * (j - i));
            if(height[i] <= height[j]) {
                i ++;
            } else {
                j --;
            }
        }
        
        return ans;
    }

矩阵中的路径

    public boolean exist(char[][] board, String word) {
         if (board == null || board[0] == null || board.length == 0 || board[0].length == 0 || word == null || word.equals("")) {
            return false;
        }

        boolean[][] visited = new boolean[board.length][board[0].length];
        char[] wordArr = word.toCharArray();

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == word.charAt(0)) {
                    if (dfs(board, wordArr, i, j, 1, visited)) return true;
                }
            }
        }

        return false;
    }



    public boolean dfs(char[][] board, char[] wordArr, int i, int j, int len, boolean[][] visited) {
        if(i < 0 || j < 0 || i == board.length || j == board[0].length || wordArr[len-1] != board[i][j] || visited[i][j]) {
            return false;
        }

        if(len == wordArr.length) {
            return true;
        }
        
        visited[i][j] = true;

        boolean ans = dfs(board, wordArr, i+1, j, len + 1, visited) || dfs(board, wordArr, i-1, j, len + 1, visited) || dfs(board, wordArr, i, j+1, len + 1, visited)|| dfs(board, wordArr, i, j-1, len + 1, visited);

        visited[i][j] = false;

        return ans;
    }

不同路径

 ```java class Solution { public int count = 0; public int uniquePaths(int m, int n) { int[][] dp = new int[m][n];

   for(int i = 0; i < m; i ++) {
       dp[i][0] = 1;
   }

    for(int i = 0; i < n; i ++) {
       dp[0][i] = 1;
    }

    for(int i = 1; i < m; i++) {
        for(int j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }

    return dp[m-1][n-1];
}

}

不同路径II

```java class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { if (obstacleGrid == null || obstacleGrid.length == 0) { return 0; } int rows = obstacleGrid.length; int cols = obstacleGrid[0].length;

      int[][] dp = new int[rows][cols];

      for(int i = 0; i < rows && obstacleGrid[i][0] != 1; ++ i) {
          dp[i][0] = 1;
      }

      for(int i = 0; i < cols && obstacleGrid[0][i] != 1; ++ i) {
          dp[0][i] = 1;
      }

      for(int i = 1; i < rows; ++ i) {
          for(int j = 1; j < cols; ++ j) {
              if(obstacleGrid[i][j] != 1) {
                  dp[i][j] =  dp[i-1][j] + dp[i][j-1];
              }
          }
      }
      return dp[rows - 1][cols - 1];
  }

}

## 不同路径III
<a name='不同路径III'>

```java
class Solution {
    public int uniquePathsIII(int[][] grid) {
        int count = 0, x = 0, y = 0;
        for(int i = 0; i <grid.length; i++ ) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j]==1) {
                    x=i;
                    y=j;
                }
                if(grid[i][j] == 0) count ++;
            }
        }

        return dfs(grid, x, y, grid.length, grid[0].length, count+1, 0);
    }

    public int dfs(int[][] grid, int x, int y, int rows, int cols, int total, int current) {
        if(x < 0 || y < 0 || x >= rows || y >= cols || grid[x][y] == -1) return 0;


        
        if(grid[x][y] == 2) {
            return current == total ? 1 : 0;
        }

        grid[x][y] = -1;
        int ans = 0;

        ans += dfs(grid, x-1, y, rows, cols, total, current +1);
        ans +=dfs(grid, x+1, y, rows, cols, total, current +1);
        ans +=dfs(grid, x, y-1, rows, cols, total, current +1);
        ans +=dfs(grid, x, y+1, rows, cols, total, current +1);

        grid[x][y] = 0;

        return ans;
    }
}

验证回文字符串 II

class Solution {
    public boolean validPalindrome(String s) {
        int len = s.length();
        if(len < 2) return true;

        int i = 0, j = len - 1;

        while(i < j) {
            if(s.charAt(i) != s.charAt(j)) {
                return isValid(s, i+1, j) || isValid(s, i, j - 1);
            }
            i++;
            j--;
        }

        return true;
    }

    public boolean isValid(String s, int start, int end) {
        while(start < end) {
            if(s.charAt(start++) != s.charAt(end--)){
                return false;
            }
        }
           
        return true;
    }
}

无重复字符的最长子串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashSet<Character> set = new HashSet<>();
        int i =0, j = 0, max = 0;
        while(j < s.length()){
            if(!set.contains(s.charAt(j))){
                set.add(s.charAt(j++));
                max = Math.max(max, set.size());
            }else{
                set.remove(s.charAt(i++));
            }
            
        }
        return max;
    }
}

 public int lengthOfLongestSubstring(String s) {
        if (s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max=0;
        for (int i=0, j=0; i<s.length(); ++i){
            if (map.containsKey(s.charAt(i))){
                j = Math.max(j,map.get(s.charAt(i))+1);
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-j+1);
        }
        return max;
    }

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int result = 0;
        int[] cache = new int[256];
        for (int i = 0, j = 0; i < s.length(); i++) {
            j = (cache[s.charAt(i)] > 0) ? Math.max(j, cache[s.charAt(i)]) : j;
            cache[s.charAt(i)] = i + 1;
            result = Math.max(result, i - j + 1);
        }
        return result;
    }
}

反转链表

class Solution {
   public ListNode reverseList(ListNode head) {
       ListNode pre = null;
       ListNode cur = head;
      
       while(cur != null) {
           ListNode next = cur.next;
           
           cur.next = pre;
           pre = cur;
           cur = next;
       }
       
       return pre;
   }
}

21 合并2个有序链

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
        if(l1 == null) return l2;
        else if(l2 == null) return l1;
        
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            
            curr = curr.next;
            
          
        }
        
        curr.next = (l1 == null) ? l2 : l1;
        return dummy.next;
    }
}

42 接雨水

// 先进行优化，创建两个array
class Solution {
    public int trap(int[] arr) {
        if(arr == null || arr.length < 2) {
            return 0;
        }
        
        int N = arr.length;
        
        int[] leftMax  = new int[N];
        int[] rightMax  = new int[N];
        
        leftMax[0] = arr[0];
        rightMax[N-1] = arr[N-1];
        
        for(int i = 1; i < N; i++) {
           leftMax[i] = Math.max(leftMax[i-1], arr[i]);
        }
        
         for(int i = N-2; i >= 0; i--) {
           rightMax[i] = Math.max(leftMax[i+1], arr[i]);
        }
        
        int water = 0;
        for(int i = 1; i < N -1; i ++) {
            water += Math.max(Math.min(rightMax[i+ 1], leftMax[i-1]) - arr[i], 0);
        }
        
        return water;
    }
}

// 双指针
  int left = 0, right = arr.length - 1;
        int ans = 0;
        int leftMax = 0, rightMax = 0;
        while(left < right) {
            if(arr[left] < arr[right]){
                arr[left] >= leftMax ? leftMax = arr[left] : ans += (leftMax - arr[left]);
                ++ left;
            } else {
                arr[right] >= rightMax ? rightMax = arr[right]: ans += (rightMax - arr[right]);
                -- right;
            }
        }
        
        return ans;

215. Kth Largest Element in an Array

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> largeK = new PriorityQueue<Integer>(k + 1);

        for(int el : nums) {
            largeK.add(el);
            if (largeK.size() > k) {
                largeK.poll();
            }
        }

        return largeK.poll();
        }
}

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        return findKth(a, 0, n-1, K);
    }

      public int findKth(int[] a, int low, int high, int k) {
        int part = partition(a, low, high);
        
        if(k == part - low + 1) return a[part];
        else if(k > part - low + 1) return findKth(a, part + 1, high, k - part + low -1);
        else return findKth(a, low, part -1, k);    
    }
                     
        
public int partition(int[] a, int left, int right) {
        int pivot = a[right];
        int low = left, high = right;
        while(low < high) {
            while(low<high && a[low] >= pivot) {
                low ++;
            }
            while(low<high && a[high] <= pivot) {
                high --;
            }
            int temp = a[low];
            a[low] = a[high];
            a[high] = temp;
        }
        int temp = a[low];
        a[low] = pivot;
        a[right] = temp;
        
        return low;
    }
}

3Sum

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        if (n <= 1) return new ArrayList<>();
        
        Arrays.sort(nums);
        List<List<Integer>> res = new LinkedList<>(); 
        
        for (int i = 0; i < n - 2; i++) {
             //为了保证不加入重复的 list,因为是有序的，所以如果和前一个元素相同，只需要继续后移就可以
            if (i==0 || (i > 0 && nums[i] != nums[i-1])) {
                int low = i + 1, high = n - 1, sum = 0 - nums[i];
                
                while (low < high) {
                    if (nums[low] + nums[high] == sum) {
                            res.add(Arrays.asList(nums[i], nums[low], nums[high]));
                            while (low < high && nums[low] == nums[low+1]) low++;
                            while (low < high && nums[high] == nums[high-1]) high --;
                            low ++;
                            high --;
                            
                        
                    } else if (nums[low] + nums[high] < sum) {
                        low ++;
                    } else {
                        high --;
                    }
                }
            }
        }
        
        
        return res;

    }
}

股票I

```java class Solution { public int maxProfit(int[] prices) { int maxcur = 0, maxsofar = 0;

    for(int i=1; i < prices.length; ++i){
        maxcur = Math.max(0, maxcur += prices[i] - prices[i-1]);
        maxsofar = Math.max(maxsofar, maxcur);
    }
    return maxsofar;
}

}

```java
    public int maxProfit(int[] prices) {
        int min = Integer.MAX_VALUE, max = 0;
        for (int price: prices) {
            min = Math.min(min, price);
            max = Math.max(price - min, max);
        }
        return max;
    }

股票II

class Solution {
    public int maxProfit(int[] prices) {
        int maxprofit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1])
                maxprofit += prices[i] - prices[i - 1];
        }
        return maxprofit;
    }
}

207 课程表

拓扑排序 + 检测环 DFS

class Solution {
    List<List<Integer>> edges;
    int[] visited;
    boolean valid = true;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<>();
        for (int i = 0; i < numCourses; ++i) {
            edges.add(new ArrayList<Integer>());
        }
        visited = new int[edges.size()];

        for(int[] p : prerequisites) {
            edges.get(p[1]).add(p[0]);
        }

        for(int i = 0; i < edges.size() & valid; i++) {
            if(visited[i] == 0) {
                dfs(i);
            }
        }

        return valid;
    }

    public void dfs(int u) {
        visited[u] = 1;

        for(int v : edges.get(u)) {
            if(visited[v] == 0) {
                dfs(v);
                if(!valid) {
                    return;
                }
            } else if(visited[v] == 1) {
                valid = false;
                return;
            }
        }

        visited[u] = 2;
    }
}

BFS

// to do

用栈实现队列

class MyQueue {
    private Stack<Integer> a;// 输入栈
    private Stack<Integer> b;// 输出栈
    /** Initialize your data structure here. */
    public MyQueue() {
        a = new Stack<>();
        b = new Stack<>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        a.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if(b.isEmpty()) {
            while(!a.isEmpty()) {
                b.push(a.pop());
            }
        }
        return b.pop();
    }
    
    /** Get the front element. */
    public int peek() {
         if(b.isEmpty()) {
            while(!a.isEmpty()) {
                b.push(a.pop());
            }
        }
        return b.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return a.isEmpty() && b.isEmpty();
    }
}

翻转二叉树

class Solution {
    public TreeNode invertTree(TreeNode root) {
//         if (root == null) 
//             return null;
        
        
//         TreeNode right = invertTree(root.right);
//         TreeNode left = invertTree(root.left);
        
//         root.left = right;
//         root.right = left;
        
//         return root;
        
        if (root == null) return null;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        
        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            TreeNode temp = current.left;
            current.left = current.right;
            current.right = temp;
            if (current.left != null) queue.add(current.left);
            if (current.right != null) queue.add(current.right);
        }
        
        
        
        return root;
    }
}

46. 全排列

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int[] visited = new int[nums.length];

        backtrack(res, nums, visited, new ArrayList<>());

        return res;
    }

    public void backtrack(List<List<Integer>> res, int[] nums, int[] visited, ArrayList<Integer> temp) {

        if(temp.size() == nums.length) {
            res.add(new ArrayList<>(temp));
            return;
        }

        for(int i = 0; i < nums.length; i++) {
            if(visited[i] == 1) continue;
            visited[i] = 1;
            temp.add(nums[i]);
            backtrack(res, nums, visited, temp);
            temp.remove(temp.size() - 1);
            visited[i] = 0;
        }
    }
}

子集

class Solution {
    public List<List<Integer>> res=new ArrayList<>();
    // public List<List<Integer>> subsets(int[] nums) {
    //     List<Integer> temp = new ArrayList<>();
    //     dfs(nums, temp,  0);
    //     res.add(new ArrayList<>());
    //     return res;
    // }

    // public void dfs(int[] nums, List<Integer> temp, int len) {

    //     for(int i = len; i < nums.length; i++) {
    //         temp.add(nums[i]);
    //         res.add(new ArrayList<>(temp));
           
    //          dfs(nums, temp, i + 1);
    //          temp.remove(temp.size() - 1);
    //     }
    // }

    public List<List<Integer>> subsets(int[] nums) {
        res.add(new ArrayList<>());

        for(int num : nums) {
            for(int i = 0, j=res.size(); i < j; i ++) {
                List<Integer> list = new ArrayList(res.get(i));
                list.add(num);
                res.add(list);
            }
        }

        return res;
    }
}

排序链表

class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;

        ListNode mid = findMid(head);
        ListNode rightNode = mid.next;
        mid.next = null;

        ListNode left = sortList(head);
        ListNode right = sortList(rightNode);

        return merge(left, right);

    }

    public ListNode findMid(ListNode head) {
        if(head == null || head.next == null) return head;

        ListNode fast = head.next, slow = head;

        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast= fast.next.next;
        }

        return slow;
    }

    public ListNode merge(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;

        while(left != null && right != null) {
            if(left.val < right.val) {
                cur.next = left;
                left = left.next;
            } else {
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;
        }

        cur.next = left != null ? left : right;

        return dummy.next;
    }
}

合并K个升序链表

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0) {
            return null;
        }

        return mergeKLists(lists, 0, lists.length - 1);

    }

    public ListNode mergeKLists(ListNode[] lists, int low, int high) {
        if(low >= high) return lists[low];

        int mid = low + ((high - low) >> 1);

        ListNode left = mergeKLists(lists, low, mid);
        ListNode right = mergeKLists(lists, mid + 1, high);

        return merge(left ,right);
    }

    public ListNode merge(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;

        while(left != null && right != null) {
            if(left.val < right.val) {
                cur.next = left;
                left = left.next;
            } else {
                cur.next = right;
                right = right.next;
            }

            cur = cur.next;
        }
        cur.next = left != null ? left : right;

        return dummy.next;
    }
}

695. 岛屿的最大面积

class Solution {
    public int maxAreaOfIsland(int[][] grid) {

        int max = 0;
        for(int i = 0; i < grid.length; ++ i) {
            for(int j = 0; j < grid[0].length; ++ j) {
                if(grid[i][j] == 1) {
                    max = Math.max(dfs(grid, i, j), max);
                }
            }
        }

        return max;
    }

    public int dfs(int[][] grid, int i, int j) {
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) return 0;
        int count = 1;


        grid[i][j] = 0;
        count += dfs(grid, i + 1, j);
        count += dfs(grid, i -1, j);
        count += dfs(grid, i, j + 1);
        count += dfs(grid, i, j - 1);

        return count;
    }
}

34. 在排序数组中查找元素的第一个和最后一个位置

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int right = search(nums, target, true);
        int left = search(nums, target, false);

        return new int[] {left, right};
    }


    // find the rightmost index of the target if <right> is true
    public int search(int[] nums, int target, boolean right) {
        int low = 0;
        int high = nums.length - 1;
        int mid;
        int index = -1;

        while(low <= high) {
            mid = low + ((high - low) >> 1);
            if(nums[mid] < target || (right && nums[mid] == target)) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
            if(nums[mid] == target) {
                index = mid;
            }
        }

        return index;
    }
}

236 二叉树的最近公共祖先

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == q || root == p) return root;

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if(left != null && right != null) {
            return root;
        } else if(left != null) {
            return left;
        } else {
            return right;
        }
    }
}

104 二叉树最大深度

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return count(root, 0);
    }

    public int count(TreeNode root, int level) {
        if(root != null) {
            return Math.max(count(root.left, level + 1), count(root.right, level +1));
        } else {
            return level;
        }
    }
}

 public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

22 括号生成

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

        return res;
    }

    public void dfs(List<String> res, String str, int left, int right, int n) {

        if(left < right || left > n) return;

        if(left + right == 2*n) {
            res.add(str);
        }

        dfs(res, str + "(", left + 1, right, n);
        dfs(res, str + ")", left, right + 1, n);
    }
}

199. 二叉树的右视图

class Solution {
    List<Integer> res = new ArrayList<>();

    public List<Integer> rightSideView(TreeNode root) {
        if(root == null) return res;
        // for bfs search 
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()) {
            int size = queue.size();
            for(int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
                if(i == size - 1) {
                    res.add(node.val);
                }

            }
        }
        return res;
    }
}

54. 螺旋矩阵

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int x = matrix[0].length, y = matrix.length;
        List<Integer> res = new ArrayList<>();

        int top = 0, left = 0, bottom = y - 1, right = x - 1;

        int total = 0;
        int index = 0;
        while(total < x*y) {
            for(int i = left; i <= right; i++) {
                res.add(matrix[top][i]);
                total ++;
            }
            top ++;

            for(int i = top; i <= bottom; i++) {
                res.add(matrix[i][right]);
                total ++;
            }
            right --;


            for(int i = right ; i >= left ;i --) {
                res.add(matrix[bottom][i]);  
                total ++;     
            }
            bottom --;

            for(int i = bottom; i >= top ; i --) {
                res.add(matrix[i][left]); 
                total ++;
            }  

            left ++;

        }   

        return res;                                  
    }
}

二叉树的镜像

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return root;
        
        TreeNode left = mirrorTree(root.left);
        TreeNode right = mirrorTree(root.right);

        root.left = right;
        root.right = left;

        return root;
    }
}

160. 相交链表

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;
        ListNode a = headA;
        ListNode b = headB;

        while(a != b) {
            a = a == null ? headB : a.next;
            b = b == null ? headA: b.next;
        }

        return a;
    }
}

103. 二叉树的锯齿形层序遍历

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(res, root, 0);
        return res;
    }

    public void dfs(List<List<Integer>> res, TreeNode root, int level) {
        if(root == null) return;

        if(res.size() == level) {
            res.add(new ArrayList<>());
        }

        if(level % 2 == 0) {
            res.get(level).add(root.val);
        } else {
            res.get(level).add(0, root.val);
        }

        dfs(res, root.left, level +1);
        dfs(res, root.right, level +1);
    }
}

会议安排

    public int solution(int[][] intervals) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int max = 0, total = 0;
        for(int[] interval : intervals) {
            int count = map.getOrDefault(interval[0], 0);
            map.put(interval[0], count + 1);
            count = map.getOrDefault(interval[1], 0);
            map.put(interval[1], count - 1);
        }

        for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
            total += entry.getValue();
            max = Math.max(total, max);
        }

        return max;
    }

    public int solution2(int[][] intervals) {
      if(intervals.length == 0) return 0;
      int max = 1;
      Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
      PriorityQueue<Integer> q = new PriorityQueue<>();
      
      for(int[] interval : intervals) {
          while(interval[0] >= q.peek()) {
              q.poll();
          }
          q.offer(interval[1]);
          max = Math.max(q.size(), max);
      }
      
      return max;
      
    }

56. merge intervals

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        ArrayList<int[]> lists = new ArrayList<>();

        // lists.add(new int[] {intervals[0][0], intervals[0][1]});

        // for(int i = 1; i < intervals.length; ++ i) {
        //     if(intervals[i][0] > lists.get(lists.size() - 1)[1]) {
        //         lists.add(new int[] {intervals[i][0], intervals[i][1]});
        //     } else {
        //         lists.get(lists.size() - 1)[1] = Math.max(lists.get(lists.size() - 1)[1], intervals[i][1]);
        //     }
        // }
        int max;

        for(int i = 0; i < intervals.length;) {
            int j = i + 1;
            int t = intervals[i][1];

            while(j< intervals.length && t >= intervals[j][0]) {
                t = Math.max(t, intervals[j][1]);    
                j ++;
            }

            lists.add(new int[] {intervals[i][0], t});

            i = j;
        }

        return lists.toArray(new int[lists.size()][2]);

    }
}