力扣100热题

记录一下算法

哈希

字母异位词

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

1 2	输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

思路：遍历每一个字符串，对其排序得到newstr，利用一个hashmap，key为排序后的字符串newstr，value为排序为newstr的字符串，如果map里面没有newstr，则创建一个list并添加当前遍历的字符串,如果已经有了newstr，则将当前遍历的字符串加入进去。遍历完后map里面的key就是答案。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res=new ArrayList<>();
        Map<String,List<String>> map=new HashMap<>();
        for(String s:strs){
            char str[]=s.toCharArray();
            Arrays.sort(str);
            String newstr=new String(str);
            if(map.containsKey(newstr)){
                map.get(newstr).add(s);
            }else{
                List<String> a=new ArrayList<>();
                a.add(s);
                map.put(newstr,a);
            }
        }
        for(Map.Entry<String,List<String>> entry:map.entrySet()){
            res.add(entry.getValue());
        }
        return res;
    }
}

最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

1
2
3

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

思路：先利用set去重。遍历set，找到起始元素，如果遍历到num，且存在num-1。则num不是起始元素。找到起始元素后以此判断num+1是否存在，如果存在，更新最长长度。

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

滑动窗口

无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

1
2
3

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

思路：滑动窗口通式：

定义窗口状态为无重复字符，用一个map来记录字符个数。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int map[] = new int[200];
        char str[] = s.toCharArray();
        int res = 0;
        for (int left = 0, right = 0; right < s.length(); right++) {
            map[str[right]]++;
            while (map[str[right]] > 1) {
                map[str[left]]--;
                left++;
            }
            res = Math.max(res, right - left + 1);
        }
        return res;
    }
}

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

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

思路：小技巧：将map初始化为p的字符数量，加入窗口时做的是–，当遇到不是p中的字符数，会变成负数。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int map[] = new int[300];
        char str[] = s.toCharArray();
        for (Character ch : p.toCharArray()) {
            map[ch]++;
        }
        List<Integer> res = new ArrayList<>();
        for (int left = 0, right = 0; right < s.length(); right++) {
            map[str[right]]--;
            while (map[str[right]] < 0) {
                map[str[left]]++;
                left++;
            }
            if (right - left + 1 == p.length()) {
                res.add(left);
            }
        }
        return res;
    }
}

子串

和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

1 2	输入：nums = [1,1,1], k = 2 输出：2

思路：求子数组的和，首先想到前缀和，等价与求prefix[j]-prefix[i-1]=k ==> prefix[j]-k=prefix[i-1]==》两数之和

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int prefixSum[] = new int[n];
        int sum = 0;
        int count = 0;
        for (int i = 0; i < n; i++) {
            sum = sum + nums[i];
            prefixSum[i] = sum;
        }

        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int num : prefixSum) {
            if (map.containsKey(num - k)) {
                count = count + map.get(num - k);
            }
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        return count;
    }
}

滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

1 2	输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7]

思路：维护一个双端队列，且要是从左(尾)到右(头)是单调的。看代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int res[] = new int[n - k + 1];
        Deque<Integer> q = new ArrayDeque<>();
        int index = 0;
        for (int i = 0; i < n; i++) {
            //判断队列的最大值是否还在当前窗口
            while (!q.isEmpty() && q.peekFirst() < i - k + 1) {
                q.pollFirst();
            }
            //维护单调队列
            while (!q.isEmpty() && nums[i] > nums[q.peekLast()]) {
                q.pollLast();
            }
            q.addLast(i);
            //到了收集的位置才收集
            if (i - k + 1 >= 0) {
                res[index++] = nums[q.peekFirst()];
            }
        }
        return res;
    }
}

普通数组

最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

1
2
3

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

思路1：前缀和，题目求nums[i,j]的最大值，等价于求prefixSum[j]-prefixSum[i-1]的最大值。

class Solution {
    public int maxSubArray(int[] nums) {

        int prefixSum[] = new int[nums.length];
        prefixSum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i];
        }

        int max = Integer.MIN_VALUE;
        int min = 0;
        for (int num : prefixSum) {
            max = Math.max(max, num - min);
            min = Math.min(min, num);
        }
        return max;
    }
}

思路2：动态规划：dp[i]表示以nums[i]结尾的连续子数组最大和。

1
2
3

转移方程：dp[i]=nums[i]+max(d[i-1],0)
如果dp[i-1]是负数，则是负优化，舍弃。
如果dp[i-1]是正数，则是正优化，加上。

class Solution {
    public int maxSubArray(int[] nums) {

        int dp[]=new int[nums.length];
        dp[0]=nums[0];
        int max=dp[0];
        for(int i=1;i<nums.length;i++){
            dp[i]=nums[i]+Math.max(0,dp[i-1]);
            max=Math.max(max,dp[i]);
        }
        return max;
        
    }
}

空间优化：dp[i]只依赖于dp[i-1]，所以可以不用数组，用一个变量premax=nums[i]+Math.max(0,premax);右侧的premax就是先前的值，左侧的premax就是等待更新的值。

class Solution {
    public int maxSubArray(int[] nums) {

        int max = nums[0];
        int premax = nums[0];
        for (int i = 1; i < nums.length; i++) {
            premax = nums[i] + Math.max(0, premax);
            max = Math.max(max, premax);
        }
        return max;

    }
}

合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

1
2
3

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

思路：先对数组排序，排序规则为按照第一个元素排序。排序之后把第一个元素加入到一个集合里，然后遍历后面的数组，如果集合的最后一个数组的[1]>=当前遍历数组的[0]，说明这两个数组可以合并，集合的最后一个数组的[1]=这两个数组的[1]的最大值。如果不能合并就直接加入到集合里，最后把集合转成数组。

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int[]> res = new ArrayList<>();
        res.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            int listEnd[] = res.get(res.size() - 1);
            int interval[] = intervals[i];
            if (listEnd[1] >= interval[0]) {
                listEnd[1] = Math.max(listEnd[1], interval[1]);
            } else {
                res.add(interval);
            }
        }
        return res.toArray(new int[res.size()][2]);
    }
}

轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

1 2	输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4]

思路1：先将整个数组翻转，再翻转0到k-1,再翻转k到n-1;注意k>n的的话要取余。

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;

        reverse(nums, 0, n - 1);
        reverse(nums, 0, k % n - 1);
        reverse(nums, k % n, n - 1);
    }

    public void reverse(int nums[], int i, int j) {
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

    public void swap(int nums[], int i, int j) {
        int temp = nums[j];
        nums[j] = nums[i];
        nums[i] = temp;
    }
}

思路2：原地打转（环形替换）：将数组看成一个环，每一个元素都有一个目标值，环上的元素依次向右移动，直到回到原点。

用cur记录当前位置（最开始是start=0），pre保存当前位置的值,计算出下一个位置的值nextIndex，把下一个位置的值先保存在temp中，再替换成pre，然后cur移动到nextIndex重复下一次，没移动一次就技术一次，每个元素都操作完成后就结束循环。

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        int count = 0;
        int start = 0;
        while (count < n) {
            int cur = start;
            int pre = nums[cur];
            do {
                int nextIndex = (cur + k) % n;
                int temp = nums[nextIndex];
                nums[nextIndex] = pre;
                pre = temp;
                cur = nextIndex;
                count++;
            } while (cur != start);
            start++;
        }
    }

}

除自身以外数组的乘积

给你一个整数数组 nums，返回数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:

1 2	输入: nums = [1,2,3,4] 输出: [24,12,8,6]

思路1：空间优化：不用额外定义两个数组，第一次遍历后顺便求出前缀乘积，第二次遍历顺便求出后缀乘积。

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int res[] = new int[nums.length];
        for (int i = 0; i < res.length; i++) {
            res[i] = 1;
        }
        int left = 1;
        for (int i = 0; i < nums.length; i++) {
            res[i] *= left;
            left *= nums[i];
        }
        int right = 1;
        for (int j = nums.length - 1; j >= 0; j--) {
            res[j] *= right;
            right *= nums[j];
        }
        return res;
    }
}

缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

1
2
3

输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

思路：原地哈希。既然是找最小的正整数，所以我们只关心[1,n]。对于理想情况下标0处的位置是1，下标1处的位置是2。。。。。。

所以遍历数组时候，我们把当前处于[1,n]内的元素放在他理想情况的位置，其他的不管。这样处理后得到的数组就会是1，2，。。。。这样的，我们按顺序遍历，当出现顺序不对的时候，说明缺失的最小的正整数就是他。

class Solution {
    public int firstMissingPositive(int[] nums) {
        /**
         0  1  2 3
         1 -1  3 4
        
         */
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] < 1 || nums[i] > n) {
                continue;
            }
            if (nums[i] != nums[nums[i] - 1]) {
                swap(nums,i,nums[i]-1);
              
                
                i--;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }

    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

矩阵

矩阵置零

给定一个 *m* x *n* 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用原地算法。

示例 1：

1 2	输入：matrix = [[1,1,1],[1,0,1],[1,1,1]] 输出：[[1,0,1],[0,0,0],[1,0,1]]

思路1：用两个行列数组来标记哪一行哪一列有0：

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int hang[] = new int[matrix.length];
        int lie[] = new int[matrix[0].length];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    hang[i] = 1;
                    lie[j] = 1;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (hang[i] == 1) {
                    matrix[i][j] = 0;
                }
                if (lie[j] == 1) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

空间优化：不用额外数组，直接利用第一行和第一列

class Solution {
    public void setZeroes(int[][] matrix) {
        boolean hang=false;
        boolean lie=false;
        int m=matrix.length,n=matrix[0].length;
        //提前记录第一行和第一列是否有0
        for(int i=0;i<m;i++){
            if(matrix[i][0]==0){
                lie=true;
                break;
            }
        }
        for(int i=0;i<n;i++){
            if(matrix[0][i]==0){
                hang=true;
                break;
            }
        }
        //遍历内部，遇到0，把队友的行和列标记再第一行和第一列
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(matrix[i][j]==0){
                    matrix[0][j]=0;
                    matrix[i][0]=0;
                }
            }
        }

        for(int i=1;i<m;i++){
            if(matrix[i][0]==0){
                for(int j=0;j<n;j++){
                    matrix[i][j]=0;
                }
            }
        }
        //遍历第一行和列，遇到0，把该行和列置0；
        for(int i=1;i<n;i++){
            if(matrix[0][i]==0){
                for(int j=0;j<m;j++){
                    matrix[j][i]=0;
                }
            }
        }
        //处理第一行和列
        if(hang){
            for(int i=0;i<n;i++){
                matrix[0][i]=0;
            }
        }
        if(lie){
            for(int i=0;i<m;i++){
                matrix[i][0]=0;
            }
        }
    }
}

螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

1 2	输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]

思路：从上->右->下->左遍历

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int left = 0, top = 0, right = matrix[0].length - 1, down = matrix.length - 1;
        while (left <= right && top <= down) {
            for (int i = left; i <= right; i++) {
                res.add(matrix[top][i]);
            }
            top++;
            for (int i = top; i <= down; i++) {
                res.add(matrix[i][right]);
            }
            right--;

            if (top <= down) {
                for (int i = right; i >= left; i--) {
                    res.add(matrix[down][i]);
                }
                down--;
            }

            if (left <= right) {
                for (int i = down; i >= top; i--) {
                    res.add(matrix[i][left]);
                }
                left++;
            }
        }
        return res;
    }
}

旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在** 原地** 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

1 2	输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[[7,4,1],[8,5,2],[9,6,3]]

思路1:先对角线翻转再垂直翻转，或者先水平翻转再对角线翻转；

