模板网站如何引擎收录,昆明网站,网站制作设计方案,wordpress增加定位锚点1.移动零
移动零
题目描述#xff1a; 思路#xff1a;
本题我们把数组分块#xff0c;将非零元素移动到左边#xff0c;为零元素移动右边。
我们使用双指针算法#xff08;利用数组下标来充当指针#xff09;
两个指针的作用#xff1a;
cur#xff1a;从左往右…1.移动零
移动零
题目描述 思路
本题我们把数组分块将非零元素移动到左边为零元素移动右边。
我们使用双指针算法利用数组下标来充当指针
两个指针的作用
cur从左往右扫描数组遍历数组
dest已经处理的区间内非零元素的最后一个位置
我们将数组分为三个区间 如何做到
cur从前往后遍历的过程中
1,遇到0元素cur;
2.遇到非零元素
swap(dast1,cur);destcur;
参考代码如下
class Solution {
public:void moveZeroes(vectorint nums) {int cur 0;int dest -1;while(cur nums.size()){if(nums[cur] 0){cur;}else{swap(nums[cur],nums[dest1]);cur;dest;}}}
};
这个题其实我们用到了快排的思想 2.复写零
复写零
题目描述 题目分析题目说不要超过数组长度其实就是告诉我们不要越界题目还告诉我们不能创建额外数组让我们就地修改原数组我们不需要返回任何内容。
思路我们依旧使用双指针算法先根据“异地”操作然后优化成双指针下的“就地”操作
1.先找到最后一个复写的数
先判断cur位置的值决定dest向后移动一步或者两步判断一下dest是否已经到结束为止cur
2.然后从后向前复写
这里有个例外需要额外处理一下 以上这种情况在我们进行从后向前复写的时候会发生越界访问把这个位置给修改为0在LeetCode上越界访问会直接报错所以我们要单独处理一下这种情况
n-1位置直接修改为0在让dest - 2cur--;
参考代码如下
class Solution {
public:void duplicateZeros(vectorint arr) {int dest -1;int cur 0;//找到最后一个复写while(cur arr.size()){if(arr[cur] 0){dest 2;}else{dest;}if(dest arr.size()-1){break;}cur;}//处理越界if(dest arr.size()){arr[arr.size()-1] 0;--cur;dest - 2;}while(dest 0){if(arr[cur] 0){arr[dest--] 0;arr[dest--] 0;cur--;}else{arr[dest--] arr[cur--];}}}
}; 3.快乐数
快乐数
题目描述 题目分析 题目意思大概就是这样。
思路我们之前在数据结构中不是学了一个判断链表是否有环这里就可以运用起来使用快慢双指针。
1.定义快慢指针
2.快慢指针每次向后移动一步快指针每次向后移动两步
3.判断相遇时候的值即可。 参考代码如下
class Solution {
public:int bitSum(int n){int sum 0;while(n){int t n % 10;sum t * t;n / 10;}return sum;}bool isHappy(int n) {int slow n,fast bitSum(n);while(slow ! fast){slow bitSum(slow);fast bitSum(bitSum(fast));}return slow 1;}
}; 4.盛最多水的容器
盛最多水的容器
题目描述 题目分析如示例1下标为1的它的高度是8和下标为8的它的高度为7这个容器的高度不能超过7也就是取他们的最小值那么从下标1到下标8的宽度为7也就是下标为1到下标为8的距离得出高为7宽为7相乘得出49那么最多容纳水量49而我们要取这个容器里面的最大水量。
思路
解法一大部分人最容易想到的就是用两个for循环暴力枚举让1和后面的数依次枚举但是这样时间复杂度是O(N^2)效率太低。 解法二
利用单调性使用双指针来解决问题时间复杂度O(N)
我们使用双指针一个left一个right选取这两个数的最小值也就是高度然后让right减left得出宽度进行计算即可把结果存储起来选出最大值也就是最大水量了然后我们让小的那个数往前走依次内推这里我们知道如果一个数的宽度总是在减小那么这个水容量也会减小而我们需要的是最大水容量。
参考代码
class Solution {
public:int maxArea(vectorint height) {int left 0,right height.size()-1,ret 0;while(left right){int v min(height[left],height[right]) * (right - left);ret max(v,ret);if(height[left] height[right]) left;else --right;}return ret;}
}; 5. 有效三角形的个数
有效三角形的个数
题目描述 思路
解法一暴力枚举下面是一个伪代码它的时间复杂度是O(N^3)效率太低 解法二我们先把数组排序一下然后使用双指针算法我们让leftright的结果和最后一个也就是最大值进行比较如果大于说明right-left这个区间的值都能组成我们直接让right--如果left-right的结果小于最大值说明right-left这个区间不能组成所以我们left比较完之后我们在让倒数第二个元素做为最大值对他们进行比较以此内推。时间复杂度为O(N^2) 参考代码
class Solution {
public:int triangleNumber(vectorint nums) {sort(nums.begin(),nums.end());int ret 0,n nums.size()-1;for(int i n;i 2;i--){int left 0,right i-1;while(left right){if(nums[left] nums[right] nums[i]){ret right -left;--right;}else{left;}}}return ret;}
}; 6.查找总价格为目标的两个商品
查找总价格为目标的两个商品
题目描述 解法一如下是伪代码 解法二本题解法使用双指针我们让最左边的值和最右边的值进行相加然后和target进行比较那么比较的结果无法就是三种第一种sum t第二种sumt第三张sumtsum就是左边和右边之和如果大于t说明left到right都大于那么我们-right即可如果小于t说明left到right都小于t所以left即可以此内推。 参考代码
class Solution {
public:vectorint twoSum(vectorint price, int target) {int n price.size()-1; int left 0,right n;vectorintv;while(left right){int sum price[left] price[right];if(sum target){--right;}else if(sum target){left;}else{return {price[left],price[right]};}}return {-1,-1};}
}; 7.三数之和
三数之和
题目描述 题目分析 我们看示例1可以看到三个数相加之和要等于0题目中说不可以重复那是什么意思呢如上我们可以看到-1 0 1和0 1 -1还有-1 1 0他们都等于0但是他们里面的元素是相同的只不过位置不同这样就重复了只需一种即可。
思路
解法一排序暴力解法利用set去重时间复杂度 o(N^3),暴力解法其实就是一个一个去试三个for循环
解法二我们依旧使用双指针如下
排序固定一个数a(a0因为已经排过序了如果a0那么leftright只会更加大因为left是从a后面开始的)在该数后面的区间内利用“双指针算法”快速找到两个的和等于-a即可。
处理细节问题
1.去重
找到一种结果之后left和right指针要跳过重复元素当使用完一次双指针算法之后i也需要跳过重复的元素注意避免越界
2.不漏
找到一种结果之后不要“停”缩小区间继续寻找 参考代码
class Solution {
public:vectorvectorint threeSum(vectorint nums) {sort(nums.begin(),nums.end());int n nums.size();vectorvectorint ret;for(int i 0;i n;){int left i1,right n-1,target -nums[i];if(nums[i] 0) break;while(left right){int sum nums[left] nums[right];if(sum target) --right;else if(sum target) left;else{ret.push_back({nums[i],nums[left],nums[right]});left,--right;//去重leftrightwhile(left right nums[left] nums[left -1]) left;while(left right nums[right] nums[right 1]) --right;}}//去重ii;while(i n nums[i] nums[i-1]) i;}return ret;}
}; 8.四数之和
四数之和
题目描述 这个题和三数之和的题类似
解法一排序暴力枚举利用set去重
解法二排序双指针
依次固定一个数a在a后面的区间内利用“三数之和”找到三个数使这三个数等于target-a即可
补充一下上面说的三数之和
依次固定一个数b在b后面的区间内利用“双指针”找到两个数使这两个的和等于target-a-b即可。
时间复杂度O(N^3) 参考代码
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {sort(nums.begin(),nums.end());vectorvectorintret;int n nums.size();for(int i 0;in;){for(int j i1;jn;){long long amin (long long)target - nums[i] - nums[j];int left j 1,right n-1;while(left right){int sum nums[left] nums[right];if(left right sum amin)--right;else if(left right sum amin) left;else{ret.push_back({nums[i],nums[j],nums[left],nums[right--]});//去重left,rightwhile(left right nums[left] nums[left-1]) left;while(left right nums[right] nums[right1]) -- right;}}//去重jj;while(j n nums[j] nums[j-1]) j;}//去重ii;while(i n nums[i] nums[i-1]) i;}return ret;}};
结束语 掌握双指针算法对于解决复杂问题至关重要刷题则是积累经验、提升能力的关键途径。通过不断练习我们不仅能提升自己的解题速度和准确性更能培养灵活运用各种算法的能力为解决更为复杂的问题打下坚实基础。
