Leetcode

Algorithms are used in every part of computer science. They form the field's backbone. In computer science, an algorithm gives the computer a specific set of instructions, which allows the computer to do everything, be it running a calculator or running a rocket.

异或运算

特点：

1. 与自己异或等于0，与0异或等于自己
2. 遵循交换律和结合律

例：

1//1.两数交换：
2arr[i] = arr[i] ^ arr[j]; // a = a ^ b
3arr[j] = arr[i] ^ arr[j]; // b = (a ^ b) ^ b = a
4arr[i] = arr[i] ^ arr[j]; // a = (a ^ b) ^ a = b

 1//2.数组中有一个出现奇数次的数
 2int eor = 0;
 3for(int cur : arr){
 4    eor ^= cur; //[a,a,b,b,c,c,c]  => a^a^b^b^c^c^c = c
 5}
 6System.out.println(eor);
 7
 8//3.数组中有两个出现奇数次的数
 9int eor = 0;
10for(int cur : arr){
11    eor ^= cur; //[a,a,b,b,b,c,c,c]  => a^a^b^b^b^c^c^c = b^c
12}
13//eor = b ^ c
14//eor != 0
15//eor必然有个一位置上是1, 说明这个位置上b和c不同
16int rightOne = eor & (~eor + 1);  //（取反 + 1） & 自己 = 提取出只保留最右侧的1
17
18int result1 = 0;
19for(int cur : arr){
20    if((cur & rightOne) == 0){ //已知在rightOne这个位置上b和c不同，通过(& rightOne)把b和c区分开,别的数是偶数个，异或起来是0不同管
21        result1 ^= cur; //这样result1是b或者c
22    }
23}
24int result2 = eor ^ result1;

排序

冒泡排序

选择排序

插入排序

• 

• 概念： 将后部分的数据(从第二开始)按照一定的顺序一个一个的插入到前部分有序的表中

• 时间复杂度：O(N^2)

• 额外空间复杂度：O(1)

数据状况不同，时间复杂度不同:

• 时间复杂度是按照最差情况考虑

 1public static void insertionSort(int[] arr) {
 2    if (arr == null || arr.length < 2){
 3        return;
 4    }
 5    for (int i = 1; i < arr.length; i++){
 6        for(int j = i - 1; j >= 0 && arr[j] > arr[j+1]; j--){
 7            swap(arr, j, j+1);
 8        }
 9    }
10}
11public static void swap(int[] arr, int i, int j){
12    arr[i] = arr[i] ^ arr[j]; 
13	arr[j] = arr[i] ^ arr[j]; 
14	arr[i] = arr[i] ^ arr[j];
15}

递归

 1public static int getMax(int[] arr){
 2    return process(arr, 0, arr.length - 1);
 3}
 4
 5public static int process(int[] arr, int L, int R){
 6    if(L == R){
 7        return arr[L];
 8    }
 9    int mid = L + ((R - L) >> 1);
10    int leftMax = process(arr, L, mid);
11    int rightMax = process(arr, mid + 1, R);
12    return Math.max(leftMax, rightMax);
13}

递归时间复杂度估算

• Master公式： T(N) = a * T (N / b) + 0 (N ^ d)
  1. log(b, a) > d, 则复杂度为O(N ^ log(b, a))
  2. log(b, a) = d, 则复杂度为O(N ^ d * logN)
  3. log(b, a) < d, 则复杂度为O(N ^ d)

归并排序

• 

• 概念：将n个元素分成个含n/2个元素的子序列，用合并排序法对两个子序列递归的排序，合并两个已排序的子序列已得到排序结果。
• 时间复杂度：使用Master公式： T(N) = NlogN
• 代码实现：

 1public static void process(int[] arr, int L, int R){
 2    if(L == R){
 3        return;
 4    }
 5    int mid = L + ((R - L) >> 1);
 6    process(arr, L, mid);
 7    process(arr, mid + 1, R);
 8    merge(arr, L, mid, R);
 9}
10
11public static void merge(int[] arr, int L, int M, int R){
12    int[] extra = new int[R - L + 1];
13    int i = 0;
14    int p1 = L;
15    int p2 = M + 1;
16    while(p1 <= M && p2 <= R){
17        extra[i++] = arr[p1] <= arr[p2] ? arr[p1++]: arr[p2++];
18    }
19    while(p1 <= M){
20        extra[i++] = arr[p1++];
21    }
22    while(p2 <= R){
23        extra[i++] = arr[p2++];
24    }
25    for(i = 0; i < extra.length; i++){
26        arr[L + i] = extra[i];
27    }
28}

小和问题、逆序对问题

[1, 3, 4, 2, 5] 的小和是 0 + 1 + 4 + 1 +10 = 16（ 在一个数组中,每一个数左边比当前数小的数累加起来,叫做这个数组的小和。）

归并排序思路，目的就是减少对比次数。增加一个外部空间，记录在一次merge中的小和。

 1public static int process(int[] arr, int l, int r){
 2if (l == r){
 3  return 0;
 4}
 5int mid = 1 + ((r - l) >> 1);
 6return process(arr, 1 , mid) 
 7        + process(arr, mid + 1 , r)
 8        + merge(arr, 1 , mid, r);    
 9}