class Solution {
    public void rotate(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int left = 0, right = n - 1;
        for (int i = 0; i < m; i++) {
            for (int j = i; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        while (left < right) {
            for (int i = 0; i < m; i++) {
                int temp = matrix[i][left];
                matrix[i][left] = matrix[i][right];
                matrix[i][right] = temp;
            }
            left++;
            right--;
        }

    }
}

思路2：缩圈法：看代码推导

class Solution {
    public void rotate(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        //1 2 3 4 5 6 7 8
        //(i,j)->(j,n-1-i);
        //(j,n-1-i)->(n-1-i,n-1-j);
        //(n-1-i,n-1-j)->(n-1-j,i);
        //(n-1-j,i)->(i,j);
        for (int i = 0; i < m / 2; i++) {
            for (int j = i; j < n - 1 - i; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - j][i];
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
                matrix[j][n - 1 - i] = temp;
            }
        }

    }
}

搜索二维矩阵 II

编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例 1：

1 2	输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5 输出：true

思路： //观察到右上角元素是这一行的最大值，是这一列的最小值。利用这个思想来进行伪二分

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        //观察到右上角元素是这一行的最大值，是这一列的最小值。
        int m = matrix.length;//1
        int n = matrix[0].length;//2
        int right = n - 1;
        int top = 0;
        while (right >= 0 && top <= m - 1) {
            if (matrix[top][right] == target) {
                return true;
            } else if (matrix[top][right] > target) {
                right--;
            } else {
                top++;
            }
        }
        return false;
    }
}

链表

相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。

思路1：计算两个链表长度，让长的链表走差值。

思路2：用一个集合存储其中一个链表的路径，走第二个链表时判断当前节点是否在集合中。

思路3：走你走过的路：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* getIntersectionNode(struct ListNode* headA,
                                     struct ListNode* headB) {
    struct ListNode* A = headA;
    struct ListNode* B = headB;
    while (A != B) {
        A = A ? A->next : headB;
        B = B ? B->next : headA;
    }
    return A;
}

反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

1 2	输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]

思路：没什么好说的：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* dum = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* p = head;
    dum->next = NULL;
    while (p) {
        struct ListNode* q = p->next;
        p->next = dum->next;
        dum->next = p;
        p = q;
    }
    return dum->next;
}

回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

1 2	输入：head = [1,2,2,1] 输出：true

思路：用快慢指针找到中间节点，把中间节点后面翻转，然后对比。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverse(struct ListNode* head) {
    struct ListNode* dum = (struct ListNode*)malloc(sizeof(struct ListNode));
    dum->next = NULL;
    struct ListNode* p = head;
    while (p) {
        struct ListNode* q = p->next;
        p->next = dum->next;
        dum->next = p;
        p = q;
    }
    return dum->next;
}
bool isPalindrome(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    struct ListNode* re = reverse(slow->next);
    slow->next = re;
    struct ListNode* p = slow->next;
    while (p) {
        if (p->val != head->val) {
            return false;
        }
        p = p->next;
        head = head->next;
    }
    return true;
}

环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。否则，返回 false 。

示例 1：

1
2
3

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

思路：快慢指针：龟兔一直赛跑，兔子总是能追上龟：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode* head) {
    if (head == NULL) {
        return false;
    }
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

1
2
3

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

思路：

当 n=1 时（快指针恰好比慢指针多走一圈）：此时a=c,即：头节点到环入口的距离 = 相遇点到环入口的距离

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* detectCycle(struct ListNode* head) {
    if (!head)
        return NULL;
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            while (slow != head) {
                slow = slow->next;
                head = head->next;
            }
            return slow;
        }
    }
    return NULL;
}

合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

1 2	输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]

思路：没什么好说的

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next = NULL;
    struct ListNode* p = head;
    while (list1 && list2) {
        if (list1->val < list2->val) {
            p->next = list1;
            list1 = list1->next;

        } else {
            p->next = list2;
            list2 = list2->next;
        }
        p = p->next;
    }
    p->next = list1 ? list1 : list2;
    return head->next;
}

两数相加

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

1
2
3

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

思路：就是一个模拟十进制进位的过程，没什么好说的，提前把进位设置为0：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    // 2 4 3 8 9 9
    // 5 9 6
    // 7 3 0 9 9 9
    struct ListNode* p = l1;
    struct ListNode* q = l2;
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));

    head->next = NULL;
    struct ListNode* r = head;
    int jin = 0;

    while (p || q) {
        int a = p ? p->val : 0;
        int b = q ? q->val : 0;
        int sum = (a + b + jin);
        int res = sum % 10;
        jin = sum / 10;
        struct ListNode* node =
            (struct ListNode*)malloc(sizeof(struct ListNode));
        node->val = res;
        node->next = r->next;
        r->next = node;
        r = node;

        if (p)
            p = p->next;
        if (q)
            q = q->next;
    }
    if (jin == 1) {
        struct ListNode* node =
            (struct ListNode*)malloc(sizeof(struct ListNode));
        node->val = 1;
        node->next = r->next;
        r->next = node;
        r = node;
    }
    return head->next;
}

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

1 2	输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]

思路：先让一个指针p走n次，然后再让另一个指针first和p同步走，当p走到尾节点时，first的下一个节点就是要删除的；

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode* dum = (struct ListNode*)malloc(sizeof(struct ListNode));
    dum->next = head;
    struct ListNode* p = dum;
    for (int i = 0; i < n; i++) {
        p = p->next;
    }
    struct ListNode* first = dum;
    while (p->next) {
        p = p->next;
        first = first->next;
    }
    first->next = first->next->next;
    return dum->next;
}

两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

1 2	输入：head = [1,2,3,4] 输出：[2,1,4,3]

思路：理想情况是两两交换，看图：

两两成对时，最后p为空；结束循环。

有一个单独节点时，p存在、q为空，其实就不同调整，也就是不管了，直接结束循环。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* swapPairs(struct ListNode* head) {
    //[] 1 2 3 4
    //[] 2 1 3 4
    if (!head)
        return head;
    if (head->next == NULL) {
        return head;
    }
    struct ListNode* dum = (struct ListNode*)malloc(sizeof(struct ListNode));
    dum->next = head;
    struct ListNode* pre = dum;
    struct ListNode* p = pre->next;
    struct ListNode* q = pre->next->next;
    while (p && q) {
        p->next = q->next;
        q->next = pre->next;
        pre->next = q;
        pre = q->next;
        p = pre->next;
        if (p)
            q = p->next;
    }
    return dum->next;
}

随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码只接受原链表的头节点 head 作为传入参数。

示例 1：

1 2	输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

思路：特别恶心的一道题，编译器不告诉你哪里空指针。填充链表。

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

struct Node* copyRandomList(struct Node* head) {
    // 先不填充random
    struct Node* dum = (struct Node*)malloc(sizeof(struct Node));
    dum->next = head;
    struct Node* p = dum->next;
    while (p) {
        struct Node* node = (struct Node*)malloc(sizeof(struct Node));
        // 特别注意要初始化random
        node->random = NULL;
        node->val = p->val;
        node->next = p->next;
        p->next = node;
        p = node->next;
    }
    p = dum->next;

    while (p) {
        // 特别注意
        if (p->random != NULL) {
            p->next->random = p->random->next;
        }
        p = p->next->next;
    }
    struct Node* s = dum;
    // 特别注意，编译器不告诉你哪里空指针
    while (s && s->next) {
        s->next = s->next->next;
        s = s->next;
    }
    return dum->next;
}

排序链表

给你链表的头结点 head ，请将其按升序排列并返回 排序后的链表 。

示例 1：

1 2	输入：head = [4,2,1,3] 输出：[1,2,3,4]

思路：细节点：空指针的判断，可以一个一个试

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* merge(struct ListNode* pre, struct ListNode* l1,
                       struct ListNode* l2);
struct ListNode* sortList(struct ListNode* head) {
    struct ListNode* dum = (struct ListNode*)malloc(sizeof(struct ListNode));
    dum->next = head;
    struct ListNode* p = head;
    int length = 0;
    while (p) {
        length++;
        p = p->next;
    }

    for (int len = 1; len < length; len = len * 2) {
        struct ListNode* pre = dum;
        struct ListNode* cur = dum->next;
        while (cur) {
            struct ListNode* left = cur;
            for (int i = 1; i < len && cur->next; i++) {
                cur = cur->next;
            }
            struct ListNode* right = cur->next;
            cur->next = NULL;
            cur = right;
            for (int i = 1; i < len && cur && cur->next; i++) {
                cur = cur->next;
            }
            struct ListNode* next = NULL;
            if (cur) {
                next = cur->next;
                cur->next = NULL;
            }

            pre = merge(pre, left, right);
            cur = next;
        }
    }
    return dum->next;
}

struct ListNode* merge(struct ListNode* pre, struct ListNode* l1,
                       struct ListNode* l2) {
    while (l1 && l2) {
        if (l1->val < l2->val) {
            pre->next = l1;
            l1 = l1->next;
        } else {
            pre->next = l2;
            l2 = l2->next;
        }
        pre = pre->next;
    }
    pre->next = l1 ? l1 : l2;
    while (pre->next) {
        pre = pre->next;
    }
    return pre;
}

合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

1 2	输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6]

思路1：采用归并排序的思想：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* merge(struct ListNode* l1, struct ListNode* l2);
struct ListNode* mergeSort(struct ListNode** lists, int low, int high);
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
    if (!lists || listsSize == 0)
        return NULL;

    return mergeSort(lists, 0, listsSize - 1);
}
struct ListNode* mergeSort(struct ListNode** lists, int low, int high) {
    if (low >= high) {
        return lists[low];
    }
    int mid = (low + high) / 2;
    struct ListNode* l1 = mergeSort(lists, low, mid);
    struct ListNode* l2 = mergeSort(lists, mid + 1, high);
    return merge(l1, l2);
}
struct ListNode* merge(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* dum = (struct ListNode*)malloc(sizeof(struct ListNode));
    dum->next = NULL;
    struct ListNode* p = dum;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            p->next = l1;
            l1 = l1->next;
        } else {
            p->next = l2;
            l2 = l2->next;
        }
        p = p->next;
    }
    p->next = l1 ? l1 : l2;
    return dum->next;
}

思路2：利用java的小根堆，把所有节点插入到小根堆

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> q = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode list : lists) {
            while (list != null) {
                q.add(list);
                list = list.next;
            }
        }

        ListNode head = new ListNode();
        head.next = null;
        ListNode r = head;
        while (!q.isEmpty()) {
            ListNode node = q.poll();
            node.next = r.next;
            r.next = node;
            r = node;
        }
        return head.next;
    }

}

LRU 缓存

思路：也是非常恶心的题目：

class LRUCache {
    class Node {
        int key;
        int value;
        Node pre;
        Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private HashMap<Integer, Node> map;
    private Node head;
    private Node tail;
    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        //先查询，如果存在，先更新双链表，再返回；
        //不存在，返回-1
        Node p = map.get(key);
        if (p == null) {
            return -1;
        }
        movetofirst(p);
        return p.value;
    }

    public void put(int key, int value) {
        /**
        先查询是否有这个key
        如果有这个key，更新value的值。
        如果没有这个key，先判断map 的容量满没满；
        如果满的，先删除尾节点和队友的map，再put，再更新链表
        如果没满，则put，再更新链表
         */
        Node p = map.get(key);
        if (p == null) {
            Node newnode = new Node(key, value);
            if (map.size() >= capacity) {
                Node q = deleteTail();
                map.remove(q.key);

            }
            map.put(key, newnode);
            addtoHead(newnode);

        } else {
            p.value = value;
            map.put(key, p);
            movetofirst(p);
        }
    }

