Acwing - 算法基础课 - 笔记（三）

本是古典何须时尚 2023-01-19 03:27 5阅读 0赞

### 文章目录 ###

*   *  基础算法（三）
     *   *  双指针
         *   *  小结
         *  位运算
         *  离散化
         *  区间合并

## 基础算法（三） ##

这节讲的是双指针算法，位运算，离散化，区间合并

### 双指针 ###

*  2个指针指向不同的序列
    
    比如归并排序
 *  2个指针指向同一个序列
    
    比如快速排序

对于形如

for(int i = 0; i < n; i++) { 
        for(int j = 0; j < n; j++) { 
            
        }
    }

这一类的双层循环，可能可以使用双指针来进行优化，从而能够把时间复杂度从O(n2)降低到O(n)，比如求**一个数组中最长的连续不重复的子序列的长度**

最容易想到的暴力解法是：枚举 i = 0~n，对于每个i，将其看作右端点，尝试找到其左边最远的左端点。

int maxLen = 0;
    for(int i = 0; i < n; i++) { 
        for(int j = 0; j <= i; j++) { 
            // 若[j, i]区间内不包含重复元素
            if(noRepeat(j, i)) maxLen = max(maxLen, i - j + 1);
        }
    }

经过简单的推算，可以得知，当某个`[j, i]`区间内有重复元素，那么对于所有`i + 1`之后的数作为右端点，其左边的最远端点，最多取到`j + 1`。也就是说，随着`i`从左往右移动，每个`i`对应的最远的左端点`j`，也只能单向地从左往右移动。所以可以采用双指针算法，两个指针`i`，`j`最多只需要各自从0走到n（共2n次操作），即可找到答案，时间复杂度为O(n)。

int maxLen = 1;
    for(int i = 0, j = 0; i < n; i++) { 
        while(j <= i && hasRepeat(j, i)) j++;  // 若[j, i]区间内包含重复元素, 右移j
        maxLen = max(maxLen, i - j + 1); // 找到当前i作为右端点, 最长的子序列
    }
    // 其中 hasRepeat 函数检查是否有重复元素, 可以用哈希表，或者开一个数组用计数排序的思路

练习题：[Acwing - 799: 最长连续不重复子序列][Acwing - 799_]

#include<iostream>
    using namespace std;
    
    const int N = 1e5 + 10;
    int n;
    int q[N], c[N];  // 这里对于判断重复, 采用了计数排序的思想, 若数的范围较大, 或者数不是整数, 可以考虑用哈希表
    
    int main() { 
        scanf("%d", &n);
        for(int i = 0; i < n; i++) scanf("%d", &q[i]);
        
        int res = 0;
        for(int i = 0, j = 0; i < n; i++) { 
            c[q[i]]++; // i往后移动一位, 计数加一, 将q[i]这个数纳入判重的集合
            while(c[q[i]] > 1) {   // 若在[j, i]区间内有重复元素的话, 只可能重复新加入的这个q[i], 只需判断q[i]的个数大于1
                // 有重复, j 往右移动一位
                c[q[j]]--; // 将j这个位置的数的计数减1, 即把q[j]从判重的集合中移除
                j++;
            }
            res = max(res, i - j + 1); // 针对该i, 找到最远的左端点j
        }
        printf("%d", res);
        return 0;
    }

练习题：[Acwing - 800: 数组元素的目标和][Acwing - 800_]

#include<iostream>
    using namespace std;
    
    const int N = 1e5 + 10;
    
    int a[N], b[N];
    
    int main() { 
    	int n, m, x;
    	scanf("%d%d%d", &n, &m, &x);
    	for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    	for(int i = 0; i < m; i++) scanf("%d", &b[i]);
    	int i = 0, j = m - 1;
    	while(i < n && j >= 0) { 
    		int sum = a[i] + b[j];
    		if(sum < x) i++;
    		else if(sum > x) j--;
    		else break;
    	}
    	printf("%d %d\n", i, j);
    	return 0;
    }

