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;
}
};