产品包装设计公司网站,简述什么是虚拟主机,手机网站建设与制作,外链发布平台#x1f308;个人主页#xff1a;小新_- #x1f388;个人座右铭#xff1a;“成功者不是从不失败的人#xff0c;而是从不放弃的人#xff01;”#x1f388; #x1f381;欢迎各位→点赞#x1f44d; 收藏⭐️ 留言#x1f4dd; #x1f3c6;所属专栏#xff1… 个人主页小新_- 个人座右铭“成功者不是从不失败的人而是从不放弃的人” 欢迎各位→点赞 收藏⭐️ 留言 所属专栏 计算机组成原理 欢迎订阅持续更新中~~~ ✨让小新带着你快乐的学习吧~✨ 目录
一、相关知识
一概念
二常见类型及应用场景 1. 快慢指针
2. 左右指针
三、优势 四、注意事项
二、经典题目练习
一移动零
1、题目描述
2、算法原理
3、代码实现
二复写零
1、题目描述
2、算法原理
3、代码实现
三快乐数
1、题目描述
2、算法原理
3、代码实现
四盛容器最多的容器
1、题目描述
2、算法原理
3、代码实现
五有效三角形个数
1、题目描述
2、算法原理
3、代码实现
六 查找总价格为目标值的两个商品
1、题目描述
2、算法原理
3、代码实现
七三数之和
1、题目描述
2、算法原理
3、代码实现
八四数之和
1、题目描述
2、算法原理
3、代码实现 一、相关知识
双指针算法是一种常用的算法技巧主要用于解决数组或链表相关的问题。以下是对双指针算法学习总结 一概念 双指针是指使用两个指针来遍历数据结构通常一个指针用于遍历另一个指针用于辅助操作或记录特定位置。根据指针的移动方式和作用可以分为不同类型的双指针算法如快慢指针、左右指针等。 二常见类型及应用场景 1. 快慢指针 - 概念两个指针在数据结构中以不同的速度移动。通常一个指针移动速度较快称为快指针另一个指针移动速度较慢称为慢指针。 - 应用场景 - 判断链表是否有环快指针每次移动两步慢指针每次移动一步。如果链表有环快指针一定会追上慢指针。 - 寻找链表的中间节点当快指针到达链表末尾时慢指针正好位于链表的中间位置。 2. 左右指针 - 概念两个指针分别从数据结构的两端开始向中间移动或者从同一端开始向不同方向移动。 - 应用场景 - 数组中的两数之和问题通过左右指针遍历数组找到满足特定条件的两个元素。 - 容器盛水问题利用左右指针遍历容器的两侧计算最大的盛水量。 三、优势 1. 时间复杂度低在一些情况下双指针算法可以在一次遍历中解决问题时间复杂度为 O(n)相比其他算法可能更加高效。 2. 空间复杂度低通常只需要使用两个指针变量不需要额外的数据结构空间复杂度为 O(1)。 3. 灵活性高可以根据不同的问题场景灵活调整指针的移动方式和条件判断。 四、注意事项 1. 边界条件在使用双指针算法时需要注意指针的初始位置、移动条件和边界情况避免出现指针越界或无限循环等问题。 2. 循环条件正确设置循环条件确保指针能够在合适的时候停止移动。 3. 问题的特殊性不同的问题可能需要对双指针算法进行适当的调整和优化不能生搬硬套。 总之双指针算法是一种非常实用的算法技巧通过合理地运用双指针可以高效地解决许多数组和链表相关的问题。在学习和使用双指针算法时需要深入理解其原理和应用场景并通过大量的练习来掌握这种技巧。 二、经典题目练习
一移动零
题目链接283. 移动零 - 力扣LeetCode
1、题目描述
给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。
请注意 必须在不复制数组的情况下原地对数组进行操作。 示例 1:
输入: nums [0,1,0,3,12]
输出: [1,3,12,0,0]示例 2:
输入: nums [0]
输出: [0] 提示:
1 nums.length 104-231 nums[i] 231 - 1
2、算法原理
使用双指针左指针指向当前已经处理好的序列的尾部右指针指向待处理序列的头部。
右指针不断向右移动每次右指针指向非零数则将左右指针对应的数交换同时左指针右移。
注意到以下性质
左指针左边均为非零数右指针左边直到左指针处均为零。
因此每次交换都是将左指针的零与右指针的非零数交换且非零数的相对顺序并未改变。 3、代码实现
class Solution {
public:void moveZeroes(vectorint nums) {int cur0,dest-1;//定义指针for(int i0;inums.size();i)//遍历数组{if(nums[cur]0)//遇到零cur跳过{cur;}else{swap(nums[dest1],nums[cur]);//遇到非零,dest1与cur交换然后各自加加dest;cur;}}}
};
二复写零
题目链接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]提示
1 arr.length 1040 arr[i] 9
2、算法原理
我们只需要用两个指针来进行标记栈顶位置和现在需要放置的元素位置即可。我们用 top 来标记栈顶位置用 i 来标记现在需要放置的元素位置那么我们找到原数组中对应放置在最后位置的元素位置然后在数组最后从该位置元素往前来进行模拟放置即可。
3、代码实现
class Solution {
public:void duplicateZeros(vectorint arr) {int n arr.size();int top 0;int i -1;while (top n) {i;if (arr[i] ! 0) {top;} else {top 2;}}int j n - 1;if (top n 1) {arr[j] 0;j--;i--;} while (j 0) {arr[j] arr[i];j--;if (!arr[i]) {arr[j] arr[i];j--;} i--;}}
};
三快乐数
题目链接202. 快乐数 - 力扣LeetCode
1、题目描述
编写一个算法来判断一个数 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 231 - 1
2、算法原理
使用 “快慢指针” 思想找出循环“快指针” 每次走两步“慢指针” 每次走一步当二者相等时即为一个循环周期。此时判断是不是因为 1 引起的循环是的话就是快乐数否则不是快乐数。
3、代码实现
class Solution {
public:
int GetSum(int n)
{int sum0;while(n){int tn%10;sum t*t;n/10;}return sum;
}bool isHappy(int n) {int fastGetSum(n);int slown;while(slow!fast){slowGetSum(slow);fastGetSum(GetSum(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
输入height [1,1]
输出1
提示
n height.length2 n 1050 height[i] 104
2、算法原理
解法一暴力解法遍历数组每次计算一个值最后取最大值。不细讲
时间复杂度On*2超时 解法二双指针法
我们知道体积V长度L(俩数距离)*高度H俩数较小者
根据数学知识我们知道 定义左右两个指针分别向数组中间走可以看出容器的容量就是两个指针指向的值中最小的那个值乘以两个指针之间的距离可以用木桶效应来解释即桶的容量取决于最短的那块木板。 第一次结果出来后值较小的指针往中间走这期间更新最大值直到俩指针相遇。
我们先从题目中的示例开始一步一步地解释双指针算法的过程。稍后再给出算法正确性的证明。
题目中的示例为
[1, 8, 6, 2, 5, 4, 8, 3, 7] ^ ^ 在初始时左右指针分别指向数组的左右两端它们可以容纳的水量为 min(1,7)∗88
此时我们需要移动一个指针。移动哪一个呢直觉告诉我们应该移动对应数字较小的那个指针即此时的左指针。这是因为由于容纳的水量是由两个指针指向的数字中较小值∗指针之间的距离两个指针指向的数字中较小值 * 指针之间的距离决定的。如果我们移动数字较大的那个指针那么前者「两个指针指向的数字中较小值」不会增加后者「指针之间的距离」会减小那么这个乘积会减小。因此我们移动数字较大的那个指针是不合理的。因此我们移动 数字较小的那个指针。
有读者可能会产生疑问我们可不可以同时移动两个指针 先别急我们先假设 总是移动数字较小的那个指针 的思路是正确的在走完流程之后我们再去进行证明。
所以我们将左指针向右移动
[1, 8, 6, 2, 5, 4, 8, 3, 7] ^ ^ 此时可以容纳的水量为 min(8,7)∗749。由于右指针对应的数字较小我们移动右指针
[1, 8, 6, 2, 5, 4, 8, 3, 7] ^ ^ 此时可以容纳的水量为 min(8,3)∗618。由于右指针对应的数字较小我们移动右指针
[1, 8, 6, 2, 5, 4, 8, 3, 7] ^ ^ 此时可以容纳的水量为 min(8,8)∗540。两指针对应的数字相同我们可以任意移动一个例如左指针
[1, 8, 6, 2, 5, 4, 8, 3, 7] ^ ^ 此时可以容纳的水量为 min(6,8)∗424。由于左指针对应的数字较小我们移动左指针并且可以发现在这之后左指针对应的数字总是较小因此我们会一直移动左指针直到两个指针重合。在这期间对应的可以容纳的水量为min(2,8)∗36min(5,8)∗210min(4,8)∗14
在我们移动指针的过程中计算到的最多可以容纳的数量为 49即为最终的答案。 3、代码实现
class Solution {
public:int maxArea(vectorint height) {int left0,rightheight.size()-1,ret0;while(leftright){int vmin(height[left],height[right])*(right-left);retmax(v,ret);if(height[left]height[right]){left;}else{right--;}}return ret;}
};
五有效三角形个数
题目链接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提示:
1 nums.length 10000 nums[i] 1000
2、算法原理
对于正整数 a,b,ca, b, ca,b,c它们可以作为三角形的三条边当且仅当 abc acb bca 均成立。如果我们将三条边进行升序排序使它们满足 a≤b≤c那么 acb和bca一定成立我们只需要保证abc
首先对数组排序。固定最长的一条边运用双指针扫描 如果 nums[l] nums[r] nums[i]同时说明 nums[l 1] nums[r] nums[i], ..., nums[r - 1] nums[r] nums[i]满足的条件的有 r - l 种r 左移进入下一轮。如果 nums[l] nums[r] nums[i]l 右移进入下一轮。 枚举结束后总和就是答案。
3、代码实现
class Solution{
public:int triangleNumber(vectorint nums) {sort(nums.begin(),nums.end());int ret0,nnums.size();for(int in-1;i2;i--){int left0,righti-1;while(leftright){if(nums[left]nums[right]nums[i]){retright-left;right--;}else{left;}}}return ret;}
};
六 查找总价格为目标值的两个商品
题目链接LCR 179. 查找总价格为目标值的两个商品 - 力扣LeetCode
1、题目描述
购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况返回任一结果即可。
示例 1
输入price [3, 9, 12, 15], target 18
输出[3,15] 或者 [15,3]示例 2
输入price [8, 21, 27, 34, 52, 66], target 61
输出[27,34] 或者 [34,27]
提示
1 price.length 10^51 price[i] 10^61 target 2*10^6
2、算法原理
使用左右指针分别指向数组的首尾两个元素。 如果二者之和大于目标值只能让右指针往左走。 因为左指针往右全部不满足。 如果二者之和小于目标值只能让左指针往右走。 因为右指针往左全部不满足。 如果相等直接返回。 3、代码实现
class Solution
{public:vectorint twoSum(vectorint price, int target) {int left0,rightprice.size()-1;while(leftright){int sumprice[left]price[right];if(sumtarget){left;}if(sumtarget){right--;}if(sumtarget){return {price[left],price[right]};}}return{-1,-1};//保证每条路径都有返回值}
};
七三数之和
1、题目描述
题目链接15. 三数之和 - 力扣LeetCode
给你一个整数数组 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 3000
-105 nums[i] 105
2、算法原理
先将 nums 排序时间复杂度为 O(NlogN)
固定 333 个指针中最左最小元素的指针 k双指针 ij 分设在数组索引 (k,len(nums)) 两端。
双指针 i , j 交替向中间移动记录对于每个固定指针 k 的所有满足 nums[k] nums[i] nums[j] 0 的 i,j 组合
当 nums[k] 0 时直接break跳出因为 nums[j] nums[i] nums[k] 0即 3个元素都大于 000 在此固定指针 k 之后不可能再找到结果了。 当 k 0且nums[k] nums[k - 1]时即跳过此元素nums[k]因为已经将 nums[k - 1] 的所有组合加入到结果中本次双指针搜索只会得到重复组合。 ij 分设在数组索引 (k,len(nums)) 两端当i j时循环计算s nums[k] nums[i] nums[j]并按照以下规则执行双指针移动
当s 0时i 1并跳过所有重复的nums[i]当s 0时j - 1并跳过所有重复的nums[j]当s 0时记录组合[k, i, j]至res执行i 1和j - 1并跳过所有重复的nums[i]和nums[j]防止记录到重复组合。
图解如下 3、代码实现
class Solution {
public:vectorvectorint threeSum(vectorint nums){vectorvectorint TreeDddZero;sort(nums.begin(), nums.end());int n nums.size();for (int i 0; i n; i){int left i 1, right n - 1;// printf(left:%d right:%d i:%d\n, left, right, i);while (left right){int sum nums[left] nums[right] nums[i];if (sum 0){left;// printf(left:%d left1:%d\n, left, left 1);}else if (sum 0){right--;//printf(right:%d right1:%d, right, right 1);}else{// printf(left:%d right:%d i:%d\n, left, right, i);if (left right) break;TreeDddZero.push_back({ nums[i],nums[left],nums[right] });left;right--;while (left right nums[left] nums[left - 1]){left;}while (left right nums[right] nums[right 1]){right--;}}}while (in-1 nums[i] nums[i 1]){i;}}return TreeDddZero;}
};
八四数之和
1、题目描述
题目链接18. 四数之和 - 力扣LeetCode
给你一个由 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]]提示
1 nums.length 200-109 nums[i] 109-109 target 109
2、算法原理
最朴素的方法是使用四重循环枚举所有的四元组然后使用哈希表进行去重操作得到不包含重复四元组的最终答案。假设数组的长度是 nnn则该方法中枚举的时间复杂度为 O(n4)去重操作的时间复杂度和空间复杂度也很高因此需要换一种思路。
为了避免枚举到重复四元组则需要保证每一重循环枚举到的元素不小于其上一重循环枚举到的元素且在同一重循环中不能多次枚举到相同的元素。
为了实现上述要求可以对数组进行排序并且在循环过程中遵循以下两点
每一种循环枚举到的下标必须大于上一重循环枚举到的下标同一重循环中如果当前元素与上一个元素相同则跳过当前元素。
使用上述方法可以避免枚举到重复四元组但是由于仍使用四重循环时间复杂度仍是 O(n4)。注意到数组已经被排序因此可以使用双指针的方法去掉一重循环。
使用两重循环分别枚举前两个数然后在两重循环枚举到的数之后使用双指针枚举剩下的两个数。假设两重循环枚举到的前两个数分别位于下标 i 和 j其中 ij。初始时左右指针分别指向下标 j1和下标 n−1。每次计算四个数的和并进行如下操作
如果和等于 target\textit{target}target则将枚举到的四个数加到答案中然后将左指针右移直到遇到不同的数将右指针左移直到遇到不同的数如果和小于 target\textit{target}target则将左指针右移一位如果和大于 target\textit{target}target则将右指针左移一位。
使用双指针枚举剩下的两个数的时间复杂度是 O(n)因此总时间复杂度是 O(n3)低于 O(n4)。
具体实现时还可以进行一些剪枝操作
在确定第一个数之后如果 nums[i]nums[i1]nums[i2]nums[i3]target说明此时剩下的三个数无论取什么值四数之和一定大于 target因此退出第一重循环在确定第一个数之后如果 nums[i]nums[n−3]nums[n−2]nums[n−1]target说明此时剩下的三个数无论取什么值四数之和一定小于 target因此第一重循环直接进入下一轮枚举 nums[i1]在确定前两个数之后如果 nums[i]nums[j]nums[j1]nums[j2]targett说明此时剩下的两个数无论取什么值四数之和一定大于 target因此退出第二重循环在确定前两个数之后如果 nums[i]nums[j]nums[n−2]nums[n−1]target说明此时剩下的两个数无论取什么值四数之和一定小于 target因此第二重循环直接进入下一轮枚举 nums[j1] 3、代码实现
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint AddtoFour;sort(nums.begin(), nums.end());int n nums.size();if (n 4)return AddtoFour;for (int i 0; i n; i){for (int j i 1; j n; j){int left j 1, right n - 1;while (left right){long long int aim (long long) nums[i] nums[j] nums[left] nums[right];if (aim target) left;else if (aim target) right--;else{if (left right)break;AddtoFour.push_back({ nums[i],nums[j],nums[left],nums[right] });left, right--;while (left right nums[left] nums[left - 1]) left;while (left right nums[right] nums[right 1]) right--;}}while (j n-1 nums[j] nums[j 1]) j;}while (i n-1 nums[i] nums[i 1]) i;}return AddtoFour;}
}; 最后感谢大家的观看
