dw用ps切片做网站seo规则

当前位置： 首页 > news >正文

dw用ps切片做网站,seo规则,网页版qq中心登录入口,建筑工程ppt模板免费下载每日激励#xff1a;“不设限和自我肯定的心态#xff1a;I can do all things。 — Stephen Curry” 绪论​#xff1a; 本章将学习分治算法#xff0c;将通过练习促学习的方式来学习#xff0c;主要通过先从归并算法开始带你打好基础#xff0c;后续三道困难题都将在这… 每日激励“不设限和自我肯定的心态I can do all things。 — Stephen Curry” 绪论​ 本章将学习分治算法将通过练习促学习的方式来学习主要通过先从归并算法开始带你打好基础后续三道困难题都将在这个排序的基础上进行扩展利用归并的思想来解决在排序的过程中快速查找在自己后面的比自己小的值降序排序以及在自己前面比自己大的值升序排序具体细节让我们见文章吧。 ———————— 早关注不迷路话不多说安全带系好发车啦建议电脑观看。 分治归并排序 具体训练

1. 归并排序 题目 归并排序的核心思想 根据中间的mid分成两部分先排左边内部有是一个归并当数组只有一个值时返回再拍右边内部同样是一个归并当数组只有一个值时返回将左右两个数组合并成一个有序数组返回 class Solution { public:vectorint tmp;vectorint sortArray(vectorint nums) {msort(nums,0,nums.size()-1);return nums;}//Merge Sortvoid msort(vectorint nums,int left,int right){if(left right) return ;int mid left (right - left) / 2;//mid 1 2 3 4 mid 1// 2 3 mid msort(nums,left,mid);msort(nums,mid1,right);//left ~ mid - 1//mid ~ righttmp.clear();int cur1 left,cur2 mid 1;while(cur1 mid cur2 right){if(nums[cur1] nums[cur2]) tmp.push_back(nums[cur1]);else tmp.push_back(nums[cur2]);}//处理剩下的while(cur1 mid){tmp.push_back(nums[cur1]);//处理剩下的}while(cur2 right){tmp.push_back(nums[cur2]);}for(int i left;i right;i)nums[i] tmp[i - left];} };其中本质就是后序遍历的方法先遍历左左边结束后才到右最后到结点 快排是每一层选择一个基准元素key然后进行分组后重复直到数组分成一个元素时分组结束 而快排就相当于一种前序遍历处理完结点后分成两组后再分别处理 本质区别就是处理数组时机不同 2. 交易逆序对的总数 题目 分析题目 对于暴力解法来说比较简单两层暴力枚举即可找到最多的逆序对但一定是会超时的 优化方法 上图描述 首先将一整个区间划分成两部分 a、b然后在新区域a、b中找逆序对得到a、b个然后再将 a、b区域联合起来看选择一个a区域中的逆序对然后再选择一个b区域的最终组合成新的逆序对个数为c那么最终逆序对个数为 a b c 顺序是先挑a区域、再挑b区域、最后查询 a 和 b 组合左半部分、右半部分、一左一右 那么再次优化先找左半部分找完后进行排序、同理找完右半部分进行排序最后一左一右因为排序后找一左一右就有单调性了就能快速的确定个数 最终本质就很归并排序是一样的了如下图 其中对合并排序和其中需要的其他操作来找结果的详细解释如下图
   当到达归并排序的某一层时的操作 首要目的是为了合并但同时也要记录逆序对的个数回顾个数的计算a左 b右 c左右其中a、b在上一层已经计算了所以本层只用计算 c 即可记录个数c 一左一右那么也就是要找 cur1 后面能接的 cur2记住回到公式当 num[cur1] num[cur2] 时就正常进行归并排序cur1而当 num[cur1] num[cur2] 时这时cur1即往后的值都是大于cur2的因为a区间是始终升序的所以个数就能直接增加 ret mid - cur1 1个然后进行正常归并排序步骤cur2 题目核心逻辑 class Solution { public:int reversePairs(vectorint record) {return mergesort(record,0,record.size()-1);}//归并int mergesort(vectorint record,int left,int right){if(left right) return 0;int mid left (right - left) / 2;int a mergesort(record,left,mid);int b mergesort(record,mid1,right);vectorint temp;// cint c 0;//进行归并此处是升序取出小的放入容器中int cur1 left,cur2 mid1;while(cur1 mid cur2 right){//策略1找前面有多少大的针对cur2来看if(record[cur1] record[cur2]){c mid - cur1 1;temp.push_back(record[cur2]);cur2;}else{//cur1 cur2temp.push_back(record[cur1]);cur1;}}while(cur1 mid) temp.push_back(record[cur1]);while(cur2 right) temp.push_back(record[cur2]);for(int j left; j right; j)record[j] temp[j - left];return a b c;}};3. 计算右侧小于当前元素的个数 题目 分析题目 分析题目和例1 找当前这个数的右边有多少比自己小的 所以就和上题比较像可以使用 上一题中的第二个策略找当前元素后边有多少个比我小前提降序 在降序的前提下这里的降序本质就是在归并排序中执行的排序操作 排序后就是内部的一些问题同样的也是 左区间 右区间 左右区间 其中具体已经在上题中说明了本题主要还是讲解左右区间 通过比较cur1、cur2找到比自己小的元素具体公式如下图 本题需要返回的是一个数组nums其中它对应的是它上方数值右边比他小的个数 当cur1 cur2时因为是降序cur2右边都将比他小所以就直接加上right - cur2 - 1
   如何处理当排序后其索引改变导致找不到原数据的问题 那么其中就会有一个问题当排完序后如何仍然找到对应的原始的下标呢因为排完序后位置就发生了改变低下记录值的数组nums就将不再对应上所以就需要进行一定的处理一般来说可以使用hash的kv进行绑定值和下标但本题可能会出现重复的值所以就不适合使用那么可以使用一个index新数组进行绑定管理索引其中在操作nums的同时index也是同样的改变这样index数组中的索引就始终对应了
   题目核心逻辑 本题重点 通过新增一个start_index索引数组来记录当前索引的位置并且在更改位置的过程中记录当前索引的位置然后实时的也进行修改其中也多借助了一个index辅助数组进行存储移动前的索引的位置 class Solution { public:vectorint countSmaller(vectorint nums) {int n nums.size();//归并排序vectorint res(n);vectorint start_index(n);for(int i 0;i nums.size();i)start_index[i] i;mergeSort(nums,res,start_index,0,n - 1);return res;}int temp[100010] {};int index[100010] {};void mergeSort(vectorint nums,vectorint res,vectorint start_index,int left,int right){if(left right) return ;//当超过范围就返回int mid (right left) / 2;//取中进行划分mergeSort(nums,res,start_index,left,mid);mergeSort(nums,res,start_index,mid1,right);//a b合并的同时进行计算int p1 left,p2 mid 1,ti 0;while( p1 mid p2 right){//降序等于 在归并排序中本质放到哪里都行但在本题需要找的是 p1 p2 的才个数所以将 等于 放到 处if(nums[p1] nums[p2]){index[ti] start_index[p2];//存储他的下标temp[ti] nums[p2]; }else{//记录长度//start_index是他的原始索引位置res[start_index[p1]] right - p2 1;index[ti] start_index[p1];//存储他的下标temp[ti] nums[p1];}}while(p1 mid) {res[start_index[p1]] right - p2 1;index[ti] start_index[p1];//存储他的下标temp[ti] nums[p1];}while(p2 right) {index[ti] start_index[p2];//存储他的下标temp[ti] nums[p2]; }//将temp放入数组for(int i left;i right ;i){start_index[i] index[i - left];//让原数位置也跟着移动nums[i] temp[i - left];//移动值的同时移动index//num[i]是新值i是新}}};4. 翻转对 题目 分析题目 分析题目找出所有值是后面值的两倍的的个数如下图3 1*2 共有两次所以也就是2 那么类似的还是找比自己小的元素只不过此时是小两倍的元素就会导致运算情况和归并并不一样了 此时就需要将算左 右区间的情况单独出来看用一个双指针的方式这里就不过诉了看下图来提前处理排好序的值找到左 右区间合起来看时有多少符合翻转对的值具体为什么不能放到归并中操作下述代码中已经注释一个基础的单调性双指针算法有问题可以评论
   题目核心逻辑 具体细节写在注释 class Solution { public:int reversePairs(vectorint nums) {return mergeSort(nums,0,nums.size()-1);}int tmpNums[50010];int mergeSort(vectorint nums, int left, int right) {if (left right)return 0;int mid (left right) / 2;int ret 0;// [left, mid] [mid 1, right]// 2. 处理左右两个区间ret mergeSort(nums, left, mid);ret mergeSort(nums, mid 1, right);// 3. 处理⼀左⼀右的情况int cur1 left, cur2 mid 1, i 0;//双指针提前处理计算左右区间中的值while (cur1 mid cur2 right) // 降序排序{//主要不同就是在这里不能再归并中同时处理就是因为可能会跳过处理某些情况//若当cur1 cur2 时会不断的走cur1的而不会动 cur2这样就会导致 cur1 2*cur2 其中的cur2不变导致 ret 无法遍历所有情况if (numscur1 2*nums[cur2]) {cur1;ret right - cur2 1;} else {cur2;}}cur1 left, cur2 mid 1;//恢复值//不放在一起的原因是他们运算的过程不一致主要体现在 nums[cur1] 2*num[cur2] 时才需要记录答案这里有许多细节//并不好叙述主要就是理解他们 运算是不一样的 会导致某些问题的方式从而让 cur2 和 cur1 的比较并不正常具体如上描述while (cur1 mid cur2 right) // 降序排序{if (nums[cur1] nums[cur2]) {tmpNums[i] nums[cur2];} else {tmpNums[i] nums[cur1];}}// 4. 处理剩余的排序⼯作while (cur1 mid) {tmpNums[i] nums[cur1];}while (cur2 right) {tmpNums[i] nums[cur2];}for (int j left; j right; j) {nums[j] tmpNums[j - left];}return ret;} };