淘先锋技术网

首页 1 2 3 4 5 6 7

LeetCode 热题 HOT 100 算法题参考解法

力扣链接:LeetCode 热题 HOT 100

1. 两数之和

力扣链接:1. 两数之和

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

2. 两数相加

力扣链接:2. 两数相加

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        int carry = 0;
        while(l1 != null || l2 != null) {
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            int sum = x + y + carry;
            
            carry = sum / 10;
            sum = sum % 10;
            cur.next = new ListNode(sum);

            cur = cur.next;
            if(l1 != null)
                l1 = l1.next;
            if(l2 != null)
                l2 = l2.next;
        }
        if(carry == 1) {
            cur.next = new ListNode(carry);
        }
        return pre.next;
    }
}

3. 无重复字符的最长子串

力扣链接:3. 无重复字符的最长子串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int r=0;
        int n = s.length();
        int res =0;
        for(int i=0;i<n;i++){
            while(r<n && !set.contains(s.charAt(r))){
                set.add(s.charAt(r));
                r++;
            }
            res = Math.max(res,r-i);
            set.remove(s.charAt(i));
        }
        return res;
    }
}

4. 寻找两个正序数组的中位数

力扣链接:4. 寻找两个正序数组的中位数

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int len = m+n;
        int i = 0,j=0;
        int prev =-1,last = -1;
        for(int k=0;k<=len/2;k++){
            prev = last;
            if(i<m && (j>=n || nums1[i]<nums2[j])){
                last = nums1[i++];
            }else{
                last = nums2[j++];
            }
        }
        return len%2==1 ? last : (prev+last)/2.0;
    }
}

5. 最长回文子串

力扣链接:5. 最长回文子串

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        String res = "";
        for(int i=0;i<2*n-1;i++){
            int l = i/2;
            int r = l + i%2;
            while(l>=0 && r<n && s.charAt(l)==s.charAt(r)){
                String t = s.substring(l,r+1);
                if(t.length()> res.length()){
                    res = t;
                }
                l--;
                r++;
            }
        }
        return res;
    }
}




class Solution {
    public String longestPalindrome(String s) {
        if(s==null || s.length() == 0){
            return "";
        }
        int start=0;
        int end = 0;
        for(int i=0;i<s.length();i++){
            int len1 = extend(s,i,i);
            int len2 = extend(s,i,i+1);
            int len = Math.max(len1,len2);
            if(len > end-start){
                start = i- (len-1)/2;
                end = i+ len/2;
            }
        }
        return s.substring(start,end+1);
    }
    public int extend(String s,int left,int right){
        while(left>=0 && right<s.length() && s.charAt(left) == s.charAt(right)){
            left--;
            right++;
        }
        return right-left-1;
    }
}

10. 正则表达式匹配

力扣链接:10. 正则表达式匹配

11. 盛最多水的容器

力扣链接:11. 盛最多水的容器

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

15. 三数之和

力扣链接:15. 三数之和

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        if(n<3){return res;}
        for(int i=0;i<n;i++){
            if(nums[i]>0){
                break;
            }
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            int l = i+1;
            int r = n-1;
            while(l<r){
                int sum = nums[i]+nums[l]+nums[r];
                if(sum==0){
                    res.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){
                    r--;
                }else{
                    l++;
                }
            }
        }
        return res;
    }
}

17. 电话号码的字母组合

力扣链接:17. 电话号码的字母组合

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if(digits.length() == 0){
            return res;
        }
        Map<Character,String> mp = new HashMap<>();
        mp.put('2',"abc");
        mp.put('3',"def");
        mp.put('4',"ghi");
        mp.put('5',"jkl");
        mp.put('6',"mno");
        mp.put('7',"pqrs");
        mp.put('8',"tuv");
        mp.put('9',"wxyz");

        backtrack(res,digits,mp,0,new StringBuilder());
        return res;
    }
    public void backtrack(List<String> res,String digits,Map<Character,String> mp,int idx,
                        StringBuilder t){
        if(idx == digits.length()){
            res.add(new String(t.toString()));
            return;
        }
        char c = digits.charAt(idx);
        String words = mp.get(c);
        for(char ch : words.toCharArray()){
            t.append(ch);
            backtrack(res,digits,mp,idx+1,new StringBuilder(t));
            t.deleteCharAt(idx);
        }
    }
}

19. 删除链表的倒数第 N 个结点

力扣链接:19. 删除链表的倒数第 N 个结点

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

20. 有效的括号

力扣链接:20. 有效的括号

class Solution {
    public boolean isValid(String s) {
        Map<Character,Character> mp = new HashMap<>();
        mp.put('(',')');
        mp.put('[',']');
        mp.put('{','}');
        if(s==null || s.length()==0 || s.length()%2==1){
            return false;
        }
        Stack<Character> stack = new Stack<>();
        for(Character c:s.toCharArray()){
            if(mp.containsKey(c)){
                stack.push(c);
            }else{
                if(stack.isEmpty() || mp.get(stack.pop()) != c ) return false;
            }
        }
        return stack.isEmpty();
    }
}

21. 合并两个有序链表

力扣链接:21. 合并两个有序链表

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;
        }
    }
}

22. 括号生成

力扣链接:22. 括号生成

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

    public void dfs(List<String> res,int left,int right,String t){
        if(left == 0 && right ==0){
            res.add(new String(t));
            return;
        }
        if(left>right || left<0 || right<0){
            return;
        }
        dfs(res,left-1,right,t+"(");
        dfs(res,left,right-1,t+")");
    }
}

