C/C++：优选算法(持续更新~~)

一、双指针

1.1移动零

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

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]输出: [1,3,12,0,0] 

解法：

通过两个指针（并非是真的指针，只是数组的下标），dest和cur将长度为n的数组划分为三个部分；

[0,dest]：cur已经遍历过的地方，处理过不为0的部分；

[dest+1,cur-1]：cur已经遍历过的地方，处理过为0的部分；

[cur,n-1]：cur未遍历的地方；

第一种情况： cur指向数组元素为0

[0,dest]部分是处理过并且元素不为0的部分，cur指向0，所以处理后[0,dest]不变；

[dest+1,cur-1]部分是处理过为0的部分，所以处理后[dest+1,cur-1]长度加一；

[cur,n-1]部分长度减一；

 第二种情况： cur指向数组元素不为0

[0,dest]部分是处理过并且元素不为0的部分，cur指向1，所以处理后[0,dest]长度加一，dest往后移一位，用来存放1；

[dest+1,cur-1]部分是处理过为0的部分，所以处理后[dest+1,cur-1]长度不变；

[cur,n-1]部分长度减一；

 dest往后移一位，dest指向为0的部分，只需要将此时的dest指向和cur指向元素交换即可，之后cur++；

初始状态，dest=-1，cur=0；

1.nums[cur]为0，cur++；

2.nums[cur] 不为0，dest++后，在交换nums[dest]和nums[cur];

c++解法： 

class Solution {
public:
    void moveZeroes(vector<int>& nums) 
    {
        for(int dest=-1,cur=0; cur<nums.size(); cur++)
        {
            if(nums[cur])
                swap(nums[cur], nums[++dest]);
        }
    }
};

c语言解法： 

void moveZeroes(int* nums, int numsSize) 
{
    for(int dest=-1,cur=0; cur<numsSize; cur++)
    {
        if(nums[cur])
        {       
            int temp = 0;
            temp = nums[++dest];
            nums[dest] = nums[cur];
            nums[cur] = temp;
        }
    }
}

1.2复写零

  链接：1089. 复写零 - 力扣（LeetCode）

给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。

示例 1：

输入：arr = [1,0,2,3,0,4,5,0]
输出：[1,0,0,2,3,0,0,4]
解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]

解法：

在不用额外的数组情况下，从前往后复写会造成数据覆盖的影响，因此需要从后往前复写；

但从什么位置从后向前进行复写，需要额外确定；

1.找出从后往前开始复写的位置；

2.从后往前复写；

初始状态 ：

1.cur指向的元素不为0，dest往后移一位；

2.cur指向的元素为0，dest往后移两位； 

初始状态：cur指向1，dest++；

cur再往后移一位，指向元素为0；

dest往后移两位；

当dest移动到最后一位时，停止移动，记录此刻cur的位置； 

特殊情况： 

当cur指向元素0时，dest往后移动两位，此刻dest越界；

手动将数组最后一位，将其元素改为0；

cur往前移动一位，dest往前移两位；

从此刻开始复写；

1.arr[cur]不为0，arr[dest] = arr[cur]；

2. arr[cur]为0，arr[dest] = arr[dest-1] = 0；

直到cur=0；

c++实现： 

class Solution {
public:
    void duplicateZeros(vector<int>& arr) 
    {
        int cur = 0, dest = -1;
        int n = arr.size();
        for(cur=0,dest=-1; dest<n-1; cur++)
        {
            if(arr[cur])
                dest++;
            else
                dest += 2;
        }
        if(dest == n)
        {
            arr[n-1] = 0;
            dest -= 2;
            cur--;
        }

        cur--;
        for(; cur>=0; cur--)
        {
            if(arr[cur])
            {
                arr[dest] = arr[cur];
                dest--;
            }
            else
            {
                arr[dest] = 0;
                arr[dest-1] = 0;
                dest -= 2;
            }
        }
    }
};

1.3 快乐数

链接：202. 快乐数 - 力扣（LeetCode）

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 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

 对应两种情况：

1.重复操作最后结果会变成1：

例如19，经过4步操作后变为1；

2.重复一定操作步骤后陷入无限循环中：

例如2，平方后变成4，又经过几次操作后又出现了4，所以会一直陷入循环中；

上述两种情况都会进入 一个循环，第一种进入的循环全为1；第二种循环中不会出现1；根据此判断是否为快乐数;

快慢指针可以解决是否是环形链式结构，只需判断出slow指针和fast指针相遇时的值是否为1即可；slow++，fast+=2；

class Solution 
{
public:
    int func(int 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 = func(n);
        while(slow != fast)
        {
            slow = func(slow);
            fast  =func(func(fast));
        }
        return slow == 1;
    }
};

1.4 盛最多水的容器

链接：11. 盛最多水的容器 - 力扣（LeetCode）

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。说明：你不能倾斜容器。

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

解法1：暴力解法

0-1，0-2，...0-8；

1-2，1-3，...1-8；

...

7-8；找出他们中的最大值

解法2： 

选取两个边5和7，所盛水的体积,高度为min(5,7)=5,底为4，v=高×底 = 20；

1.因数1×因数2 = 乘积1； 因数1减小，因数2不变，乘积1减小；

2.因数1×因数2 = 乘积2； 因数1减小，因数2减小，乘积2减小；

下图：

（固定较矮的一侧，移动较高的一侧）

1.固定左边蓝色条，右边蓝色条移动，向左移动一位，右边蓝色条高度变为3（比左边蓝色条高），因此此刻高不变（仍为1），底减小，容积变小；

容积最大时为初始状态（下标0-8），向里缩只会减小；

上述较矮的一方向里侧移动，左侧蓝色条向右移动一位后如下图所示。

1.固定右边蓝色条，左边蓝色条移动，向右移动一位，右边蓝色条高度变为6（比右边蓝色条矮），因此此刻高减小（为6），底减小，容积变小；

容积最大时为初始状态（下标1-8），向里缩只会减小；

重复上述操作： 

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);
            if(ret < v)
                ret = v;
            if(height[left] < height[right])
                left++;
            else
                right--;
        }
        return ret;
    }
};