10
11public static void merge(int[] arr, int L, int mid, int R){
12    int[] extr = new int[R - L + 1];
13    int i = 0;
14    int p1 = L;1
15    int p2 = M + 1;
16    int res = 0;
17    while(p1 <= M && p2 <= R){
18        res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0
19        extr[i++] = arr[p1] < arr[p2] ? arr[p1++]: arr[p2++];
20    }
21    while(p1 <= M){
22        extr[i++] = arr[p1++];
23    }
24    while(p2 <= R){
25        extr[i++] = arr[p2++];
26    }
27    for(i = 0; i < extra.length; i++){
28        arr[L + i] = extra[i];
29    }
30    return res;
31}

快速排序

时间复杂度：O(NlogN)，因为有随机概率行为，所以时间复杂度为期望值。

空间复杂度：O(logN)

荷兰国旗问题

问题1：给一个 arr 和 num，要求把小于等num的数放左，大于num放右，时间复杂度为O(N)，空间为O(1)

问题2：给一个 arr 和 num，要求把小于等num的数放左，等于放中间，大于num放右，时间复杂度为O(N)，空间为O(1)

 1public static void quickSort(int[] arr, int L, int R){
 2    if(L < R){
 3        swap(arr, L + (int)(Math.random() * (R - L + 1)), R);//随机选一个数和最后位置交换
 4        int[] p = partition(arr, L, R);//=区域的左右边界
 5        quickSort(arr, L, p[0] - 1);
 6        quickSort(arr, p[1] + 1, R);
 7    }
 8}
 9public static int[] partition(int[] arr, int L, int R){
10    int less = L - 1;// <区域的右边界
11    int more = R; //>区的左边界
12    while(L < more){ // L表示当前数的位置
13        if(arr[L] < arr[R]){
14            swap(arr, ++less, L++);
15        }else if(arr[L] > arr[R]){
16            swap(arr, --more, L);
17        }else{
18            L++;
19        }
20    }
21    swap(arr, more, R);
22    return new int[]{ less + 1, more };
23}
24
25private static void swap(int[] arr, int i, int j) {
26    if(i != j){
27        arr[i] = arr[i] ^ arr[j];
28        arr[j] = arr[i] ^ arr[j];
29        arr[i] = arr[i] ^ arr[j];
30    }
31}

堆排序

时间复杂度：O(NlogN)

大根堆：在完全二叉树（最后一层的结点都连续集中在最左边，其余层满节点）的前提下，每一棵子树的最大值是头结点的数。

小根堆：在完全二叉树（最后一层的结点都连续集中在最左边，其余层满节点）的前提下，每一棵子树的最小值是头结点的数。

优先级队列结构，就是堆结构

1//处在index位置上的数，往上继续移动
2public static void heapInsert(int[] arr, int index){
3	while(arr[index] > arr[(index - 1) / 2]) {
4		swap(arr, index, (index - 1) / 2);
5		index = (index - 1) / 2;
6	}
7}

返回最大值（arr[0]上的数），并删除最大值：

1. 返回根节点。
2. 把 arr[heapSize] 的数放到根节点。
3. heapSize--，最后一个节点即与堆断连。
4. while 循环，与子节点比较，小则替换，直到满足大根堆。

 1// 处在index位置上的数，往下继续移动
 2public static void heapify(int[] arr, int index, int heapSize){
 3    int left = index * 2 + 1; //节点左孩子下标
 4    while(left < heapSize){ //判断下方是否有孩子
 5        //两个孩子中，谁的值大，把下标给最大的
 6        int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
 7        //节点与孩子比较，谁的值大，把下标给最大的
 8        largest = arr[largest] > arr[index] ? largest : index;
 9        if(largest == index){
10            break;
11        }
12        swap(arr, largest, index);
13        index = largest;
14        left = index * 2 + 1;
15    }
16}

HeapSort

 1public static void heapSort(int[] arr){
 2    if(arr == null || arr.length < 2){
 3        return;
 4    }
 5    for(int i = 0; i < arr.length; i++){
 6        heapInsert(arr, i);//数组整体范围变成大根堆
 7    }
 8    int heapSize = arr.length;
 9    swap(arr, 0, --heapSize);//大根堆的root(最大值)放到arr最后
10    while(heapSize > 0){
11        heapify(arr, 0, heapSize);
12        swap(arr, 0, --heapSize);
13    }
14}

一个数组如果把它排好序的话，每个元素移动的距离不超过k，k相对于数组长度比较小，选择一个合适的排序算法排序

• 方法：

  最小堆排方法，先取出前k个数字组成最小堆，根位置为0位置上的数；添加一个数，堆化，根位置为第二个位置上的数。以此类推

  1PriorityQueue<Integer> heap = new PriorityQueue<>();//优先级队列结构，就是堆结构
  

  扩容方式：双倍扩容

   1public void sortedArrDistanceLessK(int[] arr, int k){
   2    PriorityQueue<Integer> heap = new PriorityQueue<>();//默认小根堆
   3    int index = 0;
   4    for(; index <= Math.min(arr.length, k); index++){//生成前k个数的最小堆
   5        heap.add(arr[index]);
   6    }
   7    int i = 0;
   8    for(;index < arr.length; i++, index++){//弹一个，放入一个
   9        heap.add(arr[index]);
  10        arr[i] = heap.poll();
  11    }
  12    while(!heap.isEmpty()){
  13        arr[i++] = heap.poll();
  14    }
  15}
  

桶排序

计数排序：

