做网站相册,奢侈品,教育机构招聘,网站开发好做还是平面好做Welcome to 9ilks Code World (๑•́ ₃ •̀๑) 个人主页: 9ilk
(๑•́ ₃ •̀๑) 文章专栏#xff1a; 算法Journey 本篇博客我们分享一下双指针算法中的快慢指针以及对撞双指针#xff0c;下面我们开始今天的学习吧~ #x1f3e0; 快乐数 #x1f4d2; 题… Welcome to 9ilks Code World (๑•́ ₃ •̀๑) 个人主页: 9ilk
(๑•́ ₃ •̀๑) 文章专栏 算法Journey 本篇博客我们分享一下双指针算法中的快慢指针以及对撞双指针下面我们开始今天的学习吧~ 快乐数 题目解析 题目链接202. 快乐数 - 力扣LeetCode 题目内容 对于这道题题中告诉了我们快乐数的定义也就是说9对于一个正整数经过变换会进入两种循环1.一种是一直循环12.另一种是不同数的循环 算法原理 思路1 找规律
这个思路本人按照以往学数学的规律发现不满足快乐数的会陷入4-16-37-58-89-145-42-20的循环当中 因此我们的思路是申请一块数组空间当某个正整数变化到这个数组中的某个数时说明不是快乐数反之一直变化都没出现这里面的数变化到1停止说明就是快乐数。 参考代码
class Solution
{
public:int squre(int n){int sum 0 ;while(n 0){sum ((n%10)*(n%10));n / 10;}return sum;}bool find(vectorint v1,int x){for(int i 0 ; i v1.size();i){if(v1[i] x)return true;}return false;}bool isHappy(int n) {if(n 1)return true;vectorint v1 {4,16,37,58,89,145,42,20};int sum n;while(sum ! 1){sum squre(sum);if(find(v1,sum))return false;elsecontinue; }return true;}
}; 思路2 快慢指针
思路1属于投机取巧的做法,猜到就是赚到,万一猜不到呢? 我们由题目可知,这个正整数只有两种变化情况,有的朋友可能会想是否有可能不会进入循环一直变成不同的数呢?答案是不可能 ! 证明过程: 1.鸽巢(抽屉)原理:如果有n个巢,n1只鸽子,那么至少有一个巢的鸽数大于1. 2.对于这道题而言最大为21亿多( 2147483647),也就是最多有10个位,假设每一位都是9,即9999999999,那么经过一次变换就是9*9*10 810 3.int范围内每个正整数经过一次变化在[0,810]这个闭区间内,那么假设存在某个数经过810次变换后都是不同的数,但再变一次这个数一定是之前变换过程中的一个数,类比来看,这个闭区间就相当于鸽巢,因此一定会进入循环! 既然只有两种情况,我们看到两种环是否感到熟悉,我们在解决链表是否带环问题,常用的解决方法就是快慢指针 这里我们要打破固有思维,我们要理解的是快慢指针的应用场景,在这里slow走一步相当于这个正整数变化一次,fast走两步,相当于这个正整数变化两次
总结快慢指针思路:slow变化一次,fast变化两次,通过判断他们相遇时(变化成的数相等时),这个数是否变化为1,为1则说明是快乐数;反之不是. 参考代码
class Solution {
public:int squre(int x){int sum 0;while(x 0){sum ((x%10)*(x%10));x / 10;} return sum;}bool isHappy(int n){int slow squre(n);int fast squre(squre(n));while(slow ! fast){slow squre(slow);fast squre(squre(fast));}if(slow 1){return true;}return false;}}; 盛最多水的容器 题目解析 题目链接11. 盛最多水的容器 - 力扣LeetCode 题目内容 这道题目简单来说就是让我们确定横坐标差值m以及纵坐标n,使得m*n最大 算法原理 思路1 暴力求解
对于这道题我第一时间能想到的就是暴力求解套两个循环定义一个max变量不断比较更新max
class Solution {
public:int maxArea(vectorint height){int maxV 0;for(int i 0 ; i height.size() ; i){for(int j i 1 ; j height.size() ; j){int row j - i;int col height[i] height[j] ? height[i] : height[j];if(maxV row*col)maxV row*col;}}return maxV;}
};
但题目不给我们过O(N^2)的解法需要另寻他路 思路2 对撞指针
发现规律 假设在【6,2,3,4】这个区间我们设横坐标值为m纵坐标的值为n,则固定住44左边的数分别与4求体积我们会发现这样的一个规律 结论当区间左右端点值较小的值固定住后不断逼近过程中V一定是一定减小的那么左右端点值形成的V就是这段区间中最大的 发现完这个规律我们就可以避免了很多不必要情况的枚举直捣黄龙取“最大”。 对撞指针所谓对撞指针就是定义一个left指针和一个指针分别指向容器的左右端left和right分别向中间逼近当left right或 left right时停止遍历。 结合我们发现的规律以及对撞指针的原理我们的代码思路就是left和right分别向中间逼近比较left和right 位置对应位置的较小值固定 left / right求出左右端点值对应的v由发现的规律知此时的v就是这个对应左右边界最大的v接着移动left / right继续下一个左右区间...直到left 和 right 相遇。 参考代码
class Solution {
public:int maxArea(vectorint height) {int left 0;int right height.size() - 1;vectorint v1;while(left right){int v (right-left)*(height[left] height[right] ? height[left] :height[right]);v1.push_back(v);cout v left :left right: right endl;if(height[left] height[right]){left;}else if(height[left] height[right]){right--;}else{left;}}int maxV 0;for(int i 0 ; i v1.size();i){if(v1[i]maxV)maxV v1[i];}return maxV;}
}; 总结本篇博客我们介绍了双指针算法中的快慢指针和对撞指针快慢指针常用于解决“带环”问题对撞指针需要我们先发现规律确定好对撞停止条件以及对撞指针更新的条件一般适用于排除区间或查找某种条件是否成立的场景
