基础算法

发表于 更新于 分类于 ， 阅读次数： 本文字数： 954 阅读时长 ≈ 3 分钟

包括二分、前缀和、差分、双指针

二分

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
/*整数*/
bool check(int x) {/* ... */} // 检查x是否满足某种性质

/*区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：*/
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
/*区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：*/
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;
}
/*浮点数*/
bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

前缀和

例题：给定 $n$ 个正整数组成的数列 $a_1, a_2, \cdots, a_n$ 和 $m$ 个区间 $[l_i,r_i]$，分别求这 $m$ 个区间的区间和。

前缀和：「数列的前 n 项的和」

性质：$S_n - S_{n-r}=a_{n-r+1}+···+a_n$，可以快速求出区间和

多维前置和

  • 基于容斥定理 : ($A_i$表示集合)

二维前缀和：$sum_{i,j}=sum_{i-1,j}+sum_{i,j-1}-sum_{i-1,j-1}+a_{i,j}$

  • 基于DP的高维前缀和：

二维：

1
2
3
4
5
6
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        a[i][j] += a[i - 1][j];
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        a[i][j] += a[i][j - 1];

三维：

1
2
3
4
5
6
7
8
9
10
11
12
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        for(int k = 1; k <= n; k++) 
            a[i][j][k] += a[i - 1][j][k];
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        for(int k = 1; k <= n; k++)
            a[i][j][k] += a[i][j - 1][k];
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        for(int k = 1; k <= n; k++)
            a[i][j][k] += a[i][j][k - 1];

核心思想：一维一维来处理

复杂度$n·n^x$

树上前缀和

差分

差分算法：

$$
b_i=\begin{cases}a_i-a_{i-1},&i \in[2,n] \ a_1,&i=1\end{cases}
$$

双指针

同向双指针

条件：

  1. 单调性
  2. 连续序列

时间复杂度：O(左指针遍历+右指针遍历)

例题：

长度最小的子数组

相向双指针

以二数和为例，如果暴力求二数和的所有情况，时间复杂度是 $O(n^2)$ 级别；

将数组排序，选择最大最小两数，其和与target数值进行比较，我们可以用$O(1)$ 的复杂度去获取$O(n)$ 的信息，从而优化

两数之和 II - 输入有序数组

参考代码：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        int left = 0, right = numbers.size() - 1;
        for (;;) { // left < right
            int s = numbers[left] + numbers[right];
            if (s == target) return {left + 1, right + 1};
            s > target ? --right : ++left;
        }
    }
};

三数之和

参考代码：

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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            vector<vector<int>> ans;
            int n = nums.size();
            for(int i = 0; i < n - 2; ++i){
                int x = nums[i];
                if( i && x == nums[i - 1])continue;
                if( x + nums[i + 1] + nums[i + 2] > 0)break;
                if( x + nums[n - 2] + nums[n - 1] < 0)continue;
                int j = i + 1, k = n - 1;
                while(j < k){
                    int s = x + nums[j] + nums[k];
                    if(s > 0) --k;
                    else if(s < 0) ++j;
                    else{
                        ans.push_back({x,nums[j],nums[k]});
                        for(++j; j < k && nums[j] == nums[j - 1]; ++j);
                        for(--k; k > j && nums[k] == nums[k + 1]; --k);
                    }
                } 
            }
            return ans;
    }
};

近似三数和

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
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int ans = 0;
        int temp = 0xFFFFFFF;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        if(target >= nums[n - 1] + nums[n - 2] + nums[n - 3])
            return nums[n - 1] + nums[n - 2] + nums[n - 3];
        if(target <= nums[0] + nums[1] + nums[2])
            return nums[0] + nums[1] + nums[2];
        for(int i = 0; i < n - 2; i++){
            int j = i + 1;
            int k = n -1;
            while(j < k){
                int s =nums[i] + nums[j] + nums[k];
                if(s == target){ans = s;break;}
                if(abs(s-target) < temp){temp = abs(s-target);ans = s;}
                else if(s > target) --k;
                else ++j;
            }
        }
        return ans;
    }
};

参考链接

[1].高维前缀和总结(sosdp)

[2].基础算法精讲-灵茶山艾府)

推荐讲师：灵茶山艾府（2023力扣榜单前5）