    //新增节点到头部；
    public void addtoHead(Node node) {
        node.next = head.next;
        node.pre = head;
        head.next = node;
        head.next.next.pre = node;
    }

    //删除指定节点
    public void delete(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    //移动指定节点到头部
    public void movetofirst(Node node) {
        delete(node);
        addtoHead(node);
    }

    //删除并返回末尾节点；
    public Node deleteTail() {
        Node p = tail.pre;
        delete(tail.pre);
        return p;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

1
2
3

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

思路：直接看代码：

class Solution {
    public String minWindow(String s, String t) {
        char str[] = s.toCharArray();
        int map[] = new int[300];
        for (char ch : t.toCharArray()) {
            map[ch]++;
        }
        int resleft = 0, resright = s.length();
        int count = 0;
        for (int left = 0, right = 0; right < s.length(); right++) {
            map[str[right]]--;
            if (map[str[right]] >= 0) {
                count++;
            }
            while (count == t.length()) {
                if (resright - resleft > right - left) {
                    resleft = left;
                    resright = right;
                }

                if (map[str[left]] >= 0) {
                    count--;
                }
                map[str[left]]++;

                left++;

            }
        }

        return resright == str.length ? "" : s.substring(resleft, resright + 1);
    }
}

二叉树（Morris）

二叉树的中序遍历(√)

给定一个二叉树的根节点 root ，返回 它的中序遍历 。

1 2	输入：root = [1,null,2,3] 输出：[1,3,2]

解法：没啥好说的。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void zhongxu(struct TreeNode* root, int* res, int* returnSize);
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int* res = (int*)malloc(sizeof(int) * 1000);
    *returnSize = 0;
    zhongxu(root, res, returnSize);
    return res;
}
void zhongxu(struct TreeNode* root, int* res, int* returnSize) {
    if (root == NULL) {
        return;
    }
    zhongxu(root->left, res, returnSize);
    res[(*returnSize)++] = root->val;
    zhongxu(root->right, res, returnSize);
}

二叉树的最大深度(√)

给定一个二叉树 root ，返回其最大深度。

解法：没啥好说的。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int deep(struct TreeNode* root);
int maxDepth(struct TreeNode* root) { return deep(root); }
int deep(struct TreeNode* root) {
    if (!root) {
        return 0;
    }
    int l = deep(root->left);
    int r = deep(root->right);
    return (l > r ? l : r) + 1;
}

翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

1 2	输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]

解法：只能用后续遍历。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
void reverse(struct TreeNode* root);
struct TreeNode* invertTree(struct TreeNode* root) {
    reverse(root);
    return root;
}

void reverse(struct TreeNode* root) {
    if (!root) {
        return;
    }
    reverse(root->left);
    reverse(root->right);
    struct TreeNode* temp = root->left;
    root->left = root->right;
    root->right = temp;
}

对称二叉树

给你一个二叉树的根节点 root ，检查它是否轴对称。

解法：利用队列。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root->left);
        q.push(root->right);
        while (!q.empty()) {
            TreeNode* l = q.front();
            q.pop();
            TreeNode* r = q.front();
            q.pop();
            if (!l && !r)
                continue;
            if (l == NULL || r == NULL || l->val != r->val)
                return false;
            q.push(l->left);
            q.push(r->right);
            q.push(l->right);
            q.push(r->left);
        }
        return true;
    }
};

二叉树的直径

给你一棵二叉树的根节点，返回该树的直径。

二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的长度由它们之间边数表示。

1
2
3

输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

解法：问题转换为：对于任意一个节点，经过该节点的最长路径 = 左子树深度 + 右子树深度。我们需要遍历所有节点，找到这个最大值。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int max(int a, int b) { return a > b ? a : b; }
int func(struct TreeNode* root, int* res) {
    if (root == NULL) {
        return 0;
    }
    int l = func(root->left, res);
    int r = func(root->right, res);
    *res = max(*res, l + r);
    return max(l, r) + 1;
}
int diameterOfBinaryTree(struct TreeNode* root) {
    int res = 0;
    func(root, &res);
    return res;
}

二叉树的层序遍历(√)

1 2	输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]

解法：没啥好说的。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {

        queue<TreeNode*> q;
        vector<vector<int>> res;
        if (!root)
            return res;
        q.push(root);
        while (!q.empty()) {
            int size = q.size();
            vector<int> temp;
            for (int i = 0; i < size; i++) {
                TreeNode* p = q.front();
                q.pop();
                temp.push_back(p->val);
                if (p->left)
                    q.push(p->left);
                if (p->right)
                    q.push(p->right);
            }
            res.push_back(temp);
        }
        return res;
    }
};

将有序数组转换为二叉搜索树(x)

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵平衡二叉搜索树。

解法：由于输入数组已经有序，选择中间元素作为根节点，左半部分构建左子树，右半部分构建右子树，这样可以保证树的高度平衡。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* addNode(int data) {
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left = NULL;
    root->right = NULL;
    root->val = data;
    return root;
}
struct TreeNode* create(int* nums, int left, int right) {
    if (left > right) {
        return NULL;
    }
    int mid = left + (right - left) / 2;
    struct TreeNode* root = addNode(nums[mid]);
    root->left = create(nums, left, mid - 1);
    root->right = create(nums, mid + 1, right);
    return root;
}
struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {
    return create(nums, 0, numsSize - 1);
}

验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

解法：用一个前驱节点来保存。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool func(struct TreeNode* root, struct TreeNode** pre) {
    if (!root) {
        return true;
    }
    bool l = func(root->left, pre);
    if ((*pre) != NULL && (*pre)->val >= root->val) {
        return false;
    }
    (*pre) = root;
    bool r = func(root->right, pre);
    return l && r;
}
bool isValidBST(struct TreeNode* root) {
    struct TreeNode* pre = NULL;

    return func(root, &pre);
}

二叉搜索树中第 K 小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

1 2	输入：root = [3,1,4,null,2], k = 1 输出：1

解法：跟踪计数。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
void func(struct TreeNode* root, int k, int* count, int* res) {
    if (!root)
        return;
    func(root->left, k, count, res);
    (*count)++;
    if (*count == k) {
        *res = root->val;
    }
    func(root->right, k, count, res);
}
int kthSmallest(struct TreeNode* root, int k) {
    int res = 0;
    int count = 0;
    func(root, k, &count, &res);
    return res;
}

二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

1
2
3

输入：root = [1,2,3,4,null,null,null,5]

输出：[1,3,4,5]

解法：就是层序遍历，只取最右边的值。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        vector<int> res;
        if (!root) {
            return res;
        }
        while (!q.empty()) {
            int n = q.size();
            for (int i = 0; i < n; i++) {
                TreeNode* p = q.front();
                q.pop();
                if (i == n - 1) {

                    res.push_back(p->val);
                }
                if (p->left)
                    q.push(p->left);
                if (p->right)
                    q.push(p->right);
            }
        }
        return res;
    }
};

二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

1 2	输入：root = [1,2,5,3,4,null,6] 输出：[1,null,2,null,3,null,4,null,5,null,6]

解法1：反向先序遍历，右→左→中。看代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
void func(struct TreeNode* root, struct TreeNode** pre) {
    if (!root)
        return;
    func(root->right, pre);
    func(root->left, pre);
    root->right = *pre;
    root->left = NULL;
    *pre = root;
}
void flatten(struct TreeNode* root) {
    struct TreeNode* pre = NULL;
    func(root, &pre);
}

解法2：Morris思想，我们要按前序遍历的顺序重新组织节点：

根 → 左子树 → 右子树

对于每个节点，如果它有左子树，我们需要找到左子树的最右节点

将当前节点的右子树接到左子树最右节点的右边

然后将左子树移到右边，左子树置为null

用图来理解：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

void flatten(struct TreeNode* root) {
    struct TreeNode* p = root;
    while (p) {
        if (p->left != NULL) {
            struct TreeNode* temp = p->left;
            while (temp->right) {
                temp = temp->right;
            }
            temp->right = p->right;
            p->right = p->left;
            p->left = NULL;
        }
        p = p->right;
    }
}

路径总和 III(x)

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

1
2
3

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

解法：

核心思想： 我们可以利用前缀和的性质来快速判断任意一段路径的和。

什么是前缀和？ 在二叉树的路径中，从根节点到当前节点的所有节点值之和，就是当前节点的前缀和。

关键观察： 如果我们知道两个节点的前缀和分别是 prefixSum1 和 prefixSum2，那么这两个节点之间的路径和就是：

1	路径和 = prefixSum2 - prefixSum1

转化问题： 原问题：找路径和等于 targetSum 的路径数量转化为：找两个节点，使得它们的前缀和之差等于 targetSum

即：prefixSum2 - prefixSum1 = targetSum 也就是：prefixSum1 = prefixSum2 - targetSum

举个例子：

节点10的前缀和：10
节点5的前缀和：10 + 5 = 15
节点3的前缀和：10 + 5 + 3 = 18

如果 targetSum = 8，我们要找前缀和为 18 - 8 = 10 的节点，正好是根节点10！所以路径 5 -> 3 的和就是 8。

哈希表存储

Key： 前缀和的值

Value： 该前缀和出现的次数

为什么要记录次数？ 因为可能有多个节点具有相同的前缀和（特别是有负数节点时），每个都对应一条有效路径。

为什么要移除当前节点的前缀和？

因为我们的哈希表只应该存储当前路径上的前缀和，而不是整棵树所有访问过的节点的前缀和。

用例子说明：

假设 targetSum = 3，让我们跟踪遍历过程：

第一条路径：1 -> 2 -> 4

节点1：currentSum=1，哈希表={0:1, 1:1}
节点2：currentSum=3，哈希表={0:1, 1:1, 3:1}，找到路径1->2
节点4：currentSum=7，哈希表={0:1, 1:1, 3:1, 7:1}
回溯到节点2：移除7，哈希表={0:1, 1:1, 3:1}
回溯到节点1：移除3，哈希表={0:1, 1:1}

第二条路径：1 -> 3 6. 节点3：currentSum=4，哈希表={0:1, 1:1, 4:1}

如果不回溯会怎样？ 当处理节点3时，哈希表仍然是{0:1, 1:1, 3:1, 7:1}，这样就会错误地认为节点2和节点4还在当前路径上，可能产生错误的路径计算。

回溯的本质： 确保哈希表始终只包含从根节点到当前节点这条路径上的前缀和，保证计算的正确性。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
public:
    int func(TreeNode* root, int targetSum, long long cur,
             unordered_map<long long, int>& map) {
        if (!root)
            return 0;
        cur = cur + root->val;
        int count = map[cur - targetSum];//不能用targetSum-cur，只有cur - targetSum才是下面的-上面的
        map[cur]++;
        count = count + func(root->left, targetSum, cur, map);
        count = count + func(root->right, targetSum, cur, map);
        map[cur]--;
        return count;
    }
    int pathSum(TreeNode* root, int targetSum) {
        unordered_map<long long, int> map;
        map[0] = 1;
        return func(root, targetSum, 0, map);
    }
};

二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

1
2
3

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

解法：

如果root为空，直接返回
如果root=p或者q，返回root。
如果在左右子树都找到了p或者q。说明当前节点就是祖先
如果左边找到了p右边没找到q，说明q在左下
如果在右边找到了p左边没找到q，说明q在右下

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* func(struct TreeNode* root, struct TreeNode* p,
                      struct TreeNode* q) {
    if (!root)
        return NULL;
    if (root == p || root == q)
        return root;
    struct TreeNode* left = func(root->left, p, q);
    struct TreeNode* right = func(root->right, p, q);
    if (left != NULL && right != NULL)
        return root;
    if (left != NULL)
        return left;
    return right;
}
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p,
                                      struct TreeNode* q) {
    return func(root, p, q);
}