练习题：[Acwing - 2816: 判断子序列][Acwing - 2816_]

#include<iostream>
    using namespace std;
    const int N = 1e5 + 10;
    int a[N], b[N];
    
    int main() { 
    	int n, m;
    	scanf("%d%d", &n, &m);
    	for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    	for(int i = 0; i < m; i++) scanf("%d", &b[i]);
    
    	int i = 0, j = 0;
    	while(i < n && j < m) { 
    		if(a[i] == b[j]) { 
    			i++;
    			j++;
    		} else j++;
    	}
    	if(i < n) printf("No\n");
    	else printf("Yes\n");
    	return 0;
    }

#### 小结 ####

双指针算法，通常是适用于有两层循环的情况（循环变量分别为`i`，`j`）。首先是写一个暴力的解法，然后观察一下`i`和`j`之间是否存在单调性的关系（即`i`和`j`是否都往着同一个方向移动，不回头）。若`i`和`j`之间存在着这种单调性关系，则我们可以用双指针，来将时间复杂度从O(n2)降低到O(n)。

双指针算法模板

for(int i = 0, j = 0; i < n; i++) { 
        while(j < i && check(i, j)) j++;
        // 具体逻辑
    }

### 位运算 ###

*  获取一个数的二进制的第k位：`x >> k & 1`
    
    即，先将x右移k位，然后和`1`做`与运算`
 *  获取一个数的二进制的最后一位1：`lowbit(x) = x & -x`
    
    如，10的二进制表示是`1010`，则对10做`lowbit`运算，得到`10`（二进制），转为十进制即为2
    
    `lowbit`运算的原理是，`x & -x`，由于`-x`采用补码表示，它等于对x的原码取反再加1，即`-x = ~x + 1`
    
    比如 x 的二进制表示是：
    
    `100101000`，对x取反得
    
    `011010111`，加1得
    
    `011011000`
    
    所以`x & (~X + 1)`，则x的最后一位1，被保留了下来，这个位置后面，两个数全是0，这个位置前面，两个数是取反，做与运算后也全为0。
    
    `lowbit`的最简单的应用：**统计x的二进制表示中，1的个数**。具体的实现方式是：每次对x做`lowbit`运算，并将运算结果从x中减去。循环做下去，直到x被减为0，一共减了多少次，x中就有多少个1。
    
    练习题：[Acwing - 801: 二进制中1的个数][Acwing - 801_ _1]
    
        #include<iostream>
        using namespace std;
        
        const int N = 1e5 + 10;
        int n;
        
        int lowbit(int x) { 
            return x & -x;
        }
        
        int main() { 
            scanf("%d", &n);
            while(n--) { 
                int x;
                scanf("%d", &x);
                int c = 0;
                while(x > 0) { 
                    x -= lowbit(x);
                    c++;
                }
                printf("%d ", c);
            }
            return 0;
        }

### 离散化 ###

有的数组，其元素的**值域很大**，比如数组中的元素取值都是`[0, 10^9]`，但**元素的个数很少**，比如只有1000个元素。

有时（例如计数排序的思想），我们需要将元素的值，作为数组的下标来操作。此时不可能开一个`10^9`大小的数组。

此时我们把这些元素，映射为从0（或者从1）开始的自然数。（也可以理解为对稀疏数组进行压缩）

例子如下

有一个数组a，`[1, 3, 100, 2000, 500000]`（已经排好序），我们把这个数组中的元素，映射为

`[0, 1, 2, 3, 4]`，这个映射的过程，称之为**离散化**

离散化有2个要点：

*  原数组a中若有重复元素，可能需要去重
 *  如何根据`a[i]`，算出其离散化后的值：由于原数组已经排好序，故这里用二分查找即可

离散化的代码模板

