基础算法

正文

介绍常用基础算法

1. 快速排序

1
2
3


确定分界点
调整 <x 左边 x >x 右边
递归排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


void quick_sort(int q[], int l, int r) 
{
    if (l >= r) return;
    int x = q[l], i = l - 1, j = r + 1;
    while (i < j) 
    {
        do i++; while (q[i] < x);
        do j--; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

2.归并排序

1
2
3
4


时间复杂度：n*logN  logN 层 每层 n 次
确定分界点 mid = （l+r）/2
递归排序
归并 合二为一 两个数组分别用 tmp1 tmp2 下标进行比较 形成有序的新数组

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


void merge_sort(int q[], int l, int r) 
{
    if (l >= r) return;
    int mid = (l + r) >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int tmp[100010]; // 假设数组长度不超过 1e5
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) tmp[k++] = q[j++];
    for (i = l, j = 0; i <= r; i++, j++)
        q[i] = tmp[j];
}

3.二分排序

1

有单调性一定可以二分 没有单调性也可能可以二分

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


int bsearch_1(int l, int r) 
{
    while (l < r) 
    {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}


int bsearch_2(int l, int r) 
{
    while (l < r) 
    {
        int mid = (l + r + 1) >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

4.高精度

1

数据逆向存储

1）加法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


// C = A + B，A、B为非负整数，按低位到高位存储
vector<int> add(vector<int>& A, vector<int>& B) 
{
    vector<int> C;
    int t = 0;                       // 进位
    for (int i = 0; i < A.size() || i < B.size() || t; ++i) 
    {
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);         // 当前位
        t /= 10;                     // 新的进位
    }
    return C;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


// C = A + B，A、B为非负整数，按低位到高位存储
vector<int> add(vector<int>& A, vector<int>& B) 
{
    vector<int> C;
    if (A.size() < B.size()) return add(B, A); // 保证 A 较长
    int t = 0;                                 // 进位
    for (int i = 0; i < A.size(); ++i) 
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);                   // 当前位
        t /= 10;                               // 新的进位
    }
    if (t) C.push_back(t);                     // 处理最高位进位
    return C;
}

2）减法

 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


// 判断 A >= B
bool cmp(vector<int>& A, vector<int>& B) 
{
    if (A.size() != B.size()) return A.size() > B.size();
    for (int i = A.size() - 1; i >= 0; --i)
        if (A[i] != B[i]) return A[i] > B[i];
    return true;          // 完全相等
}

// C = A - B，调用前需保证 A >= B
vector<int> sub(vector<int>& A, vector<int>& B) 
{
    vector<int> C;
    int t = 0;            // 借位
    for (int i = 0; i < A.size(); ++i) 
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);   // 保证本位非负
        if (t < 0) t = 1;             // 需要借位
        else       t = 0;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back(); // 去掉前导 0
    return C;
}

3）乘法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


// C = A * b，A 为高精度（低位在前），b 为 int
vector<int> mul(vector<int>& A, int b) 
{
    vector<int> C;
    int t = 0;                          // 进位
    for (int i = 0; i < A.size() || t; ++i) 
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);            // 当前位
        t /= 10;                        // 新的进位
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back(); // 去前导 0
    return C;
}

4）除法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


// C = A / b，r 返回余数（A 高位在前，C 低位在前）
vector<int> div(vector<int>& A, int b, int& r) 
{
    vector<int> C;
    r = 0;
    for (int i = 0; i < A.size(); ++i) 
    {   // 从高位到低位
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    // 把结果改成低位在前，去掉前导 0
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

5.前缀和与差分

1）前缀和

1
2
3


sum[i]=sum[i-1]+nums[i] （ sum[0]=0 ）
for (int i = 1; i <= n; ++i) 
	s[i] = s[i - 1] + a[i];

2）二维前缀和

1
2


sum[x1][y1]=sum[x1-1][y1]+sum[x1][y1-1]-sum[x1-1][y1-1]+nums[x1][y1]
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];

1
2


任一区域=sum[x1][y1]-sum[x2][y1]-sum[x1][y2]+sum[x2][y2]
s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];

3）差分

1
2
3
4
5
6


前缀和的逆运算
a1 = b1                  b1 = a1
a2 = b1 + b2             b2 = a2-a1
a3 = b1 + b2 +b3		b3 = a3-a2
	An = B1+....+Bn   A 为 B 的前缀和   B 为 A 的差分
	O（n）  B --> A

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


void insert(int l, int r, int c) 
{
    b[l] += c;
    b[r + 1] -= c;
}

for (int i = 1; i <= n; i ++) 
    insert(i, i, a[i]);
    
    while (m--) 
    {
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c);
    }

4）二维差分

1
2
3
4
5
6
7


void insert(int x1, int y1, int x2, int y2, int c) 
{
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


while (q--) 
{
    int x1, y1, x2, y2, c;
    cin >> x1 >> y1 >> x2 >> y2 >> c;
    insert(x1, y1, x2, y2, c);
}

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];

6.双指针算法

核心是优化

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


for (int i = 0, j = 0; i < n; i++) 
{
    s[a[i]]++;
    while (s[a[i]] > 1) 
    {
        s[a[j]]--;
        j++;
    }
    res = max(res, i - j + 1);
}

7.位运算

(n >> k & 1)          // 取 n 的第 k 位

1
2
3
4
5


lowbit(x) 返回 x 的最后一位 1 
     x    =  1010````1000
     ~x   =  0101````0111
   ~x +1  =  0101````1000
x&(~x +1) =  0000````1000

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


int lowbit(int x) // 返回 x 的最后一位 1
{   
    return x & -x;
}

while (x) // 每次减去 x 的最后一位 1
{
    x -= lowbit(x);
    res++;
}

8.离散化

对分散数据进行映射存储

1
2
3
4
5
6
7
8
9


vector<int>::iterator unique(vector<int> &a) 
{
    int j = 0;
    for (int i = 0; i < a.size(); i++)
        if (!i || a[i] != a[i - 1])
            a[j++] = a[i];
    // a[0] ~ a[j - 1] 保存 a 中所有不重复的数
    return a.begin() + j;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


vector<int> alls;   // 存储所有待离散化的值
sort(alls.begin(), alls.end());   // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素

// 二分求出 x 对应的离散化的值
int find(int x) // 找到第一个大于等于 x 的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r) 
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;   // 映射到 1, 2, ... n
}

9.区间合并

1）按区间左端点排序

2）三种区间

1
2
3


包含     省略
相交     扩充成两个区间的交集 
无交集  保存 更新成下一个区间

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


// 将所有存在交集的区间合并
void merge(vector<PII> &segs) 
{
    vector<PII> res;
    sort(segs.begin(), segs.end());
    int st = -2e9, ed = -2e9;
    for (auto seg : segs) 
    {
        if (ed < seg.first) 
        {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        } 
        else 
        {
            ed = max(ed, seg.second);
        }
    }
    if (st != -2e9) res.push_back({st, ed});
    segs = res;
}

正文

1. 快速排序

2.归并排序

3.二分排序

4.高精度

1） 加法

2） 减法

3） 乘法

4） 除法

5.前缀和与差分

1）前缀和

2）二维前缀和

3） 差分

4） 二维差分

6.双指针算法

7.位运算

8.离散化

9.区间合并

1） 按区间左端点排序

2） 三种区间

1）加法

2）减法

3）乘法

4）除法

3）差分

4）二维差分

1）按区间左端点排序

2）三种区间