一段话总结一道题：力扣0~50选_力扣 0,6,10,16,20,1,5

3 无重复字符最长子串

经典滑动窗口题目，同时也选入了剑指offer。
窗口中维护的是无重复的子串，并且使用一个集合维护哪些字符在窗口中，扩大窗口（右指针）的同时，更新集合。一旦右指针重复字符便开始收缩窗口，直到再次回到“稳定期”状态。其中每轮都会判断最长子串的长度。

    public int lengthOfLongestSubstring(String s) {
        if(s.equals(""))return 0;
        char[] chars = s.toCharArray();
        HashSet<Character> set = new HashSet<>();
        int left=0;
        int res=0;
        for (int right = 0; right < chars.length; right++) {
            if(set.contains(chars[right])){
               while (set.contains(chars[right])){
                   set.remove(chars[left++]);
               }
            }
            res=Math.max(res,right-left+1);
            set.add(chars[right]);
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

4 寻找两个有序数组的中位数

如果使用O（m+n）去做，就相当于是合并有序数组，合并到中位数大小就退出。题目要求我们log（m+n）
这一题这得是难处边界了，思路写出来也不好实现，这里提供一种参考题解区大佬的思路和代码。
我们把寻找中位数问题转换为寻找有序数组第K小的问题，假设两个数组的长度为a和b，如果将这两个数组合并，那么中位数就是第K小的数或第K小与第K+1小取平均数。

两个数组如[1,3,5]和[0,2,4,6,8,10,12,14,16]，总共是12个数，那么我们应该找到第6小和第7小的数，然后取平均值。以找到第6小的数为例，因为我们从两个数组中查找，因为先找到每个数组中第3小的元素（K/2）（如果k/2越界就取边界），然后我们比较这两个数组的第k/2小元素，如果一方更大，另一方的[left…k/2]肯定不包含第K小的元素，而另一边的这个k/2对应的元素有可能是中位数。
以上面的值为例，我们第一次各种寻找数组第3个元素（5和4），其中4更小则[0,2,4]被排除，我们下一轮则寻找第3小的元素（即[1,3,5]和[6,8,10,12,14,16]），最终[1,3]被排除，最后搜索[5]和[6,8,10,12,14,16]中第1小的元素，得到5.

总结：两个有序数组寻找第K小，每轮最多可以淘汰K/2个元素，并且下一轮搜索的范围也缩减K/2，最终退化为搜索两个有序数组中最小的元素。

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int a = nums1.length;
        int b = nums2.length;
        //偏左和偏右的指针(如果是奇数，相当于重复计算了两次)
        int l = (a+b+1)/2;
        int r = (a+b+2)/2;
        return (findMedianSortedArrays(nums1,0,a-1,nums2,0,b-1,l)
        +findMedianSortedArrays(nums1,0,a-1,nums2,0,b-1,r))*0.5;
    }
1
2
3
4
5
6
7
8
9

以上相当于无差别计算了两次，避免奇偶性带来的讨论，传入的K不是索引，而是指寻找第K个小的元素

    private double findMedianSortedArrays(int[] nums1,int start1,int end1,
                                          int[] nums2,int start2,int end2,int k){

        int lenA = end1-start1+1;
        int lenB = end2-start2+1;
        /**
        计算时，按照左边短数组，右边长数组，如果左边被排除完毕，则直接返回右数组第K小的元素
         */
        if(lenA>lenB){
            return findMedianSortedArrays(nums2,start2,end2,nums1,start1,end1,k);
        }
        if(lenA==0){
            return nums2[start2+k-1];
        }
        // 普通的递归返回：退化为有序数组中寻找最小值
        if(k==1){
            return Math.min(nums1[start1],nums2[start2]);
        }
        //进行边界处理，每轮并不一定能够排除K/2个数
        int i =start1+Math.min(k/2,lenA)-1; //指向末尾元素，或者当前数组第k/2个元素
        int j =start2+Math.min(k/2,lenB)-1;
        //没有被排除的元素原样进行下一次搜索，被排除的数组改变范围，k也缩减相应范围
        if(nums1[i]>nums2[j]){
            return findMedianSortedArrays(nums1,start1,end1,nums2,j+1,end2,k-(j-start2+1));
        }else {
            return findMedianSortedArrays(nums1,i+1,end1,nums2,start2,end2,k-(i-start1+1));
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

5 最长回文串

回文串问题如果做的多，最容易想到一个状态转移方程就是dp[i][j] s[i…j]是不是一个回文串，如果s[i]=s[j]则他们是不是回文串则取决于s[i+1]和s[j-1]

    public String longestPalindrome(String s) {
        int len = s.length();
        int max = 0;
        int a =0;
        int b =1;
        boolean[][] dp = new boolean[len][len];
        for(int i=0;i<len;i++){ // 表示回文串长度s[j...j+i]
            for(int j=0;j+i<len;j++){
                if(i==0){
                    dp[j][j]=true;
                }else if(i==1 && s.charAt(j)==s.charAt(j+1)){
                    dp[j][j+i]=true;
                }else if(s.charAt(j)==s.charAt(j+i)){
                    dp[j][j+i]=dp[j+1][j+i-1];
                }
                if(i>max&&dp[j][j+i]){
                    max=i;
                    a=j;
                    b=j+i+1;
                }
            }
        }
        return s.substring(a,b);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

本题的另一种解法是中心扩散法：枚举每一个起始点，然后向两边扩散，判断以当前点为对称中心的回文串长度（需要分奇偶性讨论）。这种解法常见于：山脉数组、矩形判断等具有一定对称性的问题上

public String longestPalindrome(String s) {
        int start=0;
        int max=1;
        int len = s.length();
        for (int i = 0; i < len; i++) {
            int a =helper(s,i,i);//如果是奇数，left和right都是同一个点
            int b =helper(s,i,i+1);//如果是偶数，left和right不是同一个点
            int temp=Math.max(a,b);
            if(temp>max){
                if(temp%2==0){	//更新截取的起始坐标
                    start=i+1-temp/2;
                }else {
                    start=i-temp/2;
                }
                max=temp;	//更新回文串长度
            }
        }
        return s.substring(start,start+max);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

扩散函数，返回回文串长度

    private int helper(String s,int left,int right){
        while (left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){
            left--;
            right++;
        }
        return right-left-1;
    }
1
2
3
4
5
6
7

6 Z字型变换

如果使用过DFS实现层序遍历，那么就可以参考一下“分层”插入的思路。
我们一次深度遍历可能涉及对不同层次的追加。而本题最基本的思路也是“对字符串”进行分层，每一层涉及不同的字符串，我们需要找到一种方案去实现“自动换行”

观察上图的规律，四层，我们创建一个四层的stringBuilder集合，对0…3个字符串依次向下插入，我们使用一个计数器，一旦字符串索引为大于等于numsRows-1则开始折返，一旦达到0再次折返，依次类推

    public String convert(String s, int numRows) {
        if(numRows<2)return s;
        ArrayList<StringBuilder> res = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            res.add(new StringBuilder());
        }
       int index=0;//当前向哪一个stringBuilder插入？
       int temp=-1;//控制方向
        for (int i = 0; i < s.length(); i++) {
            res.get(index).append(s.charAt(i));
            if(index==0||index==numRows-1){
                temp=-temp;
            }
            index+=temp;
        }
        StringBuilder sb = new StringBuilder();
        for(StringBuilder res_:res){
            sb.append(res_);
        }
        return sb.toString();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

普通的去写，我们可以使用布尔值控制方向，并且通过条件判断去决定取哪一层，以上代码的巧妙之处是将取stringBuilder和控制方向完美结合，去除了不必要的条件语句。

7 整数反转

十分基础，不推荐基于字符串变换

    public int reverse(int x) {
        long res = 0;//防止溢出，面向测试
        while(x!=0){
            res*=10;
            res+=x%10;
            x/=10;
        }
       int ans = (int)res;
       if(ans==res){
           return ans;
       }else{
           return 0;
       }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

结果每轮叠加前乘十，做一个十进制左移，然后取目标数的余数进行累加，之后目标数做十进制右移，重复此过程，指定目标数右移得到0

第九题回文数判断，一个常见的思路是将源数做一个整数返回操作，然后进行一个对比。

10 正则表达式匹配

比较复杂，见之前剑指offer的文章

11 盛水最多的容器

本题乍一看有点像接雨水，其中接雨水需要考虑中间挡板，而本题只需要考虑任意两个挡板以及之间的距离。
双指针解法，两个指针一开始分别指向两端，每轮选择其中一个指向更低的挡板的指针向中间靠拢，因为每轮的距离必然会减一，那么我们为了得到最大值，优先尝试移动“低挡板”指针。

   public int maxArea(int[] height) {
     int low =0;
     int high =height.length-1;
     int max =-1;
     int min =Math.min(height[low],height[high]);//决定盛水的高度
     while (low<high){
         int result=min*(high-low);
         max= Math.max(result,max);
         //尽量让两个柱子都高——移动较小的一方，尝试搜索可能性
         if(height[low]>height[high]){
             high--;
         }else {
             low++;
         }
         //更新状态
         min =Math.min(height[low],height[high]);
     }
       return max;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

16 最接近的三数之和

本题是三数之和的变式，大框架还是三数之和的解法（固定一个，剩下两个按照两数之和去做），做之前先排序。
要找到最接近target的三数之和，我们使用临时值temp保存三数之和，res保存最终的值，那么每轮的判断条件就应该是如果Math.abs(res-target)的差值比Math.abs(sum-target) 还小(其中sum是某一三数之和)，说明有更加接近target的三数之和res

    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int len = nums.length;
        int res=nums[0]+nums[1]+nums[2];
        for(int i=0;i<len;i++){
            int cur = nums[i];
            int left = i+1;
            int right = len-1;
            while (left<right){
                int sum = nums[left]+nums[right]+cur;
                //比较res和sum对target的差值
                if(Math.abs(sum-target)<Math.abs(res-target)){
                    res=sum;
                }
                if(sum>target){
                    right--;
                }else if(sum<target){
                    left++;
                }else {
                    return sum;
                }
            }
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

后面还有四数之和，无非是定1，然后转换为3数之和问题。

22 括号生成

深度遍历，我们一开始可以生成n个左括号和n个右括号。我们每一步（每一层）可以选择生成左括号，或者生成右括号。生成左括号的前提是“当前能够生成的左括号有剩余”，而生成右括号的前提是"当前能够生成的右括号多于左括号"（因为如果右括号先生成且小于等于左括号的数量，最终一定是一个无效的括号）。当左右括号剩余生成数量为0时退出。

    public List<String> generateParenthesis(int n) {
        List<String> res =new LinkedList<>();
        generateParenthesis(n,n,res,"");
        return res;
    }
    private void generateParenthesis(int left,int right,List<String> res,String str){
        if(left==0&&right==0){
            res.add(str);
            return;
        }
        if(left>0){//左括号剩余
            generateParenthesis(left-1,right,res,str+"(");
        }
        if(right>left){//右括号剩余多于左括号
            generateParenthesis(left,right-1,res,str+")");
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

23 合并K个升序链表

本题基本是困难题中偏简单的，而且解法就是分治，和它解法相似的题是链表归并排序。K个升序链表如果拆成原子问题就是两个升序链表之间的合并。“分”操作的最后一层就是分别返回节点本身，然后依次向上合并且执行合并有序链表操作。

    public ListNode mergeKLists(ListNode[] lists) {
return mergeK(lists,0,lists.length-1);
}
    private ListNode mergeK(ListNode[] lists,int l ,int r){
        if(l==r)return lists[l];
        else if(l>r)return null;
        else {
            int mid =(l+r)>>1;
            ListNode a = mergeK(lists, l, mid);
            ListNode b = mergeK(lists, mid+1,r);
            return merge(a,b);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

merge就是合并两个升序链表，不再给出。

25 题K个一组反转链表，我们借用将每K个链表进行一次断开，并且调用反转函数，然后再重新接上。如1->2->3->4->5 如果是2个一组反转就断开成1->2->null 、 3->4->null 、5->null 依次反转并重新连接。

26 原地删除有序数组重复项

经典的双指针原地交换，把nums看作一个数据数组和一个逻辑数组，遍历的过程我们遍历的是数据数组，而赋值的时候我们是在逻辑数组中进行赋值。

    public int removeDuplicates(int[] nums) {
        int lazy=0;
        for(int i=1;i<nums.length;i++){
            if(nums[lazy]!=nums[i]){
                lazy++;
                nums[lazy]=nums[i];
            }
        }
        return lazy+1;
    }
1
2
3
4
5
6
7
8
9
10

29 两数相除

前提：不能使用取余、除号和乘号
我们可以使用减法模拟除法，但是太慢了，因此我们可以通过动态调整步长的方式提高效率。
除数可以看作距离，被除数可以看作步长，那么二者相除就是通过该距离需要的步数，例如距离15，步长为3，那么步数就是5。
15 / 3 最初步长为3,15-3=12 >= 3 ，此时我们尝试将步长翻倍，12 - 6 >= 6 因此我们一次走了两步（而不是一步一步的固定走法），再次翻倍时由于6 < 12 因此无法一次走12步，退化原来的步长3 重复上述过程。（当然了还可以继续优化，例如如果恰好距离等于步长直接返回1即可）

       public int divide(int dividend, int divisor) {
        int sign = (dividend ^ divisor) >> 31;//同号为0异号为1
        long lDividend = Math.abs((long) dividend);
        long lDivisor = Math.abs((long) divisor);
        long res = 0;
        while (lDividend >= lDivisor){
            long tmp = lDivisor;//初始步长
            long i = 1; 
            while (lDividend >= tmp){
                lDividend -= tmp;
                res += i;
                i <<= 1;
                tmp <<= 1;//动态调整补充
            }
        }
        if (sign == -1) res *= -1;
        if (res < Integer.MIN_VALUE) return Integer.MIN_VALUE;
        else if (res > Integer.MAX_VALUE) return Integer.MAX_VALUE;
        return (int)res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

30 串联所有单词的子串

前提：子串长度相同，因此父串一定是子串长度的倍数，匹配的父串中子串可以是不按照顺序的，但是必须完全包含所有子串才能算是一次成功的匹配。
本题的一种常规解法是基于固定大小的滑动窗口，从上述的描述来看，必然需要把子串存入哈希表中。
滑动窗口的大小就是父串的大小，每当滑动生成一个父串，就使用子串大小的固定窗口进行验证

    public List<Integer> findSubstring(String s, String[] words) {
        HashMap<String,Integer> wordCountMap = new HashMap<>();
        ArrayList<Integer> res = new ArrayList<>();
        for(String word:words){
            if(!s.contains(word))return res;
            wordCountMap.put(word,wordCountMap.getOrDefault(word,0)+1);
        }
        //子串长度（固定）
        int oneLen = words[0].length();
        //父串的长度（固定）
        int AllLen = oneLen*words.length;
        for(int i=0;i+AllLen<=s.length();i++){
            String sub = s.substring(i,i+AllLen);//当前待验证的父串
            HashMap<String, Integer> temp = new HashMap<>(wordCountMap);
            for(int j=0;j+oneLen<=sub.length();j+=oneLen){
                String sub2 = sub.substring(j,j+oneLen);
                //通过计数值进行验证
                if(temp.containsKey(sub2)){
                    Integer count = temp.get(sub2);
                    if(count>1){
                        temp.put(sub2,count-1);
                    }else {
                        temp.remove(sub2);
                    }
                }else {
                    break;
                }
            }
            if(temp.isEmpty()){
                res.add(i);
            }
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

31 下一个排列

前提：如果不存在下一个更大的排列,则将数字重新排列成最小的排

以1234为例，我们其中高位就是1（对应索引0），低位是4（对应索len-1）。
从低位向高位遍历，直到找到一个递减的组成（上升序列）如1234中的34（如果没有任何一个这样的值如4321，那么说明当前数不存在“下一个排列”，直接逆转为最小值）
此时指针指向这个递减组合34中较小的数3，我们从低位开始向高位寻找第一个比该数大的数如1234中的4，交换这两个数变成1243，此时指针p指向这个被交换后的较大值，之后翻转p与低位之间的数（不包含p）。
再比如15273 ，先找到27 ，然后交换3和2得到15372，然后逆转(3…2]得到15327

    public void nextPermutation(int[] nums) {
        int len = nums.length;
        int i = len-1-1;
        while (i!=-1&&nums[i]>=nums[i+1])i--;//如果是4321则i最终指向-1
        if(i==-1){
            reverse(nums,0,len-1);
        }else {
         int j = len-1;
         while (nums[i]>=nums[j])j--;
         swap(nums,i,j);
         reverse(nums,i+1,len-1);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

32 最长有效括号

本题的一种解法是动态规划，但是十分复杂，而基于栈的解法却十分友善。

我们为每个括号字符对应一个布尔值，代表这个括号是否有效，初始值全为false。
栈中只存放左括号’(’，并且每遇到一个右括号就出栈（同时两个符号对应布尔值都标记为true）。
但我们遍历)()())时，布尔数组对应FTTTTF，最后遍历一遍字符数组，拿到最长连续T即可。

    public int longestValidParentheses(String s) {
        int len=s.length();
        boolean[] isOK = new boolean[len];
        LinkedList<Integer> stack = new LinkedList<>();
        char[] chars = s.toCharArray();
        for (int i = 0; i < len; i++) {
            if(chars[i]==')'&&!stack.isEmpty()){
                isOK[i]=true;
                isOK[stack.pop()]=true;
            }else if(chars[i]=='('){
                stack.push(i);
            }
        }
        int count=0;
        int max=0;
        for(boolean b:isOK){
            if(b)count++;
            else {
                max=Math.max(max,count);
                count=0;
            }
        }
        return Math.max(count,max);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

33 搜索旋转排序数组

做旋转数组的题，首先需要确定范围哪一边是有序的，使用mid元素和right元素比较，如果nums[mid]<nums[right]，说明右边是有序的，（可以举几个极端的例子）如5 1 2 3 4 。反之（本题题干不存在重复元素）说明左边有序如 5 6 7 1 2.
一旦确定了范围，我们就能够找到“有序范围”内的最大值和最小值，和target进行比较来确定下一次二分的范围

    public int search(int[] nums, int target) {
        int left = 0 ;
        int right = nums.length-1;
        while (left<=right){
            int mid = (right-left)/2+left;
            if(nums[mid]==target)return mid;
            if(nums[mid]<nums[right]){  // 5 1 2 3 4 右边有序
                if(nums[mid]<target && target<=nums[right]){   //mid 是否落在了有序的范围
                    left=mid+1;
                }else {
                    right=mid-1;
                }
            }else { // 5 6 7 8 1 左边有序
                if(nums[left]<=target && target<nums[mid]){
                    right=mid-1;
                }else {
                    left=mid+1;
                }
            }
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

34题 在排序数组中查找元素的第一个和最后一个元素，使用三次二分（如果使用遍历，内部元素全部相同将会退化为O（n）），先找到目标元素，然后以这个目标位置mid为参考，第二个二分查找中，right=mid ，第三个二分查找中left=mid+1。

36 有效数独

前提：本题中是9X9固定棋盘，有一些是空的，我们只需要验证哪些非空的位置。
我们只需要使用三个标志位数组，每遍历一个数就判断数组中是否已经存在这个数即可。
每一行、每一列以及每个3X3小格子都可以使用一个大小为9的标志位数组，如果数字存在就标记为true，如果存在其他数字进行判断则return false。
其中9个格子，我们看成一个线性的结构，使用i / 3 * 3 + j / 3 进行线性定位某一个格子。

    public boolean isValidSudoku(char[][] board) {
        boolean[][] row = new boolean[9][9];
        boolean[][] col = new boolean[9][9];
        boolean[][] block = new boolean[9][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if(board[i][j]=='.')continue;
                int curNum = board[i][j]-'0'-1;
                int block_pos = (i/3)*3+j/3;
                if(row[i][curNum]||col[j][curNum]||block[block_pos][curNum])return false;
                row[i][curNum]=true;
                col[j][curNum]=true;
                block[block_pos][curNum]=true;
            }
        }
    return true;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

37 解数独

首先按照36题的逻辑，将棋盘填充，本题是解数独，因此给出的都是有效的数。

    boolean[][] row = new boolean[9][9];//行数-数字
    boolean[][] col = new boolean[9][9];
    boolean[][] box = new boolean[9][9];
    public void solveSudoku(char[][] board) {
        //初始化棋盘
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if(board[i][j]=='.')continue;
                int num = board[i][j] - '0' - 1;
                row[i][num] = true;
                col[j][num] = true;
                box[(i / 3)*3+j/3][num] = true;
            }
        }
        //回溯解数独
        helper(board, 0, 0);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

我们从坐标0,0开始回溯，如果x坐标走到头（0,8）就往下一行接着走（1,0），如果y坐标也走到头了，那么我们当前的结果就解出来了。
对每个位置依次尝试1-9这9个数字，如果数字是无效的（36题逻辑则剪枝），否则进入下一轮递归，如果数字已经存在，则什么都不做继续向后解数独。

    private boolean helper(char[][] board, int x, int y) {
        if (x == 9) return true;
        if (y == 9) {//换行
            return helper(board,x+1,0);
        }
        if (board[x][y] == '.') {//未填写
            for (int num = 0; num < 9; num++) {
                //无效的数字
                if(row[x][num] || col[y][num] || box[(x / 3)*3+y/3][num])continue;
                row[x][num] = true;
                col[y][num] = true;
                box[(x / 3)*3+y/3][num] = true;

                board[x][y] = (char) (num + 1 + '0');
                if (helper(board, x, y + 1)) return true;
                board[x][y] = '.';

                row[x][num] = false;
                col[y][num] = false;
                box[(x / 3)*3+y/3][num] = false;
            }
        } else {
            //当前已经存在数字，向后继续寻找
            return helper(board, x, y + 1);
        }
        return false;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

39组合总数

关键词：无重复元素、每个数字无限制选举、组成目标和的所有组合。
这个题如果是求组合数可以看作完全背包问题或者零钱兑换问题，但是它要求我们给出所有具体的组合，因此只能使用遍历（回溯）

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res =new LinkedList<>();
        LinkedList<Integer> track  =new LinkedList<>();
        Arrays.sort(candidates);
        backTrack(candidates,target,track,res,0);
        return res;
    }
1
2
3
4
5
6
7

private void backTrack(int[] nums,int target,LinkedList<Integer> track,List<List<Integer>> res,int start){
        if(target<0)return;
        if(target==0){
         res.add(new LinkedList<>(track));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if(nums[i]>target)break;
            //选择
            track.add(nums[i]);
            //因为一个数可以无限选取，因此这里不是i+1
            backTrack(nums,target-nums[i],track,res,i);
            //撤销
            track.removeLast();
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

递归的路径如上，其中箭头上的数字就是每一次的选择，相加就是目标和，如果目标和超过target就会剪枝，等于target就会返回列表。其中每个“节点”是一个选择的范围（即[i…len-1]）

40 组合总数2

关键词：只能选择一次，存在重复元素。

如果是[1,1,1,1] target=4 ，那么最终结果只能是一个[1,1,1]因为每个元素只能使用一次，如果不进行去重，那么最终将返回两个[1,1,1]

如果本题要求的是次数，那么完全可以转换为01背包问题。
本题的做法采用向下减的做法（和向上加没区别），需要考虑去重，因为之前排过序所以能够很快地淘汰重复元素，而且要求只选择一次，因此一旦选择一个元素，下一次的选择范围应该剔除当前数即（i+1）

    private void track(int[] optArray,int target,List<List<Integer>> res,List<Integer> list,int start){
     if(target==0){
         res.add(new ArrayList<>(list));
         return;
     }
     if(target<0)return;
        for (int i = start; i < optArray.length; i++) {
            if(optArray[i]>target)break;
            //[1,1,1,1]只会现在最左边的1，其他的分支全部剪枝
            if(i>start&&optArray[i]==optArray[i-1])
                continue;
            list.add(optArray[i]);
            //易错点，这里的i+1容易写成start+1
            track(optArray,target-optArray[i],res,list,i+1);
            list.remove(list.size()-1);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

41 缺失的第一个正数

数组未排序，范围没有出现的最小正整数。
正确的位置：位置=元素值-1 。一个存放不正确位置的元素value = nums[i]，它的正确位置是value-1 ， 而此时value-1这个位置存放的元素nums[value-1]也需要一个位置存放。因此我们进行交换 i 位置和 value-1 位置的元素。（交换后不应该向后遍历，而是继续交换，直到nums[i]-1位置放入了正确的元素）

      public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if(nums[i]==i+1)continue;
    //value = nums[i]的正确位置应该是value-1，而此时value-1这个位置存放的元素不是value
            while(nums[i]-1>=0&&nums[i]-1<len&&nums[nums[i]-1]!=nums[i]){
            //这里就是交换nums[i]-1位置和 i 位置的元素 
                int value = nums[i];
                nums[i]=nums[value-1];    
                nums[value-1]=value;
            }
        }
        for (int i = 0; i < len; i++) {
            if(nums[i]!=i+1)return i+1;
        }
        return len+1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

以 3 4 -1 1为例，3应该放入的正确位置是2，于是与2位置-1进行交换得到-1 4 3 1，由于-1-1=-2越界退出。4的正确位置是3，交换后-1 1 3 4,之后1又和-1交换得到 1 -1 3 4，由于-1越界退出，进入下一个数字的遍历。3的正确位置是2 ，存放正确，4的正确位置是3存放正确。
最终数组 1 -1 3 4 ，由于1的位置存放不是2，因此返回2

42 接雨水

非常容易考察的一道困难题，其中一个解法是中心扩散，不过最主要的解法还是单调栈。

height = [0,1,0,2,1,0,1,3,2,1,2,1]
维护一个递减的单调栈，一旦遍历到升序关系就进行结算。（为了方便计算，推荐在数组两侧加上哨兵节点变成height = [0,0,1,0,2,1,0,1,3,2,1,2,1,0]）
每一层结算都是一个横向水槽的结算。
假设某一时间，递减栈内元素1 0 ，这时遇到一个2 ，此时的栈顶元素指向当前槽的深度，栈顶元素的前一个元素指向**“比当前槽高一点的槽的深度”**
Math.min(height[stack.peek()],height[i])取最低的槽（就是包围的上上高度），i-stack.peek()-1是槽的结算部分的长度。min-当前槽深度就是需要结算的高度

    public int trap(int[] height) {
        LinkedList<Integer> stack = new LinkedList<>();
        int res=0;
        int len = height.length;
        for (int i = 0; i < len; i++) {
            //递减栈——遇到高的时候进行结算
            while (!stack.isEmpty()&&height[stack.peek()]<height[i]){
                int high = height[stack.pop()]; //当前“槽”的深度
                if(stack.isEmpty())break;   //说明不存在“包围关系”
                int distance = i-stack.peek()-1;//两墙之间距离
                int min = Math.min(height[stack.peek()],height[i]);
                res+=distance*(min-high);//被围起来的“水平”水量
            }
            stack.push(i);
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

当结算完毕，“低槽”就出栈了，之后结算的就是更高一些的“水平槽”

43 字符串相乘

123 和456 相乘，我们从低位向高位相乘，最终将得到长度为6的数或者长度为5的数。我们可以将整数相乘问题转换为整数中的每一位进行相乘，相乘之后结果保存在数组中，之后我们取数组中的个位数保留，高位则执行进位操作。
其中6乘123对应[0,0,0,6,12,18],接着5乘123对应[0,0,5,16,27,18],接着4乘123对应[0,4,13,28,27,18]。
我们从低位向高位遍历这个数组，只保留各位，高位向更高位累加（进位），最终可以得到[0,5,6,0,8,8]

    public String multiply(String num1, String num2) {
    if(num1.equals("0")||num2.equals("0"))return "0";
        int len1 = num1.length();
        int len2 = num2.length();
        int[] res=new int[len1+len2];//最大长len1+len2，最小len1+len2-1
        for(int i=len1-1;i>=0;i--){//越靠右位数越低
            int x=num1.charAt(i)-'0';
            for(int j=len2-1;j>=0;j--){
                int y=num2.charAt(j)-'0';
                res[i+j+1]+=x*y;//第i位乘以第j位，位于第i+j+1位（写个算式能看出来）
            }
        }
        //统一进行一次进位
        for(int i=len1+len2-1;i>0;i--){
            //从低位到高位依次进位
            res[i-1]+=res[i]/10;
            res[i]%=10;
        }
        StringBuffer ans = new StringBuffer();
        for(int i=0;i<res.length;i++){
            if(i==0&&res[i]==0)continue;
            ans.append(res[i]);
        }
        return ans.toString();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

44 通配符匹配

这道题比正则匹配容易不少，这里星号*可以用于匹配任意一个字符串（包括空串），问号?可以用于匹配单个字符。
我们遇到一个* 应该做一个判断：把它看作空字符还是任意字符串
dp[i][j] 代表字符串s[0…i]是否能够匹配字符模式p[0…j]

其中，我们向对s为空串的情况进行初始化，这时模式串中的星号只能被看作空字符。而且仅能通过星号匹配，其他字符一定是失配的（除了dp[0]/[0]）。

我们判断s[i-1]和p[j-1]如果相等p[j-1]是一个？，那么说明当前位置匹配成功，s[0…i]是否能够匹配字符模式p[0…j]我们只需要考虑s[0…i-1]和p[0…j-1]，而这个结果已经被保存在dp[i-1][j-1]中了。

而如果p[j-1]是星号：
【1】如果把它看作空字符，那么问题实际转换为了字符串s[0…i]是否能够匹配字符模式p[0…j-1]。这个结果被保存于dp[i][j-1]
【2】如果把它看作任意字符串，那么当前字符一定能够匹配，那么问题实际转换为了字符串s[0…i-1]是否能够匹配字符模式p[0…j],这个结果被保存于dp[i-1][j]

    public boolean isMatch(String s, String p){
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0]=true;
        for(int i=1;i<=n;i++){
            if(p.charAt(i-1)=='*')
                dp[0][i]=dp[0][i-1];
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if((s.charAt(i-1)==p.charAt(j-1)||p.charAt(j-1)=='?')){
                    dp[i][j]=dp[i-1][j-1];
                }else if(p.charAt(j-1)=='*'){
                    dp[i][j]=dp[i-1][j]||dp[i][j-1];
                    //dp[i-1][j] *与当前字符匹配 或者 dp[i][j-1] *看作空字符
                }
            }
        }
        return dp[m][n];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

45 跳跃游戏

贪心策略，总是在可选的跳跃范围内选择最大值作为跳跃边界，end表示跳跃的边界，以[2,3,1,1,4,2,1]为例，我们最开始从0处开始跳，这个时候的最大值就是2，因此此时的跳跃范围是[3,1]，跳跃边界是1处。
第一次跳跃是从0开始跳，没得选，而且最远只能跳到1处。
第二次我们从[3,1]中某个数进行跳跃（具体是哪个我们不关心），我们只关心新的边界是什么，而且确保这个边界一定是从[3,1]中某个位置跳跃可以达到的最大位置。后面以此类推。
总结：每次起跳确定边界位置，当下一次从边界位置开始起跳，其中新边界的选取取决于起跳范围内能够跳跃到的最大位置。

    public int jump(int[] nums) {
        int max = Integer.MIN_VALUE;
        int end=0;
        int count=0;
        for (int i = 0; i < nums.length-1;i++ ) {//i=0时进行了一次更新，因此num.length那一次就不计入了
            max = Math.max(max,i+nums[i]);
            //最小的跳跃次数，就是每次都从边界起跳
            if(i==end){
                end = max;
                count++;
            }
        }
        return count;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

48 旋转图像

先对整个矩阵进行转置，然后对矩阵的每一行进行逆转

    public void rotate(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < i; j++) {
                int temp = matrix[i][j];
                matrix[i][j]=matrix[j][i];
                matrix[j][i]=temp;
            }
        }
        for (int i = 0; i < m; i++) {
            int a=0;int b=n-1;
            while (a<b){
                int temp = matrix[i][a];
                matrix[i][a]=matrix[i][b];
                matrix[i][b]=temp;
                a++;b--;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

50 POW(a,b)

2的10次方等价于（2的五次方）的二次方，2的五次方又可以拆分为2 * 2的四次方 …

    public double myPow(double x, int n) {
    long nn =n; //为了通过边界值，需要将int的n用long接收
        return myPow2(x,nn);
    }
    private double myPow2(double x,long n){
        if(n==0)return 1;
        if(n<0){
            x=1/x;
            n=-n;
        }
        double res = myPow2(x,n/2);
        if((n&1)==1)return res*res*x;
        else return res*res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

快速幂思想，和上面的拆分相反，2的10次方等价于（2的二次方即4）的五次方…不过最终导向的值都是相同的

    private double myPow2(double x,long n){
        if(n==0)return 1;
        if(n<0){
            x=1/x;
            n=-n;
        }
        if((n&1)==1)return x*myPow2(x,n-1);
        else return myPow2(x*x,n/2);

    }
1
2
3
4
5
6
7
8
9
10