数组

704. 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

解答：

# 循环判断左右指针是否走到一起，判断中间值大于还是小于目标值，等于则返回否则，重新复制左右指针，继续循环。
class Solution {
    public int search(int[] nums, int target) {
        int left = 0,right = nums.length-1;
        while(left<=right) {
            int mid=left+(right-left)/2;
            if(nums[mid] == target) {
                return mid;
            }else if(nums[mid] > target) {
                right = mid-1;
            }else {
                left = mid+1;
            }
        }
        return -1;
    }
}

495. 提莫攻击

难度简单184

在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。

当提莫攻击艾希，艾希的中毒状态正好持续 duration 秒。

正式地讲，提莫在 t 发起发起攻击意味着艾希在时间区间 [t, t + duration - 1]（含 t 和 t + duration - 1）处于中毒状态。如果提莫在中毒影响结束 前 再次攻击，中毒状态计时器将会 重置 ，在新的攻击之后，中毒影响将会在 duration 秒后结束。

给你一个 非递减 的整数数组 timeSeries ，其中 timeSeries[i] 表示提莫在 timeSeries[i] 秒时对艾希发起攻击，以及一个表示中毒持续时间的整数 duration 。

返回艾希处于中毒状态的 总 秒数。

示例 1：

输入：timeSeries = [1,4], duration = 2
输出：4
解释：提莫攻击对艾希的影响如下：
- 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。
- 第 4 秒，提莫再次攻击艾希，艾希中毒状态又持续 2 秒，即第 4 秒和第 5 秒。
艾希在第 1、2、4、5 秒处于中毒状态，所以总中毒秒数是 4 。

示例 2：

输入：timeSeries = [1,2], duration = 2
输出：3
解释：提莫攻击对艾希的影响如下：
- 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。
- 第 2 秒，提莫再次攻击艾希，并重置中毒计时器，艾希中毒状态需要持续 2 秒，即第 2 秒和第 3 秒。
艾希在第 1、2、3 秒处于中毒状态，所以总中毒秒数是 3 。

提示：

• 1 <= timeSeries.length <= 104
• 0 <= timeSeries[i], duration <= 107
• timeSeries 按 非递减 顺序排列

思路：抛开惯性思维，不要本能 想着 从前往后 看，可以从后往前看，最后一个单独处理。

解答：

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int lastTime = 0, ans = 0;
        for(int i = 1; i < timeSeries.length; i++) {
            ans += Math.min(timeSeries[i]-timeSeries[i-1], duration);
        }
        ans += duration;
        return ans;
    }
}

46. 全排列

难度中等1653

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整数 互不相同

思路：每次for没 执行完就继续dfs了，return回来之后，后面的就是没有执行的数放进去，接着遍历，然后不断重复回到根节点之时，就是遍历完成之时。

解答：

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

        boolean[] used = new boolean[len];
        List<Integer> path = new ArrayList<>();

        dfs(nums, len,0,path, used,res);
        return res;
    }

    private void dfs(int[] nums, int len, int depth,
                List<Integer> path, boolean[] used,
                List<List<Integer>> res) {
        if (depth == len) {
            res.add(new ArrayList<>(path));
            return;
        }

        for(int i=0; i<len; i++) {
            if(!used[i]) {
                path.add(nums[i]);
                used[i]=true;

                dfs(nums, len, depth+1, path, used, res);
                used[i]=false;
                path.remove(path.size() - 1);
            }
        }
    }

}

47. 全排列 II

难度中等870

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,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 <= nums.length <= 8
• -10 <= nums[i] <= 10

思路：对数组进行排序，当前与前一个的根节点相同时，跳过这一次遍历

解答：

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int len = nums.length;
        if(len == 0) return res;

        boolean[] used = new boolean[len];
        List<Integer> path = new ArrayList<>();
        Arrays.sort(nums);

        dfs(nums, len,0,path, used,res);
        return res;
    }

    private void dfs(int[] nums, int len, int depth,
                List<Integer> path, boolean[] used,
                List<List<Integer>> res) {
        if (depth == len) {
            res.add(new ArrayList<>(path));
            return;
        }

        for(int i=0; i<len; i++) {
            if(used[i]) continue;
            // used[i-1] == false保证前一个根节点，刚撤销选择
            // i>0保证第二位开始
            if(i>0 && nums[i] == nums[i-1] && used[i-1] == false) continue;

            path.add(nums[i]);
            used[i]=true;

            dfs(nums, len, depth+1, path, used, res);
            used[i]=false;
            path.remove(path.size() - 1);
            
        }

    }
}

