160. 相交链表 - 力扣（LeetCode）

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;
        ListNode A = headA,B = headB;
        while(A != B){
            A = A == null ? headB : A.next;
            B = B == null ? headA : B.next;
        }
        return A;
    }
}

236. 二叉树的最近公共祖先 - 力扣（LeetCode）

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || p == root || q == root) return root;
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left != null && right != null) return root;
        if(left == null) return right;
        if(right == null) return left;
        return null;
    }
}

234. 回文链表 - 力扣（LeetCode）

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) return true;
        ListNode x = head;
        List<Integer> list = new ArrayList<>();
        while(x != null){
            list.add(x.val);
            x = x.next;
        }
        int left = 0, right = list.size() - 1;
        while(left <= right){
            if(list.get(left++) != list.get(right--)) return false;
        }
        return true;
    }
}

739. 每日温度 - 力扣（LeetCode）

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ans = new int[n];
        Deque<Integer> de = new ArrayDeque<>();
        for(int i = n - 1; i >= 0;i--){
            while(!de.isEmpty() && temperatures[i] >= temperatures[de.peek()]){
                de.pop();
            }
            if(!de.isEmpty()) ans[i] = de.peek() - i;
            de.push(i);
        }
        return ans;
    }
}

226. 翻转二叉树 - 力扣（LeetCode）

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return root;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int len = queue.size();
            while(len -- > 0){
                TreeNode node = queue.poll();
                TreeNode temp = node.right;
                node.right = node.left;
                node.left = temp;
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
        }
        return root;
    }
}

1. 两数之和 - 力扣（LeetCode）

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int[] result = new int[2];
        for(int i = 0; i < nums.length; i++){
            if(map.containsKey(target - nums[i])){
                result[0] = map.get(target - nums[i]);
                result[1] = i;
                break;
            }
            map.put(nums[i],i);
        }
        return result;
    }
}

49. 字母异位词分组 - 力扣（LeetCode）

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map = new HashMap<>();
        for(String str : strs){
            char[] arr = str.toCharArray();
            Arrays.sort(arr);
            String s = new String(arr);
            List<String> list = map.getOrDefault(s,new ArrayList<String>());
            list.add(str);
            map.put(s,list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

128. 最长连续序列 - 力扣（LeetCode）

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int ans = 0;
        for(int num : nums){
            set.add(num);
        }
        for(int num : nums){
            int cur = num;
            if(!set.contains(cur - 1)){
                while(set.contains(cur + 1)){
                    cur += 1;
                }
                ans = Math.max(ans, cur - num + 1);
            }
        }
        return ans;

    }
}

283. 移动零 - 力扣（LeetCode）

class Solution {
    public void moveZeroes(int[] nums) {
        int l = 0, r = 0;
        while(r < nums.length){
            if(nums[r] != 0){
                nums[l++] = nums[r];
            }
            r++;
        }
        for(int i = l ; i < nums.length;i++){
            nums[i] = 0;
        }
    }
}

11. 盛最多水的容器 - 力扣（LeetCode）

class Solution {
    public int maxArea(int[] height) {
        int ans = 0;
        int l = 0, r = height.length - 1;
        while(l < r){
            if(height[l] < height[r]){
                ans = Math.max(ans,(r-l) * height[l++]);
            }else{
                ans = Math.max(ans,(r-l) * height[r--]);
            }
        }
        return ans;
    }
}

15. 三数之和 - 力扣（LeetCode）

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        if(nums == null || nums.length < 3) return list;
        int len = nums.length;
        Arrays.sort(nums);
        for(int i = 0; i < len; i++){
            if(nums[i] > 0) break;
            if(i > 0 && nums[i] == nums[i -1]) continue;
            int L = i + 1;
            int R = len - 1;
            while(L < R){
                int sum = nums[i] + nums[L] + nums[R];
                if(sum == 0){
                list.add(Arrays.asList(nums[i],nums[L],nums[R]));
                while(L<R && nums[L] == nums[L+1]) L++;
                while(L<R && nums[R] == nums[R-1]) R--;
                L++;
                R--;
                }else if(sum < 0) L++;
                else if(sum > 0) R--;
            }
        }
        return list;
    }
}

