[数据结构与算法] [AcWing算法基础课] Chapter1 基础算法（三）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> [AcWing算法基础课] Chapter1 基础算法（三） -> 正文阅读

[数据结构与算法][AcWing算法基础课] Chapter1 基础算法（三）

文章目录

双指针算法

我们在快速排序和归并排序里就已经用到双指针算法了。

第一类：第一个指针指向序列1，第二个指针指向序列2

第二类：两个指针指向同一个序列
在这里插入图片描述

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

核心思想：将朴素算法优化到O(n)

问题1：有一个形如abc def hij的字符串，请输出每个单词（不含空格），每个单词占一行。

#include <iostream>
#include <string>
using namespace std;

int main(){
    string str;
    getline(cin,str);
    //cout<<str<<endl;
    int n=str.size();
    for(int i=0;i<n;i++){
        int j=i;
        while(j<n && str[j]!=' ') j++;
        for(int k=i;k<j;k++) cout<<str[k];
        cout<<endl;
        i=j;
    }
    return 0;
}

输入：
abc def ghi
===============
输出：
abc
def
ghi

AcWing 799. 最长连续不重复子序列

我们规定，指针i是终点，指针j是起点，先枚举终点再枚举起点。

//暴力做法 O(n^2)
for(int i=0;i<n;i++){
	for(int j=0;j<=i;j++){
		if(check(j,i)){
			res=max(res,i-j+1);
		}
	}
}

指针j的含义：j往左最远能到什么地方

优化思路：

我们枚举终点i的思路和朴素算法是一样的，看一下以每一个i为右端点的区间，它的左端点离它最远是在什么位置。

我们每一次将终点i移动一个位置，再去求一下新的j最左可以在什么位置。

当终点向后移动时，j一定不会往前走，具有单调性。所有可以优化朴素做法。
在这里插入图片描述

//双指针算法：O(n)
for(int i=0;i<n;i++){
	//check查看j,i之间有没有重复元素
	//只要j和i之间有重复元素，就把j向后移动一位，直到j和i之间没有重复元素
	while(j<=i && check(j,i)) j++;
	res=max(res,i-j+1);
}

#include <iostream>
using namespace std;
const int N=100010;
int n;
int a[N];
//s里存的是当前j到i的区间里，每一个数出现的次数
int s[N];

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    int res=0;
    for(int i=0,j=0;i<n;i++){
        //每一次加入新的数a[i]
        s[a[i]]++;
        //所以如果有重复的数，就一定是a[i]重复了
        while(s[a[i]]>1){
            s[a[j]]--;
            j++;
        }
        res=max(res,i-j+1);
    }
    cout<<res<<endl;
    return 0;
}

位运算

应用1：求n的二进制表示中第k位

n=15= $1111)_2$

先把第k位移到最后一位 n>>k

再看一下个位是几 x&1

所以公式为：n>>k&1

应用2：lowbit(x)的作用是返回x的最后一位1

x= $1010)_2$

lowbit(x)= $10)_2$

x= $101000)_2$

lowbit(x)= $1000)_2$

公式：x&-x

-x是补码，是原码的取反加一，即 -x=~x+1
在这里插入图片描述
常见应用：每次把最后一位1减掉，统计二进制数x里1的个数

AcWing 801. 二进制中1的个数

#include <iostream>
using namespace std;
int n;

int lowbit(int x){
    return x&-x;
}

int main(){
    scanf("%d",&n);
    while(n--){
        int x;
        scanf("%d",&x);
        int cnt=0;
        while(x!=0){
            x-=lowbit(x);//每次减去x的最后一位1
            cnt++;
        }
        cout<<cnt<<" ";
    }
    return 0;
}

离散化

（这里特指整数的有序的离散化）

我们现在有一些数值，它们的值域是[0,10^9] ，但是这些数的个数比较少，个数在[0,10^5]之间

这些数值的特点是：值域跨度很大，但是数量不多，比较稀疏

在有些情况下，我们可能需要以这些值为下标来解决问题，如果不做处理直接开一个数组，这是非常不现实的。

因此就需要把这个数值序列映射到从0或1开始的自然数

