1.移动零
283. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作
算法原理：定义双指针：left = 0, right = -1，++right，再检查nums[ right ] 的值，等于 1 则与nums[ left ]交换，交换后++left
class Solution {
public:
void moveZeroes(vector<int>& nums)
{
int n = nums.size();
for(int left = 0, right = -1; right < n - 1;)
if(nums[++right]) swap(nums[left++], nums[right]);
}
};这是ac代码
2.复写零
1089. 复写零
给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西
算法原理：定义双指针dest = -1， cur = 0，利用快慢指针定位到结束的最后一个字符，从后往前改变数组（从前往后会发生数据覆盖），注意边界情况处理
class Solution {
public:
void duplicateZeros(vector<int>& arr)
{
int n = arr.size(), cur = 0, dest = -1;
while(cur < n)
{
if(arr[cur]) ++dest;
else dest += 2;
if(dest >= n - 1) break;
++cur;
}
if(dest == n)
{
arr[n - 1] = 0;
dest -= 2;
--cur;
}
while(cur >= 0)
{
if(arr[cur]) arr[dest--] = arr[cur--];
else
{
arr[dest--] = 0;
arr[dest--] = 0;
--cur;
}
}
}
};这是ac代码
3.快乐数
202. 快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false
算法原理：有数学知识可知，整个快乐数计算过程中必定循环，如果循环点一直是 1 那么是快乐数，反之不是，据此编写代码即可，注意由于题目特性，这里用子函数来模拟一次操作数字
class Solution {
public:
int _isHappy(int n)
{
int ret = 0;
while(n)
{
ret += pow(n % 10, 2);
n /= 10;
}
return ret;
}
bool isHappy(int n)
{
int slow = n, fast = n;
do
{
slow = _isHappy(slow);
fast = _isHappy(_isHappy(fast));
}
while(slow != fast);
return slow == 1;
}
};这是ac代码
4.盛水最多的容器
11. 盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
算法原理：定义双指针left = 0, right = n - 1，对应高度小的往中间靠拢，计算更新面积最大值，left == right 时退出循环，返回结果
class Solution {
public:
int maxArea(vector<int>& height)
{
int n = height.size();
int ret = 0;
for(int left = 0, right = n - 1; left < right;)
{
ret = max(ret, (right - left) * min(height[right], height[left]));
if(height[left] < height[right]) ++left;
else --right;
}
return ret;
}
};这是ac代码
5.有效的三角形个数
611. 有效三角形的个数
给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数
算法原理：先对数组进行排序，再用 i 从后往前遍历，再用双指针标识前后，利用三角形两边之和大于第三边的特性，快速求出满足三角形的个数
class Solution {
public:
int triangleNumber(vector<int>& nums)
{
int n = nums.size(), ret = 0;
if(n < 3) return 0;
sort(nums.begin(), nums.end());
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;
}
};这是ac代码
6.查找总价格为目标值的两个商品
LCR 179. 查找总价格为目标值的两个商品
购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可
算法原理：使用双指针left = 0, right = n - 1，计算和，若等于target 直接返回结果，大于则right--，小于则left++
class Solution {
public:
vector<int> twoSum(vector<int>& price, int target)
{
int n = price.size();
sort(price.begin(), price.end());
for(int left = 0, right = price.size() - 1; left < right;)
{
if(price[left] + price[right] == target)
return {price[left], price[right]};
else if(price[left] + price[right] > target)
--right;
else
++left;
}
return {-1, -1};
}
};这是ac代码
7.三数之和
15. 三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组
算法原理：用i固定一个数i ，再用两数之和的解法解决即可，重点是题目要求的去重操作，如果出现重复情况需要特殊处理
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums)
{
vector<vector<int>> ret;
int n = nums.size();
sort(nums.begin(), nums.end());
for(int i = 0; i < n;)
{
if(nums[i] > 0) break;
for(int left = i + 1, right = n - 1; left < right;)
{
if(nums[i] + nums[left] + nums[right] < 0)
++left;
else if(nums[i] + nums[left] + nums[right] > 0)
--right;
else
{
ret.push_back({nums[i], nums[left], nums[right]});
++left, --right;
while(left < right && nums[left] == nums[left - 1]) ++left;
while(left < right && nums[right] == nums[right + 1]) --right;
}
}
++i;
while(i < n && nums[i] == nums[i - 1]) ++i;
}
return ret;
}
};这是ac代码
8.四数之和
18. 四数之和
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、b、c和d互不相同nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案
算法原理：用i固定两个数i j，再用两数之和的解法解决即可，重点是题目要求的去重操作，如果出现重复情况需要特殊处理
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target)
{
vector<vector<int>> ret;
int n = nums.size();
sort(nums.begin(), nums.end());
for(int i = 0; i < n;)
{
for(int j = i + 1; j < n;)
{
int left = j + 1, right = n - 1;
while(left < right)
{
long long sum = (long long)nums[left] + nums[right] + nums[i] + nums[j];
if(sum < target) ++left;
else if(sum > target) --right;
else
{
ret.push_back({nums[i], nums[j], nums[left], nums[right]});
++left, --right;
while(left < right && nums[left] == nums[left - 1]) ++left;
while(left < right && nums[right] == nums[right + 1]) --right;
}
}
++j;
while(j < n && nums[j] == nums[j - 1]) ++j;
}
++i;
while(i < n && nums[i] == nums[i - 1]) ++i;
}
return ret;
}
};这是ac代码
](https://img-blog.csdnimg.cn/direct/e060f6625e6748fa91a19ef5cb8f3ede.png)
![[muduo网络库]——muduo库的Reactor模型（剖析muduo网络库核心部分、设计思想）](https://img-blog.csdnimg.cn/direct/a2042af6c540482c8b6e5607edeccb9a.png)
