柚子快报邀请码778899分享：算法——双指针
双指针经常服务于需要一边遍历数组，一边对数组元素进行改动的题目，有些人也称双指针为快慢指针。
同时双指针只是一种思想，实际做题时并不一定会真的采用指针。
移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
本题的思路，并非是着重于将0往后移，实际上是要将非0数按顺序往前移。
由题意，我们可以将数据分成两大类：0和非0，那么我们的两个指针，一个就去找0，一个就去找非0。
两个指针均从0下标开始，其中cur找0，dest找非0。cur找到0即停下，dest找到非0即停下。
这样，dest总会走在cur的前面，两者将数据进行交换，就可以将非0元素前移，0元素后移。直至dest走到数组末尾。
class Solution {
public:
void moveZeroes(vector
int size = nums.size();
int cur = 0;
int dest = 0;
while(dest < size)
{
if(nums[cur] == 0 && nums[dest] == 0)
{
dest++;
}
else
{
swap(nums[cur++],nums[dest++]);
}
}
}
};
快乐数
「快乐数」 定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
示例 2：
输入：n = 2
输出：false
通过实例的分析，这个题目我们不难理解，值得提醒的是，无论这个数起始是多少，变化了多少次，他最终都一定会进入循环，比如示例2，就会在4这个数字进入死循环，这个我们不做讲解，感兴趣的小伙伴可以自己去尝试分析解惑。
还有一点要注意的是，实际上当数最后变为1时，如果在进行运算，是一直以1在进行循环。
所以这道题的关键解法就在于，找到循环的数字，并判断是否为1。
不知道小伙伴们还记不记得，在链表阶段，有一种循环链表的存在：
其中，我们就是通过使用快慢指针的方法，来找到这个循环的入口，也就是本题要找的快乐数。
让慢指针每次走一步，快指针每次走两步，二者相等之时，即为在入口处相遇。
class Solution {
int sum(int n)
{
int num = 0;
while(n)
{
int x = n % 10;
num += x * x;
n /= 10;
}
return num;
}
public:
bool isHappy(int n) {
int slow = n;
int fast = sum(n);
while(slow != fast)
{
slow = sum(slow);
fast = sum(sum(fast));
}
if(slow == 1)
return true;
else
return false;
}
};
因为要经常进行运算，所以我们直接将其封装为函数方便调用。
然后我们就让slow从n开始，fast从n运算后的数开始，进行循环判断，循环结束即两者相等，再判断此时值是否为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]
这个题可以说是足够简单了，对于暴力解法来说，只需要两层for循环去依次尝试两个商品的和是否等于目标值即可，但是这样的算法复杂度为0（n^2）。
那么是否可以有更加高效的方法呢？没错，就是双指针。
题目明确给出，数组里的值已经是升序了（如果不是升序，我们可以利用排序使其变为升序），所以我们可以从两头出发，left指向最小值，right指向最大值，当两者的和大于目标值时，right--去找较小的值，反之让left++去找更大的值，直至两者的和等于目标值，或者不存在两个商品的和等于目标值为止。
class Solution {
public:
vector
int left = 0;
int right = price.size() - 1;
int sum = 0;
vector
while(left < right)
{
sum = price[left] + price[right];
if(sum > target)
right--;
else if(sum < target)
left++;
else
{
v.push_back(price[left]);
v.push_back(price[right]);
break;
}
}
return v;
}
};
总结
不难看出，双指针算法最适用的场景即为线性表这样的数据结构类型，通过分析出问题的关键点，然后利用双指针，要么均从头开始，要么均从尾开始，要么一头一尾，逐步去解决问题。
关于双指针就分享这么多，喜欢本篇文章记得一键三连，我们下期再见！
柚子快报邀请码778899分享：算法——双指针
推荐文章
发表评论