3. 无重复字符的最长子串 - 力扣（LeetCode）

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character,Integer> map = new HashMap<>();
        int res = 0;
        char[] arr = s.toCharArray();
        int len = arr.length;
        for(int l = 0,r = 0; r < len; r++){
            if(map.containsKey(arr[r])){
                l = Math.max(res,map.get(arr[r]));
            }
            res = Math.max(res,r - l + 1);
            map.put(arr[r],r+1);
        }
        return res;
    }
}

206. 反转链表 - 力扣（LeetCode）

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

141. 环形链表 - 力扣（LeetCode）

public class Solution {
    public boolean hasCycle(ListNode head) {
     ListNode fast = head, slow = head;
     while(fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
        if(slow == fast) return true;
     }   
     return false;
    }
}

142. 环形链表 II - 力扣（LeetCode）

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                while(slow != head){
                    head = head.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }
}

21. 合并两个有序链表 - 力扣（LeetCode）

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;
        if(list1.val < list2.val){
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        }else{
            list2.next = mergeTwoLists(list1,list2.next);
            return list2;
        }
    }
}

2. 两数相加 - 力扣（LeetCode）

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode node = new ListNode(-1);
        int carry = 0;
        ListNode node1 = node;
        while(l1 != null || l2 != null){
            int sum = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val);
            if(carry != 0) sum += carry;
            carry = sum / 10;
            sum = sum % 10;
            node.next = new ListNode(sum);
            node = node.next;
            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
        }
        if(carry != 0){
            node.next = new ListNode(carry);
        }
        return node1.next;
    }
}

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0,head);
        ListNode l = dummy, r = dummy;
        while(n -- > 0){
            r = r.next;
        }
        while(r.next != null){
            r = r.next;
            l = l.next;
        }
        l.next = l.next.next;
        return dummy.next;
    }
}

24. 两两交换链表中的节点 - 力扣（LeetCode）

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode node = head.next.next;
        ListNode newHead  = head.next;
        newHead.next = head;
        head.next = swapPairs(node);
        return newHead;
    }
}

146. LRU 缓存 - 力扣（LeetCode）

class LRUCache {
    Map<Integer,Integer> map;
    int capacity;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new LinkedHashMap<>();
    }
  
    public int get(int key) {
        if(!map.containsKey(key)) return -1;
        int value = map.remove(key);
        map.put(key,value);
        return value;
    }
  
    public void put(int key, int value) {
        if(map.remove(key) != null){
            map.put(key,value);
            return;
        }
        if(map.size() == capacity){
            map.remove(map.keySet().iterator().next());
        }
        map.put(key,value);
    }
}

148. 排序链表 - 力扣（LeetCode）

class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode slow = head, fast = head, p = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            p = slow;
            slow = slow.next;
        }
        p.next = null;
        ListNode l = sortList(head);
        ListNode r = sortList(slow);
        return merge(l,r);
    }
     public ListNode merge(ListNode l,ListNode r) {
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while(l != null && r != null){
            if(l.val <= r.val){
                cur.next = l;
                l = l.next;
            }else{
                cur.next = r;
                r = r.next;
            }
            cur = cur.next;
        }
        if(l == null){
            cur.next = r;
        }
        if(r == null){
            cur.next = l;
        }
        return dummy.next;
     }
}

94. 二叉树的中序遍历 - 力扣（LeetCode）

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        function(root,res);
        return res;
    }
    public void function(TreeNode root,List<Integer> res){
        if(root == null) return;
        if(root.left != null) function(root.left,res);
        res.add(root.val);
        if(root.right != null) function(root.right,res);
    }
}

104. 二叉树的最大深度 - 力扣（LeetCode）

层序遍历解法

class Solution {
    public int maxDepth(TreeNode root) {
        List<List<TreeNode>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root != null) queue.offer(root);
        while(queue.size() != 0){
            List<TreeNode> list = new ArrayList<>();
            int len = queue.size();
            while(len -- > 0){
                TreeNode node = queue.poll();
                list.add(node);
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
            res.add(list);
        }
        return res.size();
    }
}

