自建网站推广,seo是搜索引擎吗,wordpress 文章太多,wordpress发卡双指针法#xff08;快慢指针法#xff09;在数组、字符串和链表的操作中是非常常见的#xff0c;这里结合力扣上的题进行可一下梳理#xff0c;主要的思路是我们要明确快指针指的是什么#xff0c;慢指针指的是什么。
1. 移除元素类问题
27. 移除元素
要我们移除目标元…双指针法快慢指针法在数组、字符串和链表的操作中是非常常见的这里结合力扣上的题进行可一下梳理主要的思路是我们要明确快指针指的是什么慢指针指的是什么。
1. 移除元素类问题
27. 移除元素
要我们移除目标元素返回移动后元素的新长度。
快指针原数组的索引这里是fast慢指针移除后数组的索引这里是slow
我们循环时一定是快指针遍历整个数组然后慢指针根据条件移动如果发现快指针不等于指定的目标元素valnums[fast] ! val我们对当前的nums[slow]赋值为nums[fast]让后slow自增。
class Solution {
public:int removeElement(vectorint nums, int val) {int slow 0;for (int fast 0; fast nums.size(); fast){if (nums[fast] ! val)nums[slow] nums[fast];}return slow;}
};26. 删除有序数组中的重复项
要我们移除数组重复的元素返回移动后元素的新长度。
快指针原数组的索引这里是fast慢指针移除后数组的索引这里是slow
为了看是否有重复项我们一定是比较nums[fast]和nums[fast - 1]看是否相等如果不相等说明不重复我们可以把当前的nums[fast]赋值给nums[slow]并且slow往前移动一位为了fast-1不越界fast的遍历应该从1开始也是遍历整个数组既然从1开始slow的初始值也应该是1因为第一个元素我们认为不需要删除。
class Solution {
public:int removeDuplicates(vectorint nums) {int slow 1;for (int fast 1; fast nums.size(); fast){if (nums[fast] ! nums[fast - 1])nums[slow] nums[fast];}return slow;}
};80. 删除有序数组中的重复项 II
要我们移除数组重复的元素返回移动后元素的新长度每个元素最多有2个。
快指针原数组的索引这里是fast慢指针移除后数组的索引这里是slow
朴素的思路是判断nums[fast]前后元素是否和nums[fast]一样。
class Solution {
public:int removeDuplicates(vectorint nums) {int slow 1;for (int fast 1; fast nums.size(); fast){if (fast nums.size() - 1){if (!(nums[fast] nums[fast - 1] nums[fast] nums[fast 1]))nums[slow] nums[fast];}else{nums[slow] nums[fast];//最后一个元素不管重不重复都放进来因为至少要2个}}return slow;}
};其实可以不拘泥于26题的写法
class Solution {
public:int removeDuplicates(vectorint nums) {int n nums.size();if (n 2)return n;int slow 2;for (int fast 2; fast n; fast){if (nums[slow - 2] ! nums[fast])nums[slow] nums[fast];}return slow;}
};移除保留最多k个元素的通用写法
class Solution {
public:int removeDuplicates(vectorint nums) {int n k;if (nums.size() k)return n;int slow k;for (int fast k; fast nums.size(); fast){if (nums[slow - k] ! nums[fast])nums[slow] nums[fast];}return slow;}
};283.移动零
要我们把零全部移动到最后一种直观的思路是使用移除元素的方法把零移除完然后从这时的slow开始把数组后面的值都赋值为0
快指针原数组的索引这里是fast慢指针移除后数组的索引这里是slow class Solution {
public:void moveZeroes(vectorint nums) {int slow 0;for (int fast 0; fast nums.size(); fast){if (nums[fast] ! 0)nums[slow] nums[fast];}for (; slow nums.size(); slow){nums[slow] 0;}}
};但我们要移动0其实也可以直接进行位置的调换每当发现一个nums[fast]的值不为0我们就调换当前nums[slow]和nums[fast]的值(而不是把nums[fast]直接幅值给nums[slow])然后slow自增
class Solution {
public:void moveZeroes(vectorint nums) {int slow 0;for (int fast 0; fast nums.size(); fast){if (nums[fast] ! 0){swap(nums[slow], nums[fast]);}}}
};844. 比较含退格的字符串
要我们比较两个字符串包含退格后是否等两个字符串都定义快指针和慢指针
快指针原数组的索引这里是sfast和tfast慢指针退格后数组的索引这里是sslow和tslow
对两个字符串都进行快慢指针退格的时候slow指针自减因为我们要用到nums[slow]slow至少为0所以在slow为0的时候我们规定不自减。
class Solution {
public:bool backspaceCompare(string s, string t) {int sfast 0;int sslow 0;int tfast 0;int tslow 0;for (; sfast s.size(); sfast){if (s[sfast] ! #)s[sslow] s[sfast];else if (sslow ! 0)sslow --;}for (; tfast t.size(); tfast){if (t[tfast] ! #)t[tslow] t[tfast];else if (tslow ! 0)tslow --;}if (tslow ! sslow)return false;else{for (int i 0; i tslow; i){if (t[i] ! s[i])return false;}}return true;}
};增加元素类题目
1089. 复写零
要我们对输入的数组就地进行上述修改将该数组中出现的每个零都复写一遍并将其余的元素向右平移。
快指针原数组的索引这里是i慢指针复写零新数组的索引这里是j
按照题目要求如果原数组的元素arr[i]碰到0新数组的索引arr[j]要额外走一步直到新数组索引越界走出整个循环.
这时候要注意的是原数组多走了一步我们需要对原数组和新数组进行一步回退。
然后往回赋值逆序遍历循环继续进行的条件是原数组的索引i大于等于0如果新数组索引j没有越界就把arr[i]的值赋值给arr[j]如果arr[i]碰到0我们要判断当前索引j前面能不能再赋值有没有越界如果可以就把j自减并且arr[j]赋值为0接着索引i和j继续自减回退直到循环结束条件达到数组也就成功复写了零
class Solution {
public:void duplicateZeros(vectorint arr) {int len arr.size(); int i 0;int j 0;while (j len){if (arr[i] 0)j;i;j;}i--;j--;while (i 0){if (j len)arr[j] arr[i];if (arr[i] 0 j - 1 0){j--;arr[j] 0;}i--;j--;}}
};
