本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】瑞学堂瑞瑞的环形花坛【题目描述】瑞瑞在校园里设计了一个环形花坛环上均匀分布着n nn个位置编号为1 11到n nn位置i ii与位置i 1 i1i1相邻位置n nn与位置1 11相邻。每个位置可以种一棵花花的种类用一个整数a i a_iai​表示相同的整数代表同一种花。瑞瑞想要选出一段连续的位置使得这段位置里的花的种类数尽可能多。然而由于环形花坛上的花形成环状这段连续位置不能超过花坛半圈的长度即所选区间的长度不能超过⌊ n / 2 ⌋ \lfloor n/2\rfloor⌊n/2⌋。请你帮瑞瑞计算在满足长度限制的条件下一段连续位置中最多能包含多少种不同的花。【输入】第一行一个整数n nn表示环形花坛的位置数量。第二行n nn个整数a 1 , a 2 , … , a n a_1,a_2,…,a_na1​,a2​,…,an​表示每个位置上花的种类。【输出】输出一行一个整数表示最多包含的不同花的种类数。【输入样例】6 1 2 3 1 2 3【输出样例】3【核心思想】问题分析给定环形数组a [ 1.. n ] a[1..n]a[1..n]a i a_iai​表示花的种类求长度不超过⌊ n / 2 ⌋ \lfloor n/2 \rfloor⌊n/2⌋的连续子数组中不同元素个数的最大值。这是一个环形数组 滑动窗口问题关键在于将环形结构通过复制翻倍转化为线性数组再用双指针维护长度受限的窗口。算法选择环形转线性复制翻倍将数组复制为a [ 1..2 n ] a[1..2n]a[1..2n]其中a [ i n ] a [ i ] a[in] a[i]a[in]a[i]使得任意环形连续区间都对应线性数组上的一个连续子数组滑动窗口双指针维护窗口[ i , j ] [i, j][i,j]保证长度j − i 1 ≤ ⌊ n / 2 ⌋ j - i 1 \leq \lfloor n/2 \rfloorj−i1≤⌊n/2⌋用哈希/数组统计窗口内不同元素个数长度限制处理当窗口长度超过限制时收缩左端点i ii关键步骤数组翻倍读入a [ 1.. n ] a[1..n]a[1..n]令a [ i n ] a [ i ] a[in] a[i]a[in]a[i]i ii从1 11到n nn得到长度2 n 2n2n的线性数组初始化双指针i 1 , j 1 i 1, j 1i1,j1计数数组cnt[]记录各元素出现次数res记录当前窗口不同种类数滑动窗口j jj从1 11遍历到2 n 2n2n长度检查若j − i 1 ⌊ n / 2 ⌋ j - i 1 \lfloor n/2 \rfloorj−i1⌊n/2⌋则右移i iicnt[a[i]]--若变为0 00则res--扩展右端点将a [ j ] a[j]a[j]加入窗口若cnt[a[j]] 0则res然后cnt[a[j]]更新答案ans max(ans, res)输出a n s ansans时间/空间复杂度时间复杂度O ( n ) O(n)O(n)双指针每个位置最多被访问两次入窗一次、出窗一次空间复杂度O ( n ) O(n)O(n)翻倍数组2 n 2n2n和计数数组离散化后种类数不超过n nn双指针 环形处理的核心思想环形转线性的经典技巧复制数组实现O ( 1 ) O(1)O(1)的环形连续区间查询避免取模运算和边界分裂讨论滑动窗口的长度约束通过while循环严格维护窗口长度≤ ⌊ n / 2 ⌋ \leq \lfloor n/2 \rfloor≤⌊n/2⌋保证满足题意计数数组维护不同元素个数res只在元素首次入窗cnt从0 00到1 11和最后出窗cnt从1 11到0 00时变化实现O ( 1 ) O(1)O(1)更新双指针的单调性右指针j jj只增不减左指针i ii只增不减确保线性时间复杂度适用于环形数组的子数组统计问题核心在于复制翻倍消环和双指针维护受限窗口【算法标签】#双指针【代码详解】#includebits/stdc.husingnamespacestd;constintN100005;// 定义数组最大容量为100005intn,res,ans;// n为环形花坛位置数res记录当前窗口内不同花的种类数ans记录最大种类数inta[N*2];// 将环形数组复制一倍展开为线性数组便于处理跨首尾的情况intcnt[N];// cnt[x]记录当前滑动窗口中花的种类x出现的次数mapint,intmp;// mp未使用原代码中用于离散化但直接用数组cnt替代了intmain(){cinn;// 读入环形花坛的位置数量nfor(inti1;in;i)// 读入每个位置的花的种类{cina[i];// 读入第i个位置的花的种类a[in]a[i];// 将数组复制一倍a[n1]a[1], a[n2]a[2], ...}intlenn/2;// 计算最大允许区间长度不超过半圈即floor(n/2)// 双指针滑动窗口i为左端点j为右端点for(inti1,j1;j2*n;j)// j从1遍历到2n枚举所有可能的右端点{// 当窗口长度超过len时收缩左端点iwhile(j-i1len)// 如果当前窗口长度超过最大允许长度{--cnt[a[i]];// 左端点元素a[i]移出窗口出现次数减1if(cnt[a[i]]0)// 如果a[i]的出现次数变为0res--;// 窗口内不同种类数减1i;// 左端点右移}// 将右端点元素a[j]加入窗口if(cnt[a[j]]0)// 如果a[j]之前不在窗口中res;// 窗口内不同种类数加1cnt[a[j]];// a[j]的出现次数加1ansmax(ans,res);// 更新最大种类数}coutansendl;// 输出满足长度限制的最大不同花种类数return0;}【运行结果】6 1 2 3 1 2 3 3