递归

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

226. 翻转二叉树 - 力扣（LeetCode）

class Solution {
    public TreeNode invertTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if(root != null) queue.offer(root);
        while(queue.size() != 0){
            int len = queue.size();
            while(len -- > 0){
                TreeNode node = queue.poll();
                TreeNode tmp = node.right;
                node.right = node.left;
                node.left = tmp;
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
        }
        return root;
    }
}

101. 对称二叉树 - 力扣（LeetCode）

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return false;
        return function(root.left,root.right);
    }
    public boolean function(TreeNode node1,TreeNode node2){
        if(node1 == null && node2 == null) return true;
        if(node1 == null || node2 == null) return false;
        if(node1.val != node2.val) return false;
        return function(node1.left,node2.right) && function(node1.right,node2.left);
    }
}

543. 二叉树的直径 - 力扣（LeetCode）

class Solution {
    int res = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        function(root);
        return res;
    }
    public int function(TreeNode root){
        if(root == null) return 0;
        int left = function(root.left);
        int right = function(root.right);
        res = Math.max(res,left+right);
        return Math.max(left,right) + 1;
    }
}

102. 二叉树的层序遍历 - 力扣（LeetCode）

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(queue.size()>0){
            List<Integer> res1 = new ArrayList<>();
            int size = queue.size();
            while(size-- > 0){
                TreeNode node = queue.poll();
                res1.add(node.val);
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
            res.add(res1);
        }
        return res;
    }
}

108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums,0,nums.length - 1);
    }
    public TreeNode dfs(int[] nums,int l,int r){
        if(l > r) return null;
        int index = l + (r - l) / 2;
        TreeNode mid = new TreeNode(nums[index]);
        mid.left = dfs(nums,l,index-1);
        mid.right = dfs(nums,index+1,r);
        return mid;
    }
}

98. 验证二叉搜索树 - 力扣（LeetCode）

class Solution {
    Integer pre;
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;
        if(!isValidBST(root.left)) return false;
        if(pre != null && root.val <= pre) return false;
        pre = root.val;
        return isValidBST(root.right);
    }
}

230. 二叉搜索树中第 K 小的元素 - 力扣（LeetCode）

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();
        inorder(root,list);
        return list.get(k - 1);
    }
    public void inorder(TreeNode root,List<Integer> list){
        if(root == null) return;
        inorder(root.left,list);
        list.add(root.val);
        inorder(root.right,list);
    }
}

199. 二叉树的右视图 - 力扣（LeetCode）

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        return function(root);
    }
    public List<Integer> function(TreeNode root){
        List<Integer> res = new ArrayList<>();
        if(root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(queue.size() > 0){
            int len = queue.size();
            while(len > 0){
                TreeNode node = queue.poll();
                if(len == 1) res.add(node.val);
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
                len--;
            }
        }
        return res;
    }
}

114. 二叉树展开为链表 - 力扣（LeetCode）

class Solution {
    public void flatten(TreeNode root) {
        List<TreeNode> list = new LinkedList<>();
        fun(root,list);
        int size = list.size();
        for(int i = 1; i < size; i++){
            TreeNode pre = list.get(i - 1);
            TreeNode cur = list.get(i);
            pre.left = null;
            pre.right = cur;
        }
    }
    public void fun(TreeNode root, List<TreeNode> list){
        if(root == null) return;
        list.add(root);
        fun(root.left,list);
        fun(root.right,list);
    }
}

236. 二叉树的最近公共祖先 - 力扣（LeetCode）

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

53. 最大子数组和 - 力扣（LeetCode）

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

42. 接雨水 - 力扣（LeetCode）

class Solution {
    public int trap(int[] height) {
        int[] left = new int[height.length];
        int[] right = new int[height.length];
        int sum = 0;
        for(int i = 1; i < height.length;i++){
            left[i] = Math.max(left[i-1],height[i-1]);
        }
        for(int i = height.length -2; i >= 0;i--){
            right[i] = Math.max(right[i+1],height[i+1]);
        }
        for(int i = 1; i < height.length -1;i++){
            int min = Math.min(left[i],right[i]);
            if(min > height[i]){
                sum = sum + (min-height[i]);
            }
        }
        return sum;
    }
}