// C++
    vector<int> v; // 待离散化的数组
    sort(v.begin(), v.end()); // 将数组先排序
    v.erase(unique(v.begin(), v.end()), v.end()); // 对数组进行去重
    // 进行离散化, 将数组的值依次映射到 0,1,2,3,4,5, ... 等自然数
    
    // 根据数的值, 求出其离散化的值
    int find(int x) { 
        int l = 0, r = v.size() - 1;
        while(l < r) {   // 找到第一个大于等于x的离散化的值
            int mid = l + r >> 1;
            if(v[mid] >= x) r = mid;
            else l = mid + 1;
        }
        return r + 1; // 是否加1, 跟题目相关, 若是前缀和差分等需要下标从1开始, 则需要加1
    }

练习题：[Acwing - 802: 区间和][Acwing - 802_]

// C++, 自己的解法
    // 只针对插入操作涉及到的数组下标, 进行离散化
    #include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    
    const int N = 1e5 + 10;
    
    int index[N], value[N];
    
    void init(vector<pair<int, int>> v) { 
        for(int i = 0; i < v.size(); i++) { 
            index[i + 1] = v[i].first; // 记录原坐标, 这样以来, 在index数组中, i是离散化后的坐标, index[i]是离散化前的坐标
            value[i + 1] = value[i] + v[i].second; // 记录这个坐标累加的值, 构造前缀和
            // 离散化的坐标从1开始
        }
    }
    
    int main() { 
        int n, m;
        scanf("%d%d", &n, &m);
        vector<pair<int, int>> insert;
        while(n--) { 
            int x, c;
            scanf("%d%d", &x, &c);
            insert.push_back({ x, c});
        }
        sort(insert.begin(), insert.end()); // 默认按照 pair 的 first 进行升序排列, 这里没有去重
        // 离散化
        init(insert);
        
        while(m--) { 
            int l, r;
            scanf("%d%d", &l, &r);
            // 因为上面离散化时没有去重, 若对同一个位置x插入了多次, 则x会对应离散化后的多个连续坐标
            // 如 [5,6] [5,7] 表示对x=5的位置, 添加值6和7, 则在离散化后的下标中, 可能x=5会对应 1,2 两个
            // 所以下面取离散化的左边界时, 要取到 >= x 的第一个值
            int ll = 1, lr = insert.size();  // 左边界
            while(ll < lr) { 
                int mid = ll + lr >> 1;
                if(index[mid] >= l) lr = mid;
                else ll = mid + 1;
            }
            // 同样因为没有去重, 这里取右边界时, 要取到 <= x 的最后一个值
            int rl = 1, rr = insert.size(); // 右边界
            while(rl < rr) { 
                int mid = rl + rr + 1 >> 1;
                if(index[mid] <= r) rl = mid;
                else rr = mid - 1;
            }
            // 先预计算出一个结果
            int res = value[rl] - value[ll - 1];
            // 当 l 和 r 二分出来的位置是相同时, [l, r]区间内可能没有任何值
            // 仅当 l <= index[ll] 并且 r >= index[ll] 时, [l, r] 之间才有值, 否则 [l, r]之间没有任何值, 结果应当为0
            if(ll == rl && (l > index[ll] || r < index[ll])) res = 0; 
            printf("%d\n", res);
        }
        return 0;
    }

