题一：移动零

一、题目

二、分析

1.双指针算法

利用数组下标充当划分指针

2.两个指针的作用：

cur: 从左往右扫描数组，遍历数组

dest: 已处理的区间内，非零元素的最后一个位置

三个区间：

[0, dest]：非 0 元素，且 ≤ tmp

[dest + 1, cur - 1]：0 元素，且 > tmp

[cur, n - 1]：待处理元素

3.做法

cur 从前往后遍历的过程中：

1. 遇到 0 元素：cur++
2. 遇到非零元素：swap(dest + 1, cur); dest++, 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]);
    }
};

题二：复写零

一、题目

二、分析

1. 先找到最后一个 “复写” 的数；

双指针算法

1. 先判断 cur 位置的值

2. 决定 dest 向后移动一步或者两步（非0一步，0两步）

3. 判断一下 dest 是否已经到结束为止

4. cur++

        

特殊情况

1.5 处理一下边界情况

     

越界了，将n-1的位置修改为0

n-1 → 0

cur --

dest -= 2

2. “从后向前” 完成复写操作

           

三、代码

class Solution
{
public:
    void duplicateZeros(vector<int>& arr)
    {
        // 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++;
        }

        // 2. 处理一下边界情况
        if(dest == n)
        {
            arr[n - 1] = 0;
            cur--; dest -= 2;
        }

        // 3. 从后向前完成复写操作
        while(cur >= 0)
        {
            if(arr[cur]) 
                arr[dest--] = arr[cur--];
            else
            {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }
};

题三：快乐数

一、题目

二、分析

示例分析

可以看到有环，判断环，想到快慢双指针（思想，不是一定要定义指针）

1.定义快、慢指针

2.让指针移动。，慢指针每次向后移动一步，快指针每次向后移动两步。

3.判断相遇时的值（是1快乐，不是1不快乐）

扩展：没有第二个条件，无法确定是否有环，存在不是环的情况

鸽巢原理（抽屉原理）

n个鸽子，n+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;
    }
};

题四：盛最多水的容器

一、题目

二、分析

解法一：暴力枚举（超时）

解法二：利用单调性，使用双指针来解决问题

6——4之间，

从六往四移动（不可取）

1.高比原来小，宽度也减小，总体减小

2.高比最小值打，高不变（木桶效应），宽减小总体减小

从四往六移动（去掉最小的）（可取）

过程

一样的时候左右都可以（感觉有漏洞）

三、代码

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

题五：有效三角形的个数

一、题目

二、分析

如果过已知，只需要验证即可

解法一：暴力枚举

伪代码

解法二：利用单调性使用双指针算法（二分也可以但不是最优）

1.

个数为

2.

总结：

先固定最大的数

在最大叔的左区间内使用双指针算法，快速统计出符合要求的三元组的个数

三、代码

int triangleNumber(vector<int>& nums)
{
    // 1. 优化
    sort(nums.begin(), nums.end());

    // 2. 利用双指针解决问题
    int ret = 0, n = nums.size();
    for(int i = n - 1; i >= 2; i--) // 先固定最大的数
    {
        // 利用双指针快速统计符合要求的三元组的个数
        int left = 0, right = i - 1;
        while(left < right)
        {
            if(nums[left] + nums[right] > nums[i])
            {
                ret += right - left;
                right--;
            }
            else
            {
                left++;
            }
        }
    }
    return ret;
}