25. K 个一组翻转链表 - 力扣（LeetCode）

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode p = head;
        for(int i = 0; i < k;i++){
            if(p == null) return head;
            p = p.next;
        }
        ListNode pre = null,cur = head, tmp = null;
        for(int i = 0; i < k;i++){
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        head.next = reverseKGroup(cur,k);
        return pre;
    }
}

200. 岛屿数量 - 力扣（LeetCode）

class Solution {
    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int res = 0;
        for(int i = 0; i < m;i++){
            for(int j = 0; j < n;j++){
                if(grid[i][j] == '1'){
                    res++;
                    dfs(grid,i,j);
                }
            }
        }
        return res;
    }
    public void dfs(char[][] grid,int i,int j){
        if(!(0 <= i && i < grid.length && 0<= j && j<grid[0].length)){
            return;
        }
        if(grid[i][j] == '1'){
            grid[i][j] = '2';
            dfs(grid,i-1,j);
            dfs(grid,i+1,j);
            dfs(grid,i,j-1);
            dfs(grid,i,j+1);
        }
    }
}

136. 只出现一次的数字 - 力扣（LeetCode）

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

46. 全排列 - 力扣（LeetCode）

class Solution {
    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> path = new LinkedList<>();
    boolean[] bool;
    public List<List<Integer>> permute(int[] nums) {
        bool = new boolean[nums.length];
        back(nums);
        return res;
    }
    public void back(int[] nums){
        if(path.size() == nums.length){
            res.add(new LinkedList<>(path));
        }
        for(int i = 0; i < nums.length;i++){
            if(bool[i]) continue;
            bool[i] = true;
            path.add(nums[i]);
            back(nums);
            bool[i] = false;
            path.removeLast();
        }
    }
}

78. 子集 - 力扣（LeetCode）

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        func(nums, 0);
        return res;
    }
    public void func(int[] nums, int startIndex){
        res.add(new ArrayList<>(path));
        if(startIndex >= nums.length){
            return;
        }
        for(int i = startIndex; i < nums.length; i++){
            path.add(nums[i]);
            func(nums, i + 1);
            path.removeLast();
        }
    }
}

438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int n = s.length();
        int m = p.length();
        List<Integer> res = new ArrayList<>();
        char[] s1 = new char[26];
        char[] p1 = new char[26];
        for(int i = 0; i < m;i++) p1[p.charAt(i) - 'a']++;
        for(int l = 0, r = 0; r < n;r++){
            s1[s.charAt(r) - 'a']++;
            if(r - l + 1 > m) s1[s.charAt(l++) - 'a']--;
            if(check(s1,p1)) res.add(l);
        }
        return res;
    }
    boolean check(char[] s1,char[] p1){
        for(int i = 0; i < 26;i++){
            if(s1[i] != p1[i]) return false;
        }
        return true;
    }
}

560. 和为 K 的子数组 - 力扣（LeetCode）

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        int sum = 0;
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,1);
        for(int x : nums){
            sum += x;
            if(map.containsKey(sum - k)){
                count += map.get(sum - k);
            }
            map.put(sum,map.getOrDefault(sum,0) + 1);
        }
        return count;
    }
}

56. 合并区间 - 力扣（LeetCode）

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,(a,b) -> a[0] - b[0]);
        List<int[]> res = new ArrayList<>();
        for(int[] p : intervals){
            int m = res.size();
            if(m >0 && p[0] <=res.get(m-1)[1]){
                res.get(m-1)[1] = Math.max(res.get(m-1)[1],p[1]);
            }else{
                res.add(p);
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}

189. 轮转数组 - 力扣（LeetCode）

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        reverse(nums,0,n-1);
        reverse(nums,0,k-1);
        reverse(nums,k,n-1);
    }
    public void reverse(int[] nums,int l ,int r){
        while(l < r){
            int temp = nums[r];
            nums[r] = nums[l];
            nums[l] = temp;
            l++;
            r--;
        }
    }
}