374. 猜数字大小

猜数字游戏的规则如下：

• 每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
• 如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。

你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：

• -1：我选出的数字比你猜的数字小 pick < num
• 1：我选出的数字比你猜的数字大 pick > num
• 0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num

返回我选出的数字。

示例 1：

输入：n = 10, pick = 6
输出：6

示例 2：

输入：n = 1, pick = 1
输出：1

示例 3：

输入：n = 2, pick = 1
输出：1

示例 4：

输入：n = 2, pick = 2
输出：2

提示：

• 1 <= n <= 231 - 1
• 1 <= pick <= n

思路：

• 设置左右两个端点

• 每次循环区间内折半

• 左右相等时退出得到正确答案

解答：

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int left=1, right=n;
        while(left < right) {
            int mid = left + (right -left)/2;
            if(guess(mid) <=0) right = mid;
            else left = mid+1;
        }
        return left;
    }
}

NC41 最长无重复子数组

知识点哈希双指针数组

描述

给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。

子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组

数据范围：0≤arre.length*≤10⁶，0<*a**r**r*[*i*]≤10⁵

要求：空间复杂度 O*(*n)，时间复杂度 O(nlogn)

示例1

输入：

[2,3,4,5]

返回值：

4

说明：

[2,3,4,5]是最长子数组      

示例2

输入：

[2,2,3,4,3]

返回值：

3

说明：

[2,3,4]是最长子数组      

示例3

输入：

[9]

返回值：

1

示例4

输入：

[1,2,3,1,2,3,2,2]

返回值：

3

说明：

最长子数组为[1,2,3]     

示例5

输入：

[2,2,3,4,8,99,3]

返回值：

5

说明：

最长子数组为[2,3,4,8,99]  

思路：

• 两个指针，一个i一个j，最开始的时候i和j指向第一个元素
• 然后i往后移，把扫描过的元素都放到map中
• 如果i扫描过的元素没有重复的就一直往后移，顺便记录一下最大值max
• 移动j的时候应该为 Math.max(j, map.get(arr[i]) + 1)
• 重复的数字可能在之前移动j的时候跳过了，所以j的位置不动。

解答：

import java.util.*;


