凤山网站seo成人职业技能培训班

引言

我们已经在这篇博客【算法/学习】双指针-CSDN博客里面讲了双指针、二分等的相关知识。

现在我们来做一些训练吧 

经典例题

1. 移动零

 思路：
  使用 0 当做这个中间点，把不等于 0(注意题目没说不能有负数)的放到中间点的左边，等于 0 的放到其右边。
这的中间点就是 0 本身，所以实现起来比快速排序简单很多，然后使用双指针 i 和 j，只要 nums[i]!=0，我们就交换 nums[i] 和 nums[j]

class Solution {
public:void moveZeroes(vector<int>& nums) {if (nums.size() == 0) return;// 双指针，前后交换即可int j = 0;for (int i = 0; i < nums.size(); i++) {//当前元素!=0，就把其交换到左边，等于0的交换到右边if (nums[i] != 0) {swap(nums[i], nums[j++]);}}}
};

2. 复写零

思路：

class Solution {
public:void duplicateZeros(vector<int>& arr) {// 1. 找到最后一个复写数 int cur = 0, dest = -1, n = arr.size();while (cur < n){if (arr[cur]) dest++;else dest += 2;if (dest >= n - 1) break;cur++;}// 2. 处理边界清空if (dest == n){arr[n - 1] = 0;cur--, dest -= 2;}// 3. 从后往前完成复写操作while (cur >= 0){if (arr[cur]) arr[dest--] = arr[cur--];else{arr[dest--] = 0;arr[dest--] = 0;cur--;}}}
};

3. 有效三角形的个数

思路：

首先对数组排序。
固定最短的两条边，二分查找最后一个小于两边之和的位置。可以求得固定两条边长之和满足条件的结果。枚举结束后，总和就是答案。

class Solution {
public:int triangleNumber(vector<int>& nums) {// 1. 排序来优化sort(nums.begin(), nums.end());// 2. 利用双指针来解决问题 int ret = 0, n = nums.size();for (int i = n - 1; i >= 2; i--) // 先固定最大的数{// 利用双指针快速统计符合要求的三元组个数int l = 0, r = i - 1;while (l < r){if (nums[l] + nums[r] > nums[i]){ret += r - l;r--;}else l++;}}return ret;}
};