算法基础模版

Last renew: September 16, 2022 pm

算法基础模版

个人学习总结所用，无版权，来自于Yjy佬个人总结。

前缀和（Prefix sum）

前缀和技巧适用于快速、频繁地计算一个索引区间内的元素之和。

一维数组中的前缀和

LeetCode 303

一维数组前缀和模版：

1
2
3
4
5
6
7
8
9
10
public int prefixSum(int[] A, int left, int right){
  int[] B = new int[A.length + 1];
  
  B[0] = 0;
  for(int i = 1; i < B.length; i++) {
    B[i] = B[i - 1] + A[i - 1];
  }
  return B[right + 1] - B[left]
}

二维数组中的前缀和

LeetCode304

1
2
3
4
5
6
7
8
9
10
11
12
13
public int prefixSum(int[][] A, int x1, int y1, int x2, int y2) {
  int m = A.length;
  int n = A[0].length;
  int[][] B = new int[m + 1][n + 1];
  
  for(int i = 1; i <= m; i++) {
    for(int j = 1; j <= n; j++) {
      B[i][j] = B[i-1][j] + B[i][j-1] + A[i-1][j-1] - B[i-1][j-1];
    }
  }
  
  return B[x2+1][y2+1] - B[x2+1][y1] - B[x1][y2+1] + B[x1][y1];
}

和为K的字数组

LeetCode560

两数之和+前缀和

两数之和就是哈希表存值出现的次数，然后加入，然后再加上前缀和可以实现O(n)的时间复杂度。

如果不加哈希表，用双循环+前缀和就是O(n^2)，不是很理想

差分数组(Difference Array)

差分数组的思想是基于前缀和的，主要适用于频繁对原始数组的某个区间的元素进行增减。

Leetcode1109

Leetcode1094

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int[] difference(int[] nums, int x1, int x2, int val) {
  if(nums.length <= 0) return;
  int[] diff = new int[nums.length];
  diff[0] = nums[0];
  // 差分数组初始化
  for(int i = 0; i < nums.length; i++) {
    diff[i] = nums[i] - nums[i-1];
  }
  
  // 加减值
  diff[x1] += val;
  if(x2 + 1 < diff.length)
    diff[x2 + 1] -= val;
  
  // 输出数组为差分数组的和
  int[] res = new int[diff.length];
  res[0] = diff[0];
  for (int i = 1; i < diff.length; i++) {
    res[i] = res[i - 1] + diff[i];
  }
  return res;
}

快速排序、归并排序、快速选择

Leetcode912

快速排序模版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class quickSort{
  public static int[] sortArray(int[] nums) {
    // Shuffle the array.
    shuffle(nums);
    sort(nums, 0, nums.length - 1);
    return nums;
  }
  
  public static void sort(int[] nums, int lo, int hi) {
    if (lo > hi) return;
    
    int p = partition(nums, lo, hi);
    sort(nums, lo, p-1);
    sort(nums, p+1, hi);
  }
  
  public static int partition(int[] nums, int lo, int hi) {
    int pivot = nums[lo];
    int i = lo + 1, j = hi;
    
    while (i<=j) {
      while(i < hi && nums[i] <= pivot){
        i++;
      }
      
      while(j > lo && nums[j] > pivot) {
        j--;
      }
      
      if(i>=j) {
        break;
      }
      swap(nums, i, j);
    }
    swap(nums, lo, j);
    return j;
  }
  
  public static void shuffle(int[] nums) {
    Random rand = new Random();
    int n = nums.length;
    
    for(int i = 0; i<n; i++) {
      int r = i + rand.nextInt(n - i);
      swap(nums, i, r);
    }
    
  }
  // Swap the two element of array.
  public static void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }
}

归并排序模版

Leetcode912

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class mergeSort{
  private static int[] temp;
  
  public static void sortArray(int[] nums){
    temp = new int[nums.length];
    
    sort(nums, 0, nums.length-1);
    return;
  }
  
  private static void sort(int[] nums, int lo, int hi){
    if(lo == hi) {
      return;
    }
    
    int mid = lo + (hi-lo)/2;
    sort(nums, lo, mid);
    sort(nums, mid+1, hi);
    merge(nums, lo, mid, hi);
  }
  
  private static void merge(int[] nums, int lo, int mid, int hi){
    for(int i = lo; i <= hi; i++){
      temp[i] = nums[i];
    }
    
    int i = lo, j = mid + 1;
    for(int p = lo; p < hi; p++){
      if(i == mid + 1) {
        nums[p] = temp[i++];
      } else if (j == hi + 1){
        nums[p] = temp[j++];
      } else if (temp[i] > temp[j]){
        nums[p] = nums[j++];
      } else {
        nums[p] = nums[i++];
      }
    }
  }
}

快速选择模版

剑指Offer40

Leetcode215

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
    public int topK(int[] nums, int k) {
        shuffle(nums);
        int lo = 0, hi = nums.length - 1;
        int p =  partition(nums, lo, hi);
        while(lo <= hi){
            if(p<k){
                hi = p-1;
            } else if(p>k){
                lo = p+1;
            } else {
                return nums[p];
            }
        }
        return -1;
    }

    public int partition(int[] nums, int lo, int hi) {
        int pivot = nums[lo];
        int i =  lo + 1, j = hi;

        while(i<=j) {
            while(i < hi && nums[i] <= pivot){
                i++;
            }
            while (j > lo && nums[j] > pivot) {
                j--;
            }

            if(i>=j) break;

            swap(nums, i, j);
        }
        swap(nums, j, lo);
        return j;
    }

    public void shuffle(int[] nums){
        Random rand = new Random();
        for(int i = 0; i<nums.length; i++) {
            int r = i + rand.nextInt(nums.length - i);
            swap(nums, i, r);
        }
    }

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

逆序对(Reverse pairs)

剑指offer51

1