二叉树中的最大路径和(背)

二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

1
2
3

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

解法：

对于每个节点，我们需要考虑两种情况：

经过该节点的最大路径和（该节点作为路径的”转折点”）
以该节点为端点向上延伸的最大路径和（该节点作为路径的一端，可以向上连接到父节点）

这两个概念完全不同：

第一种情况：路径在该节点”拐弯”，左右子树都可能被包含
第二种情况：路径在该节点”向上延伸”，只能选择左子树或右子树其中之一

递归函数返回： 以node为端点向上延伸的最大路径和，同时在递归过程中更新全局最大值。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
// 递归函数返回的当前节点向上延伸的最大路径和
int Max(int a, int b) { return a > b ? a : b; }
int func(struct TreeNode* root, int* max) {
    if (!root)
        return 0;
    int left = Max(0, func(root->left, max));
    int right = Max(0, func(root->right, max));
    int nowPath = root->val + left + right;
    *max = Max(*max, nowPath);
    return root->val + Max(left, right);
}
int maxPathSum(struct TreeNode* root) {
    int max = -0xffffff;
    func(root, &max);
    return max;
}

从前序与中序遍历序列构造二叉树(背)

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

1
2
3

前序：[1,2,4,5,3,6]

中序：[4,2,5,1,3,6]

栈操作的详细过程：

初始状态：

1 2	栈：[] inorderIndex = 0 // 指向中序的4

步骤1：处理节点1

TreeNode node1 = new TreeNode(1);
stack.push(node1);  
// 栈：[1]
// inorderIndex = 0，指向4

步骤2：处理节点2

TreeNode node2 = new TreeNode(2);
TreeNode parent = stack.peek();  // parent = 1

// 关键判断：1 != inorder[0](即4)
// 说明还在左子树，所以2是1的左子节点
parent.left = node2;
stack.push(node2);
// 栈：[1, 2]，inorderIndex = 0

步骤3：处理节点4

TreeNode node4 = new TreeNode(4);
TreeNode parent = stack.peek();  // parent = 2

// 关键判断：2 != inorder[0](即4)
// 说明还在左子树，所以4是2的左子节点
parent.left = node4;
stack.push(node4);
// 栈：[1, 2, 4]，inorderIndex = 0

步骤4：处理节点5

TreeNode node5 = new TreeNode(5);
TreeNode parent = stack.peek();  // parent = 4

// 关键判断：4 == inorder[0](即4) ！！！
// 这是第一次相等！说明什么？

相等意味着： 栈顶节点4就是中序遍历当前要访问的节点！

这时我们需要”回退”：

// 开始弹栈，找到应该挂右子树的节点
while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
    parent = stack.pop();      // parent变成4，然后弹出4
    inorderIndex++;            // inorderIndex变成1，指向2
}

// 继续判断：栈顶现在是2，inorder[1]也是2，继续相等
while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
    parent = stack.pop();      // parent变成2，然后弹出2  
    inorderIndex++;            // inorderIndex变成2，指向5
}

// 现在栈顶是1，inorder[2]是5，不相等了，退出循环
// parent = 2，所以5是2的右子节点
parent.right = node5;
stack.push(node5);
// 栈：[1, 5]，inorderIndex = 2

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        stack<TreeNode*> stack;
        TreeNode* root = new TreeNode(preorder[0]);

        int inorderIndex = 0;
        stack.push(root);
        for (int i = 1; i < preorder.size(); i++) {
            TreeNode* par = stack.top();
            TreeNode* newnode = new TreeNode(preorder[i]);
            if (par->val != inorder[inorderIndex]) {
                par->left = newnode;
                stack.push(newnode);
            } else {
                while (!stack.empty() &&
                       stack.top()->val == inorder[inorderIndex]) {
                    par = stack.top();
                    stack.pop();
                    inorderIndex++;
                }
                par->right = newnode;
                stack.push(newnode);
            }
        }
        return root;
    }
};

图论

岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

解法：遍历整个图，当遇到1时，岛屿+1，同时递归遍历他的上下左右，将1变成0代表已经遍历过。

class Solution {
    public int numIslands(char[][] grid) {
        int res = 0;
        int m = grid.length;
        int n = grid[0].length;
        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;
    }

    void dfs(char[][] grid, int i, int j) {
        int m = grid.length;
        int n = grid[0].length;
        if (i < 0 || i > m - 1 || j < 0 || j > n - 1) {
            return;
        }
        if (grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0';
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
    }

}

腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

示例 1：

1 2	输入：grid = [[2,1,1],[1,1,0],[0,1,1]] 输出：4

解法：先遍历grid的，求出新鲜橘子的数量，并把腐烂的橘子放在队列里。从队列里取出烂橘子，判断烂橘子的4个方向是否是新鲜的，如果是新鲜的，记录当前新鲜+1，并将其变为腐烂橘子2，并把腐烂橘子加在队列里，同时记录这一层为isFulan=true;这一层结束后，如果isFulan=true，就把结果分钟+1，重置isFulan=false进入下一层。最后如果当前新鲜橘子的数量=开始计算出的新鲜橘子数量，说明新鲜橘子全部被腐烂，返回分钟数，反之返回-1；

class Solution {
    public int orangesRotting(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int freshcount = 0;
        Queue<int[]> q = new LinkedList<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    freshcount++;
                } else if (grid[i][j] == 2) {
                    q.add(new int[] { i, j });
                }
            }
        }
        boolean isFulan = false;
        int curcount = 0;
        int minuts = 0;
        int arr[][] = new int[][] {
                { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 }
        };
        while (!q.isEmpty()) {
            int num = q.size();
            for (int i = 0; i < num; i++) {
                int cur[] = q.poll();
                for (int dir[] : arr) {
                    int newI = dir[0] + cur[0];
                    int newJ = dir[1] + cur[1];
                    if (newI < 0 || newI > m - 1 || newJ < 0 || newJ > n - 1) {
                        continue;
                    }
                    if (grid[newI][newJ] == 1) {
                        curcount++;
                        grid[newI][newJ] = 2;
                        q.add(new int[] { newI, newJ });
                        isFulan = true;
                    }
                }
            }
            if (isFulan == true) {
                minuts++;
                isFulan = false;
            }
        }
        return curcount == freshcount ? minuts : -1;
    }
}

课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则必须先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：

1
2
3

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：

1
2
3

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

解法：就是一个拓扑排序的过程，先构建邻接表和度数组。将度为0的节点入队，遍历队列，去出对应的邻接表，并且记录当前节点已经遍历，修改表里的节点的度-1，如果减过后度=0，则加在队列里。如果遍历的次数等于numCourses说明所有元素都已经遍历，是一个完整的拓扑排序，反之就有环。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        int du[] = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        for (int arr[] : prerequisites) {
            int pre = arr[1];
            int back = arr[0];
            graph.get(pre).add(back);
            du[back]++;
        }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (du[i] == 0) {
                q.add(i);
            }
        }
        int count = 0;
        while (!q.isEmpty()) {
            int p = q.poll();
            count++;
            List<Integer> list = graph.get(p);
            for (int data : list) {
                du[data]--;
                if (du[data] == 0) {
                    q.add(data);
                }
            }
        }
        if (count == numCourses)
            return true;
        return false;
    }
}

实现 Trie (前缀树)(背)

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

解法：直接背；

class Trie {
    private Trie children[];
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }

    public void insert(String word) {
        Trie node = this;
        for (char ch : word.toCharArray()) {
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }

    public Trie searchPrefix(String word) {
        Trie node = this;
        for (char ch : word.toCharArray()) {
            int index = ch - 'a';
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }

    public boolean search(String word) {
        return searchPrefix(word) != null && searchPrefix(word).isEnd;
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

回溯

全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

1 2	输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

解题思路：回溯算法

全排列问题的核心思想是回溯，我们可以把这个过程想象成：

从数组中选择一个数字放在第一位
从剩余数字中选择一个放在第二位
继续这个过程直到所有位置都填满
如果当前路径不满足条件，就回退到上一步，尝试其他选择

具体点：

通过交换元素位置来生成排列
每次将待排列的元素与当前位置index交换
递归处理后续位置
回溯时再次交换回来

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        huisu(nums, 0, res);
        return res;

    }

    public void huisu(int[] nums, int index, List<List<Integer>> res) {
        if (index == nums.length) {
            List<Integer> list = new ArrayList<>();
            for (int num : nums) {
                list.add(num);

            }
            res.add(list);
            return;
        }

        for (int i = index; i < nums.length; i++) {
            swap(nums, index, i);
            huisu(nums, index + 1, res);
            swap(nums, index, i);
        }

    }

    public void swap(int nums[], int i, int j) {
        int temp = nums[j];
        nums[j] = nums[i];
        nums[i] = temp;
    }

}

子集

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

1 2	输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

思路1：二进制。

长度为n的数组子集个数的2ⁿ，每个元素有两种状态：选择(1) 或不选择(0)，这正好对应二进制！

对于数组 [1, 2, 3]：

二进制 000 → 都不选 → []
二进制 001 → 选第0个 → [1]
二进制 010 → 选第1个 → [2]
二进制 011 → 选第0,1个 → [1, 2]
二进制 100 → 选第2个 → [3]
二进制 101 → 选第0,2个 → [1, 3]
二进制 110 → 选第1,2个 → [2, 3]
二进制 111 → 都选 → [1, 2, 3]

总结：

n个元素有2ⁿ个子集
用0到2ⁿ-1的所有整数来表示，即1<<n,for (int i = 0; i < (1 << n); i++)
然后判断这些整数的每一位是否是1，如果是1则加到list里面去；

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        int count = 1 << n;
        List<List<Integer>> res = new ArrayList<>();

        for (int i = 0; i < count; i++) {
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j < n; j++) {

                if (((i >> j) & 1) == 1) {
                    list.add(nums[n - j - 1]);

                }
            }
            res.add(list);
        }
        return res;

    }

}

思路2：迭代法

核心思想：逐个添加元素。

关键洞察： 每次添加一个新元素时，新的子集 = 原有的所有子集 + 原有的所有子集都加上新元素。

初始状态：

1	result = [[]] // 只有空集

第1步：添加元素1

当前result = [[]]
对每个已有子集，生成包含1的新版本：
[] → [] + [1]

result = [[], [1]]

第2步：添加元素2

当前result = [[], [1]]
对每个已有子集，生成包含2的新版本：
[] → [] + [2]
[1] → [1] + [1,2]

result = [[], [1], [2], [1,2]]

第3步：添加元素3

当前result = [[], [1], [2], [1,2]]
对每个已有子集，生成包含3的新版本：
[] → [] + [3]
[1] → [1] + [1,3]
[2] → [2] + [2,3]
[1,2] → [1,2] + [1,2,3]

最终result = [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

每一步的子集数量都会复制一倍：1 → 2 → 4 → 8

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
       
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        List<Integer> cur = new ArrayList<>();
        res.add(cur);
        for (int i = 0; i < n; i++) {
            int size = res.size();//要注意，不能使用j <  res.size()，不然里面的size一直在变
            for (int j = 0; j < size; j++) {
                List<Integer> temp = new ArrayList<>(res.get(j));//注意这里，不是直接res.get(j),要拷贝一份
                temp.add(nums[i]);
                res.add(temp);
            }
        }

        return res;
    }
}

思路3：递归回溯。

每一个元素都有两个选择，我要这个元素、我不要这个元素。

核心思想： 对于每个元素，我们都有两个选择：

选择这个元素加入当前子集
不选择这个元素

