Leetcode

Overview

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;

排序

冒泡排序

bubble_sort

选择排序

select_sort

插入排序

  • insert-sort

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

  • 时间复杂度: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)

归并排序

  • merge-sort
  • 概念:将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}

快速排序

quick_sort

时间复杂度: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}

堆排序

heap_sort

时间复杂度: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}
    

桶排序

计数排序:

基数排序:

radix_sort

 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}

小结

时间复杂度 空间复杂度 稳定性
选择 O(N2) O(1) x
冒泡 O(N2) O(1)
插入 O(N2) O(1)
归并 O(NlogN) O(N)
快排 O(NlogN) O(logN) x
堆排 O(NlogN) O(1) x
  • 一般优先选择 快速排序,快排的复杂度在常数项是最低的。
  • 对空间有要求选择 堆排序
  • 对稳定性有要求选择 归并排序

Leetcode 题解 - 排序

快速选择

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

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

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

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

快速选择也可以求解 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}

递归

1. 树的高度 Maximum Depth of Binary Tree (Easy)

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

2. 平衡树 Balanced Binary Tree (Easy)

平衡树左右子树高度差都小于等于 1

 1private boolean result = true;
 2
 3public boolean isBalanced(TreeNode root){
 4    maxDepth(root);
 5    return result;
 6}
 7
 8public int maxDepth(TreeNode root){
 9    if(root == null) return 0;
10    int l = maxDepth(root.left);
11    int r = maxDepth(root.right);
12    if(Math.abs(l - r) > 1) result = false;
13    return Math.max(l, r) + 1;
14}

3. 两节点的最长路径 Diameter of Binary Tree (Easy)

1Input:
2
3         1
4        / \
5       2  3
6      / \
7     4   5
8
9Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
 1private int max = 0;
 2public int diameterOfBinaryTree(TreeNode root){
 3    depth(root);
 4    return max;
 5}
 6
 7private int depth(TreeNode root){
 8    if(root == null) return 0;
 9    int l = depth(root.left);
10    int r = depth(root.right);
11    max = Math.max(max, l + r);
12    return Math.max(l, r) + 1;
13}

BFS层次遍历

使用 BFS 时,不需要使用两个队列来分别存储当前层的节点和下一层的节点,因为在开始遍历一层的节点时,当前队列的节点数就是当前层的节点数,只要控制遍历这么多节点数,就能保证这次遍历的都是当前层的节点。

1. 一棵树每层节点的平均数 Average of Levels in Binary Tree (Easy)

 1public List<Double> averageOfLevels (TreeNode root){
 2    List<Double> ret = new ArrayList<>();
 3    if (root == null) return ret;
 4    Queue<TreeNode> queue = new LinkedList<>();
 5    queue.add(root);
 6    while (!queue.isEmpty()){
 7        int cnt = queue.size();
 8        double sum = 0;
 9        for(int i = 0; i < cnt; i++){
10            TreeNode node = queue.poll();
11            sum += node.val;
12            if (node.left != null) queue.add(node.left);
13            if (node.right != null) queue.add(node.right);
14        }
15        ret.add(sum / cnt);
16    }
17    return ret;
18}

2. 得到左下角的节点 Find Bottom Left Tree Value (Easy)

 1Input:
 2
 3        1
 4       / \
 5      2   3
 6     /   / \
 7    4   5   6
 8       /
 9      7
10
11Output:
127

解题:

宽度优先遍历 BFS,每一行从左至右改成从右至左,然后最后一个数

 1public int findBottomLeftValue(TreeNode root) {
 2    Queue<TreeNode> queue = new LinkedList<>();
 3    queue.add(root);
 4    while(!queue.isEmpty()){
 5        root = queue.poll();
 6        if (root.right != null) queue.add(root.right);
 7        if (root.left != null) queue.add(root.left);
 8    }
 9    return root.val;
10}

前中后序遍历

非递归实现前中后序遍历

