移动零
题目链接：移动零
https://leetcode.cn/problems/move-zeroes/description/
- 算法原理
这类题是属于数组划分、数组分开题型
- 代码步骤：
- 使用cur遍历数组
- 当cur所指的元素等于0时，cur向后面移动
- 当cur所指的元素不等于0时，dest向后面移动，cur所指元素与dest移动后所指的元素交换
- 当cur指向最后一个元素的下一个时，结束。
- 代码展示
class Solution {
public:
void moveZeroes(vector<int>& nums)
{
int dest = -1;
for(int cur = 0; cur < nums.size(); ++cur)
{
//如果cur所指的元素非0，交换
if(nums[cur] != 0)
{
swap(nums[++dest], nums[cur]);
}
}
}
};复写零
题目链接：
复写零https://leetcode.cn/problems/duplicate-zeros/description/
- 算法原理
- 代码步骤：
- 代码展示
class Solution {
public:
void duplicateZeros(vector<int>& arr)
{
//寻找复写的最后一个元素
int cur = 0;
int dest = -1;
int n = arr.size();
//注意arr.sizr()是size_t无符号类型
//int(-1)比size_t整数大
while(cur < n)
{
if(arr[cur])
{
++dest;
}
else
{
dest += 2;
}
//注意这个判断条件需要在里面实现
//如果在整个循环结束判断，cur的值无法保证
if(dest >= n-1) break;
cur++;
}
//特殊情况处理
if(dest == n)
{
arr[n - 1] = 0;
--cur;
dest -= 2;
}
//进行从右向左的复写操作
for(; cur >= 0; --cur)
{
if(arr[cur])
{
arr[dest--] = arr[cur];
}
else
{
arr[dest--] = 0;
arr[dest--] = 0;
}
}
}
};快乐数
题目链接：
快乐数https://leetcode.cn/problems/happy-number/submissions/552733314/
- 算法原理
- 代码步骤：
采用快慢双指针的思想：
- 定义快慢双指针
- 设置一个每个位置平方和的函数
- 慢指针每次向后移动一步
- 快指针每次向后移动俩步
- 判断快慢指针相遇的时候的值是否为1即可
- 代码展示
class Solution {
public:
//计算数每个位置上数字的平方和
int SquareSum(int n)
{
int sum =0;
while(n > 0)
{
int num = n % 10;
sum += num * num;
n /= 10;
}
return sum;
}
bool isHappy(int n)
{
int slow = n;
int fast = SquareSum(n);
while(slow != fast)
{
fast = SquareSum(SquareSum(fast));
slow = SquareSum(slow);
}
if(slow == 1)
{
return true;
}
else
{
return false;
}
}
};盛最多水的容器
题目链接：
盛最多水的容器https://leetcode.cn/problems/container-with-most-water/
- 算法原理
- 代码步骤：
- 记录初始w最大时的初始容积
- left与right二者中较小者向里面移动，寻找比自己大的值
- 找到比自己大的值，记录面积，并与之前的面积比较大小
- 当left与right相遇的时候，结束
- 代码展示
class Solution
{
public:
int maxArea(vector<int>& height)
{
int left = 0;
int right = height.size() - 1;
//寻找边界的最小值
int min = (height[left] < height[right])
? height[left]
: height[right];
//起始容积
int vmax = min * (right - left);
while(left < right)
{
if(height[left] < height[right])
{
//记录此时的left
int num = left;
while(left < right)
{
//比较看是否有比height[left]大的值
++left;
if(height[num] < height[left])
{
break;
}
}
}
else
{
//记录此时的left
int num = right;
while(left < right)
{
//比较看是否有比height[left]大的值
--right;
if(height[num] < height[right])
{
break;
}
}
}
min = (height[left] < height[right])
? height[left]
: height[right];
int v = min * (right - left);
vmax = (v > vmax) ? v : vmax;
}
return vmax;
}
};class Solution {
public:
int maxArea(vector<int>& height)
{
int left = 0, right = height.size() - 1, vmax = 0;
while(left < right)
{
int v = min(height[left], height[right]) * (right - left);
vmax = max(vmax, v);
if(height[left] < height[right]) ++left;
else --right;
}
return vmax;
}
};有效三角形个数
题目链接：
有效三角形个数https://leetcode.cn/problems/valid-triangle-number/
- 算法原理
- 代码步骤：
- 对数组进行排序
- 设置三个指针，一个指向最大值，另外俩个形成单调双指针
- 当left + right < max时，个数为right-left，right--
- 当left + right >= max时，个数为0，left++
- 代码展示
class Solution {
public:
int triangleNumber(vector<int>& nums)
{
int n = nums.size();
//排序升序
sort(nums.begin(), nums.end());
int sum = 0;
//最大值向前移动
while(n >= 2)//确保right不越界
{
int max = nums[n - 1];
int left = 0, right = n - 2;
//利用单调性使用双指针
while(left < right)
{
if(nums[left] + nums[right] > max)
{
sum += (right - left);
right--;
}
else
{
left++;
}
}
--n;
}
return sum;
}
};三数之和
题目链接：
三数之后https://leetcode.cn/problems/3sum/
- 算法原理
- 代码步骤：
- 排序
- 固定一个数min(注意当min > 0的时候，也是可以直接结束的)
- 在该数的后面的区间之内，利用单调性使用双指针，快速找到俩个和等于-min的值
- 细节1：不漏数据
- 细节2：去重操作
- 代码展示
class Solution
{
public:
vector<vector<int>> threeSum(vector<int>& nums)
{
vector<vector<int>> vv;
//排序
sort(nums.begin(), nums.end());
int n = nums.size();
//固定一个数
int min = 0;
for(int min = 0; min < n - 2; ++min)
{
//优化
if(nums[min] > 0) break;
int left = min + 1, right = n - 1;
while(left < right)
{
if(nums[left] + nums[right] < -nums[min])
{
left++;
}
else if(nums[left] + nums[right] > -nums[min])
{
right--;
}
else
{
//添加数据
vv.push_back({nums[min], nums[left], nums[right]});
while(left < right && nums[left] == nums[left + 1])
{
left++;
}
while(left < right && nums[right] == nums[right - 1])
{
right--;
}
if(left < right)
{
left++;
right--;
}
}
}
while(min < n - 2 && nums[min] == nums[min + 1])
{
min++;
}
}
return vv;
}
};四数之和
题目链接：
四数之和https://leetcode.cn/problems/4sum/description/
- 算法原理
- 代码步骤：
- 代码展示
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target)
{
vector<vector<int>> ret;
//排序
sort(nums.begin(), nums.end());
int n = nums.size();
//四数之和
for(int minA = 0; minA < n;)
{
long targetA = target - nums[minA];
//三数之和
for(int minB = minA + 1; minB < n;)
{
long targetB = targetA - nums[minB];
int left = minB + 1, right = n - 1;
while(left < right)
{
//利用单调性使用双指针
if(nums[left] + nums[right] < targetB)
{
left++;
}
else if(nums[left] + nums[right] > targetB)
{
right--;
}
else
{
ret.push_back({nums[minA], nums[minB], nums[left], nums[right]});
//left不重
while(left + 1 < right && nums[left] == nums[left + 1])
{
left++;
}
//right不重
while(left < right - 1 && nums[right] == nums[right - 1])
{
right--;
}
//不漏
if(left < right)
{
left++;
right--;
}
}
}
//minB不重
while(minB + 1 < n && nums[minB] == nums[minB + 1])
{
minB++;
}
++minB;
}
//minA不重
while(minA + 1 < n && nums[minA] == nums[minA + 1])
{
minA++;
}
++minA;
}
return ret;
}
};