注册网站授权书怎么写,h5个人网站代码,课程网站建设中容易出现的问题,制作图网 专业图片在线制作网站双指针 双指针1. 移动零2. 复写零3. 快乐数4. 盛水最多的容器5. 有效三角形的个数6. 和为s的两个数字7. 三数之和8. 四数之和 双指针
常见的双指针有两种形式#xff0c;⼀种是对撞指针#xff0c;⼀种是左右指针。
对撞指针#xff1a;⼀般用于顺序结构中#xff0c;也称… 双指针 双指针1. 移动零2. 复写零3. 快乐数4. 盛水最多的容器5. 有效三角形的个数6. 和为s的两个数字7. 三数之和8. 四数之和 双指针
常见的双指针有两种形式⼀种是对撞指针⼀种是左右指针。
对撞指针⼀般用于顺序结构中也称左右指针。
对撞指针从两端向中间移动。⼀个指针从最左端开始另⼀个从最右端开始然后逐渐往中间逼近。对撞指针的终止条件⼀般是两个指针相遇或者错开也可能在循环内部找到结果直接跳出循环也就是 left right 两个指针指向同⼀个位置 left right 两个指针错开
快慢指针其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。这种方法对于处理环形链表或数组非常有用。
其实不单单是环形链表或者是数组如果我们要研究的问题出现循环往复的情况时均可考虑使⽤快慢指针的思想。快慢指针的实现方式有很多种最常用的⼀种就是
在⼀次循环中每次让慢的指针向后移动⼀位而快的指针往后移动两位实现⼀快⼀慢
下面我们看练习题目
1. 移动零
题目链接 - Leetcode -283.移动零
Leetcode -283.移动零
题目给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。
请注意 必须在不复制数组的情况下原地对数组进行操作。
示例 1: 输入: nums [0, 1, 0, 3, 12] 输出 : [1, 3, 12, 0, 0]
示例 2 : 输入 : nums [0] 输出 : [0]
提示 :
1 nums.length 10^42^31 nums[i] 2^31 - 1
其思路的本质是快排的思想数组划分区间 - 数组分两块我们可以用⼀个 cur 指针来扫描整个数组另⼀个 dest 指针用来记录非零数序列的最后⼀个位置。根据 cur 在扫描的过程中遇到的不同情况分类处理实现数组的划分。在 cur 遍历期间使 [0, dest] 的元素全部都是非零元素 [dest 1, cur - 1] 的元素全是零。 代码如下 class Solution {public:// 双指针void moveZeroes(vectorint nums){// dest 是最后一个非零元素的下标int cur 0, dest -1;while (cur nums.size()){// nums[cur] 不为零先dest再交换两个值 if (nums[cur]){swap(nums[dest], nums[cur]);}cur;}}};2. 复写零
题目链接 - Leetcode -1089.复写零
Leetcode -1089.复写零
题目给你一个长度固定的整数数组 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]
提示 1 arr.length 10^4 0 arr[i] 9
思路如果从前向后进行原地复写操作的话由于 0 的出现会复写两次导致没有复写的数被覆盖掉。因此我们选择「从后往前」的复写策略。但是从后向前复写的时候我们需要找到最后⼀个复写的数因此我们的大体流程分两步 i. 先找到最后⼀个复写的数 ii. 然后从后向前进行复写操作
代码如下 class Solution {public:void duplicateZeros(vectorint arr){// 先用 dest 指针模拟一遍复写当 dest n - 1dest 最终的位置就是复写零后数组的最终形式可以用 cur 位置的元素覆盖它int cur 0, dest -1, n arr.size();while (cur n){if (arr[cur] 0) dest 2;else dest;if (dest n - 1) break;cur;}// 当 dest n - 1 最后dest肯定走了两步即最后复写的元素一定是零所以直接将最后一个元素改成0后dest向前走两步cur向前走一步if (dest n){arr[n - 1] 0;cur--, dest - 2;}// 正常的覆盖while (cur 0){if (arr[cur] 0){arr[dest--] 0;arr[dest--] 0;cur--;}else{arr[dest--] arr[cur--];}}}};3. 快乐数
题目链接 - Leetcode -202.快乐数
Leetcode -202.快乐数
题目编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为 对于一个正整数每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1也可能是 无限循环 但始终变不到 1。 如果这个过程 结果为 1那么这个数就是快乐数。 如果 n 是 快乐数 就返回 true 不是则返回 false 。
示例 1 输入n 19 输出true 解释 12 92 82 82 22 68 62 82 100 12 02 02 1
示例 2 输入n 2 输出false
提示 1 n 2^31 - 1
思路为了方便叙述将「对于⼀个正整数每⼀次将该数替换为它每个位置上的数字的平方和」这⼀个操作记为 x 操作 题目告诉我们当我们不断重复 x 操作的时候计算⼀定会「死循环」死循环的方式有两种 ▪ 情况⼀⼀直在 1 中死循环即 1 - 1 - 1 - 1… ▪ 情况⼆在历史的数据中死循环但始终变不到 1 由于上述两种情况只会出现⼀种因此只要我们能确定循环是在「情况⼀」中进行还是在「情况⼆」中进行就能得到结果。
代码如下 class Solution {public:// 计算每个位上的平方相加即进行快乐数的计算int bitNum(int n){int sum 0;while (n 0){int x n % 10;sum x * x;n / 10;}return sum;}bool isHappy(int n){// 定义快慢指针慢指针一定可以追上快指针最后只需判断他们相遇时的结果是否是1即可int slow n, fast bitNum(n);while (slow ! fast){slow bitNum(slow);fast bitNum(bitNum(fast));}if (slow 1) return true;return false;}};4. 盛水最多的容器
题目链接 - Leetcode -11.盛最多水的容器
Leetcode -11.盛最多水的容器
题目给定一个长度为 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 输入height [1, 1] 输出1
提示 n height.length 2 n 10^5 0 height[i] 10^4
思路对撞指针两个指针分别定义在数组的头和尾假设是 left 和 right并假设 left right此时 left 决定了盛水的容量此时如果我们舍去 left 并使 left有可能下一条边比 left 更长此时的盛水容量有可能变大但是如果我们舍去 right并使 right–就算下一条边更长left 还是决定了盛水的容量所以盛水的容量不变或者减小所以我们不能舍去长的那一条边我们可以大胆舍去短的那一边当我们不断重复上述过程每次都可以舍去大量不必要的枚举过程直到 left 与 right 相遇。期间产生的所有的容积里面的最⼤值就是最终答案。
代码如下 class Solution {public:int maxArea(vectorint height){int n height.size(), ret 0;// 定义双指针int left 0, right n - 1;while (left right){// 盛水是要看最短的那边所以相乘用最短的板ret max(ret, (min(height[left], height[right]) * (right - left)));// 如果左边短了左指针往右移否则右指针往左移if (height[left] height[right]) left;else right--;}return ret;}};5. 有效三角形的个数
题目链接 - Leetcode -611.有效三角形的个数
Leetcode -611.有效三角形的个数
题目给定一个包含非负整数的数组 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
提示 : 1 nums.length 1000 0 nums[i] 1000
思路是对数组先排序每次固定一个数再使用对撞指针优化具体的思路参考代码中的注释 class Solution {public:int triangleNumber(vectorint nums){// 先进行排序sort(nums.begin(), nums.end());int ans 0;// 先固定一个数for (int i nums.size() - 1; i 2; i--){// 再使用双指针枚举另外两个数// 其中left在从小的开始枚举right从大的开始枚举int left 0, right i - 1;while (left right){// 如果 nums[left] nums[right] nums[i] 说明left到right区间都能和i构成三角形所以ans累加上区间内的个数// 累加完后left没必要了因为数组是有序的left都能组成三角形比left大的肯定可以所以此时让 right--if (nums[left] nums[right] nums[i]){ans (right - left);right--;}// 否则 leftelse{left;}}}return ans;}};6. 和为s的两个数字
题目链接 - Leetcode -剑指 Offer 57.和为s的两个数字
Leetcode -剑指 Offer 57.和为s的两个数字
题目输入一个递增排序的数组和一个数字s在数组中查找两个数使得它们的和正好是s。如果有多对数字的和等于s则输出任意一对即可。
示例 1 输入nums [2, 7, 11, 15], target 9 输出[2, 7] 或者[7, 2]
示例 2 输入nums [10, 26, 30, 31, 47, 60], target 40 输出[10, 30] 或者[30, 10]
限制 1 nums.length 10 ^ 5 1 nums[i] 10 ^ 6
这道题的思路与上题类似所以直接给出代码 class Solution {public:vectorint twoSum(vectorint nums, int target){// 因为数组已经有序利用有序使用双指针枚举int left 0, right nums.size() - 1;while (left right){if (nums[left] nums[right] target) return { nums[left],nums[right] };else if (nums[left] nums[right] target) right--;else left;}return { -1,-1 };}};7. 三数之和
题目链接 - Leetcode -15.三数之和
Leetcode -15.三数之和
题目给你一个整数数组 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 。
提示
3 nums.length 300010^5 nums[i] 10^5
此题与两数之和类似与两数之和稍微不同的是题目中要求找到所有不重复的三元组。那我们可以利用在两数之和那里用的双指针思想来对我们的暴力枚举做优化 i. 先排序 ii. 然后固定⼀个数 a iii. 在这个数后⾯的区间内使用「双指针算法」快速找到两个数之和等于 -a 即可。 但是要注意这道题里面需要有「去重」操作 i. 找到⼀个结果之后 left 和 right 指针要「跳过重复」的元素 ii. 当使用完⼀次双指针算法之后固定的 a 也要「跳过重复」的元素
代码如下 class Solution {public:vectorvectorint threeSum(vectorint nums){// 先对数组排序sort(nums.begin(), nums.end());vectorvectorint ret;// 先固定一个数再使用双指针for (int i 0; i nums.size() - 1; i){// 去重 nums[i] 相同的元素if (i 0 nums[i] nums[i - 1]) continue;int left i 1, right nums.size() - 1;while (left right){if (nums[left] nums[right] -nums[i]){ret.push_back({ nums[left],nums[right],nums[i] });right--, left;// 去重 left 和 rightwhile (left right nums[right] nums[right 1]) right--;while (left right nums[left] nums[left - 1]) left;}else if (nums[left] nums[right] -nums[i]){right--;}else{left;}}// 因为是排序后的数组如果 nums[i] 大于0后面的数都比它大找不到两数相加等于它的负数的数所以提前跳出环 if (nums[i] 0) break;}return ret;}};8. 四数之和
四数之和的做法也和三数之和类似大家可以自行尝试一下题目链接 - Leetcode -18.四数之和
Leetcode -18.四数之和
题目给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。 请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为两个四元组重复
0 a, b, c, d n a、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]]
提示 1 nums.length 200
10^9 nums[i] 10^910^9 target 10^9
下面直接看代码解析 class Solution {public:vectorvectorint fourSum(vectorint nums, int target){sort(nums.begin(), nums.end());vectorvectorint ret;int len nums.size();// 先固定第一个数for (int i 0; i len - 3; i){// 去重1.if (i 0 nums[i] nums[i - 1]) continue;// 固定第二个数int aim1 target - nums[i];for (int j i 1; j len - 2; j){// 去重2.if (j i 1 nums[j] nums[j - 1]) continue;// 使用双指针long long aim2 (long long)aim1 - nums[j];int left j 1, right len - 1;while (left right){if (nums[left] nums[right] aim2){right--;}else if (nums[left] nums[right] aim2){left;}else{ret.push_back({ nums[i],nums[j],nums[left],nums[right] });left, right--;// 去重3.while (left right nums[left] nums[left - 1]) left;while (left right nums[right] nums[right 1]) right--;}}}}return ret;}};