public class Solution {
    /**
     * 
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        // write code here
        if (arr.length == 0) return 0;
        int max = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0, j = 0; i < arr.length; i++) {
            if (map.containsKey(arr[i])) j = Math.max(j, map.get(arr[i]) + 1);
            
            map.put(arr[i], i);
            max = Math.max(max, i-j+1);
        }
        return max;
    }
}

NC65 斐波那契数列

知识点数组

描述

大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。

斐波那契数列是一个满足$$f i b ( x ) = { \begin{array} { l l } { 1 } & { x = 1 , 2 } \ { fib ( x - 1 ) + fib ( x - 2 ) } & { x \gt 2 } \end{array}$$的数列

数据范围：1≤n≤39

要求：空间复杂度 O*(1)，时间复杂度 O(n) ，本题也有时间复杂度 O(logn)的解法

输入描述：

一个正整数n

返回值描述：

输出一个正整数。

示例1

输入：

4

返回值：

3

说明：

根据斐波那契数列的定义可知，fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3，所以答案为4。      

示例2

输入：

1

返回值：

1

示例3

输入：

2

返回值：

1

思路：

• 递归
  • 往前推，遇到1或2才返回
• 循环
  • 循环n-2次，直接交换数据a,b,c

解答：

public class Solution {
    public int Fibonacci(int n) {
//         if (n == 1 || n == 2) return 1;
//         int a = 1, b = 1, c = 0;
//         for (int i = 2; i < n; i++) {
//             c = a+b;
//             a = b;
//             b = c; 
//         }
//         return c;
        // 递归
        if (n == 1 || n == 2) return 1;
        return Fibonacci(n-1)+Fibonacci(n-2);
    }
}

NC22 合并两个有序的数组

描述

给出一个有序的整数数组 A 和有序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个有序的升序数组

数据范围：0≤n,m≤100，|A_i| <=100， |B_i| <= 100

注意：
1.保证 A 数组有足够的空间存放 B 数组的元素， A 和 B 中初始的元素数目分别为 m 和 n，A的数组空间大小为 m+n

2.不要返回合并的数组，将数组 B 的数据合并到 A 里面就好了

\3. A 数组在[0,m-1]的范围也是有序的

示例1

输入：

[4,5,6],[1,2,3]

返回值：

[1,2,3,4,5,6]

说明：

A数组为[4,5,6]，B数组为[1,2,3]，后台程序会预先将A扩容为[4,5,6,0,0,0]，B还是为[1,2,3]，m=3，n=3，传入到函数merge里面，然后请同学完成merge函数，将B的数据合并A里面，最后后台程序输出A数组           

示例2

输入：

[1,2,3],[2,5,6]

返回值：

[1,2,2,3,5,6]

思路：

• 有序，A的数组长度足够
• 双指针，比大小，大的存入一个移动一个，从后往前（后面是空的）
• 最后剩下的数组元素，全部存入A。

解答：

import java.util.*;
public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        while(m > 0 && n > 0) {
            if (A[m-1] <= B[n-1]) {
                A[m+n-1] = B[n-1];
                n--;
            } else {
                A[m+n-1] = A[m-1];
                m--;
            }
        }
        if (n > 0) {
            for (int i = 0; i < n; i++) {
                A[i] = B[i];
            }
        }
    }
}

NC128 接雨水问题

描述

给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。(数组以外的区域高度视为0)

数据范围：0≤n≤106，数组中每个值满足 0<val≤109

要求：空间复杂度 O(1),时间复杂度 O(n)

示例1

输入：

[3,1,2,5,2,4]  

返回值：

5 

说明：

数组 [3,1,2,5,2,4] 表示柱子高度图，在这种情况下，可以接 5个单位的雨水，蓝色的为雨水 ，如题面图。    

示例2

输入：

[4,5,1,3,2]

返回值：

2 

思路：

• 双指针，左右往里靠
• 左右最大值动态更新
• 水面高度由左右两边最小的值决定

解答：

import java.util.*;


public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    public long maxWater (int[] arr) {
        // write code here
        int left = 0, right = arr.length - 1;
        int leftMax = arr[left], rightMax = arr[right];
        long water = 0;
        
        while(left < right) {
            leftMax = Math.max(leftMax, arr[left]);
            rightMax = Math.max(rightMax, arr[right]);
            
            if(leftMax < rightMax) {
                water = water + leftMax - arr[left];
                left++;
            } else {
                water = water + rightMax - arr[right];
                right--;
                
            }
        }
        return water;
    }
}

NC38 螺旋矩阵

描述

给定一个m x n大小的矩阵（m行，n列），按螺旋的顺序返回矩阵中的所有元素。

数据范围：0 \le n,m \le 100≤n,m≤10，矩阵中任意元素都满足 |val| \le 100∣val∣≤100

要求：空间复杂度 O(nm)O(n**m) ，时间复杂度 O(nm)O(n**m)

示例1

输入：

[[1,2,3],[4,5,6],[7,8,9]]

返回值：

[1,2,3,6,9,8,7,4,5]

示例2

输入：

[]

返回值：

[]

NC112 进制转换

描述

给定一个十进制数 M ，以及需要转换的进制数 N 。将十进制数 M 转化为 N 进制数。

当 N 大于 10 以后， 应在结果中使用大写字母表示大于 10 的一位，如 ‘A’ 表示此位为 10 ， ‘B’ 表示此位为 11 。

若 M 为负数，应在结果中保留负号。

数据范围： M <= 10^8 , 2 \le N \le 16M<=108,2≤N≤16

要求：空间复杂度O(M)O(M)，时间复杂度 O(M)O(M)

示例1

输入：

7,2

返回值：

"111"

示例2

输入：

10,16

返回值：

"A"

思路：

• 明确进制转换的思路，取余在反过来

  res.append(s.charAt(M%N));
              M = M/N;

• 新建一个s = “0123456789ABCDEF”，取余对应的进制在s里取

• 符号开始时进行判断，最后加进去

• 最终结果为翻转的，reverse翻转回来。

解答：

import java.util.*;


public class Solution {
    /**
     * 进制转换
     * @param M int整型 给定整数
     * @param N int整型 转换到的进制
     * @return string字符串
     */
    public String solve (int M, int N) {
        // write code here
        String s = "0123456789ABCDEF";
        StringBuffer res= new StringBuffer();
        boolean flag = false;
        if(M < 0) {
            flag = true;
            M = -M;
        }
        while(M != 0) {
            res.append(s.charAt(M%N));
            M = M/N;
        }
        if (flag) res.append("-");
        return res.reverse().toString();
    }
}