具体过程：

从第一个元素开始
对每个元素做决定：要它还是不要它
每做一次决定，就递归处理下一个元素
当处理完所有元素时，得到一个完整的子集

class Solution {
    public List<List<Integer>> subsets(int[] nums) {

        List<List<Integer>> res = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();
        huisu(res, cur, 0, nums);
        return res;

    }

    public void huisu(List<List<Integer>> res, List<Integer> cur, int index, int[] nums) {
        if (index == nums.length) {
            res.add(new ArrayList<>(cur));
            return;
        }
        //不要这个元素就直接跳
        huisu(res, cur, index + 1, nums);
		//要这个元素就添加了再回溯
        cur.add(nums[index]);
	
        huisu(res, cur, index + 1, nums);

        cur.remove(cur.size() - 1);

    }
}

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

1 2	输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

解法1：队列

核心思想：使用队列按层处理，每处理一个数字就生成一层新的组合。

具体步骤（以 digits = "23" 为例）：

初始化

：创建一个队列，放入空字符串
1
""
- 队列状态：[""]
处理第一个数字 ‘2’

：
- 出队空字符串 ""
- 将 ‘2’ 对应的每个字母（’a’, ‘b’, ‘c’）分别加到空字符串后面
- 新组合 "a", "b", "c" 依次入队
- 队列状态：["a", "b", "c"]
处理第二个数字 ‘3’

：
- 出队 "a"，加上 ‘3’ 对应的字母（’d’, ‘e’, ‘f’），得到 "ad", "ae", "af" 入队队列状态：["b", "c", "ad", "ae", "af"]
- 出队 "b"，加上 ‘3’ 对应的字母，得到 "bd", "be", "bf" 入队
  队列状态：["c", "ad", "ae", "af", "bd", "be", "bf"]
- 出队 "c"，加上 ‘3’ 对应的字母，得到 "cd", "ce", "cf" 入队队列状态：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
结束：所有数字处理完毕，队列中的元素就是所有可能的字母组合。

关键点：每处理一个数字，就要把当前队列中的所有元素都出队一遍，然后生成新的组合入队。这样可以确保每一层的组合都能与下一个数字的所有字母结合。

class Solution {

    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0) {
            return new ArrayList<>();
        }
        Queue<String> queue = new LinkedList<>();
        queue.add("");
        String map[] = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
        for (int i = 0; i < digits.length(); i++) {
            int index = digits.charAt(i) - '0';
            String str = map[index];
            int n = queue.size();
            for (int j = 0; j < n; j++) {
                String temp = queue.poll();
                for (char ch : str.toCharArray()) {

                    queue.add(temp + ch);
                }
            }
        }
        // b c ad ae af
        return new ArrayList<>(queue);

    }

}

解法2：回溯法：

class Solution {

    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0) {
            return new ArrayList<>();
        }
        String map[] = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
        List<String> res = new ArrayList<>();
        List<Character> cur = new ArrayList<>();
        huisu(res, digits, cur, 0, map);
        return res;
    }

    public void huisu(List<String> res, String digits, List<Character> cur, int index, String map[]) {
        if (index == digits.length()) {
            StringBuilder sb = new StringBuilder();
            for (char ch : cur) {
                sb.append(ch);
            }
            res.add(sb.toString());
            return;
        }
        String str = map[digits.charAt(index) - '0'];
        for (int i = 0; i < str.length(); i++) {
            cur.add(str.charAt(i));
            huisu(res, digits, cur, index + 1, map);
            cur.remove(cur.size() - 1);
        }
    }

}

组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

关键步骤总结

检查答案：if (sum == target) - 凑够了就是答案
检查超限：if (sum > target) - 加多了就退出
做选择：current.add(candidates[i]) - 放进篮子
递归：backtrack(..., i, ...) - 继续凑，可以重复选
撤销：current.remove(...) - 拿出来，试试别的

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

    public void huisu(int[] candidates, List<List<Integer>> res, List<Integer> cur, int index, int target, int sum) {
        if (sum == target) {
            res.add(new ArrayList<>(cur));
            return;
        }
        if (sum > target) {
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            cur.add(candidates[i]);
            huisu(candidates, res, cur, i, target, sum + candidates[i]);
            cur.remove(cur.size() - 1);
        }
    }

}

括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

1 2	输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]

解题思路

两段回溯

有效括号的规则：

左括号数量 = 右括号数量 = n
在任意位置，左括号数量 ≥ 右括号数量（不能出现)(这种情况）
左括号剪枝：if (left< n) - 左括号不能超过n个
右括号剪枝：if (right< lef) - 右括号不能超过左括号

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

    public void huisu(int n, List<Character> cur, List<String> res, int left, int right) {
        // 基础情况：当前路径长度等于2n，说明生成了完整的括号组合
        if (cur.size() == n * 2) {
            // 将List<Character>转换为String
            StringBuilder sb = new StringBuilder();
            for (char ch : cur) {
                sb.append(ch);
            }
            res.add(sb.toString()); // 将当前有效组合加入结果集
            return;
        }

        // 选择1：添加左括号
        // 剪枝条件：左括号数量不能超过n
        if (left < n) {
            cur.add('('); // 第1步：做选择 - 添加左括号到当前路径
            huisu(n, cur, res, left + 1, right); // 第2步：递归 - 左括号数量+1，继续构建
            cur.remove(cur.size() - 1); // 第3步：撤销选择 - 回溯，移除刚才添加的左括号
        }

        // 选择2：添加右括号
        // 剪枝条件：右括号数量不能超过当前的左括号数量（保证括号有效）
        if (right < left) {
            cur.add(')'); // 第1步：做选择 - 添加右括号到当前路径
            huisu(n, cur, res, left, right + 1); // 第2步：递归 - 右括号数量+1，继续构建
            cur.remove(cur.size() - 1); // 第3步：撤销选择 - 回溯，移除刚才添加的右括号
        }
    }
}

单词搜索

1 2	输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 输出：true

解法：

这是一个典型的二维网格回溯问题：

遍历每个起点：找到单词第一个字母的位置作为起点
四方向搜索：从起点向上下左右四个方向搜索下一个字母
标记访问状态：提前保持好字母，然后用#标记数组避免重复使用同一个格子
回溯：如果当前路径不行，撤销标记#，尝试其他路径

class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (huisu(board, i, j, word, 0, m, n)) {//注意这里不能直接return huisu，只要true才能return，如果直接return的话后面有成功的就被抛弃了
                    return true;
                }
            }
        }
        return false;
    }

    public boolean huisu(char[][] board, int i, int j, String word, int index, int m, int n) {
        // 找到完整单词
        if (index == word.length()) {
            return true;
        }
        // 边界和条件检查
        if (i < 0 || i > m - 1 ||
                j < 0 || j > n - 1 ||
                board[i][j] != word.charAt(index)) {
            return false;
        }
        // 第1步：做选择 - 暂存当前字符并标记为已访问
        char temp = board[i][j];// 用特殊字符标记已访问
        board[i][j] = '#';
        // 第2步：递归 - 四方向搜索，只要找到一个方向就算成功
        boolean isTrue = huisu(board, i + 1, j, word, index + 1, m, n) ||
                huisu(board, i - 1, j, word, index + 1, m, n) ||
                huisu(board, i, j + 1, word, index + 1, m, n) ||
                huisu(board, i, j - 1, word, index + 1, m, n);
        if (isTrue == true) {
            return true;
        }
        // 第3步：撤销选择 - 恢复原字符
        board[i][j] = temp;
        return false;
    }

}

分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1：

1 2	输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]

解法：

基本流程：

选择分割点：在每个位置尝试分割字符串
验证回文：检查分割出的子串是否为回文
递归继续：如果是回文，继续分割剩余字符串
回溯尝试：如果当前分割不行，撤销选择，尝试其他分割点

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        List<String> cur = new ArrayList<>();
        huisu(res, s, cur, 0);
        return res;
    }

    public void huisu(List<List<String>> res, String s, List<String> cur, int index) {
        // 基础情况：已经处理完整个字符串
        if (index == s.length()) {
            res.add(new ArrayList<>(cur));
            return;
        }
        // 尝试每个可能的分割点
        for (int i = index; i < s.length(); i++) {

            // 提取子串[start, end]
            String str = s.substring(index, i + 1);
            // 如果当前子串是回文，则可以作为一个分割
            if (isHui(str)) {
                cur.add(str);
                huisu(res, s, cur, i + 1);//这里如果不知道是i+1还是index+1，直接试一试
                cur.remove(cur.size() - 1);
            }
        }
    }

    //判断回文
    public boolean isHui(String s) {
        int i = 0;
        int j = s.length() - 1;
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

技巧

出现一次的数字I

给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

输入：nums = [2,2,1]

输出：1

解法1：无需多言

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

解法2：无需多言

class Solution {
    public int singleNumber(int[] nums) {
        int res=0;
        for(int i=0;i<32;i++){
            int count=0;
            for(int j=0;j<nums.length;j++){
                if( ((nums[j]>>i)&1)==1 ){
                    count++;
                }
            }
            if(count%2==1){
                res=res|(1<<i);
            }
            
        }
        return res;
    }
}

只出现一次的数字 II

给你一个整数数组 nums ，除某个元素仅出现一次外，其余每个元素都恰出现 三次。请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

示例 1：

1 2	输入：nums = [2,2,3,2] 输出：3

示例 2：

1 2	输入：nums = [0,1,0,1,0,1,99] 输出：99

解法1：相减法，先用set去重，假设每一个元素都出现3次，那么他们的乘积减去原数组x3=只出现一次的数字x2。代码无需多言。

解法2：位运算是通解：

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int j = 0; j < nums.length; j++) {
                if (((nums[j] >> i) & 1) == 1) {
                    count++;
                }
            }
            if (count % 3 == 1) {
                res = res | (1 << i);
            }

        }
        return res;
    }
}

只出现一次的数字 III

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

示例 1：

1
2
3

输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。

示例 2：

1 2	输入：nums = [-1,0] 输出：[-1,0]

解法：核心是异或完之后的结果是两个不同的数的异或结果。用n & (-n)得到最右边的1，用来作为区分位。

class Solution {
    public int[] singleNumber(int[] nums) {
        int huo = 0;
        for (int i : nums) {
            huo = huo ^ i;
        }
        int res[] = new int[2];
        int split = huo & (-huo);
        for (int i : nums) {
            if ((i & split) != 0) {
                res[0] = res[0] ^ i;
            } else {
                res[1] = res[1] ^ i;
            }
        }
        return res;
    }
}

多数元素(Boyer-Moore 投票算法x)

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

1 2	输入：nums = [3,2,3] 输出：3

示例 2：

1 2	输入：nums = [2,2,1,1,1,2,2] 输出：2

解法1：长度为n的数组，多数元素的个数一定≥n/2+1,所以多数元素的二进制位个数/(n/2+1)一定=1，少数元素的二进制位个数/(n/2+1)一定=0；

class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length / 2 + 1;
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int j = 0; j < nums.length; j++) {
                if (((nums[j] >> i) & 1) == 1) {
                    count++;
                }
                if (count / n != 0) {
                    res = res | (1 << i);
                }
            }
        }
        return res;
    }
}

颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，**原地** 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

1 2	输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]

示例 2：

1 2	输入：nums = [2,0,1] 输出：[0,1,2]

解法1：单指针法，既然有三种颜色，我们可以分两步来处理：

第一次遍历：把所有的 0 移到数组前面
第二次遍历：把所有的 1 移到 0 的后面

这样剩下的 2 自然就在数组末尾了。

