初探算法之双指针开篇
目录
前言：
此篇作为算法篇章的首篇文章，自然得简单说上几句。算法部分呢，多刷题是必不可少的。从暴力解法过渡到算法解法，过程着实有些艰辛，而算法的思考尤为关键。所以算法部分的讲解大多借助题目直接展开，以题目来传授算法知识。鉴于每个人对算法的接受程度有别，每篇通常涵盖两题左右，难题部分一般只设一道，且题目均取自LeetCode，本文会以最优解法来阐释不同的算法，通过题目解析、算法原理、算法编写这三个部分来解决问题。
双指针算法
题目一：
示例如下：
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
题目解析：
给定一个数组，需要将其中的0移动到数组末尾，同时无需考虑0的相对顺序，但要保留非零元素的相对顺序。若不使用双指针，有诸多解法，例如把所有非零元素移到开头，不过每移动一次得遍历一次，时间复杂度接近O(N²)，这属于暴力解法。那该如何运用双指针呢？
算法原理：
借助双指针可将数组划分成三个区域：[0,dest]为非零元素区域，[dest,cur]是0元素区域，[cur,end]是未遍历区域。双指针并非传统意义上的指针，而是一种形象的指向概念。这里借助数组下标来定义两个指针。起始时二者均从0开始，dest初始可先不明确，cur遍历数组，遇到非零元素时，将其放到dest位置，具体操作是dest从-1开始，找到非零元素后，dest先自增，再与cur位置元素交换，cur继续往后遍历。
算法编写：
class Solution {
public:
void moveZeroes(vector<int>& nums)
{
for(int cur = 0,dest = -1;cur < nums.size();cur++)
{
if(nums[cur])
swap(nums[++dest],nums[cur]);
}
}
};
简单分析时间复杂度，此为一次遍历，时间复杂度为O(N)，相较暴力解法有显著优化。
题目二:
示例如下：
输入： n = 19
输出： true
解释： 1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1
题目解析：
题目叫做快乐数，来瞧瞧它有多“快乐”。快乐数的定义是：将一个数的每一位数字的平方相加，多次操作后若能得到1，那这个数就是快乐数；若一直循环却无法得到1，就不是快乐数。这类题目没有暴力解法，因为暴力的话很可能陷入死循环出不来，所以直接进入算法原理部分。
算法原理：
我们可以通过画图来看看变化情况。以19为例，经过4次变化得到1；而2经过多次变化后，会出现和第一次变化相同的值4。可以理解为2在变化时形成了一个环，且数的变化无法跳出这个环，所以不是快乐数。那19是否也有环呢？换个角度想，19变化时会不会形成一个仅包含1的环呢？此时大家应该明白了，我们可以用两个指针，一个走得快，一个走得慢，它们必定会相遇，相遇时判断是否为1即可。那为什么一定会出现环呢？这就要用到鸽巢原理了。LeetCode中给出了n的最大取值，我们考虑最大情况，比如10个9组成的数，计算其一次变化后的值为810，所以变化后的值最大不超过810。定义函数F(x)表示一次变化，那么一个数经过811次变化会产生811个数，但可能的取值区间只有810个，根据鸽巢原理，必然有重复的数，也就形成了环。
算法编写：
class Solution
{
public:
int _isHappy(int num)
{
int ans = 0,sum = 0;
while(num)
{
sum = num % 10;
ans = ans + sum * sum;
num /= 10;
}
return ans;
}
bool isHappy(int n)
{
int slow = n,fast = n;
while(1)
{
slow = _isHappy(slow);
fast = _isHappy(_isHappy(fast));
if(slow == fast)
{
if(slow == 1)
return true;
else
return false;
}
}
}
};
今日算法分享至此，感谢阅读！
文章整理自互联网，只做测试使用。发布者：Lomu，转转请注明出处：https://www.it1024doc.com/13683.html
