wordpress谷歌网站地图,ih5制作平台官网,dedecms手机网站开发,如何分析企业网站优选算法第一讲#xff1a;双指针模块 1.移动零2.复写零3.快乐数4.盛最多水的容器5.有效三角形的个数6.查找总价格为目标值的两个商品7.三数之和8.四数之和 1.移动零
链接: 移动零 下面是一个画图#xff0c;其中#xff0c;绿色部分标出的是重点#xff1a; 代码实现双指针模块 1.移动零2.复写零3.快乐数4.盛最多水的容器5.有效三角形的个数6.查找总价格为目标值的两个商品7.三数之和8.四数之和 1.移动零
链接: 移动零 下面是一个画图其中绿色部分标出的是重点 代码实现
class Solution {
public:void moveZeroes(vectorint nums) {//定义双指针for(int cur 0, des -1; cur nums.size(); cur){//当cur指向的位置不为0时才进行交换if(nums[cur]){swap(nums[cur], nums[des]);//注意先des再进行交换}}}
};2.复写零
链接: 复写零 代码实现
class Solution {
public:void duplicateZeros(vectorint arr) {//先找到src的位置int src 0, des -1, n arr.size();while(src n){if(arr[src]) des;else des2;if(des n-1) break;src;}if(des n){//发生了越界时修正des的位置arr[n-1] 0;src--;des - 2;}//从后向前复写while(des 0){if(arr[src])arr[des--] arr[src--];else{arr[des--] 0;arr[des--] 0;src--;}}}
};3.快乐数
链接: 快乐数
class Solution {
public://按照题意求值int Value(int n){//循环*10 %10C语言中讲过int sum 0;while(n){int t n % 10;sum t*t;n n /10;}return sum;}bool isHappy(int n) {int slow n, fast Value(n);while(slow ! fast){slow Value(slow);fast Value(Value(fast));}return slow 1;}
};4.盛最多水的容器
链接: 盛最多水的容器 代码实现
class Solution {
public:int maxArea(vectorint height) {int left 0, right height.size()-1, ret 0;while(left right){int H min(height[left], height[right]);ret max(ret, (right-left)*H);if(height[left] height[right]) right--;else left;}return ret;}
};5.有效三角形的个数
链接: 有效三角形的个数
class Solution {
public:int triangleNumber(vectorint nums) {//1.先对数组进行排序sort(nums.begin(), nums.end());int sum 0;for(int i nums.size()-1; i2; i--){//i为最大值的下标//使用双指针进行运算int left 0, right i-1;while(left right){if(nums[left] nums[right] nums[i]){sum right-left;right--;}else left;}}return sum;}
};6.查找总价格为目标值的两个商品
链接: 查找总价格为目标值的两个商品
class Solution {
public:vectorint twoSum(vectorint price, int target) {//因为题目说明已经是升序了所以我们不用再进行排序了//使用双指针算法int left 0, right price.size()-1;while(left right){if(price[left] price[right] target) right--;else if(price[left] price[right] target) left;else return {price[left], price[right]};}return {0, 0};}
};7.三数之和 class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint ret;//1.先对数组进行排序sort(nums.begin(), nums.end());//对i的固定int i 0;while(i nums.size()-3){//双指针算法int left i1, right nums.size()-1;while(left right){if(nums[left] nums[right] -nums[i]) right--;else if(nums[left] nums[right] -nums[i]) left;else{//当相等时先插入数据ret.push_back(vectorint({nums[left], nums[right], nums[i]}));//再处理去重问题left;right--;while(left right nums[left] nums[left-1]) left;while(left right nums[right] nums[right1]) right--;}}//对i进行去重i;while(i nums.size()-3 nums[i] nums[i-1]) i;}return ret;}
};8.四数之和
链接: 四数之和