class Solution {
    public void sortColors(int[] nums) {

        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                swap(nums, index++, i);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) {
                swap(nums, index++, i);
            }
        }
    }

    public void swap(int nums[], int i, int j) {
        int temp = nums[j];
        nums[j] = nums[i];
        nums[i] = temp;
    }
}

解法2：双指针法，（荷兰国旗问题）我们用三个指针来维护数组的不同区域，通过交换元素来完成排序：

left：指向下一个 0 应该放置的位置
right：指向下一个 2 应该放置的位置
current：当前正在处理的元素

当 current 指针遇到不同数字时，我们有不同的处理方式：

情况1：nums[current] == 0（红色）

操作：将 nums[current] 与 nums[left] 交换
移动指针：left++，current++
原因：0应该放在左边区域，交换后left位置就是正确的0

情况2：nums[current] == 1（白色）

操作：什么都不做
移动指针：只有 current++
原因：1本来就应该在中间，当前位置就对了

情况3：nums[current] == 2（蓝色）

操作：将 nums[current] 与 nums[right] 交换
移动指针：right--，current不动
原因：2应该放在右边，但交换过来的元素还没检查过，所以current不能前进

class Solution {
    public void sortColors(int[] nums) {
        int left=0;
        int right=nums.length-1;
        int cur=0;
        while(cur<=right){
            if(nums[cur]==0){
                swap(nums,left,cur);
                left++;
                cur++;
            }else if(nums[cur]==1){
                cur++;
            }else{
                swap(nums,cur,right);
                right--;
            }
        }
    }
    public void swap(int nums[],int i,int j){
        int temp=nums[j];
        nums[j]=nums[i];
        nums[i]=temp;
    }
}

下一个排列

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

必须** 原地 **修改，只允许使用额外常数空间。

示例 1：

1 2	输入：nums = [1,2,7,4,3,1] 输出：[1,3,1,2,4,7]

示例 2：

1 2	输入：nums = [3,2,1] 输出：[1,2,3]

解法：

**从右往左找”峰值”**：找到第一个 nums[i] < nums[i+1] 的位置
如果找不到：说明数组完全降序，没有更大排列
如果找到了：在右边找到比 nums[i] 大的最小数字来替换
替换后颠倒后面：让右边部分尽可能小

class Solution {
    public void nextPermutation(int[] nums) {
        //[1,2,7,4,3,1]
        int i = nums.length - 2;
        while (i >= 0 && nums[i] > nums[i + 1]) {
            i--;
        }
        if (i == -1) {
            reverse(nums, 0, nums.length - 1);
            return;
        }
        int j = nums.length - 1;
        while (nums[i] >= nums[j]) {
            j--;
        }
        swap(nums, i, j);
        reverse(nums, i + 1, nums.length - 1);

    }

    public void swap(int nums[], int i, int j) {
        int temp = nums[j];
        nums[j] = nums[i];
        nums[i] = temp;
    }

    public void reverse(int nums[], int i, int j) {
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }
}

寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

1 2	输入：nums = [1,3,4,2,2] 输出：2

示例 2：

1 2	输入：nums = [3,1,3,4,2] 输出：3

解法1：

对于长度为n的数组，其数字都在 [1, n-1] 范围内，也就是说至少有一个元素是重复的，假设n=5，

理想情况下的数组是：

[1,2,3,4]

实际重复的情况下是：

[1,2,2,3,4];

对于每一个数的二进制位的和，假设如果理想情况下的第0位的和！=实际情况下第0位的和，说明这重复元素的这一位=1

class Solution {
    public int findDuplicate(int[] nums) {

        int n = nums.length;
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int actualCount = 0;
            int idealCount = 0;
            for (int j = 0; j < n; j++) {
                if ((nums[j] >> i & 1) == 1) {
                    actualCount++;
                }
            }
            for (int j = 1; j < n; j++) {
                if ((j >> i & 1) == 1) {
                    idealCount++;
                }
            }
            if (actualCount > idealCount) {
                res = res | (1 << i);
            }
        }
        return res;
    }
}

解法2：将将数组看作一个隐式的链表，数组索引看作节点，数组值看作指向下一个节点的指针，转化为寻找链表的入环口，参考链表题

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

    }
}

二分查找

搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

1 2	输入: nums = [1,3,5,6], target = 5 输出: 2

解法：注意是left<=right,循环结束后，left指向第一个≥target的位置。

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return left;
    }
}

搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：

每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 1：

1 2	输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出：true

解法：讲二维数组展开变成一维数组，然后用二分。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
    /**
        2x4 3=11
        0x4 2=2
        1x4 1=5
        11/n  11%n
        
        
         */
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0;
        int right = m * n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int i = mid / n;
            int j = mid % n;
            if (matrix[i][j] < target) {
                left = mid + 1;
            } else if (matrix[i][j] > target) {
                right = mid - 1;
            } else {
                return true;
            }
        }
        return false;
        
    }
}

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

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

1 2	输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]

示例 2：

1 2	输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1]

解法1：二分找到后不返回，继续找:

找第一个时有两种情况，当前mid不是第一个，则需要继续往左找。如果是第一个，往左找永远找不到。

找第二个时有两种情况，当前mid不是最后一个，则需要继续往右找。如果是最后一个，往右永远找不到。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int res[] = new int[2];
        res[0] = findFirst(nums, target);
        res[1] = findLast(nums, target);
        return res;
    }

    public int findFirst(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int res = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                res = mid;
                //找到了会有两种情况：
                //1、mid不是第一个，则需要继续往左找
                //2、mid是第一个，左找一定找不到
                right = mid - 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return res;
    }

    public int findLast(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int res = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                res = mid;
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return res;
    }
}

解法2：利用小数：

1	输入：nums = [5,7,7,8,8,10], target = 8，查找8-0.5和8+0.5

因为这两个数永远不会找到，所以找7.5后，left会落到第一个大于7.5的位置，也就是第一个8。

找8.5后，left会落到第一个大于8.5的位置，也就是10，那么right=left-1就落在了最后一个8.

但是要注意边界条件，这里还没有搞懂。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int res[] = new int[2];
        res[0] = findFirst(nums, target);
        res[1] = findLast(nums, target);
        return res;
    }

    public int findFirst(int[] nums, int target) {
        double newTarget = target - 0.5;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < newTarget) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        if (left < nums.length && nums[left] != target) {
            return -1;
        }
        return left < nums.length ? left : -1;
    }

    public int findLast(int[] nums, int target) {
        double newTarget = target + 0.5;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < newTarget) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        if (left - 1 >= 0 && nums[left - 1] != target) {
            return -1;
        }
        return left - 1 >= 0 ? left - 1 : -1;
    }
}

搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

1 2	输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4

示例 2：

1 2	输入：nums = [4,5,6,7,0,1,2], target = 3 输出：-1

解法：旋转数组有一个重要性质：一定有一半是完全有序的，如果left的值<=mid值，说明左边有序，反之右边有序，在有序的部分进行二分。

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[left] <= nums[mid]) {
                //左半部分有序
                if (target >= nums[left] && target <= nums[mid]) {//如果target在left和mid之间，进行二分
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                //右半部分有序
                if (target >= nums[mid] && target <= nums[right]) {//如果target在mid和right之间，进行二分
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;

    }
}

寻找旋转排序数组中的最小值(背)

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

1
2
3

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

1
2
3

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

解法：

如果左端 < 右端，说明数组没有旋转，整个数组有序

如果mid位置的值比right位置的值大，说明中间有断点，最小值在断点右边。

如果mid位置的值 ≤ right位置的值，说明从mid到right是有序的，最小值可能就是mid。

class Solution {

    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        if (nums[left] < nums[right]) {
            return nums[0];
        }
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] <= nums[right]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return nums[left];
    }
}

寻找两个正序数组的中位数(背)

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

1
2
3

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

1
2
3

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //11
        int m = nums1.length;
        int n = nums2.length;
        if (m > n) {
            return findMedianSortedArrays(nums2, nums1);
        }
        int left = 0;
        int right = m;//注意！
        while (left <= right) {
            int i = (left + right) / 2;//A左边的个数
            int j = (m + n + 1) / 2 - i;//B左边的个数
            int ALeftMax = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]);
            int ARightMin = (i == m ? Integer.MAX_VALUE : nums1[i]);
            int BLeftMax = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]);
            int BRightMin = (j == n ? Integer.MAX_VALUE : nums2[j]);
            if (ALeftMax <= BRightMin && BLeftMax <= ARightMin) {
                if ((m + n) % 2 == 1) {
                    return Math.max(ALeftMax, BLeftMax);
                } else {
                    return (Math.max(ALeftMax, BLeftMax) + Math.min(ARightMin, BRightMin)) / 2.0;
                }
            } else if (ALeftMax > BRightMin) {
                right = i - 1;
            } else {
                left = i + 1;
            }
        }
        return -1;
    }
}

动态规划

非动态规划专栏

最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

1
2
3

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

class Solution {
    public int maxSubArray(int[] nums) {
        /**
        dp[i]定义为以nums[i]结尾的最大子数组和
        dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
        以nums[i]结尾的最大子数组和，如果dp[i-1]>0,dp[i]=dp[i-1]+nums[i]
        如果dp[i-1]<0,dp[i-1]反而是累赘，不要它了，只要nums[i];
        dp[0]=nums[0];
        
         */
        if (nums.length == 1) {
            return nums[0];
        }
        int dp[] = new int[nums.length];
        dp[0] = nums[0];

        int res = dp[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            res = Math.max(res, dp[i]);
        }

        return res;

    }
}

跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：

0 <= j <= nums[i] 且
i + j < n

返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

class Solution {
    public int jump(int[] nums) {
        /**
        dp[i]定义为到达下标i的位置需要的最小次数。注意是次数
        最小问题，初始化最大值。
        如果j在（0，i）之间，且j+nums[j]>=i的话，说明j可以直接跳到i
        dp[i]=Math.min(dp[i],dp[j]+1);
        */
        int dp[] = new int[nums.length];
        Arrays.fill(dp, 1000000);
        dp[0] = 0;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (j + nums[j] >= i) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[nums.length - 1];
    }
}

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        /**
        dp[i]定义为到达第i阶的总方法数量
        dp[i]=dp[i-1]+dp[i-2]
        到达第i阶，可以从i-1来，也可以从1-2来。
        dp[0]=0;
        dp[1]=1;
        dp[2]=2;
         */
        int dp[] = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

1 2	输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

class Solution {
    public List<List<Integer>> generate(int numRows) {
        /**
        没有显式用到dp数组
        显示的话是dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
         */
        List<List<Integer>> res=new ArrayList<>();
        
        for(int i=0;i<numRows;i++){
            List<Integer> list=new ArrayList<>();
            for(int j=0;j<=i;j++){
                if(j==0||j==i){
                    list.add(1);
                }else{
                    list.add(res.get(i-1).get(j-1)+res.get(i-1).get(j));
                }
            }
            res.add(list);
        }
        return res;
    }
}

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

class Solution {
    public int rob(int[] nums) {

        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        /**
        定义dp[i]为偷下标为i的房间的最大收益
        dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
        如果偷当前房间，那么收益为dp[i-2]+nums[i]；
        如果不偷当前房间，收益为dp[i-1]，看看谁大。
        dp[0]=nums[0];
        dp[1] = Math.max(dp[0], nums[1]);
         */
        int dp[] = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(dp[0], nums[1]);

        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]);
        }
        return dp[nums.length - 1];

    }
}

完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

1
2
3

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：

1
2
3

输入：n = 13
输出：2
解释：13 = 4 + 9

