初探算法之双指针开篇

初探算法之双指针开篇

目录

前言：

此篇作为算法篇章的首篇文章，自然得简单说上几句。算法部分呢，多刷题是必不可少的。从暴力解法过渡到算法解法，过程着实有些艰辛，而算法的思考尤为关键。所以算法部分的讲解大多借助题目直接展开，以题目来传授算法知识。鉴于每个人对算法的接受程度有别，每篇通常涵盖两题左右，难题部分一般只设一道，且题目均取自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)，相较暴力解法有显著优化。

题目链接：283. 移动零 - 力扣（LeetCode）

题目二:

示例如下：

输入： 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;
            }
        }
    }
};

今日算法分享至此，感谢阅读！