前序遍历、后续遍历

 1public List<Integer> preOrderTraversal(TreeNode root){
 2    List<Integer> ret = new ArrayList<>();
 3    Stack<TreeNode> stack = new Stack<>();
 4    stack.push(root);
 5    while(!stack.isEmpty()){
 6        TreeNode node = stack.pop();
 7        if (node == null) continue;
 8        ret.add(node.val);
 9        stack.push(node.right); //先右后左,保证左子树先遍历。先左后右即为后续遍历。
10        stack.push(node.left);
11    }
12    return ret;
13}

中序遍历

 1public List<Integer> inorderTraversal(TreeNode root) {
 2    List<Integer> ret = new ArrayList<>();
 3    if (root == null) return ret;
 4    Stack<TreeNode> stack = new Stack<>();
 5    TreeNode cur = root;
 6    while(cur != null || !stack.isEmpty()){
 7        while(cur != null){
 8            stack.push(cur);
 9            cur = cur.left;
10        }
11        TreeNode node = stack.pop();
12        ret.add(node.val);
13        cur = node.right;
14    }
15    return ret;
16}    

BST二叉查找树

二叉查找树(BST):根节点大于等于左子树所有节点,小于等于右子树所有节点。

二叉查找树中序遍历有序。

1. 修剪二叉查找树 Trim a Binary Search Tree

 1Input:
 2
 3    3
 4   / \
 5  0   4
 6   \
 7    2
 8   /
 9  1
10
11  L = 1
12  R = 3
13
14Output:
15
16      3
17     /
18   2
19  /
20 1

题目描述:只保留值在 L ~ R 之间的节点

解题:

1public TreeNode trimBST(TreeNode root, int L, int R){
2    if(root == null) return null;
3    if(root.val > R) return trimBST(root.left, L, R);
4    if(root.val < L) return trimBST(root.right, L, R);
5    root.left = trimBST(root.left, L, R);
6    root.right = trimBST(root.right, L, R);
7    return root;
8}

2.寻找二叉查找树第K个元素 Kth Smallest Element in a BST (Medium)

中序遍历解法:

 1private int cnt = 0;
 2private int val;
 3
 4public int kthSmallest(TreeNode root, int k){
 5    if(node == null) return;
 6    inOrder(node.left, k); //中序遍历查找树有序,左子树走到底为最小数
 7    cnt++;
 8    if(cnt == k){
 9        val = node.val;
10        return;
11    }
12    inOrder(node.right, k); //中序遍历向右子树
13}

3. 把二叉查找树每个节点的值都加上比它大的节点的值 Convert BST to Greater Tree (Easy)

 1Input: The root of a Binary Search Tree like this:
 2
 3              5
 4            /   \
 5           2     13
 6
 7Output: The root of a Greater Tree like this:
 8
 9             18
10            /   \
11          20     13

解题:

先遍历右子树。反向中序遍历即从大到小.

 1private int sum = 0;
 2
 3public TreeNode convertBST(TreeNode root){
 4    traver(root);
 5    return root;
 6}
 7
 8private void traver(TreeNode node){
 9    if(node == null) return;
10    traver(node.right);  //到最大的节点
11    sum += node.val;
12    node.val = sum;
13    traver(node.left);
14}

4. 二叉查找树的最近公共祖先 Lowest Common Ancestor of a Binary Search Tree (Easy)

1        _______6______
2      /                \
3  ___2__             ___8__
4 /      \           /      \
50        4         7        9
6        /  \
7       3   5
8
9For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

解题:

前序遍历,第一个满足区间中的数即为最近根。

