lapt BlogPostsTagsGallerydemogameLeetCode
力扣算法：基础算法
|leetcode

基础算法

数组

排序

快排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void quickSort(int arr[], int left, int right) {
    int pivot = arr[left];
    int l = left, r = right;
    while (l < r) {
        // 顺序很重要，先找右边的
        while (l < r && arr[r] >= pivot) r--;
        arr[l] = arr[r];
        while (l < r && arr[l] <= pivot) l++;
        arr[r] = arr[l];
    }
    // 这样就保证l左边的都是小于pivot的，右边的都是大于pivot的
    arr[l] = pivot;
    if (l + 1 < right) quickSort(arr, l + 1, right);
    if (left < l - 1) quickSort(arr, left, l - 1);
}

为什么快排要先从右往左找？

因为 i 从左往右查找的话，每次停下来的位置对应的元素必然比基准要大，如果这时[跳出循环]的话，这个较大元素就会被换到前面，得到的结果就是错的；而先从右往左查找的话，停下来的位置对应的元素必然比基准要小，如果这时跳出循环的话，这个较小元素就会被换到前面。

另一种：使用随机选择基准

因为有些测试用例很坑，这样使用最左边元素作为基准的写法，对于包含大量重复元素的数组，每轮的哨兵划分都可能将数组划分为长度为 1 和 n-1 的两个部分，这种情况下快速排序的时间复杂度会退化至 O(n^2)

一种经典的实现方式就是三路快排（Quick Sort 3 Ways）将整个数组分成三部分，即小于 v、等于 v 和大于 v。

资料

image-20231116000211215 
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
void quickSort(int arr[], int left, int right) {
    if (left >= right) {
        return;
    }
    int pivot = arr[left];
    int lt = left;          // arr[left+1...lt] <   pivot   小于基准的区间
    int gt = right + 1;     // arr[gt...right]  >   pivot   大于基准的区间
    int i = left + 1;       // arr[lt+1...i)    ==  pivot   等于基准的区间
    while (i < gt) {
        if (arr[i] < pivot) {
            // 把这个小于基准的，交换到小于区间的结尾，并更新小于基准区间的结尾
            swap(arr[i], arr[lt + 1]);
            lt++;
            i++;
        } else if (arr[i] > pivot) {
            // 把这个大于基准的，交换到大于区间的开头
            swap(arr[i], arr[gt - 1]);
            gt--;
        } else {
            i++;
        }
    }
    // 结束循环时候三个区间划分：
    // 小于：[left, lt-1]
    // 等于：[lt, gt-1]
    // 大于：[gt, right]
    swap(arr[left], arr[lt]);
    quickSort(arr, left, lt - 1);   // 小于基准的区间
    quickSort(arr, gt, right);       // 大于基准的区间
}

数组去重

1
2
3
4
5
6
7
8
9
10
11
vector<int> nums = {1,1,1,2,3,3,3,7};
vector<int> N(nums);

int slow = 0, fast = 0;
while (fast < N.size()) {
    while (fast < N.size() && N[fast] == N[slow]) fast++;
    slow ++;
    if (fast < N.size()) N[slow] = N[fast];
}
// 重置长度
N.resize(slow);

二分查找

闭区间写法：

  1. 找到一个有序数组中第一个大于k的数：FFFFFFTTTTTTT (找第一个满足的)

    • L和R分别指向询问的左右边界，即闭区间 [L, R]
    • M指向正在询问的数

  2. 如果 (M == false) —> [L, M] 都是 false，剩余不确定的区间是 [M+1, R] —> 下一步 L = M+1

  3. 如果 (M == true) —> [M, R] 都是 true，剩下的不确定区间是 [L, M-1] —> 下一步 R = M-1

  4. 【循环不变量】

    • L-1 一定指向的是 False
    • R+1 一定指向的是 True

  5. 因此循环结束后，R+1就是我们要找的数，此时R+1==L，所以答案也可以用L表示

  6. 如果数组中都是F，那么L会一直往右移动，直到等于R+1，此时L也就是等于数组长度

1
2
3
4
5
6
7
8
9
10
11
def lower_bound(nums: List[int], target: int) -> int:
    left = 0
    right = len(nums) - 1  # 闭区间 [left, right]

    while left <= right:  # 区间不为空
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1  # [mid+1, right]
        else:
            right = mid - 1  # [left, mid-1]
            return left

左闭右开区间：更改(M == true)情况 [L, M-1] --> [L, M) 所以 R = M

1
2
3
4
5
6
7
8
9
10
11
def lower_bound(nums: List[int], target: int) -> int:
    left = 0
    right = len(nums)  # 左开右闭区间 [left, right)

    while left < right:  # 区间不为空
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1  # [mid+1, right]
        else:
            right = mid  # [left, mid)
            return left

开区间：

  • (M == false)情况：[M+1, R] --> [M, R]
  • [(M == true)情况：[L, M-1] --> [L, M)
1
2
3
4
5
6
7
8
9
10
11
def lower_bound(nums: List[int], target: int) -> int:
    left = -1
    right = len(nums)  # 开区间 (left, right)

    while left +1 < right:  # 区间不为空
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid  # [mid+1, right]
        else:
            right = mid  # [left, mid)
            return right

区间和

前缀和

树状数组

灵神讲解

视频可视化

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 NumArray {
private:
    vector<int> nums;
    vector<int> tree;	// 存放关键区间的sum，tree[i]，表示[i-lowbit(i)+1, i]的关键区间和。

    int prefixSum(int i) {
        int s = 0;
        // lowbit(i) = i & -i
        // i = i - lowbit(i)
        for (i; i > 0; i -= (i & -i)) {		
            sum += tree[i];
        }
        return s;
    }

public:
    NumArray(vector<int> &nums) : nums(nums.size()), tree(nums.size() + 1) {
        // 创建的时候更新tree数组
        for (int i = 0; i < nums.size(); i++) {
            update(i, nums[i]);
        }
    }

    void update(int index, int val) {
        // 修改nums中的元素，并把包含这个元素的关键区间更新。
        int delta = val - nums[index];
        nums[index] = val;
        // lowbit(i) = i & -i
        // i = i + lowbit(i)
        for (int i = index + 1; i < tree.size(); i += i & -i) {
            // 只要区间右端点的值，加上这个delta，就完成了更新
            tree[i] += delta;
        }
    }

    int sumRange(int left, int right) {
        // 求和 [left, right] = [1, right + 1] - [1, left]
        return prefixSum(right + 1) - prefixSum(left);
    }
};

关键区间：

  • 如果 i 是 2的幂，那么 [1, i] 无需拆分。
  • 如果 i 不是 2 的幂，那么先拆分出一个最小的 2 的幂，记作lowbit(i)（例如 6拆分出 2），得到长为 lowbit(i) 的关键区间 [i-lowbit(i)+1, i]，问题转换成剩下的[1,i−lowbit(i)] 如何拆分，这是一个规模更小的子问题。

举个例子：

13 = 8 + 4 + 1

前缀[1, 13] 拆分成长度为 8，4，1 的关键区间：[1, 8], [9, 12], [13, 13]

线段树

leetcode