23. 合并K个升序链表

力扣链接:23. 合并K个升序链表

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

    public ListNode merge(ListNode[] lists,int left,int right){
        if(left<right){
            int mid = (left+right)/2;
            ListNode l1 = merge(lists,left,mid);
            ListNode l2 = merge(lists,mid+1,right);
            return mergeTwoLists(l1,l2);
        }
        return lists[left];
    }

    public ListNode mergeTwoLists(ListNode l1,ListNode l2){
        if(l1==null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        if(l1.val < l2.val){
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        }else{
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
    }
}

31. 下一个排列

力扣链接:31. 下一个排列

32. 最长有效括号

力扣链接:32. 最长有效括号

class Solution {
    public int longestValidParentheses(String s) {
        int left =0,right = 0,res = 0;
        for(char c:s.toCharArray()){
            if(c == '(') left++;
            if(c == ')') right++;
            if(left == right){
                res = Math.max(res,2*right);
            }
            if(right>left){
                left = 0;
                right = 0;
            }
        }
        left = 0;
        right = 0;
        for(int i=s.length()-1;i>=0;i--){
            if(s.charAt(i)==')'){
                right++;
            }else{
                left++;
            }
            if(left == right){
                res = Math.max(res,2*left);
            }
            if(left > right){
                left = 0;
                right = 0;
            }
        }
        return res;
    }
}

33. 搜索旋转排序数组

力扣链接:33. 搜索旋转排序数组

将数组一分为二,其中一定有一个是有序的,另一个可能是有序,也能是部分有序。
此时有序部分用二分法查找。无序部分再一分为二,其中一个一定有序,另一个可能有序,可能无序。
就这样循环.

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        if(n==0) return -1;
        if(n==1) return nums[0] == target ? 0 : -1;
        int l =0;
        int r = n-1;
        while(l<=r){
            int mid = (l+r)/2;
            if(nums[mid] == target){
                return mid;
            }
            if(nums[l]<=nums[mid]){
                if(target >= nums[l] && target<nums[mid]){
                    r = mid-1;
                }else{
                    l = mid+1;
                }
            }else{
                if(target> nums[mid] && target<=nums[r]){
                    l = mid + 1;
                }else{
                    r = mid - 1;
                }

            }
        }
        return -1;
    }
}

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

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

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums.length ==0){
            return new int[]{-1,-1};
        }
        int first = first(nums,target);
        int second = second(nums,target);
        return new int[]{first,second};
    }

    public int first(int[] nums,int target){
        int n = nums.length;
        int l = 0;
        int r = n-1;
        while(l<r){
            int mid = (l+r)/2;
            if(target < nums[mid]){
                r = mid-1;
            }else if (target> nums[mid]){
                l = mid +1;
            }else{
                r= mid;
            }
        }
        return nums[l] == target ? l : -1;
    }

    public int second(int[] nums,int target){
        int n = nums.length;
        int l = 0;
        int r = n-1;
        while(l<r){
            int mid = (l+r)/2+1;
            if(target < nums[mid]){
                r = mid-1;
            }else if (target> nums[mid]){
                l = mid +1;
            }else{
                l = mid;
            }
        }
        return nums[r] == target ? l : -1;
    }
}

39. 组合总和

力扣链接:39. 组合总和

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(candidates,target,res,0,new ArrayList<>());
        return res;
    }

    public void dfs(int[] candidates,int target,List<List<Integer>> res,int idx,List<Integer> t){
        if(target == 0){
            res.add(new ArrayList<Integer>(t));
            return ;
        }
        if(idx == candidates.length){
            return;
        }
        dfs(candidates,target,res,idx+1,new ArrayList<>(t));
        if(target >=candidates[idx]){
            t.add(candidates[idx]);
            dfs(candidates,target - candidates[idx],res,idx,new ArrayList<>(t));
        }
    }
}

42. 接雨水

力扣链接:42. 接雨水

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

        right[n-1] = height[n-1];
        for(int i=n-2;i>=0;i--){
            right[i] = Math.max(right[i+1],height[i]);
        }
        int res = 0;
        for(int i=0;i<n;i++){
            res += (Math.min(left[i],right[i])-height[i]);
        }
        return res;

    }
}




class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int left = 0;
        int right = n - 1;
        int leftMax = 0;
        int rightMax = 0;
        int res = 0;
        while(left <right){
            leftMax = Math.max(height[left],leftMax);
            rightMax = Math.max(height[right],rightMax);
            if(leftMax<rightMax){
                res += leftMax-height[left];
                left ++;
            }else{
                res += rightMax-height[right];
                right --;
            }
        }
        return res;
    }
}

46. 全排列

力扣链接:46. 全排列

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        boolean[] visit = new boolean[nums.length];
        backtrack(res,nums,0,visit,new ArrayList<Integer>());
        return res;
    }

    public void backtrack(List<List<Integer>> res,int[] nums,int idx,boolean[] visit,List<Integer> t){
        if(idx == nums.length){
            res.add(new ArrayList<>(t));
            return ;
        }
        for(int i=0;i<nums.length;i++){
            if(visit[i]) continue;
            visit[i]=true;
            t.add(nums[i]);
            backtrack(res,nums,idx+1,visit,t);
            t.remove(idx);
            visit[i] = false;
        }
    }
}

48. 旋转图像

力扣链接:48. 旋转图像