238. 除自身以外数组的乘积 - 力扣（LeetCode）

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] pre = new int[n];
        int[] suf = new int[n];
        pre[0] = 1;
        suf[n-1] = 1;
        for(int i = 1; i <n;i++){
            pre[i] = pre[i-1] * nums[i-1];
        }
        for(int i = n -2; i>=0;i--){
            suf[i] = suf[i+1] * nums[i+1];
        }
        int[] ans = new int[n];
        for(int i = 0; i < n;i++){
            ans[i] = pre[i] * suf[i];
        }
        return ans;
    }
}

73. 矩阵置零 - 力扣（LeetCode）

class Solution {
    public void setZeroes(int[][] matrix) {
        Set<Integer> row_zero = new HashSet<>();
        Set<Integer> col_zero = new HashSet<>();
        int row = matrix.length;
        int col = matrix[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == 0) {
                    row_zero.add(i);
                    col_zero.add(j);
                }
            }
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (row_zero.contains(i) || col_zero.contains(j)) matrix[i][j] = 0;
            }
        }  
    }
}

54. 螺旋矩阵 - 力扣（LeetCode）

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int l = 0,r = matrix[0].length - 1,t = 0, b = matrix.length-1;
        List<Integer> res= new ArrayList<>();
        while(true){
            for(int i = l; i <= r; i++) res.add(matrix[t][i]);
            if(++t > b) break;
            for(int i = t; i <= b; i++) res.add(matrix[i][r]);
            if(l > --r) break;
            for(int i = r; i >= l ;i--) res.add(matrix[b][i]);
            if(t > --b) break;
            for(int i = b; i >= t; i--) res.add(matrix[i][l]);
            if(++l > r) break;
        }
        return res;
    }
}

77. 组合 - 力扣（LeetCode）

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        func(n,k,1);
        return res;
    }
    public void func(int n,int k ,int start){
        if(path.size() == k){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = start; i <= n - (k - path.size()) + 1;i++){
            path.add(i);
            func(n,k,i+1);
            path.removeLast();
        }
    }
}

39. 组合总和 - 力扣（LeetCode）

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        int sum = 0;
        func(candidates,target,sum,0);
        return res;
    }
    public void func(int[] candidates, int target,int sum,int start){
        if(sum > target) return;
        if(sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = start; i < candidates.length;i++){
            sum += candidates[i];
            path.add(candidates[i]);
            func(candidates,target,sum,i);
            sum -= candidates[i];
            path.removeLast();
        }
    }
}

22. 括号生成 - 力扣（LeetCode）

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res= new ArrayList<>();
        func("",n,n,res);
        return res;
    }
    public void func(String s,int l,int r,List<String> res){
        if(l == 0 && r == 0){
            res.add(s);
            return;
        }
        if(l > r) return;
        if(l > 0){
            func(s + "(",l-1,r,res);
        }
        if(r > 0){
            func(s + ")",l,r-1,res);
        }
    }
}

79. 单词搜索 - 力扣（LeetCode）

class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for(int i = 0; i < board.length;i++){
            for(int j = 0; j < board[0].length;j++){
                if(dfs(board,words,i,j,0)) return true;
            }
        }
        return false;
    }
    public boolean dfs(char[][] board, char[] words,int i,int j, int k){
        if(i < 0 || j < 0 || i >= board.length 
        || j >= board[0].length || board[i][j] != words[k]) return false;
        if(k == words.length - 1) return true;
        board[i][j] = '\0';
        boolean res = dfs(board,words,i+1,j,k+1) ||dfs(board,words,i-1,j,k+1) 
        ||dfs(board,words,i,j+1,k+1) ||dfs(board,words,i,j-1,k+1);
        board[i][j] = words[k];
        return res;

    }
}

