南京电商网站开发,网站备案条件,网站设计与制作包括,培训医院网站建设前言#xff1a;大佬写博客给别人看#xff0c;菜鸟写博客给自己看#xff0c;我是菜鸟。 学前须知#xff08;对自己#xff09;#xff1a;这里的指针不一定指地址#xff01;也可能是数组下标。
1#xff1a;移动零(双指针)
题目要求#xff1a; 解题思路#x… 前言大佬写博客给别人看菜鸟写博客给自己看我是菜鸟。 学前须知对自己这里的指针不一定指地址也可能是数组下标。
1移动零(双指针)
题目要求 解题思路
这道题的思路与先前快速排序中的lumoto法及其类似只不过先前是通过双指针在数组中寻找基准值这里是通过双指针将大于0的数排列在前。可以看到思路是完全相似的不过是要求不一样。
在这里我们定义两个指针 cur当前指针的位置初始值定义为0 dest需要替换数据的位置初始值定义为-1 让cur去遍历整个数组。 循环内去寻找数组中不为0的数字 若满足条件(不为零)让dest随后与cur位置的数据进行交换。 若不满足条件则让cur以此循环直至cur遍历完整个数组。 代码实现 void moveZeroes(vectorint nums) {size_t dest -1;size_t cur 0;size_t n nums.size()-1;while(cur n){if(nums[cur] ! 0){dest;swap(nums[cur],nums[dest]);}cur;}} 2复写零(双指针)
题目要求 解题思路 题目要求我们在原数组上进行修改这说明一定涉及①数据的交换②数据向后平移。 此题要求复写零那么不可能是数据的交换则一定考虑数据的平移。但是仅仅从左往右遍历数组然后平移数据会丢失数组中原有的数据因此需要从后往前遍历以此平移数据同时添0。 既然同样是双指针的思路那么如何正确找到两个指针的起始位置呢 同样以 cur 和 dest 来命名他们的初始值分别为 0 -1 当 cur 当前数据非零时dest 当 cur 当前数据为零时dest2 然后判断当前 dest 是否已经超过或者等于数组长度若满足则停止循环不满足则cur 如果仅仅是题目中的案例上述过程已经能正确找到 cur 和dest的位置但有一种情况例外那就是dest 超出了数组这种情况需要单独考虑。 已如下数组为例[8,4,5,0,0,0,0,7]; 如果按照上述过程最终 cur 和 dest 的位置会来到如图所示处。 此时 dest 已经越过数组因此我们所要作的就是将 dest -1 的位置置为 0 同时将 dest - 2 cur--即可。 注思考为什么将dest -1 置为 0 答之所以为产生越界是因为 cur 位置当前数据为0因此 dest 多加了一次才会导致越界说明 dest 与 dest 1 的位置原本都应该为 0但是数组越界了所以只有dest位置的数据为0因此需要将数组末尾置为0。 简单来说针对越界这种特殊情况我们手动进行了一次操作即在数组末尾插入了零。 代码实现
void duplicateZeros(vectorint arr) {int cur 0, dest -1;size_t n arr.size() - 1;while(cur n ){if(arr[cur] 0){dest 2;}else{dest;}if(dest n){break;}cur;}if(dest n){arr[dest-1] 0;dest -2;cur--;}while(cur 0){if(arr[cur] ! 0){arr[dest--] arr[cur--];}else{arr[dest--] 0;arr[dest--] 0;cur--;}}}
3快乐数(快慢指针)
题目要求 解题思路 开始讲解思路前需要知道一点快乐数与先前链表中通过快慢指针确定链表是否为环形链表类似。一个数。经过多次运算后始终会等于先前运算过的一个数然后依次往复循环。 这里我们定义 Num_Square() 函数计算每位平方数的和 slow调用一次上述函数 fast调用两次上述函数 代码实现 int Num_Square(int n){int sum 0;while(n){sum pow(n%10,2);n / 10;}return sum;}bool isHappy(int n) {int slow n;int fast Num_Square(n);while(slow ! fast){slow Num_Square(slow);fast Num_Square((Num_Square(fast)));}if(slow 1){return true;}else{return false;}}
4装最多的水(双指针单调性)
题目要求 解题思路 遇事不决暴力思路那显然是不可能的因为会超时间复杂度。单纯使用前面的双指针算法似乎也不可行。 问那这里该如何解决才能优化时间复杂度呢 答这里不仅仅需要双指针还需要结合单调性去考虑问题。 我们先定义两个指针 left初始值为0指向数组最左端。 right初始值为 n-1n为数组元素个数指向数组最右端。 现在想想水的容积是怎么算的 容积 两边最短的高度 × 长度right - left 结合单调性不难想到如果此时 right--left不变那么任何数乘以 1 都会小于原来的容积(因为高度不变长度减小)因此我们只需记录目前的最大值然后left这样就减少了遍历次数提升了效率。 此时 left 1right n -1同样结合上述单调性来看如果leftright 不变那么任何数乘以 7都会小于原来数(同样是因为高度不变长度减小)因此这次我们需要将 right--left不变这样就减少了遍历次数提升了效率。 总结通过双指针单调性去考虑这个问题 起始时left 0right n-1; 容积 min(arr[left],arr[right]) × (right - left); 高度固定时容积与长度为反比记录此时容积大小并改变较小的高度(left就right就--) 最终比较记录的容积值即可。 代码实现
int maxArea(vectorint height) {size_t left 0;size_t right height.size()-1;int Max 0;int ret 0;while(left right){Max min(height[left],height[right]) * (right - left);ret max(ret,Max);if(height[left] height[right]){right--;}else{left;}}return ret;}
5有效三角形个数(双指针单调性)
题目要求 解题思路 通常我们通过判断三次两边之和小于第三边来确定三个数是否能够构成三角形。 问怎么做才能够减少判定次数同时又能确定可以构成三角形 答用较小的两个边的和与最大的边进行比较这样只需判断一次。 问那如何找最大值呢 答遍历数组去找肯定是不可取的那么就会想到使用库函数的排序这样最大值一定在数组末尾。 在有了上述的考虑后本题同样是双指针单调性去思考问题无非就是条件不同。 以下列数组为例分析 图一 arr[left] arr[right] max 不构成三角形那么比 arr[right] 小的数都不构成三角形因此不用遍历left 图二 arr[left] arr[right] max 构成三角形那么此时只要比 arr[left] 大的数都能够构成三角形因此无需遍历直接记录一共可以构成三角行的个数 n right - left。记录完后right-- 图三 此时又回到了图一的情况不多赘述left。 直至不满足 left right 此时需要更新 maxleft 和 right 重新循环上述过程知道 max arr[2]; 代码实现
int triangleNumber(vectorint nums) {sort(nums.begin(),nums.end());size_t n nums.size() -1;int total 0;while(n 2){int left 0;int right n-1;while(left right){if(nums[left] nums[right] nums[n]){left;}else{total right - left;right--;}}n--;}return total;}
6和为 s 的两个数字(双指针单调性)
题目要求 解题思路 几乎与5是一样的只不过5中是与数组中的元素比而这里是与给定的数比因此更简单。 大致思路 考虑双指针(left,right)因为数组是有序数组从单调性考虑。 若 arr[left] arr[right] target 说明太大了right-- 若 arr[left] arr[right] target 说明太小了left 代码实现
vectorint twoSum(vectorint price, int target) {int left 0;int right price.size() -1;while(left right){if(price[left] price[right] target){right--;}else if(price[left] price[right] target){left;}else{return {price[left],price[right]};}}return {-1,-1};}
7:三数之和
题目要求 解题思路 仍就是通过双指针单调性的思路去解决这道问题但区别在于我们不能够输出重复的答案因此这里还多了一个判重的过程。 如图定义来进行模拟运算 当 arr[left] arr[right] arr[min] 时left; 当 arr[left] arr[right] arr[min] 时right--; 当 arr[left] arr[right] arr[min] 时left;如图所示 此时需将答案保存到临时容器中并让leftright--,同时需要去重即 当 arr[left] arr[left-1]时left 当 arr[right] arr[right1]时right-- 同时需要注意越界即在循环过程中left 始终小于 right 当 left 大于 right时结束一轮循环时此时 min也要去重与left 与 right 的去重思路一致同时注意越界min 始终小于容器内数据个数。 代码实现
vectorvectorint threeSum(vectorint nums) {int min 0;vectorvectorint tmp;sort(nums.begin(),nums.end());//让数组变得有序方便使用单调性while(min nums.size() nums[min] 0){int left min1;int right nums.size() - 1;while(left right){int sum nums[left] nums[right];if(sum nums[min] 0){right--;}else if(sum nums[min] 0) {left;}else{tmp.push_back({nums[min],nums[left],nums[right--]});while(left right nums[left] nums[left - 1]){left;}while(left right nums[right] nums[right 1]){right--;}}}min;while(min nums.size() nums[min] nums[min-1]){min;}}return tmp;} 8:四数之和
题目要求 解题思路 四数之和与三数之和的思路极其类似无非就是多了一个需要固定的数以及多一层循环本质没有太大区别。 如图所示固定 min 和 min1 去移动 left 和 right 当 arr[min] arr[min1] arr[left] arr[right] target时left 当 arr[min] arr[min1] arr[left] arr[right] target时right-- 当 arr[min] arr[min1] arr[left] arr[right] target时 将当前 arr[min] arr[min1] arr[left] arr[right] 插入临时容器中 left,right--再判重并注意越界 当最内层 left 和 right 循环结束时min1并判重注意越界开始下一轮循环 当 min1 等于倒数第三个下标时第二层循环的首轮结束min并判重以此往复直至循环结束。 代码实现
vectorvectorint fourSum(vectorint nums, int target) {int min 0;int n nums.size()-1;vectorvectorint tmp;sort(nums.begin(),nums.end());while(min n-3){int min1 min1;while(min1 n-2){int left min11;int right nums.size() - 1;while(left right){long sum nums[left] nums[right];long sum1 nums[min] nums[min1];if(sum sum1 target){right--;}else if(sum sum1 target) {left;}else{tmp.push_back({nums[min],nums[min1],nums[left],nums[right--]});while(left right nums[left] nums[left - 1]){left;}while(left right nums[right] nums[right 1]){right--;}}}min1;while(min1 n-2 nums[min1] nums[min1-1]){min1;}}min;while(min n-3 nums[min] nums[min-1]){min;}}return tmp;} 9总结 双指针算法 这里的指针不是地址也许是数组下标 经常和单调性挂钩有时候是根据数组长度判断单调4有时候是根据数组数据大小判断单调5、6、7根据数组数据判断单调可能需要将数组先排序再做运算
