网站开发与维护工资多少,app软件下载网站源码,专业广州做网站公司,做软件下载网站违法吗目录 一、双指针 二、双指针题目 1.移动零 解法#xff1a;
代码#xff1a; 2.复写零
编辑 解法#xff1a; 代码#xff1a;
边界情况处理: 3.快乐数
编辑 解法:快慢指针
代码#xff1a;
4.盛水最多的容器 解法#xff1a;#xff08;对撞指针#xff09;…目录 一、双指针 二、双指针题目 1.移动零 解法
代码 2.复写零
编辑 解法 代码
边界情况处理: 3.快乐数
编辑 解法:快慢指针
代码
4.盛水最多的容器 解法对撞指针
代码 5.有效三角形的个数
编辑
解法 代码
6.和为s的两个数字 解法对撞指针 代码
7.三数之和 解法 代码: 一、双指针 常⻅的双指针有两种形式⼀种是对撞指针⼀种是左右指针。 对撞指针⼀般⽤于顺序结构中也称左右指针。 对撞指针从两端向中间移动。⼀个指针从最左端开始另⼀个从最右端开始然后逐渐往中间逼近。 对撞指针的终⽌条件⼀般是两个指针相遇或者错开也可能在循环内部找到结果直接跳出循环也就是 left right 两个指针指向同⼀个位置left right 两个指针错开 快慢指针⼜称为⻳兔赛跑算法其基本思想就是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动。 这种⽅法对于处理环形链表或数组⾮常有⽤。 其实不单单是环形链表或者是数组如果我们要研究的问题出现循环往复的情况时均可考虑使⽤快 慢指针的思想。 快慢指针的实现⽅式有很多种最常⽤的⼀种就是 在⼀次循环中每次让慢的指针向后移动⼀位⽽快的指针往后移动两位实现⼀快⼀慢。 二、双指针题目 1.移动零 【数组分两块】是⾮常常⻅的⼀种题型主要就是根据⼀种划分⽅式将数组的内容分成左右两部 分。这种类型的题⼀般就是使⽤「双指针」来解决。 283. 移动零 - 力扣LeetCode 解法 两个指针 cur从左到右扫描整个数组dest已处理的数组中非零元素的最后位置 代码
class Solution {
public:void moveZeroes(vectorint nums) {//双指针for(int cur0,dest-1;curnums.size();cur)if(nums[cur])//非零元素swap(nums[dest],nums[cur]);//交换dest}
}; swap(nums[dest], nums[cur])这里的操作有两部分 dest先将 dest 指针向前移动一位。这个步骤确保了每当找到一个非零元素时它会被放置到数组的前面而 dest 会保持在下一个非零元素的位置。swap(nums[dest], nums[cur])将 cur 指向的非零元素与 dest 指向的元素交换位置。此时cur 指向的非零元素被放到数组的前面dest 也向前移动一位以准备接收下一个非零元素。 2.复写零
1089. 复写零 - 力扣LeetCode 解法 从后往前复写大体流程分为两步 先找到最后一个复写的数 先判断cur位置的值 决定dest向后移动一步或者两步 判断一下dest是否已经到结束为止 cur从后往前进行复写操作 代码
class Solution {
public:void duplicateZeros(vectorint arr) {//1.先找到最后一个数int cur0,dest-1,narr.size();while(curn){if(arr[cur]) dest;//不等于0走1步else dest2;//等于0走两步if(dest n-1) break;cur;}//2.处理一下边界情况最后一个元素是0需要复写两遍会导致越界if(dest n)//判断越界{arr[n - 1]0;cur--;dest-2;}//3.从后向前完成复写操作while(cur 0){if(arr[cur]) arr[dest--]arr[cur--];else{arr[dest--]0;arr[dest--]0;cur--;}}}
}; 边界情况处理: 如果越界1.n-1位置的值修改成0 2.cur向前移动一步 3.dest向前移动两步 3.快乐数 202. 快乐数 - 力扣LeetCode 解法:快慢指针 【快慢指针】有⼀个特性就是在⼀个圆圈中快指针总是会追上慢指针的也就是说他们总会相遇在⼀个位置上。如果相遇位置的值是 1 那么这个数⼀定是快乐数如果相遇位置不是 1的话那么就不是快乐 定义快慢指针满指针每次向后移动一步块指针每次向后移动两步判断相遇时候的值即可 补充求一个数n每个位置上的数组的平方和 1.把数 n 每⼀位的数提取出来 循环迭代下⾯步骤 int t n % 10 提取个位 n / 10 ⼲掉个位 直到 n 的值变为 0 2.提 取每⼀位的时候⽤⼀个变量 tmp 记录这⼀位的平⽅与之前提取位数的平⽅和 tmp tmp t * t 代码
class Solution {
public:int Sum(int n){int sum0;while(n){int tn%10;sumt*t;n/10;}return sum;}bool isHappy(int n) {//双指针solw走一步fast走两步int slown,fastSum(n);while(slow!fast){slowSum(slow);fastSum(Sum(fast));}return slow1;}
};
4.盛水最多的容器 11. 盛最多水的容器 - 力扣LeetCode 解法对撞指针 设两个指针 left right 分别指向容器的左右两个端点此时容器的容积 : v (right - left) * min( height[right], height[left]) 容器的左边界为 height[left] 右边界为 height[right] 。 为了⽅便叙述我们假设「左边边界」⼩于「右边边界」。 如果此时我们固定⼀个边界改变另⼀个边界⽔的容积会有如下变化形式 容器的宽度⼀定变⼩。 由于左边界较⼩决定了⽔的⾼度。如果改变左边界新的⽔⾯⾼度不确定但是⼀定不会超 过右边的柱⼦⾼度因此容器的容积可能会增⼤。 如果改变右边界⽆论右边界移动到哪⾥新的⽔⾯的⾼度⼀定不会超过左边界也就是不会 超过现在的⽔⾯⾼度但是由于容器的宽度减⼩因此容器的容积⼀定会变⼩的。 由此可⻅左边界和其余边界的组合情况都可以舍去。所以我们可以 left 跳过这个边界继续去判断下⼀个左右边界。 当我们不断重复上述过程每次都可以舍去⼤量不必要的枚举过程直到 left 与 right 相 遇。期间产⽣的所有的容积⾥⾯的最⼤值就是最终答案 代码
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(ret, v);// 移动指针if(height[left] height[right]) left;else right--;}return ret;}
}; 5.有效三角形的个数
611. 有效三角形的个数 - 力扣LeetCode 解法 先将数组排序 双指针法 从 i n-1 开始遍历每个可能的第三条边从最大的边开始。然后使用两个指针 left 和 right分别指向数组的起始和 i-1 位置。 如果 nums[left] nums[right] nums[i]说明当前的 left 和 right 可以和 nums[i] 组成一个三角形并且 [left, right-1] 之间的所有组合也满足条件。此时结果增加 right - left。如果不满足条件说明 nums[left] 太小无法与 nums[right] 和 nums[i] 组成三角形需要增大 left。 代码
class Solution {
public:int triangleNumber(vectorint nums) {sort(nums.begin(),nums.end());int nnums.size(),ret0;for(int in-1;i2;i--){int left0,righti-1;while(leftright){if(nums[left]nums[right]nums[i]){retright-left;//如果nums[left]nums[right]nums[i]说明[left,right-1]区间上的//所有元素均可以与nums[right]构成比nums[i]大的二元组//有right-left种right--;}else//nums[left] nums[right] nums[i]说明left位置的元素是不可能与[left1,right]位置上的元素构成满足条件的二元组{left;}}}return ret;}
};
6.和为s的两个数字 解法对撞指针 初始化左右指针left 0 和 right price.size() - 1。left 指向数组的起始位置right 指向数组的末尾位置。 循环条件while (left right)。这表示只要 left 小于 right就继续进行搜索。如果 left right说明已经遍历完了所有可能的组合。 计算当前和int sum price[left] price[right]。计算当前指针所指向的两个元素的和。 判断和的关系 如果和大于目标值sum target说明当前两个数的和太大了可以将 right 指针左移减小和。如果和小于目标值sum target说明当前两个数的和太小了可以将 left 指针右移增大和。如果和等于目标值sum target找到目标和直接返回这两个元素。 代码
class Solution {
public:vectorint twoSum(vectorint price, int target) {int left0,rightprice.size()-1;while(leftright){int sumprice[left]price[right];if(sumtarget) right--;//当 nums[left] nums[right] target 时,nums[right]与最小的数相加还大于target剩下的也肯定大于直接right--else if(sumtarget) left;//同理当 nums[left] nums[right] target 时,直接leftelse return {price[left],price[right]};}return {-1,-1};}
};
7.三数之和
15. 三数之和 - 力扣LeetCode 解法 利⽤在两数之和那⾥⽤的双指针思想 先排序 然后固定⼀个数 a 在这个数后⾯的区间内使⽤「双指针算法」快速找到两个数之和等于 -a 即可。 但是要注意的是这道题⾥⾯需要有「去重」操作 1.找到⼀个结果之后 left 和 right 指针要「跳过重复」的元素 2.当使⽤完⼀次双指针算法之后固定的 a 也要「跳过重复」的元素 代码:
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint ret;//1.排序sort(nums.begin(),nums.end());//2.利用双指针解决问题int nnums.size();for(int i0;in;){if(nums[i]0) break;int lefti1,rightn-1,target-nums[i];while(leftright){int sumnums[left]nums[right];if(sumtarget)right--;else if(sumtarget)left;else{ret.push_back({nums[i],nums[left],nums[right]});left,right--;while(leftright nums[left]nums[left-1])left;while(leftright nums[right]nums[right1]) right--;}}i;while(in nums[i]nums[i-1]) i;}return ret;}
}; 感谢再见
