企业官网建设流程全解析

设计建设网站公司网站,贵州网站备案查询,电商app开发定制大概多少钱,建设项目网站备案申请表#x1f3ac; 胖咕噜的稞达鸭#xff1a;个人主页#x1f525; 个人专栏: 《数据结构》《C初阶高阶》 《Linux系统学习》 《算法日记》⛺️技术的杠杆#xff0c;撬动整个世界! 颜色分类 解法#xff1a;三指针 将数组中的0#xff0c;1#xff0c;2按照顺序排序#… 胖咕噜的稞达鸭个人主页 个人专栏: 《数据结构》《C初阶高阶》《Linux系统学习》《算法日记》⛺️技术的杠杆撬动整个世界!颜色分类解法三指针将数组中的012按照顺序排序不可以使用sort()。算法i从数组索引为0的位置开始遍历left在数组下标索引为0的位置right在索引为n-1的位置。如果i遍历到的数字nums[i] 0跟nums[left]的位置交换与此同时left;如果i遍历到的nums[ i ] 1;则 i 如果i遍历到的nums[ i ] 2;则交换nums[ right ]和nums[i ],于此同时right--。循环的结束条件是i 跟right相遇。将一段数组分成三份依次存储012用leftrighti分段将数组分为4段。[0,left]:全部都是0 [left1,i-1]:全部都是1 [i,right-1]:待扫描的元素 [right,n-1]:全部都是2classSolution{public:voidsortColors(vectorintnums){intleft-1,rightnums.size();//left设置为1的位置上初始还没有找到0的位置right设置为nums.size()的位置初始化还没有找到2的位置inti0;while(iright){if(nums[i]0)swap(nums[left],nums[i]);elseif(nums[i]1)i;elseswap(nums[--right],nums[i]);//i不用不然交换过去的i是的还没有被处理的而不是2}}};912.排序数组[912. 排序数组 - 力扣LeetCode](排序数组)解法一快速排序classSolution{public:vectorintsortArray(vectorintnums){srand(time(NULL));//种下一颗随机数的种子qsort(nums,0,nums.size()-1);returnnums;}//快排voidqsort(vectorintnums,intl,intr){if(lr)return;//数组分类intkeygetRandom(nums,l,r);intil,leftl-1,rightr1;while(iright){if(nums[i]key)swap(nums[left],nums[i]);elseif(nums[i]key)i;elseswap(nums[--right],nums[i]);}//数组分为三块[l,left][left1,right - 1][right,r]qsort(nums,l,left);qsort(nums,right,r);}intgetRandom(vectorintnums,intleft,intright){intrrand();returnnums[r%(right-left1)left];}};解法二归并排序将数组划分为两块两块数组都有序之后合并到一起找两个指针ptr1,ptr2。分别遍历这两个数组ptr1从数组1开始int ptr1 left;ptr2从数组2开始int ptr2 mid 1;哪个在指向数字的过程中遇到的数小就插入随后要处理未完成的数组数组1有余留就插入到tmp中数组2同理。最后按照顺序返回排好序的数组。classSolution{vectorinttmp;public:vectorintsortArray(vectorintnums){tmp.resize(nums.size());mergeSort(nums,0,nums.size()-1);returnnums;}voidmergeSort(vectorintnums,intleft,intright){if(leftright)return;//1.选择中间点划分区间intmid(rightleft)1;//相加之后右移一位//2把左右区间排序mergeSort(nums,left,mid);mergeSort(nums,mid1,right);//3.合并两个有序数组intptr1left,ptr2mid1,i0;while(ptr1midptr2right){tmp[i]nums[ptr1]nums[ptr2]?nums[ptr1]:nums[ptr2];}//4.处理未完成的数组while(ptr1mid)tmp[i]nums[ptr1];while(ptr2right)tmp[i]nums[ptr2];//5.还原for(intileft;iright;i)nums[i]tmp[i-left];}};数组中的第k个最大元素[215. 数组中的第K个最大元素 - 力扣LeetCode](数组中的第k个最大元素)判断逻辑如果前c个最大的元素已经包含了第k大 → 去大于区找如果前(cb)个最大的元素包含了第k大 → 第k大就是key否则 → 去小于区找调整k的值具体示例分析示例1找第2大数组[5, 3, 7, 3, 1, 3, 9] k2 三路划分后小于区[1], 等于区[3,3,3], 大于区[9,7,5] c3, b3 判断 1. c3 k2 ✓ → 第2大在大于区 2. 在大于区[9,7,5]中找第2大 → 返回7示例2找第4大数组[5, 3, 7, 3, 1, 3, 9] k4 三路划分后小于区[1], 等于区[3,3,3], 大于区[9,7,5] c3, b3 判断 1. c3 k4? ✗ 2. bc6 k4? ✓ → 第4大在等于区返回key3示例3找第7大最小数组[5, 3, 7, 3, 1, 3, 9] k7 三路划分后小于区[1], 等于区[3,3,3], 大于区[9,7,5] c3, b3 判断 1. c3 k7? ✗ 2. bc6 k7? ✗ 3. 第3种情况 → 在小于区[1]找第(k-b-c)7-61大 返回1classSolution{public:intfindKthLargest(vectorintnums,intk){//种一棵随机数种子srand(time(NULL));//随机树种子returnqsort(nums,0,nums.size()-1,k);}intgetRandom(vectorintnums,intleft,intright){intrrand();returnnums[r%(right-left1)left];}intqsort(vectorintnums,intl,intr,intk){if(lr)returnnums[l];//如果数组中l和r是相等的不用进行下面的操作了直接返回//1.随机选择基准元素intkeygetRandom(nums,l,r);//在l,r这段区间随机返回一个随机数//2.随机选择基准元素将数组分为3组:[l,left][left-1,right1][right,r]intil,leftl-1,rightr1;while(iright){if(nums[i]key)swap(nums[left],nums[i]);elseif(nums[i]key)i;elseswap(nums[--right],nums[i]);}//3.分情况讨论intcr-right1;//第三组元素的数量intbright-left-1;//第二组元素的数量if(ck)returnqsort(nums,right,r,k);elseif(bck)returnkey;elsereturnqsort(nums,l,left,k-b-c);}};面试题17.14.最小K个数[面试题 17.14. 最小K个数 - 力扣LeetCode](最小K个数)解法随机数作为基准元素 数组分为三段--------------------------- | | | | l left right r [l,left]:key的元素 [left,right]:key的元素 [right,r]:key的元素返回数组中最小的K个数首先要从[l,left]中寻找假设【l,left】中有a个数字int a left - l 1;假设【left,right】中有b个数字int b right - left - 1;如果要找的k的个数小于a,就在a区间中寻找如果要找的k的个数小于a b这一大个区间返回key实在找不到可以在剩下的k - a- b个数字中也就是大于key的区间中找。classSolution{public:vectorintsmallestK(vectorintarr,intk){srand(time(NULL));qsort(arr,0,arr.size()-1,k);return{arr.begin(),arr.begin()k};//最后返回的是一个数组}voidqsort(vectorintarr,intl,intr,intk){if(lr)return;intil,leftl-1,rightr1;intkeygetRandom(arr,l,r);while(iright){if(arr[i]key)swap(arr[i],arr[left]);elseif(arr[i]key)i;elseswap(arr[i],arr[--right]);}//分情况讨论intaleft-l1;intbright-left-1;if(ak)returnqsort(arr,l,left,k);elseif(abk)return;elsereturnqsort(arr,right,r,k-a-b);}intgetRandom(vectorintarr,intleft,intright){intrrand();returnarr[r%(right-left1)left];}};遇到分区/选择类算法题的通用解法思路核心模式识别当你看到以下特征时考虑使用分区/选择算法需要重新排序数组元素如按颜色、值排序寻找第K大/第K小的元素寻找前K个最小/最大的元素题目要求O(n)时间复杂度或禁止使用sort()四步解题框架第一步分析问题类型如果是排序/分类→ 直接用三指针分区如颜色分类如果是第K个元素 → 用快速选择如果是前K个元素 → 用改进的快速选择第二步选择分区策略// 三路分区模板最常用intleftl-1,rightr1;// 扩展边界intil;// 当前指针intkeygetRandom(nums,l,r);// 随机基准值while(iright){if(nums[i]key)swap(nums[left],nums[i]);elseif(nums[i]key)i;elseswap(nums[--right],nums[i]);}// 分区结果// [l, left] key// [left1, right-1] key// [right, r] key第三步判断递归方向cpp// 对于第K大元素intlessCountleft-l1;// 小于区的数量intequalCountright-left-1;// 等于区的数量intgreaterCountr-right1;// 大于区的数量// 判断逻辑if(greaterCountk){// 在大于区找第k大returnqsort(nums,right,r,k);}elseif(greaterCountequalCountk){// 第k大在等于区returnkey;}else{// 在小于区找第(k - greaterCount - equalCount)大returnqsort(nums,l,left,k-greaterCount-equalCount);}第四步边界处理// 递归终止条件if(lr)returnnums[l];// 第K大元素if(lr)return;// 排序/分类if(k0)return{};// 前K个元素实战决策树问题类型 ├── 重新排序/分类如颜色分类 │ ├── 固定规则如0,1,2→ 三指针遍历交换 │ └── 任意规则 → 三路分区 ├── 寻找单个元素第K大/小 │ ├── 第K大 → 按大于区、等于区、小于区顺序判断 │ └── 第K小 → 按小于区、等于区、大于区顺序判断 └── 寻找多个元素最小/大的K个数 ├── K个数需要排序 → 先快速选择再对前K个排序 └── K个数无需排序 → 直接分区到正确位置关键技巧提醒随机化基准值是避免最坏情况的关键srand(time(NULL));// 随机种子intrrand();returnnums[r%(right-left1)left];指针边界处理初始时让 leftl-1, rightr1这样分区后区间更清晰i指针的处理交换到左边的元素可以 i已处理 交换到右边的元素不要 i需要重新处理复杂度分析平均O(n) 或 O(n log n)最坏O(n²) → 通过随机化避免常见易错点错误 正确做法忘记处理相等情况 一定要有else if(nums[i]key)i交换后错误移动指针 从左换来的可以i从右换来的不能i递归方向判断错误 画图明确各分区的元素数量边界条件漏掉 总是检查 if(lr)一句话总结“随机基准三路分数量判断定区间递归缩小范围找”——遇到这类问题先随机选基准值三路分区根据各区间元素数量决定下一步操作递归缩小范围直到找到答案。