在这里插入图片描述
如何找出一个数x离散化后的值是多少呢？我们下面来分析一下。

我们就用这个数的下标当作它离散化后的值，所以二分查找就可以找到数x在alls里的下标。
在这里插入图片描述

AcWing 802. 区间和

思路

把所有用到的下标存入alls内，排序去重，然后调用find函数将其映射到从1开始的自然数。

对整数x加上c就是：先求出x离散化后的值k，然后在离散化后的序列上进行a[k]+=c

在求[l,r]之间所有数的和时，先把l和r离散化到对应的下标位置 $K_l$ $K_r$ ，再求一下a[ $K_l$ ]到a[ $K_r$ ]之间的所有数的和就可以了（使用前缀和）

pair的用法C++ pair的基本用法总结（整理）
一位大佬给这道题写的超详细题解AcWing 802. 区间和

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//用pair存放x和c以及l和r
typedef pair<int,int> PII;
const int N=300010;
int n,m;
//a[N]是离散化后的数组，s[N]是前缀和数组
int a[N],s[N];
//alls是存放待离散化的数的容器
vector<int> alls;
//add存的是x和c query存的是l和r
vector<PII> add,query;

//find函数是用来离散化一个数的
int find(int 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;
}

int main(){
    scanf("%d%d",&n,&m);
    //准备操作：把数据读入，并且分别放到相应的容器中
    while(n--){
        int x,c;
        scanf("%d%d",&x,&c);
        add.push_back({x,c});
        alls.push_back(x);
    }
    while(m--){
        int l,r;
        scanf("%d%d",&l,&r);
        query.push_back({l,r});
        alls.push_back(l);
        alls.push_back(r);
    }
    //对alls进行排序和去重
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()), alls.end());
    //此时alls容器里的数据虽然去重了，但是仍然没有离散化
    //下面是添加操作
    for(auto item:add){
        //调用find函数把item.first，即题目中的x离散化
        int t=find(item.first);
        a[t]+=item.second;
    }
    //求前缀和 [alls.size()是因为离散化后，只是范围缩小，个数并没有改变]
    for(int i=1;i<=alls.size();i++) s[i]=s[i-1]+a[i];
    //下面是询问操作
    for(auto item:query){
        int l=find(item.first),r=find(item.second);
        cout<<s[r]-s[l-1]<<endl;
    }
    return 0;
}

自己造轮子实现一个unique函数
在这里插入图片描述

#include <iostream>
#include <vector>
using namespace std;

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

int main(){
    vector<int> a={1,2,2,2,3,3,3,3,3,4,4,5,6,6,7};
    cout<<unique(a)<<endl;
    return 0;
}
//结果是6

区间合并

有很多个区间，如果两个区间有交集，就把它们合并成同一个区间

绿色为合并后的区间
在这里插入图片描述
思路：

先按照左端点的排序规则对所有区间进行排序

然后维护一个区间a，a后面的区间b和区间a可能有三种关系
在这里插入图片描述

区间b不可能在区间a前面，即区间b的左端点一定小于等于区间a的左端点，这是因为我们已经按照左端点的排序规则进行排序了。

情况为1（包含）时我们维护的区间不变，不需要操作；情况为2（有交集）时我们将区间a延长，情况为3（没有交集）时我们就可以把区间a放入答案中去，并将区间更新为b

当区间b和区间a没有交集时，说明区间b以及区间b后面的所有区间都不和a相交了，我们就将维护的区间更新为区间b

AcWing 803. 区间合并

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int,int> PII;
int n;
vector<PII> segs;

bool cmp(PII a,PII b){
    if(a.first!=b.first) return a.first<b.first;
    else return a.second<b.second;
}

void merge(vector<PII> &segs){
    vector<PII> res;
    sort(segs.begin(),segs.end(),cmp);
    //我们把第一个维护的区间设置成负无穷到负无穷
    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;
}

int main(){
    scanf("%d",&n);
    while(n--){
        int l,r;
        scanf("%d%d",&l,&r);
        segs.push_back({l,r});
    }
    merge(segs);
    cout<<segs.size()<<endl;
    return 0;
}