NC88 寻找第K大

描述

有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。

给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。

要求：时间复杂度 O(nlogn)O(nlogn)，空间复杂度 O(1)O(1)

数据范围：0\le n \le 10000≤n≤1000， 1 \le K \le n1≤K≤n，数组中每个元素满足 0 \le val \le 100000000≤val≤10000000

示例1

输入：

[1,3,5,2,2],5,3

返回值：

2

示例2

输入：

[10,10,9,9,8,7,5,6,4,3,4,2],12,3

返回值：

9

说明：

去重后的第3大是8，但本题要求包含重复的元素，不用去重，所以输出9 

思路：

• 快排

解答：

import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        quickSort(a, 0, n-1);
        return a[a.length - K];
    }
    
    public void quickSort(int[] a, int left, int right) {
        if (left < right) {
            int point = partition(a, left, right);
            quickSort(a, left, point-1);
            quickSort(a, point+1, right);
        }
        
    }
    
    public int partition(int[] a, int left, int right) {
        int first = a[left];
        while(left < right) {
            while(left < right && a[right] >= first) {
                right--;
            }
            swap(a, left, right);
            while(left < right && a[left] <= first) {
                left++;
            }
            swap(a, left, right);
        }
        return left;
    }
    
    public void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}

NC140 排序

描述

给定一个长度为 n 的数组，请你编写一个函数，返回该数组按升序排序后的结果。

数据范围： 0≤n≤10⁵，数组中每个元素都满足 0≤val≤10⁹

要求：时间复杂度O*(*nlogn)，空间复杂度 O(n)

示例1

输入：

[5,2,3,1,4]

返回值：

[1,2,3,4,5]

示例2

输入：

[5,1,6,2,5]

返回值：

[1,2,5,5,6]

思路：

**快速排序(Quick Sort)**：是对冒泡排序的一种改进方法，在冒泡排序中，进行元素的比较和交换是在相邻元素之间进行的，元素每次交换只能移动一个位置，所以比较次数和移动次数较多，效率相对较低。而在快速排序中，元素的比较和交换是从两端向中间进行的，较大的元素一轮就能够交换到后面的位置，而较小的元素一轮就能交换到前面的位置，元素每次移动的距离较远，所以比较次数和移动次数较少，y速度较快，故称为“快速排序”。
快速排序的基本思想是：

1. 在待排序的元素任取一个元素作为基准(通常选第一个元素，但最的选择方法是从待排序元素中随机选取一个作为基准)，称为基准元素；
2. 将待排序的元素进行分区，比基准元素大的元素放在它的右边，比其小的放在它的左边（在这个过程中，基准元素的位置是会变的）；
3. 基准为最左边的数，则从右边开始比；
4. 对左右两个分区重复以上步骤直到所有元素都是有序的；