class Solution {
    public void rotate(int[][] matrix) {
        int m = matrix.length-1;
        int n = matrix[0].length-1;
        for(int i=0;i<=m;i++){
            for(int j=0;j<=i;j++){
                swap(matrix,i,j,j,i);
            }
        }
        for(int i=0;i<=m;i++){
            for(int j=0;j<=n/2;j++){
                swap(matrix,i,j,i,n-j);
            }
        }
    }
    public void swap(int[][] matrix,int x,int y,int m,int n){
        int t = matrix[x][y];
        matrix[x][y] = matrix[m][n];
        matrix[m][n] = t;
    }
}

49. 字母异位词分组

力扣链接:49. 字母异位词分组

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

53. 最大子数组和

力扣链接:53. 最大子数组和

class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0;
        int res = Integer.MIN_VALUE;
        for(int num:nums){
            pre = Math.max(num,pre+num);
            res = Math.max(res,pre);
        }
        return res;
    }
}

55. 跳跃游戏

力扣链接:55. 跳跃游戏

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int max = 0;
        for(int i=0;i<n;i++){
            if(i<=max){
                max = Math.max(max,i+nums[i]);
                if(max >= n-1){
                    return true; 
                }
            }
        }
        return false;
    }
}

56. 合并区间

力扣链接:56. 合并区间

class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals.length==0 || intervals[0].length==0){
            return new int[][]{};
        }
        Arrays.sort(intervals,(x,y)->(x[0]-y[0] != 0 ? x[0]-y[0] : x[1]-y[1]));
        List<int[]> merged = new ArrayList<>();
        for(int[] t : intervals){
            int l = t[0];
            int r = t[1];
            int n = merged.size();
            if(n == 0 || merged.get(n -1)[1]<l){
                merged.add(new int[]{l,r});
            }else{
                merged.get(n-1)[1] = Math.max(merged.get(n-1)[1],r);
            }
        }
        int[][] res = new int[merged.size()][];
        for(int i=0;i<merged.size();i++){
            res[i] = merged.get(i);
        }
        return res;
    }
}

62. 不同路径

力扣链接:62. 不同路径

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m+1][n+1];
        for(int i=1;i<=m;i++){
            dp[i][1]=1;
        }
        for(int i =1;i<=n;i++){
            dp[1][i] =1;
        }
        for(int i=2;i<=m;i++){
            for(int j=2;j<=n;j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m][n];
    }
}

64. 最小路径和

力扣链接:64. 最小路径和

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for(int i=1;i<m;i++){
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for(int j=1;j<n;j++){
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
}

70. 爬楼梯

力扣链接:70. 爬楼梯

class Solution {
    public int climbStairs(int n) {
        if(n==0 || n==1){
            return 1;
        }
        int a = 1;
        int b = 1;
        int c = 0;
        for(int i=2;i<=n;i++){
            c = a+b;
            a= b;
            b = c;
        }
        return c;
    }
}

72. 编辑距离

力扣链接:72. 编辑距离

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m+1][n+1];
        for(int i=0;i<=m;i++){
            dp[i][0] = i;
        }
        for(int i=0;i<=n;i++){
            dp[0][i] = i;
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i][j-1],dp[i-1][j]))+1;
                }
            }
        }
        return dp[m][n];
    }
}

75. 颜色分类

力扣链接:75. 颜色分类

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int p0 = 0;
        int p2 = n-1;
        int i =p0;
        while(i<=p2){
            if(nums[i]==0){
                swap(nums,i,p0);
                p0++;
                i++;
            }else if(nums[i]==2){
                swap(nums,i,p2);
                p2--;
            }else{
                i++;
            }
        }
    
    }
    public void swap(int[] nums,int x,int y){
        int t = nums[x];
        nums[x] = nums[y];
        nums[y] = t;
    }
}

76. 最小覆盖子串

力扣链接:76. 最小覆盖子串

class Solution {
    public String minWindow(String s, String t) {
        Map<Character,Integer> s_mp = new HashMap<>();
        Map<Character,Integer> t_mp = new HashMap<>();
        for(int i=0;i<t.length();i++){
            t_mp.put(t.charAt(i),t_mp.getOrDefault(t.charAt(i),0)+1);
        }
        String res ="";
        int len = Integer.MAX_VALUE;
        int cnt = 0;
        int j = 0;
        for(int i=0;i<s.length();i++){
            char rc = s.charAt(i);
            s_mp.put(rc,s_mp.getOrDefault(rc,0)+1);
            if(t_mp.containsKey(rc) && s_mp.get(rc) <= t_mp.get(rc)){
                cnt++;
            }
            char lc = s.charAt(j);
            while(j<i && (!t_mp.containsKey(lc) || s_mp.get(lc) > t_mp.get(lc))){
                s_mp.put(lc,s_mp.get(lc)-1);
                j++;
                lc = s.charAt(j);
            }
            if(cnt == t.length() && i-j+1<len){
                len = i-j+1;
                res= s.substring(j,i+1);
            }
        }
        return res;
    }
}




import java.util.HashMap;

class Solution {
    public String minWindow(String s, String t) {
        HashMap<Character,Integer> need = new HashMap<>();
        HashMap<Character,Integer> window = new HashMap<>();
        for (char ch : t.toCharArray()){
            need.put(ch,need.getOrDefault(ch,0)+1);
        }
        int start = 0;
        int valid = 0;
        int left = 0;
        int right = 0;
        int len = Integer.MAX_VALUE;
        while (right < s.length()){
            char c = s.charAt(right);
            right++;
            if(need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if(window.get(c).equals(need.get(c))){
                    valid++;
                }
            }
            while(valid == need.size()){
                if(right - left < len){
                    start = left;
                    len = right - left;
                }
                char d = s.charAt(left);
                left++;
                if(need.containsKey(d)){
                    if(window.get(d).equals(need.get(d))){
                        valid--;
                    }
                    
                    window.put(d,window.getOrDefault(d,0)-1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start,start+len);
    }
}

78. 子集

力扣链接:78. 子集

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums.length == 0){
            return res;
        }
        res.add(new ArrayList<>());
        for(int i=0;i<nums.length;i++){
            int size = res.size();
            for(int j=0;j<size;j++){
                List<Integer> list = new ArrayList<>(res.get(j));
                list.add(nums[i]);
                res.add(list);
            }
        }
        return res;
    }
}

