概述
原地移除给定元素
方法一：
循环遍历数组
当查到到需要移除的元素时，与当前数组的最后一个元素进行交换，并且令数组长度减1（减1即让数组减少元素）， 此时注意不能继续遍历（即不能i++），因为可能换过来的元素也是需要移除的元素，所以需要继续判断。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int n = nums.size();//n为移除元素后的数组长度
for(int i = 0; i < n;){
if(nums[i] == val){
nums[i] = nums[n-1];//与最后一个元素交换
n--;//数组长度减1
}
else{
i++;//当没有移除时，指针才后移
}
}
return n;
}
};方法二：
快慢指针
快指针 fast指向当前将要处理的元素，慢指针 slow指向下一个将要赋值的位置。
- 如果快指针指向的元素不等于 val，它一定是输出数组的一个元素，我们就将快指针指向的元素复制到慢指针位置，然后将快慢指针同时右移；
- 如果快指针指向的元素等于 val，它不能在输出数组里，此时慢指针不动，快指针右移一位。
快指针用于遍历数组，所以每循环一次，都需要后移一位。慢指针用于记录需要保存下来的元素。只有当进行复制操作时，才后移一位。整个过程保持不变的性质是：区间 [0,slow)中的元素都不等于 val。当快慢指针遍历完输入数组以后，slow的值就是输出数组的长度。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slowIndex = 0;
for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
if (val != nums[fastIndex]) {
nums[slowIndex++] = nums[fastIndex];
}
}
return slowIndex;
}
};原地删除重复元素
快指针 fast指向当前将要处理的元素，慢指针 slow指向下一个将要赋值的位置。
- 如果快指针指向的元素不等于它的前一个元素，它一定是输出数组的一个元素，我们就将快指针指向的元素复制到慢指针位置，然后将快慢指针同时右移；
- 如果快指针指向的元素等于它前一个元素，则为重复元素，它不能在输出数组里，此时慢指针不动，快指针右移一位。
快指针用于遍历数组，所以每循环一次，都需要后移一位。慢指针用于记录需要保存下来的元素。只有当进行复制操作时，才后移一位。整个过程保持不变的性质是：区间 [0,slow)中的元素都不等于 val。当快慢指针遍历完输入数组以后，slow的值就是输出数组的长度。
当数组 nums的长度大于 0时，数组中至少包含一个元素，在删除重复元素之后也至少剩下一个元素，因此 nums[0]保持原状即可，从下标 1开始删除重复元素。
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return 0;
}
int slow = 1;
for(int fast = 1;fast < n; fast++) {
if (nums[fast] != nums[fast - 1]) {//重复元素必定是连续的
nums[slow++] = nums[fast];
}
}
return slow;
}
};
移动的0
快指针 fast指向当前将要处理的元素，慢指针 slow指向下一个将要赋值的位置。
- 如果快指针指向的元素不等于0，我们就将快指针指向的元素复制到慢指针位置，然后将快慢指针同时右移；
- 如果快指针指向的元素等于0，此时慢指针不动，快指针右移一位。
快指针用于遍历数组，所以每循环一次，都需要后移一位。慢指针用于记录需要保存下来的元素。只有当进行复制操作时，才后移一位。当快慢指针遍历完输入数组以后，0到slow的元素就是数组中非0元素。再将下标为slow到数组长度的元素改为0即可。
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int slow = 0;
int n = nums.size();
for(int fast = 0;fast < n; fast++){
if(nums[fast] != 0){
nums[slow++] = nums[fast];
}
}
for(int i = slow; i < n; i++) nums[i] = 0;
}
};使用双指针，左指针指向下一个要赋值的地方，右指针指向下一个待处理的地方。
右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。
- 当右指针指向非0的元素时，与左指针指向的元素位置进行互换。左右指针同时向右移动。
- 当右指针指向0元素时，左指针不动，右指针向右移动。
左指针左边均为非零数； 右指针左边直到左指针处均为零。因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size(), left = 0;
for(int right = 0;right < n; right++) {
if (nums[right]) {
swap(nums[left], nums[right]);
left++;
}
}
}
};844. 比较含退格的字符串
一个字符是否会被删掉，取决于该字符后面的退格符。如果从前开始遍历，无法知道退格符何时出现，也就无法确认当前字符是否需要比较，因此应逆序地遍历字符串，就可以立即确定字符是否会被删掉。
定义 skip表示当前待删除的字符的数量。每次我们遍历到一个字符：
- 若该字符为退格符，则需要多删除一个普通字符，skip++；
- 若该字符为普通字符：
若 skip为 0，则说明当前字符不需要删去；
若 skip不为 0，则说明当前字符需要删去， skip--。
定义两个指针，分别指向两字符串的末尾。让两个指针分别找到对应字符串需要进行比较的字符，然后将这两个字符进行比较。重复这一过程直到找到的两个字符不相等，或遍历完其中任一字符串为止。
class Solution {
public:
bool backspaceCompare(string S, string T) {
int i = S.length() - 1, j = T.length() - 1;//从后面开始遍历
int skipS = 0, skipT = 0;//记录当前遇到的#的个数
while (i >= 0 || j >= 0) {
while (i >= 0) {
if (S[i] == '#') {//如果遇到的是#
skipS++, i--;
} else if (skipS > 0) {//如果遇到的是字母且之前遇到过#
skipS--, i--;
} else {//如果当前遇到的是字母且没有累计的#
break;
}
}//找到第一个需要比较的字符
while (j >= 0) {
if (T[j] == '#') {
skipT++, j--;
} else if (skipT > 0) {
skipT--, j--;
} else {
break;
}
}//同理
//如果i和j都没结束遍历
if (i >= 0 && j >= 0) {
if (S[i] != T[j]) {
return false;//有一个不相等的字符则直接返回false
}
} else {
//如果i和j其中有一个结束了遍历，则直接返回false
if (i >= 0 || j >= 0) {
return false;
}
}
i--, j--;
}
return true;
}
};977. 有序数组的平方
我们可以使用两个指针分别指向位置 0 和 n−1，每次比较两个指针对应的数，选择平方后较大的元素放入pos所指的位置。pos下一个确定元素的位置。
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n);
int i = 0, j = n - 1;
for (int pos = n - 1; i <= j; pos--) {
if (nums[i] * nums[i] > nums[j] * nums[j]) {
ans[pos] = nums[i] * nums[i];//取i和j所指位置元素的平方中最大的那个
++i;
}
else {
ans[pos] = nums[j] * nums[j];
--j;
}
}
return ans;
}
};最后
以上就是过时魔镜为你收集整理的双指针应用的全部内容，希望文章能够帮你解决双指针应用所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复