免费建站推广线上推广营销

1.移动零

283. 移动零 - 力扣（LeetCode）

双指针算法

两个指针的作用：

cur：从左向右遍历数组  dest：已处理区间内非零元素的最后一个位置。

[0,dest]  非零元素  

[dest+1,cur]      0

[cur,n-1]   待处理

cur遍历过程中遇到0元素cur++，遇到非0元素交换cur和dest+1位置的值，dest++和cur++

void moveZeroes(vector<int>& nums) {for(int cur = 0, dest = -1; cur < nums.size(); cur++){if(nums[cur]){swap(nums[cur],nums[dest + 1]);dest++;}}        }

2.复写零

1089. 复写零 - 力扣（LeetCode）

方法一：运用库函数

直接遍历数组，在0的位置之前插入0，最后resize为原空间大小

class Solution {
public:void duplicateZeros(vector<int>& arr) {int n = arr.size();auto it = arr.begin();while(it != arr.end()){if(*it == 0){it = arr.insert(it,0);it++;}it++;} arr.resize(n);   }
};

方法二：双指针法

1.先找到最后一个复写的数

        先判断cur位置的值，再决定dest往后移动一不还是两步，判断dest是否已经到了结束位置，cur++。

        找到最后一个复写的树，处理一下边界情况，如果dest == n 将arr[dest - 1]的位置置为0，cur--，dest -= 2。

2.从后往前完成复写操作

void duplicateZeros(vector<int>& arr) {int dest = -1,cur = 0;int n = arr.size();while (cur < n){if(arr[cur] == 0){dest += 2;}else{dest++;}if(dest >= n - 1)break;cur++;}if(dest == n){arr[dest - 1] = 0;cur--;dest -= 2;}while(cur >= 0){if(arr[cur]){arr[dest--] = arr[cur--];}else{arr[dest--] = 0;arr[dest--] = 0;cur--;}}}

3.快乐数

202. 快乐数 - 力扣（LeetCode）

思路：上述情况所示，这个值最后会形成一个环，一个环中全为1，一个环中没有1。所以可以使用判断链表是否有环的解法：快慢双指针。

1.定义快慢双指针

2.慢指针每次向后移动一位，快指针每次向后移动两步

3.判断相遇时候的值就可以

class Solution {
public:int retn(int n){int ret = 0;while(n){int x = n % 10;n /= 10;ret += x*x;}return ret;}bool isHappy(int n) {int slow = n;int fast = retn(n);while(slow != fast){slow = retn(slow);fast = retn(retn(fast));}return slow == 1;}
};

4.盛最多水的容器

11. 盛最多水的容器 - 力扣（LeetCode）

方法一（未通过）：暴力解法，直接遍历数组

class Solution 
{
public:int maxArea(vector<int>& height) {int max = 0;for(int i = 0; i < height.size(); i++){for(int j = i + 1; j < height.size();j++){int m = min(height[i],height[j]);int ret = m * (j - i);if(max < ret)max = ret;}}return max;}
};

但是数据太多会超时。

方法二：利用单调性，双指针算法

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);ret = max(ret,v);if(height[left] < height[right])left++;elseright--;}return ret;}};

5.有效三角形的个数

611. 有效三角形的个数 - 力扣（LeetCode）

思路：先对数组排序（在有序中只要判断a+b>c就可以判断是否为三角形），利用单调性，用双指针算法来解决问题

1. 先找最大的数就是排序完的最后一个数
2. 在最大数的左区间，使用双指针算法，快速统计出符合要求的三元组的个数
3. 当nums[left] + nums[right] > nums[c] 剩下left的右边的数与right的数相加必然大于c的数，ret直接加等right - left区间的数，right再--。
4. 当nums[left] + nums[right] < nums[c] left与right左边的数相加肯定小于c的数，直接++left
5. 结束条件是c的位置要大于等于2（c左边还有right和left）

class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());int c = nums.size() - 1;int left = 0, right = c - 1;int ret = 0;while(c >= 2){while(left < right){if(nums[left] + nums[right] > nums[c]){ret += right - left;right--;}else{left++;}}c--;right = c - 1;left = 0;}return ret;}
};

6.查找总价格为目标的两个商品

LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）

思路：利用单调性（题目中说了有序），使用双指针算法解决问题

定义left指向开始，和right指向结尾，判断两数相加的值与target的关系，大于就right--，小于left++

    vector<int> twoSum(vector<int>& price, int target) {vector<int> ret;int left = 0, right = price.size() - 1;while(left < right){if(price[left] + price[right] == target){ret.push_back(price[left]);ret.push_back(price[right]);break;}else if(price[left] + price[right] > target){--right;}else{++left;}}    return ret;}

还有一种直接隐式类型转换做返回值

vector<int> twoSum(vector<int>& price, int target) {       int left = 0, right = price.size() - 1;while(left < right){int sum = price[left] + price[right];if(sum > target) right--;else if(sum < target) left++;else return {price[left],price[right]};}//不加这句在leetcode上编译不过，所以要返回一个值return {-1,-1};    }

7.三数之和

思路：对数组进行排序后，使用双指针，固定一个数c，然后利用上面两个商品的两数求和来求c的相反数，区别是找到一种结果后不要停（当c大于0时，因为数组有序，所以在c右边不可能找到相加为c相反数的值）。

这道题还需要去重，找到一种结果后，left和right要跳过重复元素，当使用完一次双指针后c也要跳过重复元素。

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(),nums.end());vector<vector<int>> vv;for(int c = 0; c < nums.size() - 2; c++){if(nums[c] > 0)//大于0后，后面的数相加绝对不会等于他的相反数break;int left = c + 1;int right = nums.size() - 1;while(left < right){int x = -nums[c];int sum = nums[left] + nums[right];vector<int> v;if(sum < x)left++;else if(sum > x)right--;else{v.push_back(nums[left]);v.push_back(nums[right]);v.push_back(nums[c]);vv.push_back(v);while(left < right && nums[left] == nums[left + 1]){left++;}while(right > left &&nums[right] == nums[right - 1]){right--;}left++;right--;}while(nums[c] == nums[c + 1] && c < nums.size() - 2)c++;}}return vv;}
};

8.四数之和

18. 四数之和 - 力扣（LeetCode）

和上面三数之和的思路一样，四数之和是固定两个数，再左右指针往下走，但是这个题在减的时候会报错，所以要开成long long。

class Solution 
{
public:
vector<vector<int>> fourSum(vector<int>& nums, int target)
{sort(nums.begin(),nums.end());vector<vector<int>> vv;size_t n = nums.size();for(size_t i = 0; i < n; ){for(size_t j = i + 1; j < n;){size_t left = j + 1;size_t right = n - 1;long long x = (long long)target - nums[i] - nums[j];while(left < right){int sum = nums[left] + nums[right];if(sum < x){left++;}else if(sum > x){right--;}else{vector<int> v;v.push_back(nums[i]);v.push_back(nums[j]);v.push_back(nums[left]);v.push_back(nums[right]);vv.push_back(v);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 vv;
}
};