做本地旅游网站,asp网站500错误iis7,如何自己创建app软件,永年区住房和城乡建设局网站原理#xff1a;将数组进行区间划分#xff0c;通过指针(下标)的移动实现题目所要求的区间#xff08;数组分块#xff09; #xff08;实现代码统一是C#xff09; 建议在做题与看题解时要自己反复模拟这个实现的过程#xff0c;以后在做题做到类似的题才能举一反三将数组进行区间划分通过指针(下标)的移动实现题目所要求的区间数组分块 实现代码统一是C 建议在做题与看题解时要自己反复模拟这个实现的过程以后在做题做到类似的题才能举一反三 一移动零
链接283. 移动零 - 力扣LeetCode
思路将要实现的区间用指针划为不同的区间(非0区间与0区间)再进行指针的搜索。
class Solution {
public:void moveZeroes(vectorint nums) {int cur-1,des0;//cur固定des去进行数组的扫描即找非0元素//最后:[0,cur]为非0元素[cur1,des]为0元素while(desnums.size()){if(nums[des]!0){swap(nums[cur1],nums[des]);cur;}des;}}
};
二复写零
链接1089. 复写零 - 力扣LeetCode 思路 确定目标位置首先使用两个指针 dest 和 cur 来确定每个位置复制0后应该放置的位置。cur 指针用于遍历原始数组而 dest 指针则用于确定在复制0后应该放置新元素的位置。 cur 最终的位置就是复写后数组的最后一个数的位置。 再从后往前进行数组值的覆盖(从前向后遍历会导致数组后面元素丢失) class Solution {
public:void duplicateZeros(vectorint arr) {int cur0,des-1,narr.size();while(desn){//arr[cur1]0...如果在cur0位置上是0呢?if(arr[cur]0){des2;}else{des;}if(desn-1){break;}cur;}//[1,0,2,3,0,4]des走到n位置越界if(desn-1){//直接让des在数组的最后一个位置上并把它赋为0(越界情况一定是在复写0的时候越界的)desn-1;arr[des--]0;cur--;}//cur的位置是要实现的数组的最终位置while(cur0){//(cur的位置遇到0就让des进行复写0的操作)if(arr[cur]0){arr[des--]0;arr[des--]0;cur--;}//从后向左进行值的覆盖else{arr[des--]arr[cur--];}}}
};
三快乐数
链接202. 快乐数 - 力扣LeetCode 思路由于鸽巢原理最后必定会有两个数相等形成闭环即在某一时刻只有两种情况要么有数字等于1形成闭环要么会有两个数是相等的 那么我们可以使用在环形链表中一样使用快慢双指针来进行解答 class Solution {
public://函数实现每一位数平方和相加int bitsum(int n){int sum0;while(n){sumpow(n%10,2);n/10;}return sum;}//类似环形链表首先想到快慢双指针//不管最后有没有结果等于1都一定会有两个数相等形成闭环(重复循环)//slow与fast一定在某个时刻相等 bool isHappy(int n) {int slown,fastn;while(slow!1){slowbitsum(slow);fastbitsum(bitsum(fast));if(slowfast){break;}}return slow1;}
};
四盛最多水的容器
oj链接11. 盛最多水的容器 - 力扣LeetCode 思路使用两个指针一个在最左一个在最右算出结果进行调整移动时要移动两个中最小的那一个(短板效应)在各种结果中找出最大的容器即为题目所求 class Solution {
public:int maxArea(vectorint height) {//ret存储的是最多容纳的水int left0,rightheight.size()-1,retINT_MIN;while(leftright){//更新ret的值始终保持是所有盛水容器当中最大的retmax(ret,(right-left)*min(height[left],height[right]));//要去移动最小的高//如果是移到最大的距离在减小(高度是按最小的来算的)结果只会是减不会增if(height[left]height[right]){left;}else{right--;}}return ret;}
};
五有效三角形的个数
oj链接611. 有效三角形的个数 - 力扣LeetCode 思路先对数组进行排升序排序后要先固定最大的那个值然后就可以用双指针算法来解决问题:(与上面的思路大致相同) class Solution {
public:int triangleNumber(vectorint nums) {//先将数组进行排升序sort(nums.begin(),nums.end());int count0,left0,right0;//固定最后一个数(最大的数nums[i])for(int inums.size()-1;i0;i--){//一定left最大的数左边right进行移动left0,righti-1;while(leftright){//两个数相加最大的数则要移动left使得和变大if(nums[left]nums[right]nums[i]){left;}else{//left向后无论怎么移动和一定nums[i]即满足三角形任意两者之和大于第三边countright-left;right--;}}}return count;}
};
六 寻找总价格为目标值的两个商品 oj链接LCR 179. 查找总价格为目标值的两个商品 - 力扣LeetCode
思路与上面大体一致比较简单这里就不写了
class Solution {
public:vectorint twoSum(vectorint price, int target) {vectorint ans;int left0,rightprice.size()-1;while(leftright){if(price[left]price[right]target){left;}else if(price[left]price[right]target){right--;}else{ans.push_back(price[left]);ans.push_back(price[right]);break;}}return ans;}
};
七三数之和
oj链接LCR 007. 三数之和 - 力扣LeetCode 思路与有效三角形的个数类似先固定一个数再使用双指针进行移动找到nums[left]nums[right]-固定数。但实现起来要考虑两个细节 1不漏在找到符合值后两个指针不要‘停’,继续靠拢进行查找 2去重找到后要判断在接下来移动的时候是否会遇到重复数(遇到就直接跳过) class Solution {
public:vectorvectorint threeSum(vectorint nums) {sort(nums.begin(),nums.end());//C直接开辟二维数组vectorvectorint ans;int left0,right0,nnums.size();//固定最左边一个数在利用二数先加的题的思路去实现//但要考虑1不漏 2去重for(int i0;in;){if(nums[i]0){break;}lefti1,rightn-1;while(leftright){if(nums[left]nums[right]-nums[i]){right--;}else if(nums[left]nums[right]-nums[i]){left;}else{//C语言要开辟数组这里直接push_back爽ans.push_back({nums[left],nums[right],nums[i]});//不漏left,right--;//去重判断while循环条件先在后面否则会有越界风险while(leftrightnums[left]nums[left-1]){left;}while(leftrightnums[right]nums[right1]){right--;} }}//去重i;while(innums[i]nums[i-1]){i;}}return ans;}
};
对比用C语言写的要进行对二维数组的开辟非常麻烦
/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/int cmp(const void * a, const void * b)
{return ( *(int*)a - *(int*)b );
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){*returnSize0;//初始化//排序qsort(nums,numsSize,sizeof(int),cmp);//为规定的返回值创建类型相同的数组int** ans(int**)malloc(sizeof(int*)*numsSize*numsSize);//返回数组的数组要malloc*returnColumnSizes(int*)malloc(sizeof(int)*numsSize*numsSize);//参考两数之和利用双指针算法但要考虑去重数组越界问题for(int i0;inumsSize;){int begini1,endnumsSize-1,targetnums[i];//如果固定的值0,那么三数相加就不可能0(小优化)if(target0) break;//在固定值后在[begin,end]的区间内进行查找while(beginend){if(nums[begin]nums[end]-target){//二级数组ans中malloc存储三元数组的值(类似坐标的方式进行表达)ans[*returnSize](int*)malloc(sizeof(int)*3);//要返回数量的大小(*returnColumnSizes)[*returnSize]3;ans[*returnSize][0]nums[begin];ans[*returnSize][1]nums[end];ans[*returnSize][2]target;(*returnSize);begin;end--;//[0,0,0,0,0]while(beginend nums[begin]nums[begin-1]) begin;while(beginend nums[end]nums[end1]) end--;}else if(nums[begin]nums[end]-target) end--;else if(nums[begin]nums[end]-target) begin;}i;while(inumsSize nums[i]nums[i-1]) i;}return ans;
} 八四数之和
oj链接18. 四数之和 - 力扣LeetCode 思路与三数之和类似多个固定的数和溢出问题的解决 class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {sort(nums.begin(),nums.end());vectorvectorint ans;int left0,right0,nnums.size(),sum0;for(int i0;in;){for(int ji1;jn;){leftj1,rightn-1;//处理数据溢出long long aim(long long)target-nums[i]-nums[j];while(leftright){sumnums[left]nums[right];if(sumaim){left;}else if(sumaim){right--;}else{ans.push_back({nums[left],nums[right],nums[i],nums[j]});left,right--;while(leftrightnums[left]nums[left-1]){left;}while(leftrightnums[right]nums[right1]){right--;}}}j;while(jnnums[j]nums[j-1]){j;}}i;while(innums[i]nums[i-1]){i;}}return ans;}
};