解答：

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        quickSort(arr , 0 , arr.length-1);
        return arr;
    }
    public void quickSort(int[] list, int left, int right) {
        if (left < right) {
            // 分割数组，找到分割点
            int point = partition(list, left, right);
            // 递归调用，对左子数组进行快速排序
            quickSort(list, left, point - 1);
            // 递归调用，对右子数组进行快速排序
            quickSort(list, point + 1, right);
        }
    }

    /**
     * 分割数组，找到分割点
     */
    public int partition(int[] list, int left, int right) {
        // 用数组的第一个元素作为基准数
        int first = list[left];
        while (left < right) {
            while (left < right && list[right] >= first) {
                right--;
            }

            // 交换，这个交换会将first值移动到最右边
            swap(list, left, right);

            while (left < right && list[left] <= first) {
                left++;
            }
            
            // 交换，这个交换会将first值移动到最左边
            swap(list, left, right);
        }
        // 返回分割点所在的位置
        return left;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

NC105 二分查找-II

描述

请实现有重复数字的升序数组的二分查找

给定一个 元素有序的（升序）长度为n的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的第一个出现的target，如果目标值存在返回下标，否则返回 -1

数据范围：0 \le n \le 100000\0≤n≤100000

进阶：时间复杂度O(logn)*O*(log**n) ，空间复杂度O(n)*O*(n)

示例1

输入：

[1,2,4,4,5],4

返回值：

2

说明：

从左到右，查找到第1个为4的，下标为2，返回2    

示例2

输入：

[1,2,4,4,5],3

返回值：

-1

示例3

输入：

[1,1,1,1,1],1

返回值：

0

思路：

• 二分法查找
• index存储目标值的位置
• 设置low，high，每次变动low或者high的值
• 找到不着急退出，high-1继续分，看是否有序号更小的数值相同的

解答：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 如果目标值存在返回下标，否则返回 -1
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] nums, int target) {
        // write code here
        int index = -1;
        int low = 0, high = nums.length - 1;
        while(low <= high) {
            int mid = low + (high-low) / 2;
            if(nums[mid] == target) {
                index = mid;
                high = mid - 1;
            } else if(nums[mid] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return index;
    }
}

NC7 买卖股票的最好时机(一)

描述

假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益

1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天

2.如果不能获取到任何利润，请返回0

3.假设买入卖出均无手续费

示例1

输入：

[8,9,2,5,4,7,1]

返回值：

5

说明：

在第3天(股票价格 = 2)的时候买入，在第6天(股票价格 = 7)的时候卖出，最大利润 = 7-2 = 5 ，不能选择在第2天买入，第3天卖出，这样就亏损7了；同时，你也不能在买入前卖出股票。           

思路：

• 在找到最大价格之前找到最小价格

解答：

class Solution {
    public int maxProfit(int[] prices) {
        int pricesMin = prices[0];
        int pricesMax = 0;

        for(int i=0;i<prices.length;i++) {
            //寻找当前股票最便宜的时候
            pricesMin = Math.min(pricesMin, prices[i]);
            //寻找最贵和最便宜相差最大的价格
            pricesMax = Math.max(pricesMax,prices[i]-pricesMin);
        }
        return pricesMax;
    }
}

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

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

示例 2：

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

思路：

• 每次添加一个数据

解答：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// 子集[78]leetcode
// dfs
/*
输入
3
1 2 3

1
0
*/
public class main1 {
    static List<Integer> t = new ArrayList<Integer>();
    static List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public static void main(String[] args) throws Exception {
        System.out.println("solution()");
        solution();
    }

    public static int solution() throws IOException {
        // 取输入
        BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
        String s = buffer.readLine();
        //输入格式大小
        int inputDataForm = Integer.parseInt(s.split(" ")[0]);

        //输入数据
        int[] datas = new int [inputDataForm];
        String tmp = buffer.readLine();
        for (int i = 0; i < inputDataForm; i++) {
            datas[i] = Integer.parseInt(tmp.split(" ")[i]);
        }
//        System.out.println(Arrays.toString(datas));

        dfs(0, datas);
        System.out.println(ans);
        int res = 0;
        return res;
    }

    public static void dfs(int cur, int[] nums) {
        if (cur == nums.length) {
            ans.add(new ArrayList<Integer>(t));
            return;
        }
        t.add(nums[cur]);
        System.out.println(nums[cur]);
        dfs(cur + 1, nums);
        t.remove(t.size() - 1);
        dfs(cur + 1, nums);
    }

}

90. 子集 II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

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

示例 2：

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

思路：

• DFS
• 加一个判断nums[cur-1] == nums[cur]

解答：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

/*
输入
4
1 2 2 3

1
0
*/
public class main2 {
    static List<Integer> t = new ArrayList<Integer>();
    static List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public static void main(String[] args) throws Exception {
        System.out.println("solution()");
        solution();
    }

    public static int solution() throws IOException {
        // 取输入
        BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
        String s = buffer.readLine();
        //输入格式大小
        int inputDataForm = Integer.parseInt(s.split(" ")[0]);

        //输入数据
        int[] datas = new int [inputDataForm];
        String tmp = buffer.readLine();
        for (int i = 0; i < inputDataForm; i++) {
            datas[i] = Integer.parseInt(tmp.split(" ")[i]);
        }

        dfs(false,0, datas);
        System.out.println(ans);
        int res = 0;
        return res;
    }

    public static void dfs(boolean choosePre,int cur, int[] nums) {
        if (cur == nums.length) {
            ans.add(new ArrayList<Integer>(t));
            return;
        }
        dfs(false, cur+1, nums);
        // cur > 0是为了防止nums[cur-1]数组溢出
        if (!choosePre && cur > 0 && nums[cur-1] == nums[cur]) {
            return;
        }
        t.add(nums[cur]);
        dfs(true,cur+1, nums);
        t.remove(t.size()-1);
    }

}

快排

• 时间复杂度O(logn)

package test;

import com.sun.org.apache.xalan.internal.xsltc.util.IntegerArray;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

/*
6
3 4 1 2 9 7
*/
public class quickSortTest {
    public static void main(String[] args) throws IOException {
        BufferedReader buff = new BufferedReader(new InputStreamReader(System.in));
        String s = buff.readLine();
        int len = Integer.parseInt(s.split(" ")[0]);
        int[] datas =  new int[len];
        s = buff.readLine();
        for (int i = 0; i < len; i++) {
            datas[i] = Integer.parseInt(s.split(" ")[i]);
        }
        System.out.println(Arrays.toString(datas));

        quickSort(datas, 0, len - 1);
        System.out.println(Arrays.toString(datas));

    }

    private static void quickSort(int[] datas, int left, int right) {
        if (left >= right ) {
            return;
        }
        // 选出哨兵元素和基准元素。
        int i = left, j = right, base = datas[left];
        while (i < j) {
            //右边哨兵从后向前找
            while ( i < j && datas[j] >= base) {
                j --;
            }
            //左边哨兵从前向后找
            while (i < j && datas[i] <= base) {
                i ++;
            }
            swap(datas, i, j);
        }
        //基准元素与右哨兵交换
        swap(datas, left, j);
        // 递归调用，排序左子集合和右子集合
        quickSort(datas, left, j -1);
        quickSort(datas, j + 1, right);
    }

    private static void swap(int[] datas, int left, int right) {
        int tmp = datas[left];
        datas[left] = datas[right];
        datas[right] = tmp;
    }
}

堆排

dfs

17. 电话号码的字母组合

难度中等1787

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

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

示例 1：

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

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

解答：

package test;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
/*
leetcode17 电话号码的组合
2
2 3
* */

public class DFS1 {
    private static int len;
    private static String[] map = {"","", "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    public static void main(String[] args) throws IOException {
        BufferedReader buff = new BufferedReader(new InputStreamReader(System.in));
        String s = buff.readLine();
        len = Integer.parseInt(s.split(" ")[0]);
        s = buff.readLine();
        int[] nums = new int[len];
        for (int i = 0; i < len; i++) {
            nums[i] = Integer.parseInt(s.split(" ")[i]);
        }

        System.out.println(Arrays.toString(nums));

        ArrayList<String> res = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        dfs(nums, sb, 0,res);


        System.out.println(res);
    }

    private static void dfs(int[] nums, StringBuilder sb, int index, ArrayList<String> res) {
        //截止条件。长度达到则添加进去元素
        if (index == len) {
            res.add(sb.toString());
            return;
        }
        char[] tmps = map[nums[index]].toCharArray();
        // 候选节点。添加StringBuilder的元素
        for (char tmp : tmps) {
            sb.append(tmp);
            dfs(nums, sb, index+1, res);
            sb.deleteCharAt(sb.length() - 1);
        }
    }


}

39. 组合总和

难度中等1839

给你一个 无重复元素 的整数数组 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 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

解答：

package test;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
/*
leetcode39 组合总和
4 7
2 3 6 7
* */

public class DFS2 {
    public static void main(String[] args) throws IOException {
        BufferedReader buff = new BufferedReader(new InputStreamReader(System.in));
        String s = buff.readLine();
        int len = Integer.parseInt(s.split(" ")[0]);
        int target = Integer.parseInt(s.split(" ")[1]);

        s = buff.readLine();
        int[] nums = new int[len];
        for (int i = 0; i < len; i++) {
            nums[i] = Integer.parseInt(s.split(" ")[i]);
        }

        System.out.println(Arrays.toString(nums));

        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        ArrayList<Integer> chain = new ArrayList<>();

        dfs(nums, chain, target, res);

        System.out.println(res);
    }

    private static void dfs(int[] nums, ArrayList<Integer> chain, int target, ArrayList<ArrayList<Integer>> res) {
        int s = sum(chain);
        if( s >= target) {
            if (s == target) {
                // 引用类型new一个否则后面的值可能改变。
                // 排序判断是否重复的
                ArrayList<Integer> tmp = new ArrayList<>(chain);
                Collections.sort(tmp);
                if (!res.contains(tmp)) {
                    res.add(tmp);
                }
            }
            return;
        }

        for (int num : nums) {
            chain.add(num);
            dfs(nums, chain, target, res);
            chain.remove(chain.size() - 1);
        }
    }

    private static int sum(ArrayList<Integer> chain) {
        int sum = 0;
        for (int num : chain) {
            sum += num;
        }
        return sum;
    }


}

46. 全排列

难度中等1860

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

示例 1：

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

示例 2：

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

示例 3：

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

解答：

package test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
/*
leetcode46 全排列
3
1 2 3
* */

public class DFS3 {
    public static void main(String[] args) throws IOException {
        BufferedReader buff = new BufferedReader(new InputStreamReader(System.in));
        String s = buff.readLine();
        int len = Integer.parseInt(s.split(" ")[0]);

        s = buff.readLine();
        int[] nums = new int[len];
        for (int i = 0; i < len; i++) {
            nums[i] = Integer.parseInt(s.split(" ")[i]);
        }

        // 标记哪个数字没使用
        boolean[] used = new boolean[nums.length];
        System.out.println(Arrays.toString(nums));

        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        ArrayList<Integer> chain = new ArrayList<>();
        dfs(nums, used, chain, 0, res);

        System.out.println(res);
    }

    private static void dfs(int[] nums, boolean[] used, ArrayList<Integer> chain, int index, ArrayList<ArrayList<Integer>> res) {
        // 截止条件
        if (index == nums.length) {
            res.add(new ArrayList<>(chain));
            return;
        }
        
        // 候选节点
        for (int i = 0; i < nums.length; i++) {
            if(!used[i]) {
                chain.add(nums[i]);
                used[i] = true;
                dfs(nums, used, chain, index + 1, res);
                chain.remove(chain.size() - 1);
                used[i] = false;
            }
        }
    }
}

47. 全排列 II

难度中等978

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,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]]