class Solution {
    public int numSquares(int n) {
         /**
        这是最小最大问题，所有初始化要考虑清楚，而且没有nums数组对应dp的下标
        所以dp的长度要+1;for循环条件加个=号
        dp[i]定义为和为i所需的最小平方数,注意是数量
        dp[i]初始化为dp[i] = i;因为和为i所需的最小平方数就是i个1
        dp[i]=Math.min(dp[i-j*j]+1,dp[i]);
         */
        int dp[] = new int[n + 1];

        for(int i=0;i<=n;i++){
            dp[i]=i;
        }
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if ((i - j * j) >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
                }

            }
        }
        return dp[n];
    }
}

零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

1
2
3

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

解法1：dp

class Solution {
    public int coinChange(int[] coins, int amount) {
        /**
        
        dp[i]定义为凑成i所需要的最少金币；
        最小最大问题要考虑初始化，管他什么求最小初始化成最大就行了。
        dp[i]=dp[i-coin]+1,dp[i] 哪个更小
        dp[0]=0;
        */
        int dp[]=new int[amount+1];
        Arrays.fill(dp,Integer.MAX_VALUE-100);//这里是因为Integer.MAX_VALUE+1会溢出
        dp[0]=0;
        for(int i=1;i<=amount;i++){
            for(int coin:coins){
                if((i-coin)>=0)
                dp[i]=Math.min(dp[i],dp[i-coin]+1);
            }
        }
        return dp[amount]==Integer.MAX_VALUE-100?-1:dp[amount];
    }
}

解法2：回溯

参考组合总和，那个是求出所有总和，这个是求组合的元素最小个数

class Solution {
    private int pdmin = Integer.MAX_VALUE;

    public int coinChange(int[] coins, int amount) {
        List<Integer> cur = new ArrayList<>();
        huisu(coins, amount, cur, 0, 0);
        return pdmin == Integer.MAX_VALUE ? -1 : pdmin;
    }

    public void huisu(int[] coins, int amount, List<Integer> cur, int sum, int index) {
        if (sum == amount) {
            pdmin = Math.min(pdmin, cur.size());
            return;
        }
        if (sum > amount) {
            return;
        }
        for (int i = index; i < coins.length; i++) {
            cur.add(coins[i]);
            huisu(coins, amount, cur, sum + coins[i], i);
            cur.remove(cur.size() - 1);
        }
    }
}

单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

1
2
3

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        /**
        定义dp[i]表示前i个字符能否被正确拆分
        dp[i]=dp[j]&&j...i在dict里面
        表示如果前j个字符能被拆分，而且(j...i)还在wordDict里面，那么dp[i]能被拆分
        dp[0]=true,空串能被拆分
        */

        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++) {
                dp[i] |= dp[j] && wordDict.contains(s.substring(j, i));//注意这里是||
            }
        }
        return dp[s.length()];
    }
}

最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

1
2
3

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

1 2	输入：nums = [0,1,0,3,2,3] 输出：4

示例 3：

1 2	输入：nums = [7,7,7,7,7,7,7] 输出：1

class Solution {
    public int lengthOfLIS(int[] nums) {
        /**
        最长问题注意初始化
        dp[i]定义为以nums[i]结尾的最长连续子序列长度
        dp[i]=nums[j]<nums[i]?:dp[j]+1:0
        如果在(0,i)内有一个nums[j]<nums[i],说明nums[i]可以接在以j结尾的后面
        每一个nums[i]都可以以自身作为结尾，即dp[]=1;
        */
        int dp[] = new int[nums.length];
        Arrays.fill(dp, 1);
        int max = dp[0];
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);

                }

            }
            max = Math.max(max, dp[i]);
        }
        return max;

    }
}

乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

示例 1:

1
2
3

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

1
2
3

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

class Solution {
    public int maxProduct(int[] nums) {
        /**
        最大问题
        维护两个dp数组，因为原本是最大的数，结果遇到一个负数就g了
        dpMax[i]定义为以nums[i]结尾的最大乘积
        dpMin[i]定义为以nums[i]结尾的最小乘积
        dpMax有三种情况：
        1：只要当前元素
        2：当前元素是负数，x dpMin变为最大
        3：当前元素是正数，x dpMax变最大。
        dpMax的三种情况同理
        dpMax[i]=Math.max(Math.max(nums[i]*dpMax[i-1],nums[i]*dpMin[i-1]),nums[i]);
        dpMin[i]=Nath.min(Math.min(nums[i]*dpMax[i-1],nums[i]*dpMin[i-1]),nums[i])
        */
        int dpMax[] = new int[nums.length];
        int dpMin[] = new int[nums.length];
        dpMax[0] = dpMin[0] = nums[0];
        int res = dpMax[0];
        for (int i = 1; i < nums.length; i++) {
            dpMax[i] = Math.max(Math.max(nums[i] * dpMax[i - 1], nums[i] * dpMin[i - 1]), nums[i]);
            dpMin[i] = Math.min(Math.min(nums[i] * dpMax[i - 1], nums[i] * dpMin[i - 1]), nums[i]);
            res = Math.max(res, dpMax[i]);

        }
        return res;
    }
}

分割等和子集(待学习)

给你一个 只包含正整数 的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

1
2
3

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

1
2
3

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

用回溯会超时

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 == 1) {
            return false;
        }
        int target = sum / 2;
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();
        huisu(res, nums, cur, target, 0, 0);
        return res.size() != 0;
    }

    public void huisu(List<List<Integer>> res, int nums[], List<Integer> cur, int target, int sum, int index) {
        if (sum == target) {
            res.add(new ArrayList<>(cur));
            return;
        }
        if (sum > target || index >= nums.length) {
            return;
        }
        huisu(res, nums, cur, target, sum, index + 1);
        cur.add(nums[index]);
        huisu(res, nums, cur, target, sum + nums[index], index + 1);
        cur.remove(cur.size() - 1);
    }
}

最长有效括号(非DP)

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。

示例 1：

1
2
3

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

1
2
3

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

class Solution {
    public int longestValidParentheses(String s) {
        //用一个栈来保存下标
        /**
        初始化需要push(-1);
        因为假如"()",遇到(入栈，遇到)出栈，出栈时下标是1,如果没有记录起始位置，那么就找不到括号的长度，标记起始位置-1，那么长度就算1-peek()=2;
        一旦栈空了就要记录起始下标位置。
         */
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    max = Math.max(max, i - stack.peek());
                }
            }
        }
        return max;
    }
}

二维动态规划

不同路径

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

1 2	输入：m = 3, n = 7 输出：28

class Solution {
    public int uniquePaths(int m, int n) {
        /**
        dp[i][j]定义为到达(i,j)的路径数量
        dp[i][j]=dp[i][j-1]||dp[i-1][j]
        dp[0][0]=0;
        dp[0][1]=1;
        dp[1][0]=1;

         */
        int dp[][]=new int[m][n];
        for(int i=0;i<n;i++){
            dp[0][i]=1;
        }
        for(int i=0;i<m;i++){
            dp[i][0]=1;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=dp[i][j-1]+dp[i-1][j];
            }
        }
        return dp[m-1][n-1];

    }
}

最小路径和

给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

1
2
3

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

1 2	输入：grid = [[1,2,3],[4,5,6]] 输出：12

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        /**
        dp[i][j]定义为到达(i,j)的最小路径和
        dp[i][j]=dp[i-1][j]+dp[i][j-1]+grid[i][j]
         */
        int dp[][] = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j]);
            }
        }
        return dp[m - 1][n - 1];
    }
}

最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

1
2
3

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

1 2	输入：s = "cbbd" 输出："bb"

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2)
            return s;
        /**
        dp[i][j]定义为字符串i到j的子串是回文串；
        单个字符一定是回文
        两个字符需要判断是否相等
        三个及三个以上需要判断两段字符一样的同时，夹在中间的子串也是回文
        即dp[i][j]=(s.charAt(i)==s.charAt(j))&&dp[i+1][j-1];
         */
        int n = s.length();
        boolean[][] dp = new boolean[n][n];

        // 记录最长回文子串的起始位置和长度
        int start = 0;
        int maxLen = 1;

        // 初始化：单个字符都是回文
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        // 检查长度为2的子串
        for (int i = 0; i < n - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                start = i;
                maxLen = 2;
            }
        }

        // 检查长度大于等于3的子串
        //abcdefgh len=8
        //01234567
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;

                if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    start = i;
                    maxLen = len;
                }
            }
        }

        return s.substring(start, start + maxLen);
    }
}

最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

1
2
3

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：

1
2
3

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        /**
        定义dp[i][j]为,左边前i个字符与右边前j个字符的最长公共子序列
        dp[i][j]=dp[i-1][j-1]+1   字符相同的情况，因为这个必然要成为公共子序列的一部分
        dp[i][j]=max(dp[i-1][j],dp[i][j-1])字符不同的情况下，因为不同，所有两个字符不能同时要，所有只取一个就行了，取谁就看哪一个dp大。
        
        注意注意！i和j是代表的个数，前i个，那么第i个的下标是i-1
         */
        int m = text1.length();
        int n = text2.length();
        int dp[][] = new int[m + 1][n + 1];
        //左边前0个字符与右边前n个字符的最长公共子序列=0;
        //左边前m个字符与右边前0个字符的最长公共子序列=0;
        //初始化已经是0
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}

编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

class Solution {
    public int minDistance(String word1, String word2) {
        /**
        定义dp[i][j],左边前i个字符转换为右边前j个字符最小次数。
        注意注意！，i是前i个字符，那么下标就算i-1;
        左边前0个字符转换成右边前j个字符的最小次数是j,因为全部add
        左边前i个字符转换成右边前0个字符的最小次数是i,因为全部是delete
        如果左边第i个字符==右边第j个字符，不用转换
        dp[i][j]=dp[i-1][j-1]
        如果如果左边第i个字符！=右边第j个字符
        有三种转换方式
        替换、新增、删除
        看谁次数最少
        dp[i][j]=Math.min(Math.min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+1);
         */
        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(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 1);
                }
            }
        }
        return dp[m][n];
    }
}

总结：

栈

有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = “()”

输出：true

示例 2：

输入：s = “()[]{}”

输出：true

示例 3：

输入：s = “(]”

输出：false

示例 4：

输入：s = “([])”

输出：true

解法：很恶心的题，判断条件多。

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        char str[] = s.toCharArray();

        for (int i = 0; i < str.length; i++) {
            if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
                stack.push(str[i]);
            } else {
                if (!stack.isEmpty()) {
                    if (stack.peek() == '(' && str[i] == ')'
                            || stack.peek() == '[' && str[i] == ']'
                            || stack.peek() == '{' && str[i] == '}') {
                        stack.pop();
                    } else {
                        return false;
                    }
                } else {
                    return false;
                }

            }
        }
        if (!stack.isEmpty()) {
            return false;
        }
        return true;
    }
}

最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解法：维护两个栈，一个主栈，一个最小栈。

push：只要当最小栈为空或者添加的元素<=栈顶元素时，最小栈才push；注意是<=,因为有重复元素。

pop：只要当主栈pop的值与最小栈的栈顶值一样时，才pop；

