郫都区规划建设局网站哪些行业做网站最重要

郫都区规划建设局网站,哪些行业做网站最重要,wordpress电影资源网站,安徽网络优化公司快慢指针本质上是一种思想#xff0c;而非一种算法#xff0c;就和贪心一样#xff0c;不能把其简单地看作一种算法。概念这里的指针并非C和C中的指针#xff0c;你可以理解为数组下标或者类似的东西。快指针#xff1a;快速遍历并检测符合条件的数据#xff0c;先行一步…快慢指针本质上是一种思想而非一种算法就和贪心一样不能把其简单地看作一种算法。概念这里的指针并非C和C中的指针你可以理解为数组下标或者类似的东西。快指针快速遍历并检测符合条件的数据先行一步查找满足前置条件的数据慢指针维护已处理数据的边界即对已满足条件数据的维护双指针可以帮我们降低遍历的次数加快程序运行速度降低时间复杂度。例题有序数组去重将一个已经排序好的数组去重如1233345在去重后变成12345代码部分常规做法#includeiostream using namespace std; int main(){ int num[7] {1 , 2 , 3 , 3 , 3 , 4 , 5}; int cnt 0; //计算重了几个 for(int i 0 ; i 7 - cnt ; i ){ if(i ! 0 num[i] num[i - 1]){ cnt ; i --; for(int j i ; j 7 - cnt ; j){ num[j] num[j 1]; } } } for(int i 0 ; i 7 - cnt ; i ){ cout num[i] ; } cout endl; return 0; }但是这样双重嵌套的情况下如果数组比较长就会导致代码的运行效率异常低下。所以我们将使用双指针。快慢指针写法我们将转换思考方式我们现在想要去重就只需要把没出现过的暂时存起来这样就不需要嵌套遍历其实是空间换时间的思想#includeiostream using namespace std; int main(){ int num[7] {1 , 2 , 3 , 3 , 3 , 4 , 5}; int temp[7] {}; //定义一个零时数组 temp[0] num[0]; int j 0; //慢指针即temp的数组边界下标 for(int i 0 ; i 7 ; i){ if(temp[j] ! num[i]){ //遍历存储 temp[j 1] num[i]; j; } } for(int i 0 ; i j 1 ; i){ cout temp[i] ; } cout endl; return 0; }肥肠简单的一个例子相信没有看这个文章大家也可以想到这种方法。当然也可以不用temp[j] ! num[i]这种判断方式由于数组本身已经有序所以可以直接将相同的右边界放入temp数组中如2223的时候判断快指针所指数和下一个数是否相同不同则将该数放入。当然我们也可以对内存空间进一步优化我们舍弃temp数组直接将两个指针都用在num上完全体的快慢指针#includeiostream using namespace std; int main(){ int num[7] {1 , 2 , 3 , 3 , 3 , 4 , 5}; int j 0; //慢指针数组边界 for(int i 0 ; i 7 - 1 ; i){ if(num[i] ! num[i 1]){ //边界判断如果到边界则进行存储 num[j] num[i]; j; } } if(num[j] ! num[6]){ num[j] num[6]; //由于循环的时候我们将最后一位舍弃所以这里我们要放回 j; } for(int i 0 ; i j ; i){ cout num[i] ; } cout endl; return 0; }如此一来我们连temp的空间都省下来了原地删除如数组1234562223145我们想把2全都删掉的同时保证数组成员之间的相对关系保持不变同样的我们可以用常规方法来实现但是常规方法不但麻烦而且复杂度也比叫高所以我们使用快慢指针来实现数组成员的删除代码实现#includeiostream using namespace std; int main(){ int num[13] {1,2,3,4,5,6,2,2,2,3,1,4,5}; int j 0; //慢指针 for(int i 0 ; i 13 ; i){ if(num[i] ! 2){ num[j] num[i]; j; } } for(int i 0 ; i j ; i){ cout num[i] ; } cout endl; return 0; }代码简介而优雅最长连续不重复子序列洛谷U224090题目描述给定长度为 n 的整数序列找出最长的不包含重复的数的连续区间输出它的长度输入格式第一行包含整数n1 n 100000第二行包含 n 个整数均在0~10^5范围内表示整数序列输入51 2 2 3 5输出3对于这道题目如果我们直接使用暴力做法就会生成三层循环导致超时。暴力写法#includeiostream using namespace std; const int N 1e5 10; int arr[N]; int main(){ int n; cin n; for(int i 0 ; i n ; i){ cin arr[i]; } int maxlen 0; //最长长度 for(int i 0 ; i n - 1 ; i){ int len 1; //i和j的起始长度相差1 for(int j i 1 ; j n ; j){ int flag 0; //标记0为范围内无重复1为有重复 for(int k i ; k j ; k){ //从头到尾查一遍 if(arr[k] arr[j]){ flag 1; break; } } if(flag) break; else len; } if(len maxlen){ maxlen len; } } cout maxlen endl; return 0; }由于太过暴力十个测试点我们只能通过4个剩下的全部都超时了。所以使用暴力来解决这个问题是不恰当的此时的时间复杂度为O()所以我们要对这段代码进行优化第一次优化对最内层循环进行优化优化其判断区间是否有重复元素的逻辑这里我们首先采取空间换时间的方法来降低时间复杂度即利用计数排序的逻辑来判断这段连续子序列中每个元素的出现次数#includeiostream #includecstring using namespace std; const int N 1e5 10; int arr[N]; int main(){ int n; cin n; for(int i 0 ; i n ; i){ cin arr[i]; } int maxlen 0; //最长长度 for(int i 0 ; i n - 1 ; i){ int cnt[N]; // 定义统计出现次数的数组 memset(cnt , 0 , sizeof(cnt)); // 清空cnt数组为0 int len 0; for(int j i ; j n ; j){ if(cnt[ arr[j] ] 0){ len; cnt[ arr[j] ] 1; }else{ break; } } if(len maxlen){ maxlen len; } } cout maxlen endl; return 0; }在进行一次优化后我们的时间复杂度下降到了O()然后我们发现十个测试点就全都通过了过不去的多提交几遍就过了(bushi)第二次优化但是O()的时间复杂度还是相当大如果题目给出的 n 再大几个数量级那么我们也无法顺利通过这道题所以我们还需要进行再次优化这一次我们将根据题目的本质来进行优化题目的要求是找出最长的不重复子序列所以当出现重复的数时我们直接把慢指针移到出现过的数的后一位继续遍历125676910我们定义两个指针 i 和 j i 为慢指针当 i 为0的时候我们发现当 j 等于 5 的时候出现了重复的数据这个时候我们直接将 i 移到第一个 6 后方也就是让 i 等于 3 然后让 j 继续遍历这个方法成立的原因在于当 i 在第一个 6 之前时无论 i 如何移动 j 都无法越过第二个 6 所以我们便让 i 直接到第一个 6 后方#includeiostream #includecstring using namespace std; const int N 1e5 10; int arr[N]; int main(){ int n; cin n; for(int i 0 ; i n ; i){ cin arr[i]; } int maxlen 0; //最长长度 for(int i 0 ; i n - 1 ; i){ //慢指针 int cnt[N] {0} , len 0; // 统计数据出现次数 for(int j i ; j n ; j){ //快指针 if(cnt[arr[j]] 0){ cnt[arr[j]] 1; len; }else{ for(int k i ; k j ; k){ //查找第一次出现位置直接把i移到次位置后 if(arr[k] arr[j]){ i k; // 注意不需要加一当外层循环结束后i会自动加1 break; } } break; } } if(len maxlen){ maxlen len; } } cout maxlen endl; return 0; }虽然看起来我们的循环变成了三层但是我们利用内层循环减少了最外层循环所以从整体上看我们的代码的时间复杂度还是在下降的当然嵌套的存在还是为我们的代码增添了不确定性所以我们可以最终优化将代码变为单层循环最终优化#includeiostream #includecstring using namespace std; const int N 1e5 10; int arr[N]; int main(){ int n; cin n; for(int i 0 ; i n ; i){ cin arr[i]; } int maxlen 0; //最长长度 int i 0; // 慢指针 int cnt[N] {0}; // 统计数据出现次数 for(int j 0 ; j n ; j){ //快指针 cnt[arr[j]]; //当前位置的数统计次数加1 while(cnt[arr[j]] 1){ // 循环直到当前位置的数统计次数降到1 cnt[arr[i]]--; i; } if(j - i 1 maxlen){ maxlen j - i 1; } } cout maxlen endl; return 0; }通过这次优化我们最终将时间复杂度降到了O(n)总结双指针本质上不是一种算法它是一种思维方式当我们可以理解这种思维方式的时候我们就可以对代码进行优化同时也可以缩减代码量