20. 有效的括号 - 力扣（LeetCode）

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        char[] str = s.toCharArray();
        for(char sr : str){
            if(sr == '(' || sr == '[' || sr == '{') stack.push(sr);
            else{
                if(stack.isEmpty()) return false;
                if(sr == ')' && stack.peek() != '(') return false;
                if(sr == ']' && stack.peek() != '[') return false;
                if(sr == '}' && stack.peek() != '{') return false;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}

215. 数组中的第K个最大元素 - 力扣（LeetCode）

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return quickSort(nums,0,nums.length - 1,nums.length - k);
    }
    public int quickSort(int[] nums,int l,int r,int k){
        if(l == r) return nums[l];
        int index = randomPart(nums,l,r);
        if(index == k) return nums[index];
        if(index < k) return quickSort(nums,index+1,r,k);
        else return quickSort(nums,l,index-1,k);
    }
    public void swap(int[] nums,int l,int r){
        int temp = nums[r];
        nums[r] = nums[l];
        nums[l] = temp;
    }
    public int randomPart(int[] nums,int l,int r){
        int index = new Random().nextInt(r - l + 1) + l;
        swap(nums,index,r);
        return part(nums,l,r);
    }
    public int part(int[] nums,int l,int r){
        int i = l - 1;
        int pv = nums[r];
        for(int j = l; j <= r - 1;j++){
            if(nums[j] < pv){
                i++;
                swap(nums,i,j);
            }
        }
        swap(nums,i+1,r);
        return i+1;
    }
}

239. 滑动窗口最大值 - 力扣（LeetCode）

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
         int n = nums.length;
        int[] res = new int[n-k+1];
        Deque<Integer> deque = new ArrayDeque<>();
   
        for(int i = 0;i<n;i++){
            while(!deque.isEmpty() && nums[deque.getLast()] <= nums[i]){
                deque.removeLast();
            }
            deque.addLast(i);
            if(i - deque.getFirst() >= k){
                deque.removeFirst();
            }
            if(i >= k-1){
                res[i-k+1] = nums[deque.getFirst()];
            }
        }
        return res;
    }
}

209. 长度最小的子数组 - 力扣（LeetCode）

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0,right = 0;
        int ans = Integer.MAX_VALUE;
        int n = nums.length;
        int sum = 0;
        for(;right < n;right++){
            sum += nums[right];
            while(sum - nums[left] >= target){
                sum -= nums[left++];
            }
            if(sum >= target){
                ans = Math.min(ans,right-left+1);
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

41. 缺失的第一个正数 - 力扣（LeetCode）

class Solution {
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        for(int i = 0; i<len;i++){
            while(nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]){
                swap(nums,nums[i] - 1,i);
            }
        }
        for(int i = 0; i < len;i++){
            if(nums[i] != i+1){
                return i+1;
            }
        }
        return len+1;
    }
    public void swap(int[] nums,int l,int r){
        int temp = nums[r];
        nums[r] = nums[l];
        nums[l] = temp;
    }
}

76. 最小覆盖子串 - 力扣（LeetCode）

class Solution {
    public String minWindow(String S, String t) {
        char[] s = S.toCharArray();
        int n = s.length;
        int ansL = -1;
        int ansR = n;
        int l = 0,r=0;
        int[] cntS = new int[128];
        int[] cntT = new int[128];
        for(char c : t.toCharArray()){
            cntT[c]++;
        }
        for(;r < n;r++){
            cntS[s[r]]++;
            while(isCoverd(cntS,cntT)){
                if(r - l < ansR - ansL){
                    ansL = l;
                    ansR = r;
                }
                cntS[s[l++]]--;
            }
        }
        return ansL < 0 ? "" : S.substring(ansL,ansR+1);
    }
    public boolean isCoverd(int[] cntS,int[] cntT){
        for(int i = 'A';i <= 'Z';i++){
            if(cntS[i] < cntT[i]) return false;
        }
        for(int i = 'a';i <= 'z';i++){
            if(cntS[i] < cntT[i]) return false;
        }
        return true;
    }
}

48. 旋转图像 - 力扣（LeetCode）

class Solution {
    public void rotate(int[][] matrix) {
        int size = matrix.length;
        int[][] temp = new int[size][];
        for(int i = 0; i < size;i++){
            temp[i] = matrix[i].clone();
        }
        for(int i = 0; i < size;i++){
            for(int j = 0; j < size;j++){
                matrix[j][size-1-i] = temp[i][j];
            }
        }
    }
}

