网站服务器租金,郴州市北湖区,劳务建筑公司网站,那里有制作网站企业目录
1.双指针#xff1b;
2.滑动窗口#xff1b;
3.二分查找#xff1b;
4.前缀和#xff1b; 1.双指针#xff1b;
包括对撞指针和快慢指针(一般用来循环#xff09;#xff1b;
题目类型#xff1a;移动零#xff0c;复写零#xff0c;快乐数#xff0c;盛…目录
1.双指针
2.滑动窗口
3.二分查找
4.前缀和 1.双指针
包括对撞指针和快慢指针(一般用来循环
题目类型移动零复写零快乐数盛水最多的容器有效三角形的个数三数之和四数之和。
举个例子
移动零
首先考虑暴力方法直接遇到0元素插入到数组结尾。
优选之后使用两个指针 (记录下标并非真正的指针cur和dest。
cur如果遇到0元素就非零元素就和dest进行交换交换之后dest直到cur走到结尾。 代码编写
class Solution
{
public:void moveZeroes(vectorint nums) {int cur0,dest-1;while(curnums.size()){if(nums[cur]0){cur;}else{dest;swap(nums[dest],nums[cur]);cur;}}}
};
复写零
如果指针此c前面开始复写会造成数据被覆盖的问题那么采用从后面到前面的方法。
首先进行移动指针cur遇到非零移动一步dest移动一步cur遇到零移动一步dest移动两步。 还有特殊情况dest跳出边界了就把 arr[dest-1]0;dest-2;cur-1; 看cur的值是否为0非零就将cur的值直接赋值给dest是零就赋值两次给dest。直到cur遍历完。 代码编写
class Solution
{
public:void duplicateZeros(vectorint arr) {int dest-1;int cur0;int narr.size();//将指针移动尾部while(curn){if(arr[cur]){dest;}else{dest2;}if(dest n-1) break;cur;}//处理边界,可能跳出范围了if(dest n){arr[dest-1]0;dest-2;cur--;}while(cur 0){if(arr[cur]){arr[dest--]arr[cur--]; }else{arr[dest--]0;arr[dest--]0;cur--;}}}
};
三数之和
采用双指针的方法首先固定一个数只要找到和这个数相反的数之和就可以找到其他两个数。
那么就在 [i1,n-1]之间进行查找。如果其和大于 t 那么就要将右边指针移动后一步如果其和小于 t 那么就要将左边指针移动前一步。找到也不能停止看是否有其他选择。
那么这里就会涉及到两个去重的操作。首先是left和right区间的去重和上一次一样的数就直接跳过即可。外面固定的数也是一样的去重操作。 上代码
class Solution
{
public:vectorvectorint threeSum(vectorint nums) {int nnums.size();vectorvectorint ret;//先进行排序sort(nums.begin(),nums.end());for(int i0;in;){int lefti1;int rightn-1;int target-nums[i];while(left right){int sumnums[left]nums[right];if(sum target){left;}else if(sum target){right--;}else{//如果找到那么就插入ret并且往后面看看找到不同的解如果有重复元素就跳过。ret.push_back({nums[i],nums[left],nums[right]});right--;left;//跳过步骤while(left right nums[left]nums[left-1]) left;while(left right nums[right]nums[right1])right--;}}i;//i也是看重复元素.这个很考验能力到底写哪里很重要。while(i n nums[i]nums[i-1]) i;}return ret;}
};
2.滑动窗口
题目类型长度最小的子数组无重复字符的最长子串最大连续1的个数将x减少到零的最小操作数。题目就是找进入窗口出窗口更新数据。
长度最小的子数组
left和rightsumright的值并且与 t 比较len记录长度大于t的话出窗口更新lenright-left1;并且left。 上代码
class Solution
{
public:int minSubArrayLen(int target, vectorint nums) {//滑动窗口的题目就是1.进入窗口2.出窗口3.更新结果//多看过程int left0,right0;int lenINT_MAX;int sum0;//while循环进不去for循环简单。for(int left0,right0;rightnums.size();right){//不进窗口就right并且sum;sumnums[right];//进窗口就判断小于不断修改len以及sum.直到出去窗口//相当于两层循环。while(sum target){lenmin(len,right-left1);sum-nums[left];}}return lenINT_MAX?0:len;}
}; 3.二分查找
定义left和right的指针。
分为朴素二分和复杂二分。
左右指针以及中间指针进行移动来查找数据。
注意分析left,right,mid的取值。结束条件。
二分查找
class Solution
{
public:int search(vectorint nums, int target) {int left 0,rightnums.size()-1;while(left right){int midleft(right-left)/2;if(nums[mid] target){leftmid1;}else if(nums[mid] target){rightmid-1;}else{return mid;}}return -1;}
}; 复杂二分
class Solution
{
public:vectorint searchRange(vectorint nums, int target){if(nums.size()0) return {-1,-1};//找左端点int begin0;int left0,rightnums.size()-1;while(left right)//自己画图分析是否等于{int midleft(right-left)/2;//自己分析if(nums[mid] target){leftmid1;}else {rightmid;}}//判断是否有结果if(nums[left] ! target){return {-1,-1};}else{beginleft;}//找右端点left0,rightnums.size()-1;while(left right){int midleft(right-left1)/2;//自己分析if(nums[mid] target){leftmid;}else{rightmid-1;}}return {begin,right};}
};
4.前缀和
1.首先找规律创建dp前缀和数组使用前缀和数组完成要求。
#include iostream
using namespace std;
#includevectorint main()
{// 1.读入数据int n,q;cinnq;vectorint arr(n1);for(int i1;in;i) cinarr[i];//预处理出来前缀和数组vectorlong long dp(n1);for(int i1;in;i) dp[i]dp[i-1]arr[i];//使用前缀和数组int l 0,r0;while(q--){cinlr;coutdp[r]-dp[l-1]endl;}return 0;
}