class MinStack {
    Stack<Integer> stack;
    Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || minStack.peek() >= val) {
            minStack.push(val);
        }
    }

    public void pop() {
        int val = stack.pop();
        if (val == minStack.peek()) {
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：

1 2	输入：s = "3[a]2[bc]" 输出："aaabcbc"

示例 2：

1 2	输入：s = "3[a2[c]]" 输出："accaccacc"

示例 3：

1 2	输入：s = "2[abc]3[cd]ef" 输出："abcabccdcdcdef"

示例 4：

1 2	输入：s = "abc3[cd]xyz" 输出："abccdcdcdxyz"

解法：用两个栈，一个栈用来记录数字，一个栈用来记录上一个字符串。

初始化：数字栈、字符串栈、当前数字、当前字符串
遍历字符串，分情况处理：
- 遇到数字字符：累积构建多位数字（如”23”要构建成数字23）
- 遇到左括号 [
  
  ：
  - 说明要开始处理一个新的编码块
  - 把当前的数字和字符串”暂存”到栈中
  - 清空当前数字和字符串，准备处理括号内的内容
- 遇到右括号 ]
  
  ：
  - 说明当前编码块处理完毕
  - 从栈中取出之前保存的重复次数和字符串
  - 将当前字符串重复指定次数
  - 与之前的字符串拼接，作为新的当前字符串
- 遇到普通字母：直接添加到当前字符串中
返回最终的当前字符串

class Solution {
    public String decodeString(String s) {
        Stack<Integer> numStack = new Stack<>();
        Stack<String> strStack = new Stack<>();
        int curNum = 0;
        String curStr = "";
        char str[] = s.toCharArray();
        for (int i = 0; i < str.length; i++) {
            if (Character.isDigit(str[i])) {
                curNum = curNum * 10 + str[i] - '0';
            } else if (str[i] == '[') {
                numStack.push(curNum);
                strStack.push(curStr);
                curNum = 0;
                curStr = "";
            } else if (str[i] == ']') {
                int repeats = numStack.pop();
                String preStr = strStack.pop();
                String temp = "";
                for (int j = 0; j < repeats; j++) {
                    temp = temp + curStr;
                }
                curStr = preStr + temp;
            } else {
                curStr = curStr + str[i];
            }
        }
        return curStr;
    }
}

每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

1 2	输入: temperatures = [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0]

示例 2:

1 2	输入: temperatures = [30,40,50,60] 输出: [1,1,1,0]

示例 3:

1 2	输入: temperatures = [30,60,90] 输出: [1,1,0]

解法：使用一个栈来记录还没有找到下一个更高温度的日期索引。栈中存储的是温度数组的下标，并且栈底到栈顶对应的温度是单调递减的。

算法思路：

初始化：创建一个栈用来存储数组索引，创建结果数组 res
遍历温度数组

：对于每个位置
1
i
：
- 栈不为空且当前温度大于栈顶索引对应的温度
  
  ：说明为栈顶的日期找到了下一个更高温度
  - 弹出栈顶索引 index
  - 计算天数差：res[index] = i - index
  - 重复此过程直到栈为空或当前温度不大于栈顶温度
- 将当前索引压入栈：等待后续找到更高温度
返回结果：栈中剩余的索引对应的位置在 res 中保持默认值 0

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

数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

1 2	输入: [3,2,1,5,6,4], k = 2 输出: 5

示例 2:

1 2	输入: [3,2,3,1,2,4,5,5,6], k = 4 输出: 4

解法1：快速排序思想：

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

    public int quickSort(int[] nums, int k, int left, int right) {
        int n = nums.length;
        int part = partition(nums, left, right);
        if (part < n - k) {
            return quickSort(nums, k, part + 1, right);
        } else if (part > n - k) {
            return quickSort(nums, k, left, part - 1);
        } else {
            return nums[part];
        }

    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public int partition(int[] nums, int left, int right) {
        Random rand = new Random();
        int randomIndex = left + rand.nextInt(right - left + 1);
        swap(nums, left, randomIndex);
        int temp = nums[left];
        while (left < right) {
            while (left < right && nums[right] >= temp)
                right--;
            nums[left] = nums[right];
            while (left < right && nums[left] <= temp)
                left++;
            nums[right] = nums[left];
        }
        nums[left] = temp;
        return left;
    }

}

解法二：小根堆

public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        for (int num : nums) {
            q.add(num);
            if (q.size() > k) {
                q.poll();
            }
        }
        return q.peek();
    }

解法3：堆排序思想

class Solution {
    public int findKthLargest(int[] nums, int k) {
        build(nums);
        int n = nums.length - 1;
        for (int i = n; i >= n - k + 2; i--) {//循环的次数
            swap(nums, 0, i);//第一个元素和最后一个元素交换
            adjust(nums, 0, i - 1);//交换后数组长度-1，调整前面的。
        }
        return nums[0];
    }

    public void build(int[] nums) {
        int n = nums.length - 1;
        for (int i = n / 2; i >= 0; i--) {
            adjust(nums, i, n);
        }
    }

    public void swap(int nums[], int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void adjust(int[] nums, int k, int n) {

        for (int i = k * 2 + 1; i <= n; i = i * 2 + 1) {//注意i <= n
            if (i < n && nums[i] < nums[i + 1]) {//注意i < n
                i++;
            }
            if (nums[i] > nums[k]) {
                int temp = nums[i];
                nums[i] = nums[k];
                nums[k] = temp;
                k = i;
            }
        }
    }

}

解法4：桶排序：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int max = nums[0];
        int min = nums[0];
        for (int num : nums) {
            max = Math.max(max, num);
            min = Math.min(min, num);
        }
        //0 1 2 3 4 5
        //1 2 2 1 2 1
        int bucketLen = max - min + 1;
        int bucket[] = new int[bucketLen];
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            bucket[nums[i] - min]++;
        }
        int count = 0;
        for (int j = bucketLen - 1; j >= 0; j--) {
            count = count + bucket[j];
            if (count >= k) {
                return j + min;

            }
        }
        return -1;
    }

}

堆

数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

1 2	输入: [3,2,1,5,6,4], k = 2 输出: 5

思路1：基于快速排序的分治思想，但只需要处理包含第k大元素的那一部分。划分一次后会固定一个元素的位置，且该元素左边都比它小，右边都比它大。如果当前元素下标<n-k，说明第 k 个最大的元素在右边，否则在左边。

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

    private int quickSelect(int[] nums, int k, int left, int right) {
        int pivotIndex = partition(nums, left, right);
        int targetIndex = nums.length - k; // 第k大元素的下标
      
        if (pivotIndex == targetIndex) {
            return nums[pivotIndex];
        } else if (pivotIndex > targetIndex) {
            return quickSelect(nums, k, left, pivotIndex - 1);
        } else {
            return quickSelect(nums, k, pivotIndex + 1, right);
        }
    }

    private int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        while (left < right) {
            while (left < right && nums[right] >= pivot) right--;
            nums[left] = nums[right];
            while (left < right && nums[left] <= pivot) left++;
            nums[right] = nums[left];
        }
        nums[left] = pivot;
        return left;
    }
}

思路2：堆排序法，建立大根堆，建立好之后，每选择一次堆顶元素后调整大根堆，要找第 k 个最大的元素，则选择k-1次调整k-1次。最后的堆顶元素就是第 k 个最大的元素

public int findKthLargest(int[] arr, int k) {
        build(arr);

        for (int j = arr.length - 1; j >= arr.length - 1 - k + 2; j--) {
            int teem = arr[0];
            arr[0] = arr[j];
            arr[j] = teem;
            adjust(arr, 0, j - 1);
        }
        return arr[0];
    }

    public static void build(int[] arr) {
        for (int i = (arr.length - 1) / 2; i >= 0; i--) {
            adjust(arr, i, arr.length - 1);
        }

    }

    public static void adjust(int[] arr, int k, int n) {

        for (int i = k * 2 + 1; i <= n; i = i * 2 + 1) {
            if (i < n && arr[i] < arr[i + 1]) {
                i++;
            }
            if (arr[k] < arr[i]) {
                int temp = arr[k];
                arr[k] = arr[i];
                arr[i] = temp;
                k = i;
            }
        }
    }

思路3：小根堆法，只维护一个大小为k的小根堆，如果堆的大小超过k时，移除堆顶（最小）元素，最终堆顶元素就是第 k 个最大的元素。

public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.add(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }

        }
        return minHeap.peek();
    }

思路4：桶排序，将数组的数据放在若干个桶中，桶中记录的是相同元素的个数，桶的下标代表值（但不是真实值），倒着遍历桶，如果个数超过了k，说明第 k 个最大的元素就在这个桶中。

public int findKthLargest(int[] arr, int k) {
        int max = arr[0];
        int min = arr[0];
        for (int i : arr) {
            max = Math.max(max, i);
            min = Math.min(min, i);
        }
        int range = max - min + 1;
        int tong[] = new int[range];
        for (int i = 0; i < arr.length; i++) {
            tong[arr[i] - min]++;
        }
        int count = 0;
        for (int j = range - 1; j >= 0; j--) {
            count = count + tong[j];
            if (count >= k)
                return j + min;
        }
        return 0;
    }

前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

1 2	输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]

思路1：小根堆。维护一个大小为k的小根堆。遍历玩数组后小根堆里剩下的出现频率前 k 高的元素。因为没当小根堆的大小大于k时，堆顶元素就被移除，移除的是最小值。所以剩下的就是最大值。

public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<Map.Entry<Integer, Integer>> dui = new PriorityQueue<>(
                (a, b) -> a.getValue() - b.getValue() // 比较器：按频率升序
        );
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            dui.add(entry);
            if (dui.size() > k) {
                dui.poll();
            }
        }
        int res[] = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = dui.poll().getKey();
        }
        return res;

    }

思路2：桶排序，将频率作为桶的索引，频率最小值为1，所以桶的大小为nums.length + 1。桶里存放频率对应的数据。

public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        } /**
          1 3
          2 2
          3 1
          */
        ArrayList<Integer> tong[] = new ArrayList[nums.length + 1];
        for (Map.Entry entry : map.entrySet()) {
            int key = (int) entry.getKey();
            int value = (int) entry.getValue();
            if (tong[value] == null) {
                tong[value] = new ArrayList<>();
            }
            tong[value].add(key);
        }
        /**
        {[] [3] [2] [1]  }
         */
        int count = 0;
        int res[] = new int[k];
        for (int j = tong.length - 1; j >= 0; j--) {
            if (tong[j] != null)
                for (int v : tong[j]) {
                    res[count++] = v;
                    if (count == k) {
                        return res;
                    }
                }
        }
        return res;

    }

贪心

买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

class Solution {
    public int maxProfit(int[] prices) {

        int min = prices[0];
        int res = 0;
        for (int i = 0; i < prices.length; i++) {
            min = Math.min(min, prices[i]);
            res = Math.max(res, prices[i] - min);

        }
        return res;

    }
}

跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

1
2
3

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

1
2
3

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

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

跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：

0 <= j <= nums[i] 且
i + j < n

返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

class Solution {
    public int jump(int[] nums) {
        int dp[]=new int[nums.length];
        Arrays.fill(dp,1000000);
        dp[0]=0;
        for(int i=1;i<nums.length;i++){
            for(int j=0;j<i;j++){
                if(j+nums[j]>=i){
                    dp[i]=Math.min(dp[i],dp[j]+1);
                }
            }
        }
        return dp[nums.length-1];

        // int jump=0;
        // int maxLenIndex=0;
        // int curLen=0;
        // for(int i=0;i<nums.length-1;i++){
        //     maxLenIndex=Math.max(maxLenIndex,i+nums[i]);
        //     if(i==curLen){
        //         jump++;
        //         curLen=maxLenIndex;
        //     }
        // }
        // return jump;
    }
}

划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

class Solution {
    public List<Integer> partitionLabels(String s) {
        int map[] = new int[30];
        //统计字母z
        for (int i = 0; i < s.length(); i++) {
            map[s.charAt(i) - 'a'] = i;
        }
        List<Integer> res = new ArrayList<>();

        int start = 0;
        int end = 0;

        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, map[s.charAt(i) - 'a']);
            if (i == end) {
                res.add(end-start+1);
                start = end + 1;

            }

        }
        return res;
    }
}