首页 > 其他分享 >AcWing 799. 最长连续不重复子序列

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

时间:2024-03-30 10:34:12浏览次数:25  
标签:右移 次数 int 重复子 799 cin ++ -- AcWing

原题链接:https://www.acwing.com/problem/content/801/

题目分析

用数组记录每个元素出现的次数,遍历以第i个元素为结尾的[i,j]区间的最长长度

显然[i-1,j]必然达到最大,所以每次重复会发生在新增添的a[i]上,j右移直到到达i

和暴力做法的区别就在于指针不会回退

代码细节

每次先把s[a[j]]--,再j++

c++代码

# include <iostream>
using namespace std;

const int N = 100010;
int a[N], s[N];

int main()
{
    int n, r = 0;
    cin >> n;

    for (int i = 0, j = 0; i < n; ++ i)
    {
        cin >> a[i];
        ++ s[a[i]];
        while (s[a[i]] > 1) -- s[a[j++]]; // 先减次数后右移
        r = max(r, i - j + 1) ;
    }
    cout << r;

    return 0;
}

标签:右移,次数,int,重复子,799,cin,++,--,AcWing
From: https://blog.csdn.net/boomgloom/article/details/137143288

相关文章

  • AcWing 800. 数组元素的目标和
    原题链接:https://www.acwing.com/problem/content/802/题目分析数组是升序的,a[i]从小变大,b[j]从大变小。a代表目前可能匹配的a中最小值,若与目前b之和仍然大于k则必然j--;i从0开始从前往后遍历;j从m-1开始从后向前遍历;和纯暴力的O(n2) 算法的区别就在于:j指针不会......
  • AcWing刷题-空调
    空调差分:N=int(input())p=list(map(int,input().split()))t=list(map(int,input().split()))d,s=[0]*100010,[0]*100010foriinrange(N):d[i]=p[i]-t[i]foriinrange(N):s[i]+=d[i]s[i+1]-=d[i]ans=0foriinrange(N+1):......
  • AcWing—最短Hamilton路径
    91.最短Hamilton路径-AcWing题库所需知识:二进制状态压缩,动态规划假设现在有六个点:j/i012345002451312065312460832355805441335035312430起点为0终点为5,假设现在走到终点前一点,不妨设该点为4,即现在要确定从0到4,最少要走多远,起点为1终点为4,现有六条路可以选择:first:0–......
  • Acwing 129. 火车进栈
    https://www.acwing.com/problem/content/description/131/输入样例:3输出样例:123132213231321#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;typedefpair<int,int>PII;constLLMAXN=1e18,MINN=-MAXN,INF=0x3f3f3f3f;constLLN=......
  • [正常题解]Acwing.5308 公路
    ​首先需要理解一个证明:​ 假设我们有三个点,前两个点价格为\(a_1,\a_2\),距离为\(v_1,\v_2\)那么就有式子:\(\frac{a_1\timesv_1}{d}+\frac{a_2\timesv_2}{d}\式①\),和式子\(\frac{a_1\timesv_1}{d}+\frac{a_1\timesv_2}{d}\式子②\)$\rightarrow\frac{1}{d}(......
  • Acwing 1111. 字母
    https://www.acwing.com/problem/content/1113/#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;typedefpair<int,int>PII;constLLMAXN=1e18,MINN=-MAXN,INF=0x3f3f3f3f;constLLN=200200,M=2020;LLn,m,maxn=1;charc[M][M];ma......
  • Acwing 1491. 圆桌座位
    https://www.acwing.com/problem/content/1493/输入样例1:4112输出样例1:2输入样例2:10512345678910输出样例2:112512#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;typedefpair<int,int>PII;constLLMAXN=1e18,MINN=-MAXN,I......
  • lanqiao106. 正则问题 (第八届蓝桥杯C++A组)或者 acwing 1225. 正则问题
    问题:知识补充:1. 正则表达式的计算①括号代表优先计算,②或符号代表二选一。比如给的例子:((xx|xxx)x|(x|xx))xx 2. 字符串的语法问题:string是字符串的类型,使用的时候也使像字符一样使用,加入定义stringstr,那么使用的时候要写成str[]思考:妈呀一开始我不会算正则表达......
  • 补|(52/60)最长递增子序列、最长连续递增序列、最长重复子数组
    子序列问题最长递增子序列leetcode:300.最长递增子序列动态规划代码实现/*以nums[i]结尾的(含)递增子序列最长为dp[i]dp[i]由dp[0~i-1]的最大值推出if(nums[i]>nums[j])dp[i]=max(dp[i],dp[j]+1);//如果严格递增dp[0]=1;其余为0正序遍历*/classSol......
  • AcWing 730. 机器人跳跃问题
    Problem:AcWing730.机器人跳跃问题文章目录思路解题方法复杂度Code思路这是一个二分查找的问题。我们需要找到机器人的最小初始能量,使得它能够完成所有的跳跃。我们可以通过二分查找来找到这个最小的初始能量。我们从最小能量1开始,到最大能量100000(因为题目中......