基数排序：

 1public static void radixSort(int[] arr, int L, int R, int digit){//digit: 最大数的位数
 2final int radix = 10;
 3int i = 0, j = 0;
 4int[] bucket = new int[R - L + 1];//有多少个数准备多少个辅助空间
 5for(int d = 1; d <= digit; d++){//最大位数有多少位就进出桶多少次
 6int[] count = new int[radix]; //count[0..9]
 7//count[0] 当前(d)位是0的数字有多少个
 8//count[1] 当前(d)位小于等于1的数字有多少个
 9//count[2] 当前(d)位小于等于2的数字有多少个
10//count[i] 当前(d)位小于等于i的数字有多少个
11for(i = L; i <= R; i++){
12   count[getDigit(arr[i], d)]++;//先统计每个数字(num)出现了几次(times)，先记录在count[num] = times
13}
14for(i = 1; i < radix; i++){
15   count[i] = count[i] + count[i - 1];//再统计小于等于出现的次数
16}
17for(i = R; i >= L; i--){//从右向左
18   j = getDigit(arr[i], d);
19   bucket[count[j] - 1] = arr[i];
20}
21for(i = L, j = 0; i <= R; i++, j++){
22   arr[i] = bucket[j];//将桶中数据倒回数组
23}
24}
25}

小结

• 一般优先选择 快速排序，快排的复杂度在常数项是最低的。
• 对空间有要求选择 堆排序。
• 对稳定性有要求选择 归并排序。

Leetcode 题解 - 排序

快速选择

用于求解 Kth Element 问题，也就是第 K 个元素的问题。

可以使用快速排序的 partition() 进行实现。需要先打乱数组，否则最坏情况下时间复杂度为 O(N2)。

堆

用于求解 TopK Elements 问题，也就是 K 个最小元素的问题。使用最小堆来实现 Top 问题，最小堆使用大顶堆来实现，大顶堆的堆顶元素为当前的最大元素。

实现过程：不断地往大顶堆中插入新元素，当堆中元素的数量大于 k 时，移除堆顶元素，也就是当前堆中最大的元素，剩下的元素都为当前添加过的元素中最小的K个元素。插入和移除堆顶元素的时间复杂度都为 log₂N

快速选择也可以求解 TopK Elements 问题，因为找到了 Kth Element 之后，所有小于等于 Kth Element 的元素都是 TopK Elements。

快速选择和堆排序都可以求解 Kth Element 和 TopK Elements 问题。

题目一：Kth Element Kth Largest Element in an Array (Medium)

1Input: [3,2,1,5,6,4] and k = 2
2Output: 5

题目描述：找到倒数第 k 个的元素。

解题：

方法一：排序：时间复杂度 O(NlogN)，空间复杂度 O(1)

sort() 方法：元素少于NSERTION_SORT_THRESHOLD⽤插⼊排序，大于NSERTION_SORT_THRESHOLD，使用快排。

1public int findKthLargest(int[] nums, int k) {
2    Arrays.sort(nums); 
3    return nums[nums.length - k];
4}

方法二：堆：时间复杂度 O(NlogK)，空间复杂度 O(K)。

1public int findKthLargest(int[] nums, int k) {
2    PriorityQueue<Integer> pq = new PriorityQueue<>(); //小项堆
3    for(int val : nums){
4        pq.add(val);
5        if(pq.size() > k)
6            pq.poll(); //维护堆的大小为K，弹出最小项，留下的 k 项为数组中最大的。
7    }
8    return pq.peek();
9}

方法三：快速选择 ：时间复杂度 O(N)，空间复杂度 O(1)

 1public int findKthLargest(int[] nums, int k) {
 2    k = nums.length - k;
 3    int l = 0, h = nums.length - 1;
 4    while (l < h) {
 5        int j = partition(nums, l, h);
 6        if (j == k) {
 7            break;
 8        } else if (j < k) {
 9            l = j + 1;
10        } else {
11            h = j - 1;
12        }
13    }
14    return nums[k];
15}
16
17private int partition(int[] a, int l, int h) {
18    int i = l, j = h + 1;
19    while (true) {
20        while (a[++i] < a[l] && i < h) ;
21        while (a[--j] > a[l] && j > l) ;
22        if (i >= j) {
23            break;
24        }
25        swap(a, i, j);
26    }
27    swap(a, l, j);
28    return j;
29}
30
31private void swap(int[] a, int i, int j) {
32    int t = a[i];
33    a[i] = a[j];
34    a[j] = t;
35}

桶排序

题目二：出现频率最多的 k 个元素 Top K Frequent Elements (Medium)

1Given [1,1,1,2,2,3] and k = 2, return [1,2].

解题：

设置若干个桶，每个桶存储出现频率相同的数。桶的下标表示数出现的频率，即第 i 个桶中存储的数出现的频率为 i。

