做茶网站,asp.net 网站开发实例,室内设计软件手机版,电子商务网站策划书2000字分而治之:指的是当主问题可以被分解为一个相同次级问题加相同基本问题时#xff0c;采用这种思想#xff0c;基本问题指问题规模最小时的情况#xff0c;次级问题是指主问题的n级降低n-1级的问题。 具体实现#xff1a;多数采用递归操作分解#xff0c;然后递归操作#… 分而治之:指的是当主问题可以被分解为一个相同次级问题加相同基本问题时采用这种思想基本问题指问题规模最小时的情况次级问题是指主问题的n级降低n-1级的问题。 具体实现多数采用递归操作分解然后递归操作需要注意的是函数头函数体以及递归出口函数头由问题所需变量指定递归出口由问题最小规模返回决定函数体看问题具体的需要的信息决定。
75. 颜色分类 - 力扣LeetCode
class Solution {
public:void sortColors(vectorint nums) {int left-1;int rightnums.size();int cur0;while(curright){if(nums[cur]0) swap(nums[left],nums[cur]);else if(nums[cur]2) swap(nums[--right],nums[cur]);else cur;}return ;}
}; 分治-快速排序下面这三题都是快排其中第一题快排第二题在快排的基础上进行剪枝避免无用的排序第三题同理也是避免无用排序。通过设置进入那个递归来实现。 . - 力扣LeetCode class Solution {
public:vectorint sortArray(vectorint nums) {srand(time(0));sort1(nums,0,nums.size()-1);return nums;} void sort1(vectorint nums,int left,int right){if(leftright) return;//int keyGetrand(nums,left,right);//swap(nums[left],key);Ⅲ、交换会覆盖一个不是交换int curleft;int lleft-1; int rright1;while(curr){//Ⅱ、cur判断数据时,之后可能会越界所以一次只能判断一个条件然后需要判断curr,不能多个if。if(nums[cur]key) swap(nums[cur],nums[--r]);else if(nums[cur]key) swap(nums[cur],nums[l]);else if(nums[cur]key) cur;}sort1(nums,left,l);sort1(nums,r,right);}int Getrand(vectorint nums,int left,int right){int rdrand();return nums[rd%(right-left1)left]; //Ⅰ记得left否则超范围}
};215. 数组中的第K个最大元素 - 力扣LeetCode 数组中第k个最大元素①快速选择利用快排思想(三路划分)实现On②利用优先队列堆找大的就是用小根堆。找小的用大根堆。ONlog2k class Solution {
public:int findKthLargest(vectorint nums, int k) {srand(time(0));return qsort(nums,0,nums.size()-1,k);}int qsort(vectorint nums,int l,int r,int k){int keyGetRand(nums,l,r);int curl; int leftl-1;int rightr1;while(curright){if(nums[cur]key) swap(nums[cur],nums[left]);else if(nums[cur]key) swap(nums[cur],nums[--right]);else cur;}int aleft-l1; int bcur-left-1;int cr-right1;if(ka) return qsort(nums,l,left,k);else if(kakab) return key;else return qsort(nums,right,r,k-a-b);}int GetRand(vectorint nums,int l,int r){int rdrand();return nums[rd%(r-l1)l];}}; LCR 159. 库存管理 III - 力扣LeetCode class Solution {
public:vectorint inventoryManagement(vectorint stock, int cnt) {//如何提取区间srand(time(0));qsort(stock,0,stock.size()-1,cnt);return vectorint(stock.begin(),stock.begin()cnt);}void qsort(vectorint stock,int l,int r,int cnt){if(lr) return ;//若没有则getrand会出错%0错误。int keyGetRand(stock,l,r);int curl,leftl-1,rightr1;while(curright){if(stock[cur]key) swap(stock[cur],stock[left]);else if(stock[cur]key) swap(stock[cur],stock[--right]);else cur;}int aleft-l1; int bright-left-1; int cr-right1;if(cnta) qsort(stock,l,left,cnt);else if(cntab) return ;else qsort(stock,right,r,cnt-a-b);}int GetRand(vectorint stock,int l,int r){int rdrand();return stock[rd%(r-l1)l];}
}; 分治——归并排序
912. 排序数组 - 力扣LeetCode
class Solution {vectorint tmp;
public:vectorint sortArray(vectorint nums) {//归并tmp.resize(nums.size());MageSort(nums,0,nums.size()-1);return nums;}void MageSort(vectorint nums,int l,int r){if(lr) return;int midl(r-l)/2;MageSort(nums,l,mid);MageSort(nums,mid1,r);int cur1l;int cur2mid1;int curl;while(cur1midcur2r){if(nums[cur1]nums[cur2]){tmp[cur]nums[cur1];}else if(nums[cur1]nums[cur2]){tmp[cur]nums[cur2];}}while(cur1mid) tmp[cur]nums[cur1];while(cur2r) tmp[cur] nums[cur2];//拷贝回去int leftl,rightr;while(leftright) {nums[left]tmp[left];//*****只有一个left,首先执行”“左边的那个部分语句所有left拷贝给left1.left;}return;}
};
LCR 170. 交易逆序对的总数 - 力扣LeetCode
class Solution {vectorint tmp;
public:int reversePairs(vectorint record) {int ret0;tmp.resize(record.size());return magesort(record,0,record.size()-1,ret);}int magesort(vectorint record ,int left,int right,int ret){if(leftright) return 0;int midleft(right-left)/2;magesort(record,left,mid,ret);magesort(record,mid1,right,ret);int curleft; int cur1left,cur2mid1;while(cur1midcur2right){if(record[cur1]record[cur2]) tmp[cur]record[cur2];//降序。else{retright-cur21;//****记录左边数组的每个值对应的右边小于它的个数right-cur21是降序tmp[cur]record[cur1];}}while(cur1mid) tmp[cur]record[cur1];while(cur2right) tmp[cur]record[cur2];//拷贝回去复原for(int ileft;iright;i){//*****拷贝要left到right。完整一段record[i]tmp[i];}return ret;}
}; 315. 计算右侧小于当前元素的个数 - 力扣LeetCode
class Solution {vectorint tmp;vectorint tmp_index;vectorint index;vectorint ret;
public:vectorint countSmaller(vectorint nums) {ret.resize(nums.size());index.resize(nums.size());for(int i0;inums.size();i){//建立变换后的下标[i]与原下标i之间的映射index[i]i;}tmp.resize(nums.size());tmp_index.resize(nums.size());MageSort(nums,0,nums.size()-1);return ret;}void MageSort(vectorint nums,int left,int right){if(leftright) return;int midleft(right-left)/2;MageSort(nums,left,mid);MageSort(nums,mid1,right);int curleft;int cur1left; int cur2mid1;while(cur1midcur2right){if(nums[cur2]nums[cur1]){//降序,求右区间小于cur1的个数ret[index[cur1]]right-cur21;tmp[cur]nums[cur1];tmp_index[cur]index[cur1];//**1***保持映射}else{tmp[cur]nums[cur2];tmp_index[cur]index[cur2];}}while(cur1mid) {tmp[cur]nums[cur1];tmp_index[cur]index[cur1];}while(cur2right){tmp[cur]nums[cur2];//**1**多加了tmp_index[cur]index[cur2];}//还原for(int ileft;iright;i){nums[i]tmp[i];index[i]tmp_index[i];}}}; 493. 翻转对 - 力扣LeetCode
class Solution {int ret0;vectorint tmp;
public:int reversePairs(vectorint nums) {int nnums.size();tmp.resize(n);MageSort(nums,0,n-1);return ret;}void MageSort(vectorint nums,int left,int right){if(leftright) return ;int mid(leftright)1;MageSort(nums,left,mid);MageSort(nums,mid1,right);int cur1left; int cur2mid1;while(cur1midcur2right){// coutleft mid mid1 rightendl;//**1**打印也会出现超时的错误// coutnums[cur1]/2.0 nums[cur2]endl;if(nums[cur1]/2.0nums[cur2]){//**2***一定要2.0否则会出现3/2不大于1的情况降序retright-cur21;cur1;}else{cur2;}} int curleft; cur1left; cur2mid1;while(cur1midcur2right){if(nums[cur1]nums[cur2]){tmp[cur]nums[cur1];}else{;tmp[cur]nums[cur2];}}while(cur1mid) tmp[cur]nums[cur1];while(cur2right)tmp[cur]nums[cur2];//还原for(int ileft;iright;i){nums[i]tmp[i];}return ;}
};