240. 搜索二维矩阵 II - 力扣（LeetCode）

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = 0;
        int j = matrix[0].length - 1;
        while(i < matrix.length && j >= 0){
            if(matrix[i][j]  == target) return true;
            if(matrix[i][j] < target){
                i++;
            }else{
                j--;
            }
        }
        return false;
    }
}

138. 随机链表的复制 - 力扣（LeetCode）

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        Map<Node,Node> map = new HashMap<>();
        Node p = head;
        while(p != null){
            Node newNode = new Node(p.val);
            map.put(p,newNode);
            p = p.next;
        }
        p = head;
        while(p != null){
            Node newNode = map.get(p);
            if(p.next != null){
                newNode.next = map.get(p.next);
            }
            if(p.random != null){
                newNode.random = map.get(p.random);
            }
            p = p.next;
        }
        return map.get(head);
  
    }
}

105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0 || inorder.length == 0) return null;
        TreeNode root = new TreeNode(preorder[0]);
        for(int i = 0; i < inorder.length;i++){
            if(preorder[0] == inorder[i]){
                int[] left_pre = Arrays.copyOfRange(preorder,1,i+1);
                int[] right_pre = Arrays.copyOfRange(preorder,i+1,preorder.length);
                int[] left_in = Arrays.copyOfRange(inorder,0,i);
                int[] right_in = Arrays.copyOfRange(inorder,i+1,preorder.length);
                root.left = buildTree(left_pre,left_in);
                root.right = buildTree(right_pre,right_in);
                break;
            }
        }
        return root;
    }
}

994. 腐烂的橘子 - 力扣（LeetCode）

class Solution {
    public int orangesRotting(int[][] grid) {
        Queue<int[]> queue = new LinkedList<>();
        int h = grid.length;
        int w = grid[0].length;
        int count = 0;
        for(int i = 0;i<h;i++){
            for(int j = 0; j < w;j++){
                if(grid[i][j] == 1){
                    count++;
                }else if(grid[i][j] == 2){
                    queue.add(new int[]{i,j});
                }
            }
        }
        int round = 0;
        while(count > 0 && !queue.isEmpty()){
            round++;
            int n = queue.size();
            for(int i = 0; i < n;i++){
                int[] org = queue.poll();
                int height = org[0];
                int width = org[1];
                if(height - 1 >= 0 && grid[height-1][width] == 1){
                    count--;
                    grid[height-1][width] = 2;
                    queue.add(new int[]{height-1,width});
                }
                if(height+1<h && grid[height+1][width] == 1){
                    count--;
                    grid[height+1][width] = 2;
                    queue.add(new int[]{height+1,width});
                }
                if(width-1 >= 0 && grid[height][width-1] == 1){
                    count--;
                    grid[height][width-1] = 2;
                    queue.add(new int[]{height,width-1});
                }
                if(width+1<w && grid[height][width+1] == 1){
                    count--;
                    grid[height][width+1] = 2;
                    queue.add(new int[]{height,width+1});
                }
            }
        }
        if (count > 0) {
        return -1;
    } else {
        return round;
    }
    }
}

437. 路径总和 III - 力扣（LeetCode）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int ans;
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long,Integer> map = new HashMap<>();
        map.put(0L,1);
        dfs(root,0,targetSum,map);
        return ans;
    }
    private void dfs(TreeNode root,long s,int targetSum,Map<Long,Integer> map){
        if(root == null) return;
        s += root.val;
        ans += map.getOrDefault(s-targetSum,0);
        map.merge(s,1,Integer::sum);
        dfs(root.left,s,targetSum,map);
        dfs(root.right,s,targetSum,map);
        map.merge(s,-1,Integer::sum);
    }
}

75. 颜色分类 - 力扣（LeetCode）

class Solution {
    public void sortColors(int[] nums) {
        int n0 = 0,n1 = 0;
        for(int i = 0; i < nums.length;i++){
            int num = nums[i];
            nums[i] = 2;
            if(num < 2){
                nums[n1++] = 1;
            }
            if(num < 1){
                nums[n0++] = 0;
            }
        }
    }
}