把数都放到桶之后，从后向前遍历桶，最先得到的 k 个数就是出现频率最多的的 k 个数。

 1public int[] topKFrequent(int[] nums, int k) {
 2    Map<Integer, Integer> frequencyForNum = new HashMap<>();
 3    for(int num : nums){
 4        frequencyForNum.put(num, frequencyForNum.getOrDefault(num, 0) + 1);
 5    }
 6    List<Integer>[] buckets = new ArrayList[nums.length + 1];
 7    for(int key : frequencyForNum.keySet()){
 8        int frequency = frequencyForNum.get(key);
 9        if (buckets[frequency] == null){
10            buckets[frequency] = new ArrayList<>();
11        }
12        buckets[frequency].add(key);
13    }
14    List<Integer> topK = new ArrayList<>();//res
15    for(int i = buckets.length - 1; i >= 0 && topK.size() < k; i--){
16        if(buckets[i] == null){
17            continue;
18        }
19        if(buckets[i].size() <= (k - topK.size())){
20            topK.addAll(buckets[i]);
21        }else{
22            topK.addAll(buckets[i].subList(0, k - topK.size()));
23        }
24    }
25    int[] res = new int[k];
26	for (int i = 0; i < k; i++) {
27        res[i] = topK.get(i);
28    }
29    return res;
30}

题目三：按照字符出现次数对字符串排序 Sort Characters By Frequency (Medium)

1Input:
2"tree"
3
4Output:
5"eert"
6
7Explanation:
8'e' appears twice while 'r' and 't' both appear once.
9So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

解题：

 1public String frequencySort(String s) {
 2    Map<Character, Integer> frequencyForNum = new HashMap<>();
 3    for (char c : s.toCharArray())
 4        frequencyForNum.put(c, frequencyForNum.getOrDefault(c, 0) + 1);
 5
 6    List<Character>[] frequencyBucket = new ArrayList[s.length() + 1];
 7    for (char c : frequencyForNum.keySet()) {
 8        int f = frequencyForNum.get(c);
 9        if (frequencyBucket[f] == null) {
10            frequencyBucket[f] = new ArrayList<>();
11        }
12        frequencyBucket[f].add(c);
13    }
14    StringBuilder str = new StringBuilder();
15    for (int i = frequencyBucket.length - 1; i >= 0; i--) {
16        if (frequencyBucket[i] == null) {
17            continue;
18        }
19        for (char c : frequencyBucket[i]) {
20            for (int j = 0; j < i; j++) {
21                str.append(c);
22            }
23        }
24    }
25    return str.toString();
26}

荷兰国旗问题：快排 partition

1Input: [2,0,2,1,1,0]
2Output: [0,0,1,1,2,2]

解题：

 1public void sortColors(int[] nums) {
 2    int zero = -1, one = 0, two = nums.length;
 3    while (one < two) {
 4        if (nums[one] == 0) {
 5            swap(nums, ++zero, one++);
 6        } else if (nums[one] == 2) {
 7            swap(nums, --two, one);
 8        } else {
 9            ++one;
10        }
11    }
12}
13
14private void swap(int[] nums, int i, int j) {
15    int t = nums[i];
16    nums[i] = nums[j];
17    nums[j] = t;
18}

Leetcode 题解 - 二分查找

• 时间复杂度：O(logN) (logN默认指log以2为底)

求中间数

1mid = (L + R) / 2 			// L + R 可能会越界65535，这时mid算出负数
2mid = L + (R - L) / 2		//不会越界
3mid = L + (R - L) >> 1		//右移一位比除2快

binarySearch

 1public int binarySearch(int[] nums, int key) {
 2    int l = 0, h = nums.length;
 3    while (l < h) {
 4        //int m = l + (h - l) / 2;
 5        int m = l + (h - l) > 2;
 6        if (nums[m] >= key) {
 7            h = m;
 8        } else {
 9            l = m + 1;
10        }
11    }
12    return l;
13}

题目一：求开方 Sqrt(x) (Easy)

1Input: 4
2Output: 2
3
4Input: 8
5Output: 2
6Explanation: The square root of 8 is 2.82842..., and since we want to return an integer, the decimal part will be truncated.

解题：

一个数 x 的开方 sqrt 一定在 0 ~ x 之间，并且满足 sqrt == x / sqrt。可以利用二分查找在 0 ~ x 之间查找 sqrt。

对于 x = 8，它的开方是 2.82842...，最后应该返回 2 而不是 3。在循环条件为 l <= h 并且循环退出时，h 总是比 l 小 1，也就是说 h = 2，l = 3，因此最后的返回值应该为 h 而不是 l。

 1public int mySqrt(int x){
 2    if(x <= 1){
 3        return x;
 4    }
 5    int l = 1, h = x;
 6    while(l <= h){
 7        int mid = l + (h - l) >> 2;
 8        int sqrt = x / mid;
 9        if (sqrt == mid){
10            return mid;
11        } else if (mid > sqrt){
12            h = mid - 1;
13        } else {
14            l = mid + 1;
15        }
16    }
17    return h;
18}

题目二：大于给定元素的最小元素 Find Smallest Letter Greater Than Target (Easy)

1Input:
2letters = ["c", "f", "j"]
3target = "d"
4Output: "f"
5
6Input:
7letters = ["c", "f", "j"]
8target = "k"
9Output: "c"

解题：

 1public char nextGreatestLetter(char[] letters, char target) {
 2    int n = letters.length;
 3    int l = 0, h = n - 1;
 4    while (l <= h) {
 5        int m = l + (h - l) / 2;
 6        if (letters[m] <= target) {
 7            l = m + 1;
 8        } else {
 9            h = m - 1;
10        }
11    }
12    return l < n ? letters[l] : letters[0];
13}

题目三：有序数组的 Single Element in a Sorted Array (Medium)

1Input: [1, 1, 2, 3, 3, 4, 4, 8, 8]
2Output: 2