79. 单词搜索

力扣链接:79. 单词搜索

class Solution {
    public boolean exist(char[][] board, String word) {
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                if(dfs(board,word,0,i,j)){
                    return true;
                }
            }
        }
        return false;
    }   

    public boolean dfs(char[][] board,String word,int idx,int x,int y){
        if(x<0 || x>=board.length || y<0 || y>=board[0].length || board[x][y] != word.charAt(idx)){
            return false;
        }
        if(idx == word.length()-1){
            return true;
        }
        board[x][y] = '\0';
        boolean res = dfs(board,word,idx+1,x+1,y) || dfs(board,word,idx+1,x,y+1)
                    || dfs(board,word,idx+1,x-1,y) || dfs(board,word,idx+1,x,y-1); 
        board[x][y] = word.charAt(idx);
        return res;
    }

}

84. 柱状图中最大的矩形

力扣链接:84. 柱状图中最大的矩形

85. 最大矩形

力扣链接:85. 最大矩形

94. 二叉树的中序遍历

力扣链接:94. 二叉树的中序遍历

class Solution {
    List<Integer> list= new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        inorder(root);
        return list;
    }

    public void inorder(TreeNode root){
        if(root == null){
            return;
        }
        inorder(root.left);
        list.add(root.val);
        inorder(root.right);
    }
}

96. 不同的二叉搜索树

力扣链接:96. 不同的二叉搜索树

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n+1];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            for(int j=1;j<=i;j++){
                dp[i] += (dp[j-1] * dp[i-j]);
            }
        }
        return dp[n];
    }
}

98. 验证二叉搜索树

力扣链接:98. 验证二叉搜索树

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }
    public boolean isValidBST(TreeNode root,long left,long right){
        if(root == null){
            return true;
        }
        if(root.val <= left || root.val >= right){
            return false;
        }
        return isValidBST(root.left,left,root.val) && isValidBST(root.right,root.val,right);
    }
}

102. 二叉树的层序遍历

力扣链接:102. 二叉树的层序遍历

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

104. 二叉树的最大深度

力扣链接:104. 二叉树的最大深度

class Solution {
    public int maxDepth(TreeNode root) {
        return depth(root);
    }

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

105. 从前序与中序遍历序列构造二叉树

力扣链接:105. 从前序与中序遍历序列构造二叉树

class Solution {
    int[] preorder;
    Map<Integer,Integer> mp = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for(int i = 0;i<inorder.length;i++){
            mp.put(inorder[i],i);
        }
        return build(0,0,inorder.length-1);
    }

    public TreeNode build(int root,int left,int right){
        if(left>right){
            return null;
        }
        TreeNode node = new TreeNode(preorder[root]);
        int i = mp.get(preorder[root]);
        node.left = build(root+1,left,i-1);
        node.right = build(root+1+i-left,i+1,right);
        return node;
    }
}

114. 二叉树展开为链表

力扣链接:114. 二叉树展开为链表

class Solution {
    public void flatten(TreeNode root) {
        if(root == null){
            return;
        }
        TreeNode cur = root;
        while(cur!=null){
            if(cur.left !=null){
                TreeNode next = cur.left;
                TreeNode prev = next;
                while(prev.right!=null){
                    prev = prev.right;
                }
                prev.right = cur.right;
                cur.right = next;
                cur.left = null;
            }
            cur = cur.right;
        }
    }
}

121. 买卖股票的最佳时机

力扣链接:121. 买卖股票的最佳时机

class Solution {
    public int maxProfit(int[] prices) {
        int pre = Integer.MAX_VALUE;
        int res = 0;
        for(int p:prices){
            pre = Math.min(pre,p);
            res = Math.max(p-pre,res);
        }
        return res;
    }
}

124. 二叉树中的最大路径和

力扣链接:124. 二叉树中的最大路径和

class Solution {
    int res = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return res;
    }

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

        int t = left + right + root.val;
        res = Math.max(t,res);

        return root.val + Math.max(left,right);
    }
}

128. 最长连续序列

力扣链接:128. 最长连续序列

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

136. 只出现一次的数字

力扣链接:136. 只出现一次的数字

class Solution {
    public int singleNumber(int[] nums) {
        int n = 0;
        for(int num:nums){
            n ^= num;
        }
        return n;
    }
}

139. 单词拆分