解题：

package test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
/*
leetcode47 全排列II
3
1 1 2
* */

public class DFS4 {
    public static void main(String[] args) throws IOException {
        BufferedReader buff = new BufferedReader(new InputStreamReader(System.in));
        String s = buff.readLine();
        int len = Integer.parseInt(s.split(" ")[0]);

        s = buff.readLine();
        int[] nums = new int[len];
        for (int i = 0; i < len; i++) {
            nums[i] = Integer.parseInt(s.split(" ")[i]);
        }

        // 标记哪个数字没使用
        boolean[] used = new boolean[nums.length];
        System.out.println(Arrays.toString(nums));

        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        ArrayList<Integer> chain = new ArrayList<>();
        dfs(nums, used, chain, 0, res);

        System.out.println(res);
    }

    private static void dfs(int[] nums, boolean[] used, ArrayList<Integer> chain, int index, ArrayList<ArrayList<Integer>> res) {
        // 截止条件
        if (index == nums.length) {
            ArrayList<Integer> tmp = new ArrayList<>(chain);
            if (!res.contains(tmp)) {
                res.add(new ArrayList<>(chain));
            }
            return;
        }

        // 候选节点
        for (int i = 0; i < nums.length; i++) {
            if(!used[i]) {
                chain.add(nums[i]);
                used[i] = true;
                dfs(nums, used, chain, index + 1, res);
                chain.remove(chain.size() - 1);
                used[i] = false;
            }
        }
    }
}

二叉树前中后序遍历