高效算法之双指针初涉

高效算法之双指针初涉

双指针

• 移动零
• 复写零
• 快乐数
• 盛最多水的容器

---

移动零

题目链接：移动零

题目描述：

算法原理：

此类问题属于数组的分块范畴，可运用双指针策略解决。双指针包含两个变量，分别作为数组的索引，模拟指针的功能。

双指针的区间划分：
cur：向前遍历数组的未知部分
dest：标记已处理区间的末尾位置

双指针将数组划分为三个区间：
[0, dest] 是非零元素区间
[dest + 1, cur – 1] 是全零元素区间
[cur, n – 1] 是待扫描区间

初始状态时，cur设为0，dest设为-1，此时尚未开始扫描，dest指向首元素的前一位。

在cur向前遍历过程中：

1. 遇0元素，cur指针后移
2. 遇非零元素，交换nums[++dest]与nums[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]);
    }
};

---

复写零

题目链接：复写零

题目描述：

算法原理：

利用双指针在原数组上操作来解决问题。

首先通过双指针进行“异地操作”以探寻可转为“原地操作”的途径。

发现从前向后遍历时dest会超出cur，故不能从前向后遍历。

尝试从后向前遍历，发现可行，但需确定cur的起始位置。

总结步骤：
1. 确定最后一个需复写的数的位置
此时需在双指针中嵌套另一双指针以辅助后续复写操作。

1. 判断cur位置的元素值
2. 根据是否为0，决定dest后移一步或两步
3. 判断dest的位置
4. 根据是否在最后一位之前，决定是否++cur
5. 循环条件为dest < n – 1

2. 处理边界情况

边界情况产生于最后一个要复写的数为0，致使dest移动两步后等于n。
解决办法：
arr[n – 1] = 0;
dest -= 2;
–cur;

3. 从后向前完成复写操作

1. 若cur位置的元素非0
   arr[dest–] = arr[cur–];

2. 若cur位置的元素为0
   arr[dest–] = arr[cur];
   arr[dest–] = arr[cur–];

3. 循环条件：cur >= 0

代码：

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        // 1. 确定最后一个需复写的数的位置
        int dest = -1, cur = 0, n = arr.size();
        while(dest < n - 1)
        {
            if(arr[cur]) ++dest;
            else dest += 2;
            if(dest < n - 1) ++cur;
        }
        // 2. 处理边界情况
        if(dest == n)
        {
            arr[n - 1] = 0;
            dest -= 2;
            --cur;
        }
        // 3. 从后向前完成复写操作
        while(cur >= 0)
        {
            if(arr[cur]) arr[dest--] = arr[cur--];
            else
            {
                arr[dest--] = arr[cur];
                arr[dest--] = arr[cur--];
            }
        }
    }
};

---

快乐数

题目链接：快乐数

题目描述：

题目解析

以示例一为例：19 -> 82 -> 68 -> 100 -> 1，之后进入1的循环；示例二：2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4，进入循环。

此两种情况分别对应题目中的两种结果：
1. 持续循环至1
2. 持续循环至其他数，无法到达1

扩展了解

若题目未给出提示，可能会考虑第三种情况，但经证明该情况不存在。

证明过程

1. 数据范围最大值为2^31 – 1 = 2147483647，近似为9999999999，经一次平方和操作后变为9^2 * 10 = 810，故变化区间在[1, 810]。
2. 根据鸽巢原理，经811次平方和操作后，必然形成循环。
3. 因此，不存在不进入循环的情况。

算法原理：

若熟悉数据结构中的链表环检测，可采用快慢指针解决。此处的快慢指针指向各个数。

1. 定义快慢指针
2. 慢指针每次走一步，快指针每次走两步
3. 判断相遇时的值是否为1

代码：

class Solution {
public:

    int bitSum(int n) // 计算n各位数的平方和
    {
        int sum = 0;
        while(n)
        {
            int t = n % 10;
            sum += t * t;
            n /= 10;
        }
        return sum;
    }

    bool isHappy(int n) 
    {
        int slow = n, fast = bitSum(n);
        while(slow != fast)
        {
            slow = bitSum(slow);
            fast = bitSum(bitSum(fast));
        }
        return slow == 1;
    }
};

---

盛最多水的容器

题目链接：盛最多水的容器

题目描述：

题目解析

算法原理：

代码：

class Solution 
{
public:
    int maxArea(vector<int>& height) 
    {
        int left = 0, right = height.size() - 1;
        int ret = 0;
        while(left < right)
        {
            int v = (right - left) * min(height[left], height[right]);
            ret = max(ret, v);
            if(height[left] < height[right]) ++left;
            else --right;
        }
        return ret;
    }
};