力扣链接:139. 单词拆分

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for(int i=1;i<=s.length();i++){
            for(int j=0;j<i;j++){
                if(dp[j] && set.contains(s.substring(j,i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

141. 环形链表

力扣链接:141. 环形链表

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

142. 环形链表 II

力扣链接:142. 环形链表 II

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

146. LRU 缓存

力扣链接:146. LRU 缓存

class LRUCache {
    class Node{
        int key;
        int value;
        Node prev;
        Node next;
        public Node(){}
        public Node(int key,int value){
            this.key = key;
            this.value = value;
        }
    }
    Map<Integer,Node> mp = new HashMap<>();
    Node head;
    Node tail;
    int capacity;
    int size = 0;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        if(!mp.containsKey(key)){
            return -1;
        }else{
            Node node = mp.get(key);
            deleteNode(node);
            moveToHead(node);
            return node.value;
        }
    }
    
    public void put(int key, int value) {
        if(!mp.containsKey(key)){
            if(capacity == size){
                Node node = deleteTail();
                mp.remove(node.key);
                size--;
            }
            Node node = new Node(key,value);
            mp.put(key,node);
            moveToHead(node);
            size++;
        }else{
            Node node = mp.get(key);
            node.value = value;
            deleteNode(node);
            moveToHead(node);
        }
    }

    public void deleteNode(Node node){
        node.next.prev = node.prev;
        node.prev.next = node.next;
        node.prev = null;
        node.next = null;
    }

    public void moveToHead(Node node){
        node.prev = head;
        node.next = head.next;
        head.next = node;
        node.next.prev = node;
    }

    public Node deleteTail(){
        Node node = tail.prev;
        deleteNode(node);
        return node;
    }

}

148. 排序链表

力扣链接:148. 排序链表

# 有个小细节,无头节点链表的快慢指针,快指针要快慢指针一步,不然slow指针不能从中间分隔
class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next!=null && fast.next.next !=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode t = slow.next;
        slow.next = null;
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(t);
        
        ListNode res = new ListNode();
        ListNode p = res;
        while(l1 !=null && l2 !=null){
            if(l1.val < l2.val){
                p.next = l1;
                l1=l1.next;
            }else{
                p.next = l2;
                l2 = l2.next;
            }

            p = p.next;
        }
        p.next = (l1==null) ? l2 :l1;
        return res.next;
    }
}



class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast!=null && fast.next !=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode t = slow.next;
        slow.next = null;
        
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(t);
        return merge(l1,l2);
    }

    public ListNode merge(ListNode l1,ListNode l2){
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        if(l1.val < l2.val){
            l1.next = merge(l1.next,l2);
            return l1;
        }else{
            l2.next = merge(l1,l2.next);
            return l2;
        }
    }
}

152. 乘积最大子数组

力扣链接:152. 乘积最大子数组

class Solution {
    public int maxProduct(int[] nums) {
        int res = Integer.MIN_VALUE,max = 1,min = 1;
        for(int num:nums){
            if(num<0){
                int t = max;
                max = min;
                min = t;
            }
            max = Math.max(num,num*max);
            min = Math.min(num,num*min);

            res = Math.max(res,max);
        }
        return res;
    }
}

155. 最小栈

力扣链接:155. 最小栈

class MinStack {

    Stack<Integer> stack;
    Stack<Integer> min_stack;
    public MinStack() {
        stack = new Stack<>();
        min_stack = new Stack<>();
        min_stack.push(Integer.MAX_VALUE);
    }
    
    public void push(int val) {
        stack.push(val);
        min_stack.push(Math.min(val,min_stack.peek()));
    }
    
    public void pop() {
        stack.pop();
        min_stack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return min_stack.peek();
    }
}

160. 相交链表

力扣链接:160. 相交链表

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p = headA;
        ListNode q = headB;
        while(p!=q){
            p = (p==null) ? headB : p.next;
            q = (q==null) ? headA : q.next;
        }
        return p;
    }
}

169. 多数元素

力扣链接:169. 多数元素

class Solution {
    public int majorityElement(int[] nums) {
        int cnt = 0;
        int res = nums[0];
        for(int num:nums){
            if(cnt == 0){
                res = num;
            }
            if(num == res){
                cnt++;
            }else{
                cnt--;
            }
        }
        return res;
    }
}

198. 打家劫舍

力扣链接:198. 打家劫舍

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

200. 岛屿数量

力扣链接:200. 岛屿数量

class Solution {
    public int numIslands(char[][] grid) {
        int cnt = 0;
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]=='1'){
                    dfs(grid,i,j);
                    cnt++;
                }
            }
        }
        return cnt;
    }

    public void dfs(char[][] grid,int x,int y){
        if(x<0 || y<0 || x>=grid.length || y>=grid[0].length || grid[x][y] == '0'){
            return;
        }
        grid[x][y] = '0';
        dfs(grid,x+1,y);
        dfs(grid,x-1,y);
        dfs(grid,x,y+1);
        dfs(grid,x,y-1);
    }
}

206. 反转链表

力扣链接:206. 反转链表

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

207. 课程表

力扣链接:207. 课程表

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indeg = new int[numCourses];
        List<List<Integer>> list = new ArrayList<>();
        for(int i=0;i<numCourses;i++){
            list.add(new ArrayList<>());
        }
        for(int[] e : prerequisites){
            indeg[e[0]]++;
            list.get(e[1]).add(e[0]);
        }

        Queue<Integer> qu = new LinkedList<>();
        for(int i=0;i<numCourses;i++){
            if(indeg[i]==0){
                qu.offer(i);
            }
        }
        while(!qu.isEmpty()){
            Integer node = qu.poll();
            numCourses--;
            for(int t : list.get(node)){
                indeg[t]--;
                if(indeg[t]==0){
                    qu.offer(t);
                }
            }
        }
        return numCourses == 0;

    }
}

208. 实现 Trie (前缀树)

力扣链接:208. 实现 Trie (前缀树)

class Trie {
    Trie[] child;
    boolean isEnd;
    public Trie() {
        child = new Trie[26];
        isEnd = false;
    }
    
