忧郁兔斯基个人主页个人专栏《从零开始的C学习之旅》《C语言》《数据结构》《Linux学习》《优选算法》励志名言道阻且长行则将至个人介绍​本文是博主开设的《优选算法》专栏的第一篇文章本专栏会介绍一些常用的算法技巧并利用这些技巧解决多个例题。一个专题会分成上下两文一篇文章会每个例题的讲解会分成三个部分1、题目分析 2、算法原理 3、代码实现 最后希望各位观众佬爷看完能有所收获。目录一、双指针二、移动零2.1 题目分析2.2 算法原理2.3 代码实现三、复写零3.1 题目分析3.2 算法原理3.3 代码实现四、快乐数4.1 题目分析4.2 算法原理4.3 代码实现五、盛最多水的容器5.1 题目分析5.2 算法原理5.3 代码实现一、双指针误区“双指针”中的指针并不是我们在C/C中学到的指针这里更多是指功能上的相似都是用于定位元素的。像我们在数组中用下标来进行定位等思想。常见的双指针有两种形式⼀种是对撞指针⼀种是左右指针。对撞指针⼀般用于顺序结构中也称左右指针。对撞指针从两端向中间移动。⼀个指针从最左端开始另⼀个从最右端开始然后逐渐往中间逼 近。对撞指针的终止条件⼀般是两个指针相遇或者错开也可能在循环内部找到结果直接跳出循环也就是left right 两个指针指向同⼀个位置 或者left right 两个指针错开快慢指针又称为龟兔赛跑算法其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。这种方法对于处理环形链表或数组非常有用。 其实不单单是环形链表或者是数组如果我们要研究的问题出现循环往复的情况时均可考虑使⽤快慢指针的思想。快慢指针的实现方式有很多种最常用的⼀种就是在一次循环中每次让慢的指针向后移动⼀位而快的指针往后移动两位实现⼀快⼀慢。二、移动零2.1 题目分析题目链接283. 移动零 - 力扣LeetCode题目要求1、将数组中非零元素在不改变相对顺序的情况下左移零元素全部右移2、不能额外创建数组2.2 算法原理这道题目问题在与不能额外创建数组不然我们直接创建一个数组然后对原数组进行遍历将非零元素全部按顺序移到新数组中。那么这种对数组进行原地操作数组分区的问题它的特点给定一个数组根据题目给出的规则将其划分为多个区间本题是将所有的非零的元素移到左边零元素移到右边针对这种问题我们采用双指针算法这里的指针是利用数组的下标来充当指针我们设置的两个指针如下dest destination:已处理的区间内非零元素的最后一个位置在刚开始因为我们还没对数组进行操作所以我们将其指向下标为-1的位置curcurrent):从左往右扫描遍历数组,会将整个数组划分成两个区间左边是已处理区间右边是待处理区间设置为0遍历整个数组根据题目要求处理后的区间需要左边为非零元素右边为零元素dest作为分割线结构如下[0,dest] [dest1,cur-1] [cur,n-1]非零 零 待处理对于该题目0 1 0 3 1 2cur0,dest-1;在cur从左往右扫描的过程中如果碰到零元素cur;因为我们的目标是让 [dest 1, cur - 1]内的元素全都是零因此当 cur遇到0的时候直接就可以让0在cur - 1的位置上从⽽在 [dest 1, cur - 1]内如果遇到非零元素我们需要让dest,然后交换两个指针对应的数再让cur swap(arr[dest],arr[cur];cur;因为dest指向的位置是非零元素区间的最后⼀个位置如果扫描到⼀个新的⾮零元素那么它的位置应该在 dest 1的位置上因此dest先⾃增1dest之后指向的元素就是0元素因为非零元素区间末尾的后⼀个元素就是0 因此可以交换到cur所处的位置上实现[0, dest]的元素全部都是非零元素 [dest 1, cur - 1]的元素全是零。2.3 代码实现283. 移动零 - 力扣LeetCodeclass Solution { public: void moveZeroes(vectorint nums) { int cur0,dest-1; int sizenums.size(); while(size--) { if(nums[cur]) swap(nums[dest],nums[cur]); cur; } } };通过截图三、复写零3.1 题目分析题目链接1089. 复写零 - 力扣LeetCode题目描述1、将数组中出现的零再复写一次同时将其余元素右移2、不创建数组只能进行原地操作不能越界3.2 算法原理我们上面已经说过像是对数组进行原地操作的题目我们优先考虑一下双指针。本题我们先尝试创建一个数组来模拟和熟悉一下复写零的操作此时上一行的数组只遍历到4就结束了。我们熟悉了操作后设置两个指针cur:用于遍历数组dest:指向已经处理的最后一个数字我们发现当我们从前向后完成复写操作时dest在第二次就会超过cur,原数组的元素就被覆盖了这必然会导致结果的错误。那我们就需要从后向前完成复写操作即我们第一次模拟的倒置操作。可以说是反向操作但是我们需要让cur和dest指针指向最后一次复写的位置所以我们需要先进行正向的变换此次变换的目的是作位置变换不需要考虑数值的变换规则就是destn-1的情况下让cur遍历数组当cur指向的是零dest2,否则dest;但是需要注意的是如果当destn-2,且cur此时指向的是0那么就会导致dest的越界所以我们在得到最终位置后需要进行判断如果destn那么设置arr[n-1]0,cur--,dest-2;得到最终位置后我们只需要从后向前复写即可。3.3 代码实现class Solution { public: void duplicateZeros(vectorint arr) { //进行位置变换等到最后的位置 int cur-1,dest-1,narr.size();//dest是指向处理后的最后一个元素的位置 while(destn-1)//注意这里不能是等于如果是等于就一定会越界的 { if(!arr[cur])//如果是0 dest2; else dest; } //对越界的情况进行处理,即向前回推一步 if(destn) { arr[n-1]0; cur--,dest-2; } //从后向前进行复写 while(cur0) { if(arr[cur]) { arr[dest--]arr[cur--]; } else { arr[dest--]0; arr[dest--]0; cur--; } } } };注意cur以及dest需要保证是同步进行操作所以我将cur设置为-1如果是0那么就会导致最后cur指向的是正确位置的下一个位置那么结果就错误了如果将第一步的代码替换成下面这样也可以// 1. 先找到最后⼀个数 int cur 0, dest -1, n arr.size(); while(cur n) { if(arr[cur]) dest; else dest 2; if(dest n - 1) break; cur; }四、快乐数4.1 题目分析题目链接202. 快乐数 - 力扣LeetCode题目分析将n替换成各个数位上的平方和最终会有两个结果1、变成1 2、无限循环 如果最终结果为1那么就是快乐数否则就不是重点要么是最终变成1要么就是无限循环4.2 算法原理我们把上面的结构画出来很明显看出是一个带环的结构我们说过带环结构使用快慢指针有奇效根据快慢指针相遇时指向的元素是否相等就可以确定是否是快乐数。定义快慢指针 慢指针每次向后走1步快指针每次向后走两步判断相遇时候的值即可。快慢指针相遇时一定都在环上如果此时指针的值为1那么就是快乐数为什么一定会循环呢经过⼀次变化之后的最大值9^2 * 10 810(2^31-12147483647。选⼀个更大的最⼤9999999999)也就是变化的区间在[1, 810]之间根据「鸽巢原理」⼀个数变化811次之后必然会形成⼀个循环其实就是说数的大小是有限的必然会出现数的重复这样就会导致循环。因此变化的过程最终会⾛到⼀个圈⾥⾯因此可以⽤「快慢指针」来解决。4.3 代码实现class Solution { public: int getNum(int n) { int sum0; while(n) { int tmpn%10;//得n最后一个数位上的数 sumtmp*tmp; n/10;//最终n会变成0 } return sum; } bool isHappy(int n) { int slown, fastgetNum(n); while(slow!fast) { slowgetNum(slow); fastgetNum(getNum(fast)); } return fast1; } };五、盛最多水的容器5.1 题目分析题目链接11. 盛最多水的容器 - 力扣LeetCode数组中的数字代表高度数组中元素的间距代表宽度求数组中存在的两个元素对应的宽度和高度的乘积最大值5.2 算法原理设两个指针leftright分别指向容器的左右两个端点此时容器的容积 :v (right - left) * min( height[right], height[left])容器的左边界为height[left]右边界为height[right]。为了方便叙述我们假设「左边边界」小于「右边边界」。如果此时我们固定⼀个边界改变另⼀个边界⽔的容积会有如下变化形式容器的宽度⼀定变⼩。由于左边界较小决定了水的⾼度。如果改变左边界新的⽔⾯⾼度不确定但是⼀定不会超过右边的柱⼦⾼度因此容器的容积可能会增⼤。如果改变右边界⽆论右边界移动到哪⾥新的⽔⾯的⾼度⼀定不会超过左边界也就是不会超过现在的水面高度但是由于容器的宽度减小因此容器的容积⼀定会变⼩的。由此可见左边界和其余边界的组合情况都可以舍去。所以我们可以left跳过这个边界继续去判断下⼀个左右边界。5.3 代码实现class Solution { public: int maxArea(vectorint height) { int nheight.size(); int left0,rightn-1; int ret0; while(leftright) { int vmin(height[left],height[right])*(right-left); retmax(v,ret); if(height[left]height[right]) left; else right--; } return ret; } };下一篇文章将会继续讲解双指针有关的四道例题