题目描述：一个有序数组只有一个数不出现两次，找出这个数。要求以 O(logN) 时间复杂度求解，因此不能遍历数组并进行异或操作来求解，这么做的时间复杂度为O(N)

解题：

令 index 为 Single Element 在数组中的位置。在 index 之后，数组中原来存在的成对状态被改变。如果 m 为偶数，并且 m + 1 < index，那么 nums[m] == nums[m + 1]；m + 1 >= index，那么 nums[m] != nums[m + 1]。

 1public int singleNonDuplicate(int[] nums) {
 2    int l = 0, h = nums.length - 1;
 3    while (l < h) {
 4        int m = l + (h - l) / 2;
 5        if (m % 2 == 1) {
 6            m--;   // 保证 l/h/m 都在偶数位，使得查找区间大小一直都是奇数
 7        }
 8        if (nums[m] == nums[m + 1]) {
 9            l = m + 2;
10        } else {
11            h = m;
12        }
13    }
14    return nums[l];
15}

题目：找一个局部最小（i-1 < i < i+1）的数，复杂度小于 O(N)

例题：

1. 在一个有序数组中，找某个数是否存在

2. 在一个有序数组中，找 >= 某个数最左侧的位置：二分查找直到左侧没有数

3. 无序，相邻数一定不相等，找一个局部最小(i-1 < i < i+1)的数，复杂度能否好于O(N)

   1先判断首尾项是否满足要求，若首尾项不满足要求，一定是\进/出，中间一定有低谷拐点。
   2然后判断中间点是否满足要求，若不满足，分为两种情况：
   31. 斜坡，则一方可与起点或终点组成\进/出。
   42. 顶峰，则两方向都满足\进/出条件，两个方向都可继续进行二分法
   5直到判断出某个二分法中点满足要求。
   

Leetcode 题解 - 哈希表 - 有序表

哈希表介绍

1. 哈希表使用层面上可以理解为一种集合结构。
2. 有无伴随数据，是HashMap和HashSet唯一的区别，底层的数据结构一样。
3. 使用哈希表 put，remove，put，get 的操作，可以认为时间复杂度为O(1)，但常数时间比较大。

哈希表使用 O(N) 空间复杂度存储数据，并且以 O(1) 时间复杂度求解问题。

Java 中的 HashSet 用于存储一个集合，可以查找元素是否在集合中。如果元素有穷，并且范围不大，那么可以用一个布尔数组来存储一个元素是否存在。例如对于只有小写字符的元素，就可以用一个长度为 26 的布尔数组来存储一个字符集合，使得空间复杂度降低为 O(1)。

Java 中的 HashMap 主要用于映射关系，从而把两个元素联系起来。HashMap 也可以用来对元素进行计数统计。在对一个内容进行压缩或者其他转换时，利用 HashMap 可以把原始内容和转换后的内容联系起来。例如在一个简化 url 的系统中。

利用 HashMap 就可以存储精简后的 url 到原始 url 的映射，使得不仅可以显示简化的 url，也可以根据简化的 url 得到原始 url 从而定位到正确的资源。

有序表介绍

1. 有序表在使用层面上可以理解为一种集合结构。
2. 有无伴随数据，是TreeSet和TreeMap唯一的区别，底层的数据结构一样。
3. 有序表和哈希表的区别是，有序表把key按照顺序组织起来，而哈希表完全不组织。
4. 红黑树、AVL树、size-balance-tree和跳表都属于有序表结构，只是底层具体实现不同。

1. 数组中两个数的和为给定值 Two Sum (Easy)

解题：

可以先对数组进行排序，然后使用双指针方法或者二分查找方法。这样做的时间复杂度为 O(NlogN)，空间复杂度为O(1)。

用 HashMap 存储数组元素和索引的映射，在访问到 nums[i] 时，判断 HashMap 中是否存在 target - nums[i]，如果存在说明 target - nums[i] 所在的索引和 i 就是要找的两个数。该方法的时间复杂度为 O(N)，空间复杂度为O(N)，使用空间来换取时间。

 1public int[] twoSum(int[] nums, int target){
 2    HashMap<Intger, Intger> indexForNum = new HashMap<>();
 3    for(int i = 0; i < nums.length; i++){
 4        if(indexForNum.containsKey(target - nums[i])){
 5            return new int[]{indexForNum.get(target - nums[i]), i};
 6        } else {
 7            indexForNum.put(nums[i], i);
 8        }
 9    }
10    return null;
11}

2. 判断数组是否含有重复元素 Contains Duplicate (Easy)

1public boolean containsDuplicate(int[] nums){
2    Set<Integer> set = new HashSet<>();
3    for (int num : nums){
4        set.add(num);
5    }
6    return set.size() < nums.length;
7}

3. 最长和谐序列 Longest Harmonious Subsequence (Easy)

和谐序列中最大数和最小数之差正好为 1，应该注意的是序列的元素不一定是数组的连续元素。

1Input: [1,3,2,2,5,2,3,7]
2Output: 5
3Explanation: The longest harmonious subsequence is [3,2,2,2,3].

 1public int findLHS(int[] nums){
 2    Map<Integer, Integer> countForNum = new HashMap<>();
 3    for(int num : nums){
 4        countForNum.put(num, countForNum.getOrDefault(nums, 0) + 1);
 5    }
 6    int longest = 0;
 7    for(int num : countForNum.keySet()){
 8        if(countForNum.containsKey(num + 1)){
 9            longest = Math.max(longest, countForNum.get(num + 1) + countForNum.get(num));
10        }
11    }
12    return longest;
13}