    public void insert(String word) {
        Trie node = this;
        for(char c : word.toCharArray()){
            if(node.child[c-'a']==null){
                node.child[c-'a'] = new Trie();
            }
            node = node.child[c-'a'];
        }
        node.isEnd = true;
    }

    public Trie prefixWith(String word){
        Trie node = this;
        for(char c : word.toCharArray()){
            if(node.child[c-'a']==null){
                return null;
            }
            node = node.child[c-'a'];
        }
        return node;
    }
    
    public boolean search(String word) {
        Trie node = prefixWith(word);
        return node!=null && node.isEnd;
    }
    
    public boolean startsWith(String prefix) {
        return prefixWith(prefix)==null ? false: true;
    }
}

215. 数组中的第K个最大元素

力扣链接:215. 数组中的第K个最大元素

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return find(nums,0,nums.length-1,nums.length -k);
    }

    public int find(int[] nums,int l,int r,int k){
        int j = partition(nums,l,r);
        if(j== k){
            return nums[j];
        }
        return k<j ? find(nums,l,j-1,k) : find(nums,j+1,r,k);
    }

    public int partition(int[] nums,int l,int r){
        int t = nums[l];
        while(l<r){
            while(l<r && nums[r]>=t){
                r--;
            }
            nums[l] = nums[r];
            while(l<r && nums[l]<=t){
                l++;
            }
            nums[r] = nums[l];
        }
        nums[l] = t;
        return l;
    }
}

221. 最大正方形

力扣链接:221. 最大正方形

class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        int res = 0;
        for(int i=0;i<m;i++){
            dp[i][0] = matrix[i][0] - '0';
            res = Math.max(res,dp[i][0]);
        }
        for(int i=0;i<n;i++){
            dp[0][i] = matrix[0][i] - '0';
            res = Math.max(res,dp[0][i]);
        }

        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(matrix[i][j] == '1'){
                    dp[i][j] = Math.min(dp[i-1][j],Math.min(dp[i][j-1],dp[i-1][j-1]))+1;
                    res = Math.max(dp[i][j],res);
                }
            }
        }
        return res*res;
    }
}


class Solution {
    public int maximalSquare(char[][] matrix) {
        int res = 0;
        if(matrix.length ==0 || matrix[0].length == 0){
            return 0;
        }
        int m = matrix.length,n= matrix[0].length;
        int[][] dp = new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j]=='1'){
                    if(i==0 || j==0){
                        dp[i][j] = 1;
                    }else{
                        dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
                    }
                    res = Math.max(res,dp[i][j]);
                }
            }
        }
        return res*res;
    }
}

226. 翻转二叉树

力扣链接:226. 翻转二叉树

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

234. 回文链表

力扣链接:234. 回文链表

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast !=null && fast.next !=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode l1 = head;
        ListNode l2 = reverse(slow);
        slow.next = null;
        while(l1!=null && l2!=null && l1.val == l2.val){
            l1 = l1.next;
            l2 = l2.next;
        }
        return l1==null ;

    }

    public ListNode reverse(ListNode head){
        ListNode newhead = new ListNode();
        while(head !=null){
            ListNode cur = head;
            head= head.next;
            cur.next = newhead.next;
            newhead.next = cur;
        }
        return newhead.next;
    }
}






class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head==null || head.next == null){
            return true;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next!=null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode t = reverse(slow.next);
        slow.next = null;
        ListNode  p = head;
        ListNode  q = t;
        boolean flg = true;
        while(q!=null){
            if(flg && p.val != q.val){
                flg =  false;
            }
            p = p.next;
            q = q.next;
        }
        reverse(t);
        return flg;
    }

    public ListNode reverse(ListNode head){
        ListNode prev = null;
        ListNode curr = head;
        while(curr !=null){
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

236. 二叉树的最近公共祖先

力扣链接:236. 二叉树的最近公共祖先

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q){
            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;
    }
}

238. 除自身以外数组的乘积

力扣链接:238. 除自身以外数组的乘积

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];

        left[0] = 1;
        for(int i=1;i<n;i++){
            left[i] = left[i-1]*nums[i-1];
        }

        right[n-1] = 1;
        for(int i = n-2;i>=0;i--){
            right[i] = right[i+1]*nums[i+1];
        }

        for(int i=0;i<n;i++){
            nums[i] = left[i]* right[i];
        }
        return nums;
    }
}

239. 滑动窗口最大值

力扣链接:239. 滑动窗口最大值

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n-k+1];
        Deque<Integer> qu = new LinkedList<>();
        for(int i=0;i<n;i++){
            while(!qu.isEmpty() && nums[qu.peekLast()] < nums[i]){
                qu.pollLast();
            }
            qu.offerLast(i);
            if(qu.peekFirst() <= i-k){
                qu.pollFirst();
            }
            if(i+1>=k){
                res[i+1-k] = nums[qu.peekFirst()];
            }
        }
        return res;
    }
}

240. 搜索二维矩阵 II

力扣链接:240. 搜索二维矩阵 II

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

279. 完全平方数

力扣链接:279. 完全平方数

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        for(int i=1;i<=n;i++){
            dp[i]=i;
            for(int j=1;j*j<=i;j++){
                dp[i] = Math.min(dp[i],dp[i-j*j]+1); 
            }
        }
        return dp[n];
    }
}

283. 移动零

力扣链接:283. 移动零

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

287. 寻找重复数

力扣链接:287. 寻找重复数