1public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
2    if(root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
3    if(root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
4}

6. 从有序数组中构造二叉查找树 Convert Sorted Array to Binary Search Tree (Easy)

 1public TreeNode sortedArrayToBST(int[] nums){
 2    return toBST(nums, 0, nums.length - 1);
 3}
 4
 5private TreeNode toBST(int[] nums, int sIdx, int eIdx){
 6    if(sIdx > eIdx) return null;
 7    int mIdx = (sIdx + eIdx) / 2;
 8    TreeNode root = new TreeNode(nums[mIdex]);
 9    root.left = toBST(nums, sIdx, mIdx - 1);
10    root.right = toBST(nums, mIdx + 1, eIdx);
11    return root;
12}

7. 根据有序链表构造平衡的二叉查找树 Convert Sorted List to Binary Search Tree (Medium)

8. 在二叉查找树中寻找两个节点,使它们的和为一个给定值 Two Sum IV - Input is a BST (Easy)

 1Input:
 2
 3    5
 4   / \
 5  3   6
 6 / \   \
 72   4   7
 8
 9Target = 9
10
11Output: True

解题:

使用中序遍历得到有序数组之后,再利用双指针对数组进行查找。

应该注意到,这一题不能用分别在左右子树两部分来处理这种思想,因为两个待求的节点可能分别在左右子树中。

 1public boolean findTarget(TreeNode root, int k) {
 2    List<Integer> nums = new ArrayList<>();
 3    inOrder(root, nums);
 4    int i = 0, j = nums.size() - 1;
 5    while (i < j) {
 6        int sum = nums.get(i) + nums.get(j);
 7        if (sum == k) return true;
 8        if (sum < k) i++;
 9        else j--;
10    }
11    return false;
12}
13
14private void inOrder(TreeNode root, List<Integer> nums) {
15    if (root == null) return;
16    inOrder(root.left, nums);
17    nums.add(root.val);
18    inOrder(root.right, nums);
19}

9. 在二叉查找树中查找两个节点之差的最小绝对值 Minimum Absolute Difference in BST (Easy)

 1Input:
 2
 3   1
 4    \
 5     3
 6    /
 7   2
 8
 9Output:
10
111

解题:

利用二叉查找树的中序遍历有序的性质,计算中序遍历中临近的两个节点之差的绝对值,取最小值。

 1private int minDiff = Integer.MAX_VALUE;
 2private TreeNode preNode = null;
 3public int getMinimumDifference(TreeNode root){
 4    inOrder(root);
 5    return minDiff;
 6}
 7private void inOrder(TreeNode node){
 8    if (node == null) return;
 9    inOrder(node.left);
10    if (preNode != null) minDiff = Math.min(minDiff, node.val - preNode.val);
11    preNode = node;
12    inOrder(node.right);
13}

10. 寻找二叉查找树中出现次数最多的值 Find Mode in Binary Search Tree (Easy)

 1private int curCnt = 1;
 2private int maxCnt = 1;
 3private TreeNode preNode = null;
 4public int[] findMode(TreeNode root){
 5    List<Integer> maxCntNums = new ArrayList<>();
 6    inOrder(root, maxCntNums);
 7    int[] ret = new int[maxCntNums.size()];
 8    int idx = 0;
 9    for(int num : maxCntNums){
10        ret[idx++] = num;
11    }
12    return ret;
13}
14private void inOrder(TreeNode node, List<Integer> nums){
15    if(node == null) return;
16    inOrder(node.left, nums);
17    if(preNode != null){
18        if (preNode.val == node.val) curCnt++;
19        else curCnt = 1;
20    }
21    if(curCnt > maxCnt){
22        maxCnt = curCnt;
23        nums.clear;
24        nums.add(node.val);
25    } else if (curCnt == maxCnt){
26        nums.add(node.val);
27    }
28    preNode = node;
29    inOrder(node.right, nums);
30}

Trie 前缀树

Trie 概念:单词集合生成由字母组成的树。又称前缀树或字典树,用于判断字符串是否存在或者是否具有某种字符串前缀。

trie

1.实现一个 Trie Implement Trie (Prefix Tree) (Medium)

 1class Trie{
 2    private class Node{
 3        Node[] childs = new Node[26];
 4        boolean isLeaf;
 5    }
 6    private Node root = new Node();
 7    public Trie(){
 8    }
 9    public void insert(String word, Node node){
10        insert(word, root);
11    }
12    private void insert(String word, Node node){
13        if(node == null) return;
14        if(word.length() == 0){
15            node.isLeaf = true;
16            return;
17        }
18        int index = indexForChar(word.charAt(0));
19        if(node.childs[index] == null){
20            node.childs[index] = new Node();
21        }
22        insert(word.substring(1), node.childs[index]);
23    }
24    public boolean search(String word){
25        return search(word, root);
26    }
27    private boolean search(String word, Node node){
28        if(node == null) return false;
29        if(word.length() == 0) node.isLeaf;
30        int index = indexForChar(word.charAt(0));
31        return search(word.substring(1), node.childs[index]);
32    }
33    
34    public boolean startsWith(String prefix){
35        return startWith(prefix, root);
36    }
37    private boolean startWith(String prefix, Node node){
38        if(node == null) return false;
39        if(prefix.length() == 0) return true;
40        int index = indexForChar(prefix.charAt(0));
41        return startWith(prefix.substring(1), node.childs[index]);
42    }
43    
44    private int indexForChar(char c) {
45        return c - 'a';
46    }
47    
48}

Leetcode 题解 - 栈和队列

1. 用栈实现队列 Implement Queue using Stacks (Easy)

解题:

栈的顺序为后进先出,而队列的顺序为先进先出。使用两个栈实现队列,一个元素需要经过两个栈才能出队列,在经过第一个栈时元素顺序被反转,经过第二个栈时再次被反转。

 1class MyQueue{
 2    private Stack<Integer> in = new Stack<>();
 3    private Stack<Integer> out = new Stack<>();
 4    public void push(int x){
 5        in.push(x);
 6    }
 7    public int pop(){
 8        in2out();
 9        return out.pop();
10    }
11    public int peek(){
12        in2out();
13        return out.peek();
14    }
15    private void in2out(){
16        if(out.isEmpty()){
17            while(!in.isEmpty()){
18                out.push(in.pop());
19            }
20        }
21    }
22    public boolean empty(){
23        return in.isEmpty() && out.isEmpty();
24    }
25}

2. 用队列实现栈 Stack using Queues (Easy)

解题:

在将一个元素x插入队列时,为了维护原来的后进先出顺序,需要让x插入队列首部。而队列默认插入顺序是队列尾部,因此在将x插入队列尾部之后,需要让除了x之外的所有元素出队列,再入队列。

3. 最小值栈 Min Stack (Easy)

 1class MinStack {
 2
 3    private Stack<Integer> dataStack;
 4    private Stack<Integer> minStack;
 5    private int min;
 6
 7    public MinStack() {
 8        dataStack = new Stack<>();
 9        minStack = new Stack<>();
10        min = Integer.MAX_VALUE;
11    }
12
13    public void push(int x) {
14        dataStack.add(x);
15        min = Math.min(min, x);
16        minStack.add(min);
17    }
18
19    public void pop() {
20        dataStack.pop();
21        minStack.pop();
22        min = minStack.isEmpty() ? Integer.MAX_VALUE : minStack.peek();
23    }
24
25    public int top() {
26        return dataStack.peek();
27    }
28
29    public int getMin() {
30        return minStack.peek();
31    }
32}

对于实现最小值队列问题,可以先将队列使用栈来实现,然后就将问题转换为最小值栈。

4. 用栈实现括号匹配 Valid Parentheses (Easy)

1"()[]{}"
2
3Output : true
 1public boolean isValid(String s){
 2    Stack<Character> stack = new Stack<>();
 3    for(char c : s.toCharArray()){
 4        if(c == '(' || c == '{' || c == '['){
 5            stack.push(c);
 6        } else {
 7            if(stack.isEmpty()){
 8                return false;
 9            }
10            char cStack = stack.pop();
11            boolean b1 = c == ')' && cStack != '(';
12            boolean b2 = c == ']' && cStack != '[';
13            boolean b3 = c == '}' && cStack != '{';
14            if(b1 || b2 || b3){
15                return false;
16            }
17        }
18    }
19    return stack.isEmpty();
20}

5. 数组中元素与下一个比它大的元素之间的距离 Daily Temperatures (Medium)

1Input: [73, 74, 75, 71, 69, 72, 76, 73]
2Output: [1, 1, 4, 2, 1, 1, 0, 0]

解题:

在遍历数组时用栈把数组中的数存起来,如果当前遍历的数比栈顶元素来的大,说明栈顶元素的下一个比它大的数就是当前元素。

 1public int[] dailyTemperatures(int[] temperatures){
 2    int n = temperatures.length;
 3    int[] dist = new int[n];
 4    Stack<Integer> indexs = new Stack<>();
 5    for(int curIndex = 0; curIndex < n; curIndex ++){
 6        while(!indexs.isEmpty() && temperatures[curIndex] > temperatures[indexs.peek()]){
 7            int preIndex = indexs.pop();
 8            dist[preIndex] = curIndex - preIndex;
 9        }
10        indexs.add(curIndex);
11    }
12    return dist;
13}

6. 循环数组中比当前元素大的下一个元素 Next Greater Element II (Medium)

1Input: [1,2,1]
2Output: [2,-1,2]
3Explanation: The first 1's next greater number is 2;
4The number 2 can't find next greater number;
5The second 1's next greater number needs to search circularly, which is also 2.

解题:

与 Daily Temperatures (Medium) 不同的是,数组是循环数组,并且最后要求的不是距离而是下一个元素。

 1public int[] nextGreaterElements(int[] nums){
 2    int n = nums.length;
 3    int[] next = new int[n];
 4    Stack<Integer> pre = new Stack<>();
 5    for(int i = 0; i < n * 2; i++){
 6        int num = nums[i % n];
 7        while(!pre.isEmpty() && nums[pre.peek()] < num){
 8            next[pre.pop()] = num;
 9        }
10        if(i < n){
11            pre.push(i);
12        }
13    }
14    return next;
15}

Leetcode 题解 - 分治

题目一:给表达式加括号 Different Ways to Add Parentheses (Medium)

1Input: "2-1-1".
2
3((2-1)-1) = 0
4(2-(1-1)) = 2
5
6Output : [0, 2]

解题:

利用分治算法,在顺序扫描表达式的时候,当遇到一个运算符,该运算符将整个表达式分成了两部分,表达式左右均是完整的表达式,可以对两边的表达式分开处理,分别得到两个表达式的结果数组,然后根据该运算符对两边的结果数组做相应的处理,再对整体表达式的下一个运算符做上述处理,直到所有运算符。

 1public List<Integer> diffWaysToCompute(String input) {
 2    List<Integer> ways = new ArrayList<>();
 3    for (int i = 0; i < input.length(); i++) {
 4        char c = input.charAt(i);
 5        if (c == '+' || c == '-' || c == '*') {
 6            List<Integer> left = diffWaysToCompute(input.substring(0, i));
 7            List<Integer> right = diffWaysToCompute(input.substring(i + 1));
 8            for (int l : left) {
 9                for (int r : right) {
10                    switch (c) {
11                        case '+':
12                            ways.add(l + r);
13                            break;
14                        case '-':
15                            ways.add(l - r);
16                            break;
17                        case '*':
18                            ways.add(l * r);
19                            break;
20                    }
21                }
22            }
23        }
24    }
25    if (ways.size() == 0) {
26        ways.add(Integer.valueOf(input));
27    }
28    return ways;
29}

题目二:不同的二叉搜索树 Unique Binary Search Trees II (Medium)

给定一个数字 n,要求生成所有值为 1...n 的二叉搜索树。

二叉搜索树:对于树中每个节点:

  • 若其左子树存在,则其左子树中每个节点的值都不大于该节点值;
  • 若其右子树存在,则其右子树中每个节点的值都不小于该节点值。
 1Input: 3
 2Output:
 3[
 4  [1,null,3,2],
 5  [3,2,null,1],
 6  [3,1,null,null,2],
 7  [2,1,3],
 8  [1,null,2,null,3]
 9]
10Explanation:
11The above output corresponds to the 5 unique BST's shown below:
12
13   1         3     3      2      1
14    \       /     /      / \      \
15     3     2     1      1   3      2
16    /     /       \                 \
17   2     1         2                 3

解题:

 1public List<TreeNode> generateTrees(int n) {
 2    if (n < 1) {
 3        return new LinkedList<TreeNode>();
 4    }
 5    return generateSubtrees(1, n);
 6}
 7
 8private List<TreeNode> generateSubtrees(int s, int e) {
 9    List<TreeNode> res = new LinkedList<TreeNode>();
10    if (s > e) {
11        res.add(null);
12        return res;
13    }
14    for (int i = s; i <= e; ++i) {
15        List<TreeNode> leftSubtrees = generateSubtrees(s, i - 1);
16        List<TreeNode> rightSubtrees = generateSubtrees(i + 1, e);
17        for (TreeNode left : leftSubtrees) {
18            for (TreeNode right : rightSubtrees) {
19                TreeNode root = new TreeNode(i);
20                root.left = left;
21                root.right = right;
22                res.add(root);
23            }
24        }
25    }
26    return res;
27}

Leetcode 题解 - 动态规划

递归和动态规划的区别

都是将原问题拆成多个子问题然后求解,他们之间最本质的区别是,动态规划保存了子问题的解,避免重复计算。

斐波那契数列

题目一:爬楼梯 Climbing Stairs (Easy)

题目描述:有 N 阶楼梯,每次可以上一阶或者两阶,求有多少种上楼梯的方法。

解题:

定义一个数组 dp 存储上楼梯的方法数(为了方便讨论,数组下标从 1 开始),dp[i] 表示走到第 i 个楼梯的方法数目。

第 i 个楼梯可以从第 i-1 和 i-2 个楼梯再走一步到达,走到第 i 个楼梯的方法数为走到第 i-1 和第 i-2 个楼梯的方法数之和。

dp[i] = dp[i - 1] + dp[i - 2]

考虑到 dp[i] 只与 dp[i - 1] 和 dp[i - 2] 有关,因此可以只用两个变量来存储 dp[i - 1] 和 dp[i - 2],使得原来的 O(N) 空间复杂度优化为 O(1) 复杂度。

 1public int climbStairs(int n){
 2    if(n <= 2){
 3        return n;
 4    }
 5    int pre2 = 1, pre1 = 2;
 6    for(int i = 2;i < n;i++){
 7        int cur = pre1 + pre2;
 8        pre2 = pre1;
 9        pre1 = cur;
10    }
11    return pre1;
12}

题目二:强盗抢劫 House Robber (Easy)

题目描述:抢劫一排住户,但是不能抢邻近的住户,求最大抢劫量。

解题:

图的描述方式:

 1public class Node {
 2 public int value; //点的编号
 3 public int in; //入度的个数
 4 public int out; //出度的个数
 5 public ArrayList<Node> nexts; //邻居点
 6 public ArrayList<Edge> edges; //邻居边
 7
 8 public Node(int =value) {
 9     this.value = value;
10     in = 0;
11     out = 0;
12     nexts = new ArrayList<>();
13     edges = new ArrayList<>();
14 }
15}
16
17public class Edge {
18 public int weight;
19 public Node from;
20 public Node to;
21
22 public Edge(int weight, Node from, Node to) {
23     this.weight = weight;
24     this.from = from;
25     this.to = to;
26 }
27}
28
29public class Graph {
30 public HashMap<Integer, Node> nodes; //点集
31 public HashSet<Edge> edges; //边集
32
33 public Graph() {
34     nodes = new HashMap<>();
35     edges = new HashSet<>();
36 }
37}

图的宽度优先遍历:

  1. 利用队列实现
  2. 从源节点开始依次按照宽度进队列,然后弹出
  3. 每弹出一个点,把该节点所有没有进过队列的邻接点放入队列
  4. 直到队列变空
 1public static void bfs(Node node){
 2    if (node == null){
 3        return;
 4    }
 5    Queue<Node> queue = new LinkedList<>();
 6    HashSet<Node> set = new HashSet<>(); //放入已处理的节点,检查点是否重复。
 7    queue.add(node);
 8    set.add(node);
 9    while(!queue.isEmpty()){
10        Node cur = queue.poll();
11        System.out.println(cur.value);
12        for(Node next : cur.nexts){
13            if(!set.contains(nexts)){
14                set.add(next);
15                queue.add(next);
16            }
17        }
18    }
19}

图的广度优先遍历:

  1. 利用栈实现
  2. 从源节点开始依次按照深度进队列,然后弹出
  3. 每弹出一个点,把该节点所有没有进过队列的邻接点放入队列
  4. 直到队列变空
 1public static void dfs(Node node){
 2    if (node == null){
 3        return;
 4    }
 5    Stack<Node> stack = new Stack<>();
 6    HashSet<Node> set = new HashSet<>();
 7    stack.add(node);
 8    set.add(node);
 9    System.out.println(node.value);
10    while(!stack.isEmpty()){
11        Node cur = stack.pop();
12        for(Node next : cur.nexts){
13            if(!set.contains(next)){
14                stack.push(cur);
15                stack.push(next);
16                set.add(next);
17                System.out.println(next.value);
18                break;
19            }
20        }
21    }
22}

拓扑排序问题:

实际问题:编译依赖是个有向无环图。如何决定编译顺序。

方法:找到入度为0的点输出,然后擦掉该节点和该节点边,再找到入度为0点输出。以此往复。

 1public static List<Node> sortedTopoloty(Graph graph){
 2HashMap<Node, Integer> inMap = new HashMap<>(); // key: 某一个Node; value:剩余的入度
 3Queue<Node> zeroInQueue = new LinkedList<>(); // 入度为0放入这个队列。
 4for(Node node: graph.nodes.values()){
 5inMap.put(node, node.in);
 6if(node.in == 0){
 7   zeroInQueue.add(node);
 8}
 9}
10// 拓扑排序结果,依次加入result
11List<Node> result = new ArrayList<>();
12while(!zeroInQueue.isEmpty()){
13Node cur = zeroInQueue.poll();
14result.add(cur);
15for(Node next : cur.nexts){
16   inMap.put(next, inMap.get(next) - 1);
17   if(inMap.get(next) == 0){
18       zeroInQueue.add(next);
19   }
20}
21}
22return result;
23}

kruskal算法:适用范围要求无向图

prim算法:适用范围要求无向图

Dijkstra算法:适用范围没有权值为负数的边

暴力递归

哈希函数

问题:2的32次方个由 0 - 2 的32次方组成的随机数,用1G内存,返回出现次数最多的数

如果直接使用哈希表 {key :次数},会占用8 * 2 32 个字节(32G)。

可以将每个数算出哈希值后%100 后存入哈希表,这样 2 32 个 key:value 变成了一百个key:value。

再将次数最多的 key 进行统计。

布隆过滤器

解决问题:

  • 黑名单系统(100亿 URL 组成的黑名单,每次访问要判断是否在黑名单中,用 HashSet 则占用 640G 内存)
  • 爬虫去重问题等 (使用1000个线程爬虫,不希望爬已经爬过的网站,需要把已经爬过的网站做成集合)

功能:

  • 只有添加和搜索功能,没有删除功能
  • 使用很少的内存,允许有一定的失误

位图代码:

 1int [] arr = new int[10];  //每个 int 4个字节32位,10个int数组可以表示 32bit * 10 -> 320bit
 2//例:想拿到第178位的状态
 3int numIndex = 178 / 32;
 4int bitIndex = 178 % 32;
 5//拿到178位的状态
 6int s = ((arr[numIndex] >> (bitIndex)) & 1);
 7//把178位的状态改成1
 8arr[numIndex] = arr[numIndex] | (1 << (bitIndex));
 9//把178位的状态改成0
10arr[numIndex] = arr[numIndex] & (~ (1 << (bitIndex)));

布隆过滤器逻辑:

 1生成布隆过滤器
 2//1. 生成 m 长度的位图
 3//2. 加入黑名单:URL1 通过k个 hash 函数算出k个 hash 值 %m ,确立k个位数值位 1 。更新到位图上
 4//3. 此时位图已记录 URL1 。以此重复, 已经为1继续为1,直到写入 100亿 URL
 5    
 6查询
 7// URL 通过k个 hash 函数算出k个 hash 值 %m,在位图上验证,都为 1 则满足
 8    
 9m和k值如何确定
10// m 越大越好,k 过大过小都不好。有计算公式

一致性哈希

解决问题:

数据服务器如何组织,解决分布式数据库负载均衡,高低频查询。

传统分布式存储:

海量数据分布式存储:数据通过key值算出哈希值 % 机器数量 决定数据存放服务器节点。

当服务器硬盘大小不够,需要增加服务器。这时需要数据全量迁移,而且重新将hash值 % 新的服务器数量

通过一致性哈希存储保证不 % ,并减少迁移代价:

如有 3 台机器分布式存储数据。通过 MD5 作哈希值。

将1 ~ 264-1 想象成一个环,将 [0 , 264 / 3] 分给节点1,[264 / 3 , 264 / 3 * 2] 分给节点2,[264 / 3 * 2 , 264] 分给节点3。

当增加节点时,比如节点放在节点2和节点3正中间。只用从节点2上移动 264 / 3 / 2 个数据到新节点上。

问题1:开始如何均分数据

问题2:增加减少节点导致负载不均衡

虚拟节点技术 :按比例去抢环,增加节点时,按比例从每个节点拿数据放到新节点。删除节点也按比例分配到别的节点。

一致性哈希按比例同时可以解决:性能强的机器数据量大,性能弱的机器数据少。

【题目】: 岛问题

【题目】矩阵中只有0和1两种值,每个位置都可以和自己的上下左右四个位置相连,相邻的一片1叫做一个岛,求一个矩阵中有多少个岛?

1001010
2111010
3100100
4000000
5> 这个矩阵中有三个岛

【解题】顺序遍历节点,遇到1则进入感染函数,将与该1一起的岛改成2,岛数++。

感染函数:

 1public static void infect (int[][]m, int i, int j, int N, int M){ //(i,j)位置 N,M矩形长宽
 2    if(i < 0 || i >= N || j < 0 || j >= M || m[i][j] != 1){ //i,j没越界,并且当前位置是1
 3        return;
 4    }
 5    m[i][j] = 2;
 6    infect(m, i + 1, j, N, M);
 7    infect(m, i - 1, j, N, M);
 8    infect(m, i, j + 1, N, M);
 9    infect(m, i, j - 1, N, M);
10}

时间复杂度:O(N * M)

【进阶】如何设计一个并行算法解决这个问题

并查集

解决两个集合查重合并。使用 链表hashSet 效率都不高。链表 合并的复杂度是 O(1),查重是 O(n2)。使用 hashSet 查重 复杂度是 O(n),合并 复杂度是 O(n)。

 1//找到头结点函数:判断集合是否是一个集合只用判断头结点是否相同。
 2//找头结点时同时优化:将该节点到头节点路径上的节点拍平,直接插到头结点上。当调用 findHead 函数次数越多,时间复杂度越接近 O(1)
 3private Element<V> findHead(Element<V> element){
 4 Stack<Element<V>> path = new Stack<>();
 5 while (element != fatherMap.get(element)){
 6     path.push(element);
 7     element = fatherMap.get(element);
 8 }
 9 while (!path.isEmpty()){
10     fatherMap.put(path.pop(), element);
11 }
12 return element;
13}
14
15//判断是否为同一集合函数
16public boolean isSameSet(V a, V b){
17 if (elementMap.containsKey(a) && elementMap.containsKey(b)){
18     return findHead(elementMap.get(a)) == findHead(elementMap.get(b));
19 }
20 return false;
21}
22
23
24//合并集合函数, 小集合插到大集合尾部
25public void union(V a, V b){
26 if (elementMap.containsKey(a) && elementMap.containsKey(b)){
27     ...
28 }
29}

并行解决方案:

如有两个线程,将岛图切分成 2 块,分别进行顺序遍历感染。这样统计出分散的岛视为不同的集合,将这些集合进行并查集合并操作,算出合并后的岛数。

Leetcode 题解 - 贪心思想 笔试面试都很少出现

概念:保证每次操作都是局部最优的,并且最后得到的结果是全局最优的。

因为变化太多,笔试面试都很少出现。

题目一:分配饼干 Assign Cookies (Easy)

1Input: grid[1,3], size[1,2,4]
2Output: 2

题目描述:每个孩子都有一个满足度 grid,每个饼干都有一个大小 size,只有饼干的大小大于等于一个孩子的满足度,该孩子才会获得满足。求解最多可以获得满足的孩子数量。

解题:

 1public int findContentChildren(int[] grid, int[] size) {
 2 if (grid == null || size == null) return 0;
 3 Arrays.sort(grid);
 4 Arrays.sort(size);
 5 int gi = 0, si = 0;
 6 while (gi < grid.length && si < size.length) {
 7     if (grid[gi] <= size[si]) {
 8         gi++;
 9     }
10     si++;
11 }
12 return gi;
13}