4. 最长连续序列 Longest Consecutive Sequence (Hard)

链表

• 笔试 面试区分，面试时需考虑空间复杂度。

题目一：判断一个链表是否回文

方法一：笔试用：进栈出栈

 1public static boolean isPalindrome1(Node head) {
 2Stack<Node> stack = new Stack<Node>();
 3Node cur = head;
 4while (cur != null) {
 5  stack.push(cur);
 6  cur = cur.next;
 7}
 8while (head != null) {
 9  if (head.value != stack.pop().value) {
10      return false;
11  }
12  head = head.next;
13}
14return true;
15}

方法2：快慢指针：空间复杂度O(1)，使用了有限几个变量

 1public static boolean isPalindrome3(Node head) {
 2if (head == null || head.next == null) {
 3  return true;
 4}
 5Node n1 = head;
 6Node n2 = head;
 7while (n2.next != null && n2.next.next != null) {
 8  n1 = n1.next; //n1 -> mid
 9  n2 = n1.next.next; //n2 -> end
10}
11n2 = n1.next; //n2 -> right part first node
12Node n3 = null;
13while (n2 != null) { //right part convert
14  n3 = n2.next; // save next node
15  n2.next = n1; // right direct to left direct
16  n1 = n2;
17  n2 = n3;
18}
19n3 = n1; // last node
20n2 = head; // fist node
21boolean res = true;
22while (n1 != null && n2 != null) {
23  if (n1.value != n2.value) {
24      res = false;
25      break;
26  }
27  n1 = n1.next;
28  n2 = n2.next;
29}
30n1 = n3.next; // recover list
31n3.next = null;
32while (n1 != null) {
33  n2 = n1.next;
34  n1.next = n3;
35  n3 = n1;
36  n1 = n2;
37}
38return res;
39}

题目二：单链表按某值划分成左边小，中间相等，右边大

方法一：（笔试）放到数组里，在数组里partition

方法二：（面试）创建6个空节点，每两个一组，作为三个区域的首尾节点。遍历原链表，放到不同的区域并调整各组首尾节点，最后三个拼装。

题目三：复制含有随机指针节点的链表

1class Node {
2int value;
3Node next;
4Node rand;
5
6Node(int val) {
7  value = val;
8}
9}

方法一：hashmap

 1public static Node copyListWithRand1(Node head) {
 2HashMap<Node, Node> map = new HashMap<Node, Node>();
 3Node cur = head;
 4while (cur != null) {
 5  map.put(cur, new Node(cur.value));
 6  cur = cur.next;
 7}
 8cur = head;
 9while (cur != null) {
10  map.get(cur).next = map.get(cur.next);
11  map.get(cur).rand = map.get(cur.rand);
12  cur = cur.next;
13}
14return map.get(head);
15}

方法二：利用位置关系省去哈希表。

1. 当前节点的下一个就放克隆节点。

2. 1curCopy = cur.next;
   2curCopy.rand = cur.rand != null ? cur.rand.next:null;
   

3. 跳过旧链表。

题目四：两个单链表相交的一系列问题

先判断有无环：

方法一：Hashset。get一个，看之前是否加入过，否则put进set。

方法二：快慢指针。不会走到空节点，快慢指针一定会相遇，而且快指针在环中不会超过两圈。相遇后快指针回到开头，然后两个指针都走一步，一定会在入环节点相遇。

情况一：两链表都无环

1. 判断链表长度
2. 判断end节点是否是一个，不同则不相交。
3. 长链表先走差值步，然后两链表一起走，一定会一起走到第一个相交点。

情况二：两链表都有环

情况二之一：链表无交集

情况二之二：入环节点是同一个节点。

情况二之三：入环节点不同。

 1public static Node bothLoop(Node head1, Node head2, Node loop1, Node loop2) {//两链表头节点，入环节点
 2Node cur1 = null;
 3Node cur2 = null;
 4if (loop1 == loop2) { //情况二之二：入环节点是同一个节点。
 5    cur1 = head1;
 6    cur2 = head2;
 7    int n = 0;
 8    while (cur1 != loop1) { //判断到达入环节点的长度
 9         n++;
10         cur1 = cur1.next;
11    }
12    while (cur2 != loop2) { //判断是1链表头结点到入环节点长度和2链表到入环节点长度的差值
13         n--;
14         cur2 = cur2.next;
15    }
16    cur1 = n > 0 ? head1 : head2;
17    cur2 = cur1 == head1 ? head2 : head1;
18    n = Math.abs(n);
19    while (n != 0) {// 使两个链表到入环点长度一样
20         n--;
21         cur1 = cur1.next;
22    }
23    while (cur1 != cur2) {
24         cur1 = cur1.next;
25         cur2 = cur2.next;
26    }
27    return cur1;
28} else { // 情况二之三：入环节点不同 或 情况二之一：链表无交集
29    cur1 = loop1.next;
30    while (cur1 != loop1) { // 限定只转一圈，碰不到loop2就是无交集
31         if (cur1 == loop2) {
32             return loop1;
33         }
34         cur1 = cur1.next;
35    }
36    return null;
37}
38}

Leetcode 题解 双指针

题目一：有序数组的 Two Sum Two Sum II - Input array is sorted (Easy)