class Solution {
    public int findDuplicate(int[] nums) {
        int n =nums.length;
        int fast = 0;
        int slow = 0;
        while(true){
            fast = nums[nums[fast]];
            slow = nums[slow];
            if(fast==slow){
                break;
            }
        }
        fast = 0;
        while(fast!=slow){
            fast = nums[fast];
            slow = nums[slow];
        }
        return slow;
    }
}

297. 二叉树的序列化与反序列化

力扣链接:297. 二叉树的序列化与反序列化

300. 最长递增子序列

力扣链接:300. 最长递增子序列

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int res=1;
        Arrays.fill(dp,1);
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            res = Math.max(dp[i],res);
        }
        return res;
    }
}



301. 删除无效的括号

力扣链接:301. 删除无效的括号

309. 最佳买卖股票时机含冷冻期

力扣链接:309. 最佳买卖股票时机含冷冻期

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;


        //dp[i][0] : 今天不持股,今天没卖
        //dp[i][1] : 今天不持股,今天卖的
        //dp[i][2] : 持股

        int[][] dp = new int[n][3];
        dp[0][0]=0;
        dp[0][1]=0;
        dp[0][2]=-prices[0];

        for(int i=1;i<n;i++){
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]);
            dp[i][1] = dp[i-1][2]+prices[i];
            dp[i][2] = Math.max(dp[i-1][2],dp[i-1][0]-prices[i]);
        }

        return Math.max(dp[n-1][0],dp[n-1][1]);
    }
}

312. 戳气球

力扣链接:312. 戳气球

322. 零钱兑换

力扣链接:322. 零钱兑换

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp =new int[amount+1];
        int n = coins.length;
        Arrays.fill(dp,amount+1);
        dp[0] = 0;
        for(int i=0;i<n;i++){
            for(int j=1;j<=amount;j++){
                if(j>=coins[i]){
                    dp[j] = Math.min(dp[j-coins[i]]+1,dp[j]);
                }
            }
        }
        return dp[amount]==amount+1?-1:dp[amount];
    }
}

337. 打家劫舍 III

力扣链接:337. 打家劫舍 III

// arr[0] : 当前节点不偷
 // arr[1] : 当前节点偷
class Solution {
    public int rob(TreeNode root) {
        int[] arr = func(root);
        return Math.max(arr[0],arr[1]);
    }

    public int[] func(TreeNode root){
        if(root == null){
            return new int[2];        
        }

        int[] l = func(root.left);
        int[] r = func(root.right);
        int[] arr = new int[2];

        arr[0] = Math.max(l[0],l[1]) + Math.max(r[0],r[1]);
        arr[1] = l[0] +r[0] + root.val;

        return arr;

    }
}

338. 比特位计数

力扣链接:338. 比特位计数

class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n+1];
        for(int i=0;i<=n;i++){
            res[i] = func(i);
        }
        return res;
    }

    public int func(int n){
        int cnt = 0;
        while(n!=0){
            n = (n&(n-1));
            cnt++;
        }
        return cnt;
    }
}

347. 前 K 个高频元素

力扣链接:347. 前 K 个高频元素

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> mp = new HashMap<>();
        for(int num:nums){
            mp.put(num,mp.getOrDefault(num,0)+1);
        }

        PriorityQueue<int[]> qu = new PriorityQueue<>((x,y)-> x[1]==y[1] ? x[0]-y[0] : x[1]-y[1]);

        for(int key:mp.keySet()){
            int val = mp.get(key);
            if(qu.size()==k){
                if(qu.peek()[1]<val){
                    qu.poll();
                    qu.offer(new int[]{key,val});
                }
            }else{
                qu.offer(new int[]{key,val});
            }
        }
        int[] res=  new int[k];
        for(int i=0;i<k;i++){
            res[i] = qu.poll()[0];
        }
        return res;

    }
}

394. 字符串解码

力扣链接:394. 字符串解码

class Solution {
    public String decodeString(String s) {
        StringBuilder res = new StringBuilder();
        int num =0;
        Stack<String> res_stack = new Stack<>();
        Stack<Integer> num_stack = new Stack<>();
        for(char c : s.toCharArray()){
            if(c == '['){
                res_stack.push(res.toString());
                num_stack.push(num);
                res = new StringBuilder();
                num = 0;
            }else if(c == ']'){
                int cur = num_stack.pop();
                StringBuilder t = new StringBuilder();
                for(int i=0;i<cur;i++){
                    t.append(res);
                }
                res = new StringBuilder(res_stack.pop() + t);
            }else if(c>='0' && c<='9'){
                num = num*10 + c-'0';
            }else{
                res.append(c);
            }
        }
        return res.toString();
    }
}

399. 除法求值

力扣链接:399. 除法求值

406. 根据身高重建队列

力扣链接:406. 根据身高重建队列

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people,(x,y)->(x[0]==y[0] ? x[1]-y[1] : y[0]-x[0]));
        List<int[]> res = new ArrayList<>();
        for(int[] e : people){
            res.add(e[1],e);
        }
        int[][] ans = new int[res.size()][];
        for(int i=0;i<ans.length;i++){
            ans[i] = res.get(i);
        }
        return ans;
    }
}

416. 分割等和子集

力扣链接:416. 分割等和子集

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for(int num:nums){
            sum += num;
        }
        if(sum%2!=0){
            return false;
        }
        int target = sum/2;
        boolean[][] dp = new boolean[n+1][target+1];
        dp[0][0] = true;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=target;j++){
                dp[i][j] = dp[i-1][j];
                if(j>=nums[i-1]){
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[n][target];
    }
}

437. 路径总和 III

