移动零
- 算法原理
这类题是属于数组划分、数组分开题型
- 代码步骤：
- 使用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]); } } } };
复写零
题目链接：
- 算法原理
- 代码步骤：
- 代码展示
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; } } } };
快乐数
题目链接：
- 算法原理
- 代码步骤：
采用快慢双指针的思想：
- 定义快慢双指针
- 设置一个每个位置平方和的函数
- 慢指针每次向后移动一步
- 快指针每次向后移动俩步
- 判断快慢指针相遇的时候的值是否为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; } } };
盛最多水的容器
题目链接：
- 算法原理
- 代码步骤：
- 记录初始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; } };
有效三角形个数
题目链接：
- 算法原理
- 代码步骤：
- 对数组进行排序
- 设置三个指针，一个指向最大值，另外俩个形成单调双指针
- 当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; } };
三数之和
题目链接：
- 算法原理
- 代码步骤：
- 排序
- 固定一个数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; } };
四数之和
题目链接：
- 算法原理
- 代码步骤：
- 代码展示
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; } };