1Input: numbers={2, 7, 11, 15}, target=9
2Output: index1=1, index2=2

题目描述：在有序数组中找出两个数，使它们的和为 target。

解题：

使用双指针，一个指针指向最小的元素，一个指针指向最大的元素，两指针向中间遍历

• 如果两指针的和 sum == garget，return 结果；
• 如果 sum > target，移动较大的元素，使 sum 变小一些；
• 如果 sum < target，移动较小的元素，使 sum 变小一些。

最多遍历一遍，时间复杂度为 O(N)。只是用两个额外的变量，空间按复杂度为 O(1)

 1public int[] twoSum(int[] numbers, int target){
 2    if (numbers == null) return null;
 3    int i = 0,j = numbers.length - 1;
 4    while(i < j){
 5        int sum = numbers[i] + numbers[j];
 6        if (sum == target) {
 7            return new int[]{i + 1, j + 1};
 8        } else if (sum < target) {
 9            i++;
10        } else {
11            j--;
12        }
13    }
14    return null;
15}

题目二：两数平方和 Sum of Square Numbers (Easy)

题目描述：判断一个非负整数是否为两个整数的平方和。

解题：

可以看成是在元素为 0 ~ target 的有序数组中查找两个数，使得这两个数的平方和为 target。

• 与 题一 逻辑一致，不同的是：左指针从 0位置上的0开始，右指针从 sqrt(target) 位置开始；

时间复杂度 O(sqrt(target))，时间复杂度 O(1)

题目三：反转字符串中的元音字符 Reverse Vowels of a String (Easy)

1Given s = "leetcode", return "leotcede".

解题：

使用双指针，一个指针从头遍历，一个指针从尾遍历，当两个指针都遇到元音时，交换这两个元音字符。

• 为了快速判断字符是不是元音字符，将元音字符添加到集合 HashSet 中，从而以 O(1) 的时间复杂度进行该操作

• 1private final static HashSet<Character> vowels = new HashSet<>(
  2        Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));
  

时间复杂度 O(N)，空间复杂度 O(1)

题目四：回文字符串 Valid Palindrome II (Easy)

1Input: "abca"
2Output: True
3Explanation: You could delete the character 'c'.

题目描述：可以删除一个字符，判断是否能构成回文字符串。

使用 双指针（stack进栈出栈、快慢指针（空间复杂度为O(1)））容易判断一个字符串是否是回文字符串。

本题的关键是处理删除一个字符。在使用双指针遍历字符串时，如果出现两个指针指向的字符不相等的情况，我们就试着删除一个字符，再判断删除完之后的字符串是否是回文字符串。

在判断是否为回文字符串时，我们不需要判断整个字符串，因为左指针左边和右指针右边的字符之前已经判断过具有对称性质，所以只需要判断中间的子字符串即可。

在试着删除字符时，我们既可以删除左指针指向的字符，也可以删除右指针指向的字符。

 1public boolean validPalindrome(String s){
 2 for(int i = 0, j = s.length() - 1; i < j; i++,j--){
 3     if(s.charAt(i) != s.charAt(j)){
 4         return isPalindrome(s, i, j - 1) || isPalindrome(s, i + 1, j);
 5     } 
 6 }
 7 return true;
 8}
 9
10private bool isPalindrome(String s, int i, int j) {
11 while (i < j){
12     if(s.charAt(i++) != s.charAt(j--)){
13         return false;
14     }
15 }
16 return ture;
17}

题目五：归并两个有序数组 Merge Sorted Array (Easy)

题目描述：把归并结果存到第一个数组上。

1Input:
2nums1 = [1,2,3,0,0,0], m = 3
3nums2 = [2,5,6],       n = 3
4
5Output: [1,2,2,3,5,6]

解题：

类似归并排序合并字符串。

 1public void merge(int[] nums1, int m, int[] nums2, int n) {
 2 int index1 = m - 1, index2 = n - 1;
 3 int indexMerge = m + n - 1;
 4 while (index2 >= 0) {
 5     if (index1 < 0) {
 6         nums1[indexMerge--] = nums2[index2--];
 7     } else if (index2 < 0) {
 8         nums1[indexMerge--] = nums1[index1--];
 9     } else if (nums1[index1] > nums2[index2]) {
10         nums1[indexMerge--] = nums1[index1--];
11     } else {
12         nums1[indexMerge--] = nums2[index2--];
13     }
14 }
15}
16
17//归并排序merge方法
18public static void merge(int[] arr, int L, int M, int R){
19 int[] extra = new int[R - L + 1];
20 int i = 0;
21 int p1 = L;
22 int p2 = M + 1;
23 while(p1 <= M && p2 <= R){
24     extra[i++] = arr[p1] <= arr[p2] ? arr[p1++]: arr[p2++];
25 }
26 while(p1 <= M){
27     extra[i++] = arr[p1++];
28 }
29 while(p2 <= R){
30     extra[i++] = arr[p2++];
31 }
32 for(i = 0; i < extra.length; i++){
33     arr[L + i] = extra[i];
34 }
35}

题目六：判断链表是否存在环 Linked List Cycle (Easy)

解题：

使用快慢指针。如果存在环，那么这两个指针一定会相遇。

题目七：最长子序列 Longest Word in Dictionary through Deleting (Medium)

1Input:
2s = "abpcplea", d = ["ale","apple","monkey","plea"]
3
4Output:
5"apple"