力扣链接:437. 路径总和 III

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long,Integer> mp = new HashMap<>();
        mp.put(0L,1);
        return dfs(root,mp,targetSum,0);
    }

    public int dfs(TreeNode root,Map<Long,Integer> mp,int targetSum,long curSum){
        if(root == null){
            return 0;
        }
        int res = 0;
        curSum += root.val;
        res += mp.getOrDefault(curSum-targetSum,0);
        mp.put(curSum,mp.getOrDefault(curSum,0)+1);
        res += dfs(root.left,mp,targetSum,curSum);
        res += dfs(root.right,mp,targetSum,curSum);
        mp.put(curSum,mp.get(curSum)-1);
        return res;
    }
}

438. 找到字符串中所有字母异位词

力扣链接:438. 找到字符串中所有字母异位词

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int m = s.length();
        int n = p.length();

        List<Integer> res = new ArrayList<>();
        if(m<n){
            return res;
        }

        int[] s_arr = new int[26];
        int[] p_arr = new int[26];
        for(int i=0;i<n;i++){
            s_arr[s.charAt(i)-'a']++;
            p_arr[p.charAt(i)-'a']++;
        }
        if(Arrays.equals(s_arr,p_arr)){
            res.add(0);
        }
        for(int i=0;i<m-n;i++){
            s_arr[s.charAt(i)-'a']--;
            s_arr[s.charAt(i+n)-'a']++;

            if(Arrays.equals(s_arr,p_arr)){
                res.add(i+1);
            }
        }
        return res;
    }
}

448. 找到所有数组中消失的数字

力扣链接:448. 找到所有数组中消失的数字

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int n = nums.length;
        for(int num:nums){
            int x = (num-1)%n;
            nums[x] += n;
        }
        List<Integer> ret = new ArrayList<>();
        for(int i=0;i<n;i++){
            if(nums[i] <=n ){
                ret.add(i+1);
            }
        }
        return ret;
    }
}

461. 汉明距离

力扣链接:461. 汉明距离

class Solution {
    public int hammingDistance(int x, int y) {
        int n =x^y;
        int cnt = 0;
        while(n!=0){
            n = n&(n-1);
            cnt++;
        }
        return cnt;
    }
}

494. 目标和

力扣链接:494. 目标和

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int diff = sum - target;
        if (diff < 0 || diff % 2 != 0) {
            return 0;
        }
        int n = nums.length, neg = diff / 2;
        int[][] dp = new int[n + 1][neg + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            int num = nums[i - 1];
            for (int j = 0; j <= neg; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= num) {
                    dp[i][j] += dp[i - 1][j - num];
                }
            }
        }
        return dp[n][neg];
    }
}

538. 把二叉搜索树转换为累加树

力扣链接:538. 把二叉搜索树转换为累加树

class Solution {
    int res = 0;
    public TreeNode convertBST(TreeNode root) {
        dfs(root);
        return root;
    }

    public void dfs(TreeNode root){
        if(root == null){
            return ;
        }
        dfs(root.right);
        res += root.val;
        root.val = res;
        dfs(root.left);
    }
}

543. 二叉树的直径

力扣链接:543. 二叉树的直径

class Solution {
    int res=0;
    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return res;
    }

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

560. 和为 K 的子数组

力扣链接:560. 和为 K 的子数组

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer,Integer> mp = new HashMap<>();
        mp.put(0,1);
        int cnt = 0,pre = 0;
        for(int num:nums){
            pre+=num;
            cnt += mp.getOrDefault(pre-k,0);
            mp.put(pre,mp.getOrDefault(pre,0)+1);
        }
        return cnt;
    }
}

581. 最短无序连续子数组

力扣链接:581. 最短无序连续子数组

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int max = nums[0];
        int min = nums[n-1];
        int end=-1,start=-1;
        for(int i=0;i<n;i++){
            if(nums[i]<max){
                end = i;
            }else{
                max = nums[i];
            }
        }
        for(int i=n-1;i>=0;i--){
            if(nums[i]>min){
                start= i;
            }else{
                min = nums[i];
            }
        }
        return end==-1 ? 0:end-start +1;
    }
}

617. 合并二叉树

力扣链接:617. 合并二叉树

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1==null){
            return root2;
        }
        if(root2==null){
            return root1;
        }
        root1.val = root1.val+root2.val;
        root1.left = mergeTrees(root1.left,root2.left);
        root1.right = mergeTrees(root1.right,root2.right);
        return root1;
    }
}

621. 任务调度器

力扣链接:621. 任务调度器

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] arr = new int[26];
        Arrays.fill(arr,0);
        for(char c: tasks){
            arr[c-'A']++;
        }
        int max = 0;
        for(int num:arr){
            max = Math.max(max,num);
        }
        int time= (max-1)*(n+1);
        for(int num:arr){
            if(num==max){
                time++;
            }
        }
        return Math.max(time,tasks.length);
    }
}

647. 回文子串

力扣链接:647. 回文子串

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        int cnt = 0;
        for(int i=0;i<2*n+1;i++){
            int l = i/2;
            int r = l + i %2;
            while(l>=0 && r<n && s.charAt(l)==s.charAt(r)){
                cnt++;
                l--;
                r++;
            }
        }
        return cnt;
    }
}

739. 每日温度

力扣链接:739. 每日温度

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        Stack<Integer> stack = new Stack<>();
        for(int i=0;i<n;i++){
            while(!stack.isEmpty() && temperatures[stack.peek()]<temperatures[i]){
                int idx = stack.pop();
                res[idx] =i-idx;
            }
            stack.push(i);
        }
        return res;
    }
}

如有侵权,请联系我