Decade
Basic Algorithm
Zhongjun Qiu 元婴开发者
  2022-08-22 15:45:43   2025-04-29 21:27:59    1.4k Words  6 Mins  

梦开始的地方

1. 二分

不多说，基础中的基础。

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
int binary_search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if(nums[mid] == target) {
            // 直接返回
            return mid;
        }
    }
    // 直接返回
    return -1;
}

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            // 别返回，锁定左侧边界
            right = mid - 1;
        }
    }
    // 最后要检查 left 越界的情况
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}


int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            // 别返回，锁定右侧边界
            left = mid + 1;
        }
    }
    // 最后要检查 right 越界的情况
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}

2. 位运算

  • 基础位操作

获取一个数二进制的某一位：

1
2
// 获取 a 的第 b 位，最低位编号为 0
int getBit(int a, int b) { return (a >> b) & 1; }

将一个数二进制的某一位设置为 0：

1
2
// 将 a 的第 b 位设置为 0 ，最低位编号为 0
int unsetBit(int a, int b) { return a & ~(1 << b); }

将一个数二进制的某一位设置为 1：

1
2
// 将 a 的第 b 位设置为 1 ，最低位编号为 0
int setBit(int a, int b) { return a | (1 << b); }

将一个数二进制的某一位取反：

1
2
// 将 a 的第 b 位取反 ，最低位编号为 0
int flapBit(int a, int b) { return a ^ (1 << b); }
  • 2 的幂次运用

判断一个数是不是 2 的非负整数次幂：

1
bool isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }

==lowbit== 一个数二进制表示从低往高的第一个 连同后面的零，如 1010 的 lowbit 是 0010

1
2
3
int lowbit(int x) {
  return x & -x;
}
  • 模拟集合操作（二进制枚举）

一个数的二进制表示可以看作是一个集合（ 0 表示不在集合中， 1 表示在集合中）。比如集合 {1，3，4，8} ，可以表示成（100011010） 。而对应的位运算也就可以看作是对集合进行的操作。

操作 集合表示 位运算语句
交集 a ∩ b a & b
并集 a ∪ b a
补集 ā ~a （全集为二进制都是 1）
差集 a \ b a & (~b)
对称差 a△b a ^ b

子集

3. 前缀和与差分

  • 前缀和

  • 一维

K 倍区间

  • 二维

给以为左上角，为右下角的子矩阵中的所有元素加上：

P1719 最大加权矩形

  • 差分

这种策略的定义是令 简单性质：

  • ai 的值是 bi 的前缀和，即
  • 计算 ai 的前腏和 sum 它可以维护多次对序列的一个区间加上一个数，并在最后询问某一位的数或是多次询问某一位的 数。注意修改操作一定要在查询操作之前。

地毯

4. 排序

4.1. 快排

  • 递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private static void sorted(int[] n, int low, int up) {
    if (low >= up) return;
    int randIdx = new Random().nextInt(up-low+1)+low;swap(n, up, randIdx);
    // 一般 pivot = n[up] 就可以了
    int pivot = n[up], idx = low-1;
    for (int i = low;i < up;++i){
        if (n[i] <= pivot) swap(n, ++idx, i);
    }
    swap(n, ++idx, up);
    sorted(n, low, idx-1);
    sorted(n, idx+1, up);
}
private static void swap(int[] n, int up, int randIdx) {
    int tp = n[up];
    n[up] = n[randIdx];
    n[randIdx] = tp;
}
  • 用于线性求第 K 大的数
1
2
3
4
5
6
7
8
9
int k;
...
private void sorted(int[] n, int low, int up) {
    ...
    //只有下面不同
    if (idx == k) return;
    else if (idx > k) sorted(n, low, idx-1);
    else sorted(n, idx+1, up);
}

数组中的第 K 个最大元素

4.2. 归并

  • 分治
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private static void mergeSort(int[] n, int left, int right) {
    if (left >= right) return;
    int mid = left+(right-left)/2;
    mergeSort(n, left, mid);//左
    mergeSort(n, mid+1, right);//右
    merge(n, left, mid+1, right+1);//合并
}
private static void merge(int[] n, int low, int mid, int up) {
    int loc = 0, s1 = low, s2 = mid;
    int[] arr = new int[up-low];
    while (s1 < mid && s2 < up) {//合并有序数组
        if (n[s1] < n[s2]) arr[loc++] = n[s1++];
        else arr[loc++] = n[s2++];
    }
    while (s1 < mid) arr[loc++] = n[s1++];
    while (s2 < up) arr[loc++] = n[s2++];
    for (int i = 0;i < up-low;i++) {
        n[i+low] = arr[i];
    }
}
  • 逆序对

所谓逆序对，就是对于一个数组 a ，满足 ai > aj且i < j 的数对 (i, j)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int ans = 0;
...
void merge(int[] nums, int left, int mid, int right){
 ...
    while (i<n && j<m){
        if (nums[i]<=nums[j]) tp[idx++] = nums[i++];
            else{
                // 如果nums[i]>nums[j]且i<j 说明原数组中(i, j)已经形成逆序对
                // 又i~mid-1间是已经排好序的 所以逆序对数是 mid-1-i+1 = mid-i
                ans += (mid-i);
                tp[idx++] = nums[j++];
        }
    }
 ...
}

逆序对也可以用 树状数组、线段树 等数据结构求解。这三种方法的时间复杂度都是 O(nlog n)。

5. 单调队列&&滑动窗口

有一个长为 n 的序列 aa，以及一个大小为 k 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private static void max_deque() {
Deque<Integer> q = new LinkedList<>();// 队头 最大值下标  队尾 最小值下标
    for (int i = 0;i < n;i++){
        int cur = a[i];
        while (!q.isEmpty() && a[q.peekLast()] <= cur) q.pollLast();
        q.offerLast(i);
        while (!q.isEmpty() && q.peekFirst() <= i-k) q.pollFirst();
        if (i >= k-1) System.out.print(a[q.peekFirst()]+" ");
    }
}
private static void min_deque() {
    Deque<Integer> q = new LinkedList<>();// 队头 最小值下标  队尾 最大值下标
    for (int i = 0;i < n;i++){
        int cur = a[i];
        while (!q.isEmpty() && a[q.peekLast()] >= cur) q.pollLast();
        q.offerLast(i);
        while (!q.isEmpty() && q.peekFirst() <= i-k) q.pollFirst();
        if (i >= k-1) System.out.print(a[q.peekFirst()]+" ");
    }
}
  • 滑动窗口+贪心

P1638 逛画展

Basic Algorithm
2022/08/22/Basic-Algorithm/
Author
Zhongjun Qiu
Published
2022-08-22 15:45
License
 REWARD AUTHOR
 Comments
Comment plugin failed to load
Loading comment plugin
  1. 1. 二分
  2. 2. 位运算
  3. 3. 前缀和与差分
  4. 4. 排序
    1. 4.1. 快排
    2. 4.2. 归并
  5. 5. 单调队列&&滑动窗口
  1. 1. 二分
  2. 2. 位运算
  3. 3. 前缀和与差分
  4. 4. 排序
    1. 4.1. 快排
    2. 4.2. 归并
  5. 5. 单调队列&&滑动窗口