网站开发编程入门学习,做团购网站需要注册哪些商标,软件开发工资一般多少,河北百度seo点击软件双指针
我们常见的双指针的形式有两种#xff0c;一种是对撞指针#xff0c;一种是快慢指针#xff01; 对撞指针#xff1a;一般用于顺序结构中#xff0c;也称左右指针。 1、对撞指针从两端向中间移动。一个指针从最左端开始#xff0c;另一个从最右端开始#xff0c…双指针
我们常见的双指针的形式有两种一种是对撞指针一种是快慢指针 对撞指针一般用于顺序结构中也称左右指针。 1、对撞指针从两端向中间移动。一个指针从最左端开始另一个从最右端开始然后逐渐向中间逼近。 2、对撞指针的终止条件一般是两个指针相遇或者错开也可能在循环内部找到结果跳出循环也就是以下两种情况 left right (两个指针指向同一个位置) left right两个指针错开 快慢指针又称为龟兔赛跑算法。 1、其基本意思是使用两个移动速度不同的指针在数组或者链表等序列结构上移动。 2、这种方法对于处理环形链表或者数组非常有用。 3、在⼀次循环中每次让慢的指针向后移动⼀位⽽快的指针往后移动两位实现⼀快⼀慢。 一、移动零
283. 移动零 - 力扣LeetCode 1、题目描述 给定⼀个数组 nums 编写⼀个函数将所有 0 移动到数组的末尾同时保持⾮零元素的相对顺序。 请注注意必须在不复制数组的情况下原地对数组进⾏操作。 ⽰例1: 输⼊: nums [0,1,0,3,12] 输出:[1,3,12,0,0] ⽰例2 输⼊:nums [0] 输出:[0] 2、算法思路 在本题中我们可以⽤⼀个cur 指针来扫描整个数组另⼀个 dest 指针⽤来记录⾮零数序列的最后⼀个位置。根据cur在扫描的过程中遇到的不同情况分类处理实现数组的划分。在 cur 遍历期间使[0, dest] 的元素全部都是⾮零元素 [dest 1, cur - 1] 的元素全是零。
当我们遍历数组是遇到0时只需要 cur 遇到非0时只需要dest,并且交换dest和cur位置的元素之后让cur,扫描下一个元素。
3、算法代码
class Solution
{
public:void moveZeroes(vectorint nums){for(int cur 0, dest -1; cur nums.size(); cur){ if(nums[cur]) // 处理⾮零元素{swap(nums[dest], nums[cur]);} }}
};
二、复写0
1089. 复写零 - 力扣LeetCode 1、题目描述 给你一个长度固定的整数数组 arr 请你将该数组中出现的每个零都复写一遍并将其余的元素向右平移。 注意请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改不要从函数返回任何东西。 示例 1 输入arr [1,0,2,3,0,4,5,0]
输出[1,0,0,2,3,0,0,4]
解释调用函数后输入的数组将被修改为[1,0,0,2,3,0,0,4]示例 2
输入arr [1,2,3]
输出[1,2,3]
解释调用函数后输入的数组将被修改为[1,2,3]2、算法思路
如果「从前向后」进⾏原地复写操作的话由于 0 的出现会复写两次导致没有复写的数 [被覆盖掉]。因此我们选择「从后往前」的复写策略。 但是「从后向前」复写的时候我们需要找到「最后⼀个复写的数」因此我们的⼤体流程分两 步 i. 先找到最后⼀个复写的数 ii. 然后从后向前进⾏复写操作
3、算法代码
class Solution {
public:void duplicateZeros(vectorint arr) {int cur0,dest0;//先找出最后一位数while(curarr.size()){if(arr[cur]){dest;}else{dest2;}if(destarr.size()){break;}cur;}//边界情况if(destarr.size()1){arr[arr.size()-1]0;dest-2;cur--;}//从后往前开始复习while(cur0){if(arr[cur]){arr[--dest]arr[cur];}else{arr[--dest]0;arr[--dest]0;}cur--;}}
};
三、快乐数
202. 快乐数 - 力扣LeetCode 1、题目描述 编写⼀个算法来判断⼀个数 n 是不是快乐数。 「快乐数」定义为 ◦ 对于⼀个正整数每⼀次将该数替换为它每个位置上的数字的平⽅和。 ◦ 然后重复这个过程直到这个数变为1也可能是⽆限循环但始终变不到 1 。 ◦ 如果这个过程结果为 1 那么这个数就是快乐数。 ◦ 如果 n 是快乐数就返回 true 不是则返回 false 。 ⽰例1 输⼊ n 19 输出 true 解释 19 - 1 * 1 9 * 9 82 82 - 8 * 8 2 * 2 68 68 - 6 * 6 8 * 8 100 100 - 1 * 1 0 * 0 0 * 0 1 ⽰例2 输⼊ n 2 输出 false 解释这⾥省去计算过程只列出转换后的数 2 - 4 - 16 - 37 - 58 - 89 - 145 - 42 - 20 - 4 - 16 往后就不必再计算了因为出现了重复的数字最后结果肯定不会是 1 2、算法思路
为了⽅便叙述将「对于⼀个正整数每⼀次将该数替换为它每个位置上的数字的平⽅和」这⼀个 操作记为 x 操作 题⽬告诉我们当我们不断重复 x 操作的时候计算⼀定会「死循环」死的⽅式有两种 ▪ 情况⼀⼀直在 1 中死循环即1 - 1 - 1 - 1...... ▪ 情况⼆在历史的数据中死循环但始终变不到 1 由于上述两种情况只会出现⼀种因此只要我们能确定循环是在「情况⼀」中进⾏还是在「情 况⼆」中进⾏就能得到结果。
三、算法嗲吗
class Solution {
public:int mulsum(int n){int sum0;while(n){sumpow(n%10,2);n/10;}return sum;}bool isHappy(int n) {int fastmulsum(n);int slown;while(fast!slow){slowmulsum(slow);fastmulsum(mulsum(fast));}return slow1;}
};
四、盛水最多的容器
11. 盛最多水的容器 - 力扣LeetCode
1、题目描述
给定⼀个⻓度为 n 的整数数组height。有 n 条垂线第i条线的两个端点是 (i, 0) 和 (i,height[i]) 。 找出其中的两条线使得它们与x轴共同构成的容器可以容纳最多的⽔。 返回容器可以储存的最⼤⽔量 说明你不能倾斜容器。 ⽰例1 输⼊ [1,8,6,2,5,4,8,3,7] 输出 49
解释图中垂直线代表输⼊数组 [1,8,6,2,5,4,8,3,7] 。在此情况下容器能够容纳⽔表⽰为蓝⾊部分的最⼤值为49 。
2、算法思路
1暴力求解会超时
枚举出能构成的所有容器找出其中容积最⼤的值。 容器容积的计算⽅式 设两指针i j 分别指向⽔槽板的最左端以及最右端此时容器的宽度为 j - i 。由于容器的⾼度由两板中的短板决定因此可得容积公式 v (j - i) * min(height[i], height[j])
2对撞指针
设两个指针 left right 分别指向容器的左右两个端点此时容器的容积: v (right - left) * min( height[right], height[left]) 容器的左边界为 height[left] 右边界为 height[right] 。 为了⽅便叙述我们假设「左边边界」⼩于「右边边界」。 如果此时我们固定⼀个边界改变另⼀个边界⽔的容积会有如下变化形式 ◦ 容器的宽度⼀定变⼩。 ◦ 由于左边界较⼩决定了⽔的⾼度。如果改变左边界新的⽔⾯⾼度不确定但是⼀定不会超 过右边的柱⼦⾼度因此容器的容积可能会增⼤。 ◦ 如果改变右边界⽆论右边界移动到哪⾥新的⽔⾯的⾼度⼀定不会超过左边界也就是不会 超过现在的⽔⾯⾼度但是由于容器的宽度减⼩因此容器的容积⼀定会变⼩的。 由此可⻅左边界和其余边界的组合情况都可以舍去。所以我们可以 left 跳过这个边界继 续去判断下⼀个左右边界。 当我们不断重复上述过程每次都可以舍去⼤量不必要的枚举过程直到 left 与 right 相 遇。期间产⽣的所有的容积⾥⾯的最⼤值就是最终答案
3、代码实现
class Solution {
public:int maxArea(vectorint height) {int nheight.size();int left0,rightn-1;int max0;while(rightleft){int v((right-left)*min(height[left],height[right]));maxfmax(max,v);if(height[left]height[right]){right--;}else{left;}}return max;}
};
五、有效三角形的个数
611. 有效三角形的个数 - 力扣LeetCode 1、题目描述 给定一个包含非负整数的数组 nums 返回其中可以组成三角形三条边的三元组个数。 示例 1: 输入: nums [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3 示例 2: 输入: nums [4,2,3,4]
输出: 4 2、算法思路
1暴力求解会超时
三层 for 循环枚举出所有的三元组并且判断是否能构成三⻆形。 判断三⻆形的优化 ▪ 如果能构成三⻆形需要满⾜任意两边之和要⼤于第三边。但是实际上只需让较⼩的两条边 之和⼤于第三边即可。 ▪ 因此我们可以先将原数组排序然后从⼩到⼤枚举三元组⼀⽅⾯省去枚举的数量另⼀⽅ ⾯⽅便判断是否能构成三⻆形。
class Solution {
public:int triangleNumber(vectorint nums) {int nnums.size();int count0;sort(nums.begin(),nums.end());for(int i0;in;i){for(int ji1;jn;j){for(int kj1;kn;k){if(nums[i]nums[j]nums[k]){count;}}}}return count;}
};
2排序双指针
先将数组排序。 根据「解法⼀」中的优化思想我们可以固定⼀个「最⻓边」然后在⽐这条边⼩的有序数组中找 出⼀个⼆元组使这个⼆元组之和⼤于这个最⻓边。由于数组是有序的我们可以利⽤「对撞指针」来优化。 设最⻓边枚举到 i 位置区间 [left, right] 是 i 位置左边的区间也就是⽐它⼩的区间 ◦ 如果 nums[left] nums[right] nums[i] ▪ 说明 [left, right - 1] 区间上的所有元素均可以与 nums[right] 构成⽐nums[i] ⼤的⼆元组 ▪ 满⾜条件的有 right - left 种 ▪ 此时 right 位置的元素的所有情况相当于全部考虑完毕 right-- 进⼊下⼀轮判断 ◦ 如果 nums[left] nums[right] nums[i] ▪ 说明 left 位置的元素是不可能与[left 1, right] 位置上的元素构成满⾜条件的⼆元组 ▪ left 位置的元素可以舍去 left 进⼊下轮循环
3、算法代码
class Solution {public:int triangleNumber(vectorint nums) {sort(nums.begin(),nums.end());int sum0;for(int inums.size()-1;i2;i--){int left0,righti-1;while(rightleft){if(nums[left]nums[right]nums[i]){sumsum(right-left);right--;}else{left;}}}return sum;}
};
六、和为S的两个数字
LCR 179. 查找总价格为目标值的两个商品 - 力扣LeetCode
1、题目描述 输⼊⼀个递增排序的数组和⼀个数字 s 在数组中查找两个数使得它们的和正好是 s 。如果有多对数字的和等于 s 则输出任意⼀对即可。 ⽰例1 输⼊ nums [2,7,11,15], target 9 输出 [2,7] 或者 [7,2] 2、算法思路
1暴力求解会超时
两层 for 循环列出所有两个数字的组合判断是否等于⽬标值。
2对撞指针
由于题目给的是一个递增排序的数组我们就可以利用数组的单调性
设指针i指向第一个元素也就是最小的一个元素设指针j指向最后一个元素。设两个的和s nums[i] nums[j]如果s target就意味着nums[j] 分别与 nums[0], nums[1], nums[2]...nums[j - 1]构成的和都是 target的此时就需要j--。
同理如果s target, 就意味着nums[i] 分别与 nums[i 1], nums[i 2]...nums[j]构成的和都是 target的因此i。
class Solution {
public:vectorint twoSum(vectorint price, int target) {int nprice.size();int left0,rightn-1;while(rightleft){int sumprice[left]price[right];if(sumtarget){right--;}else if(sumtarget){left;}else{return {price[left],price[right]};}}return {-1,-1};}
};
七、三数之和
15. 三数之和 - 力扣LeetCode 1、题目描述 给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。 注意答案中不可以包含重复的三元组。 示例 1 输入nums [-1,0,1,2,-1,-4]
输出[[-1,-1,2],[-1,0,1]]
解释
nums[0] nums[1] nums[2] (-1) 0 1 0 。
nums[1] nums[2] nums[4] 0 1 (-1) 0 。
nums[0] nums[3] nums[4] (-1) 2 (-1) 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意输出的顺序和三元组的顺序并不重要。 示例 2 输入nums [0,1,1]
输出[]
解释唯一可能的三元组和不为 0 。示例 3 输入nums [0,0,0]
输出[[0,0,0]]
解释唯一可能的三元组和为 0 。 2、算法思路
与两数之和稍微不同的是题⽬中要求找到所有「不重复」的三元组。那我们可以利⽤在两数之和 那⾥⽤的双指针思想来对我们的暴⼒枚举做优化
i. 先排序 ii. 然后固定⼀个数 a iii. 在这个数后⾯的区间内使⽤「双指针算法」快速找到两个数之和等于 -a 即可。 但是要注意的是这道题⾥⾯需要有「去重」操作 i. 找到⼀个结果之后 left 和 right 指针要「跳过重复」的元素 ii. 当使⽤完⼀次双指针算法之后固定的 a 也要「跳过重复」的元素
3、算法代码
class Solution {
public:vectorvectorint threeSum(vectorint nums) {sort(nums.begin(),nums.end());vectorvectorint vv;int nnums.size();for(int i0;in;){if(nums[i]0) break;int lefti1,rightn-1,targe-nums[i];while(rightleft){int sumnums[left]nums[right];if(sumtarge) right--;else if(sumtarge) left;else {vv.push_back({nums[i],nums[left],nums[right]});right--,left;while(rightleftnums[left]nums[left-1]) left;while(rightleftnums[right]nums[right1]) right--;}}i;while(i n nums[i] nums[i-1]) i;}return vv;}
};
八、四数之和
18. 四数之和 - 力扣LeetCode 1、题目描述 给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为两个四元组重复 0 a, b, c, d na、b、c 和 d 互不相同nums[a] nums[b] nums[c] nums[d] target 你可以按 任意顺序 返回答案 。 示例 1 输入nums [1,0,-1,0,-2,2], target 0
输出[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]示例 2 输入nums [2,2,2,2,2], target 8
输出[[2,2,2,2]] 2、算法思路
1. 依次固定⼀个数 a 2. 在这个数 a 的后⾯区间上利⽤「三数之和」找到三个数使这三个数的和等于 target- a 即可
3、算法代码
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint vv;sort(nums.begin(),nums.end());int nnums.size();for(int i0;in;) //定一个数{for(int ji1;jn;) //三数之和{ int leftj1,rightn-1;long long aim(long long)target-nums[i]-nums[j];while(rightleft){int sumnums[left]nums[right];if(sumaim) right--;else if(sumaim) left;else{vv.push_back({nums[i],nums[j],nums[left],nums[right--]});while(rightleftnums[left]nums[left-1]) left;while(rightleftnums[right]nums[right1]) right--;}}j;while(jnnums[j]nums[j-1]) j;} i;while(innums[i]nums[i-1]) i;}return vv;}
};
