wordpress 素材网站模版,贵州省兴义市专做网站公司,建设部网站企业资质,wordpress剧情网引言
我们已经在这篇博客【算法/学习】双指针-CSDN博客里面讲了双指针、二分等的相关知识。
现在我们来做一些训练吧
经典例题 1. 移动零 思路#xff1a; 使用 0 当做这个中间点#xff0c;把不等于 0(注意题目没说不能有负数)的放到中间点的左边#xff0c;等于 0 的…引言
我们已经在这篇博客【算法/学习】双指针-CSDN博客里面讲了双指针、二分等的相关知识。
现在我们来做一些训练吧
经典例题 1. 移动零 思路 使用 0 当做这个中间点把不等于 0(注意题目没说不能有负数)的放到中间点的左边等于 0 的放到其右边。 这的中间点就是 0 本身所以实现起来比快速排序简单很多然后使用双指针 i 和 j只要 nums[i]!0我们就交换 nums[i] 和 nums[j] class Solution {
public:void moveZeroes(vectorint 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(vectorint 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(vectorint 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;}
};
