算法基础学习笔记——⑥双指针

命运之光

发布于 2024-03-20 10:52:14

920

发布于 2024-03-20 10:52:14

文章被收录于专栏：我在本科期间写的文章

✨博主：命运之光 ✨专栏：算法基础学习

前言：算法学习笔记记录日常分享，需要的看哈O(∩_∩)O，感谢大家的支持！

✨双指针

双指针算法的核心思想：

for(int i=0;i<n;i++)

for(int j=0;j<n;j++)

O(n^2)

将上面的朴素算法优化到O(n)

🍓双指针模板：

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

常见问题分类：

(1) 对于一个序列，用两个指针维护一段区间

(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

🍓例题：统计日志

#include <iostream>
#include <algorithm>
using namespace std;
const int N=100000+5;
typedef struct Log{
int ts,id;
}Log; 
Log logs[N];
//(tk-D,tk]
int n,d,k; 
int cnt[N];//cnt[i]始终存储的是连续d分钟内id=i的帖子的点赞量 
bool rt[N]; 
bool cmp(Log qian,Log hou){
    if(qian.ts<hou.ts)
    	return true;
    return false;
}
int main(){
    scanf("%d%d%d",&n,&d,&k);
    int m=0;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&logs[i].ts,&logs[i].id);
        m=max(m,logs[i].id);
    }
    sort(logs+1,logs+n+1,cmp); 
    for(int i=1,j=1;i<=n;i++){//i和j始终维护长度小于d的区间 
        cnt[logs[i].id]++; 
        while(logs[i].ts-logs[j].ts>=d){
            cnt[logs[j].id]--;
            j++;
    	}
        if(cnt[logs[i].id]>=k){
        	rt[logs[i].id]=true;
        }
    }
    for(int i=0;i<=m;i++){
        if(rt[i]==true)
        	printf("%d\n",i);
    }
}

🍓例题：统计子矩阵

#include <iostream>
using namespace std;
const int N=510;
int n,m,k; 
int s[N][N];
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>s[i][j];
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];
        }
    }
    long long ans=0;
    for(int l=1;l<=m;l++){
        for(int r=l;r<=m;r++){
            for(int d=1,u=1;d<=n;d++){
                while(u<=d&&(s[d][r]-s[d][l-1]-s[u-1][r]+s[u-1][l-1]>k))
                	u++;
                if(u<=d)
                	ans+=d-u+1;
            }
        }
    }
    cout<<ans<<endl;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-03-19，如有侵权请联系 cloudcommunity@tencent.com 删除

指针