题目描述：删除 s 中的一些字符，使得它构成字符串列表 d 中的一个字符串，找出能构成的最长字符串。如果有多个相同长度的结果，返回字典序的最小字符串。

解题：

通过删除字符串 s 中的一个字符能得到字符串 t，可以认为 t 是 s 的子序列，我们可以使用双指针来判断一个字符串是否为另一个字符串的子序列。

 1public String findLongestWord(String s, List<String> d) {
 2    String longestWord = "";
 3    for(String target: d){
 4        int l1 = longestWord.length(), l2 = target.length();
 5        if(l1 > l2 || (l1 == l2 && longestWord.compareTo(target) < 0)){
 6            continue;
 7        }
 8        if(isSubstr(s,target)){
 9            
10        }
11    }
12    return longestWord;
13}
14
15private boolean isSubstr(String s,String target){
16    int i = 0,j = 0;
17    while(i < s.length() && j < target.length()){
18        if(s.charAt(i) == target.charAt(j)){
19            j++;
20        }
21        i++;
22    }
23    return j == target.length();
24}

Leetcode 题解 - 树

递归遍历：

 1public static void orderRecur(Node head){
 2if(head == null){
 3return;
 4}
 5//operation(...) //先序遍历
 6orderRecur(head.left);
 7//operation(...) //中序遍历
 8orderRecur(head.right);
 9//operation(...) //后序遍历
10}

深度优先遍历：中序遍历

宽度优先遍历并求最大宽度：队列 LinkedList

 1public static void weight(Node head) {
 2if (head == null) {
 3  return;
 4}
 5Queue<Node> queue = new LinkedList<>();
 6queue.add(head);
 7HashMap<Node, Integer> levelMap = new HashMap<>();//记录行数
 8levelMap.put(head, 1);
 9int curLevel = 1;
10int curLevelNodes = 0;
11int max = Integer.MIN_VALUE;
12while (!queue.isEmpty()) {
13  Node cur = queue.poll();
14  int curNodeLevel = levelMap.get(cur);
15  if (curNodeLevel == curLevel) {
16      curLevelNodes++;
17  } else {
18      max = Math.max(max, curLevelNodes);
19      curLevel++;
20      curLevelNodes = 0;
21  }
22  System.out.println(cur.value);
23  if (cur.left != null) {
24      levelMap.put(cur.left, curNodeLevel + 1);
25      queue.add(cur.left);
26  }
27  if (cur.right != null) {
28      levelMap.put(cur.right, curNodeLevel + 1);
29      queue.add(cur.right);
30  }
31}
32}

判断是否是搜索二叉树：左孩子小于父节点，右孩子大于父节点。

中序遍历：中间打印节点值的地方改成和前节点值比较。

判断是否是完全二叉树：每一层是满的，或者最后一层节点都在左边。

非递归方法：

同时满足

1. 任一节点有右无左 --> false
2. 遇到一个左右子树不全的节点，后续皆是叶节点。

 1public static boolean isCBT(Node head){
 2    if(head == null){
 3        return true;
 4    }
 5    LinkedList<Node> queue = new LinkedList<>();
 6    //是否遇到过左右两个孩子不双全的节点
 7    boolean leaf = false;
 8    Node l = null;
 9    node r = null;
10    queue.add(head);
11    while(!queue.isEmpty()){
12        head = queue.poll();
13        l = head.left;
14        r = head.right;
15        if(
16        //节点不双全，又发现有孩子
17            (leaf && (l ！= null || r ！= null))
18            ||
19            (l == null && r != null)
20        ){
21            return false;
22        }
23        if (l != null){
24            queue.add(l);
25        }
26        if (r != null){
27            queue.add(r);
28        }
29        if (l == null || r == null){
30            leaf = true;
31        }
32        return true;
33    }
34}

判断满二叉树：

二叉树DP题目固定套路：递归

二叉树DP题目: 可以通过从左右树要信息解决问题可以使用这个固定方法。

 1public static class Info {
 2 public int height;
 3 public int nodes;
 4
 5 public Info(int h, int n) {
 6     height = h;
 7     nodes = n;
 8 }
 9}
10
11public static Info f(Node x) {
12 if (x == null) {
13     return new Info(0, 0);
14 }
15 Info leftData = f(x.left);
16 Info rightData = f(x.right);
17 int height = Math.max(leftData.height, rightData.height) + 1;
18 int nodes = leftData.nodes + rightData.nodes + 1;
19 return new Info(height, nodes);
20}

判断平衡二叉树：左树高度和右树高度的差都不超过1

同时满足：

1. 左子树是平衡二叉树
2. 右子树是平衡二叉树
3. 左树高度和右树高度的差不超过1

 1public static class ReturnType{
 2    public boolean isBalanced;
 3    public int height;
 4    public ReturnType(boolean isB, int hei){
 5        isBalanced = isB;
 6        height = hei;
 7    }
 8}
 9public static ReturnType Process(Node x){
10    if(x = null){
11        return new ReturnType(true, 0);
12    }
13    ReturnType leftData = process(x.left);
14    ReturnType rightData = process(x.right);
15    int height = Math.max(leftData.height, rightData.height) + 1;
16    boolean isBalanced = leftData.isBalanced && rightData.isBalanced && Math.abs(leftData.height - rightData.height) < 2;
17    return new ReturnType(isBalanced, height);
18}