// C++, 按照yxc的思路的解法
    // 将所有用到的下标先存起来, 对全部下标进行离散化(所有的x, l, r)
    #include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    
    typedef pair<int, int> PII;
    
    const int N = 3e5 + 10; // 用到的下标总数为 n + 2m , 300000 量级
    
    vector<PII> add; // 插入操作
    vector<PII> query; // 询问操作
    vector<int> index; //所有待离散化的下标
    
    int s[N]; // 记录前缀和
    int a[N]; // 记录值
    
    // 进行离散化
    int find(int x) { 
        int l = 0, r = index.size() - 1;
        while(l < r) { 
            int mid = l + r >> 1;
            if(index[mid] >= x) r = mid;
            else l = mid + 1;
        }
        return l + 1; // 离散化后的下标从1开始, 因为需要计算前缀和
    }
    
    vector<int>::iterator unique(vector<int> &v) { 
        // 去除有序数组的重复元素
        int j = 0;
        for(int i = 0; i < v.size(); i++) { 
            if( i == 0 || v[i] != v[i - 1]) v[j++] = v[i];
        }
        
        // j 最后的位置是, 去重后的第一个位置
        return v.begin() + j; // 
    }
    
    int main() { 
        int n, m;
        scanf("%d%d", &n, &m);
        // 读入全部数据
        while(n--) { 
            int x, c;
            scanf("%d%d", &x, &c);
            add.push_back({ x, c});
            index.push_back(x); // 添加待离散化的下标
        }
        while(m--) { 
            int l, r;
            scanf("%d%d", &l, &r);
            query.push_back({ l, r});
            index.push_back(l);// 添加待离散化的下标
            index.push_back(r);
        }
        // 对所有的下标点进行离散化
        sort(index.begin(), index.end()); // 先对 index 排序
        index.erase(unique(index), index.end()); // 对 index 数组进行去重
        
        // 处理插入
        for(int i = 0; i < add.size(); i++) { 
            int p = find(add[i].first); // 找到待插入的位置(离散化后的位置)
            a[p] += add[i].second; // 插入
        }
        
        // 计算前缀和
        for(int i = 1; i <= index.size(); i++) { 
            s[i] = s[i - 1] + a[i]; // 对所有用到的下标, 计算前缀和
        }
        
        // 处理查询
        for(int i = 0; i < query.size(); i++) { 
            int l = find(query[i].first);
            int r = find(query[i].second);
            printf("%d\n", s[r] - s[l - 1]);
        }
        return 0;
    }

值域跨度很大，但是实际用到的数字的个数不多，这种场景适合用离散化

练习题：[美团笔试题: 格子染色][Link 1]

### 区间合并 ###

给定很多个区间，若2个区间有交集，将二者合并成一个区间

做法思路：

1.  先按照区间的左端点进行排序
2.  然后遍历每个区间，进行合并即可（类似双指针的思想）

练习题：[Acwing - 8023: 区间合并][Acwing - 8023_]

#include<iostream>
    #include<vector>
    #include<algorithm>
    
    using namespace std;
    
    typedef pair<int, int> PII;
    
    int main() { 
        
        int n;
        vector<PII> segments;
        scanf("%d", &n);
        while(n--) { 
            int l, r;
            scanf("%d%d", &l, &r);
            segments.push_back({ l, r});
        }
        // 数据读入完毕
        // 排序
        sort(segments.begin(), segments.end());
        int cnt = 0; // 开始计数
        for(int i = 0; i < segments.size(); i++) { 
            if(i == segments.size() - 1) { 
                // 当前的区间是最后一个区间
                cnt++;
                break;
            } else { 
                // 存在后续区间, 进行合并
                int r = segments[i].second; // 当前区间的右边界
                // 当存在后续区间时, 进行循环合并
                while(i + 1 < segments.size()) { 
                    if(segments[i + 1].first > r) break;  // 后一个区间和该区间不存在交集
                    else { 
                        // 存在交集, 更新右边界
                        r = max(r, segments[i + 1].second);
                        i++;
                    }
                }
                cnt++; // 当前区间合并完毕, 计数 + 1
            }
        }
        printf("%d", cnt);
        return 0;
    }

[Acwing - 799_]: https://www.acwing.com/problem/content/801/
[Acwing - 800_]: https://www.acwing.com/problem/content/description/802/
[Acwing - 2816_]: https://www.acwing.com/problem/content/description/2818/
[Acwing - 801_ _1]: https://www.acwing.com/problem/content/803/
[Acwing - 802_]: https://www.acwing.com/problem/content/804/
[Link 1]: https://www.acwing.com/problem/content/761/
[Acwing - 8023_]: https://www.acwing.com/problem/content/805/