双指针法的一些应用

目录

移除元素

反转字符串

替换数字

反转字符串里的单词

翻转链表

删除链表的倒数第N个结点

链表相交

环形链表Ⅱ

三数之和

四数之和

总结

字符串

链表

N数之和

---

移除元素

题目：给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

• 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
• 返回 k。

具体代码：

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow = 0, fast = 0;
        for(; fast < nums.size(); fast++) {
            if(nums[fast] == val) {
                continue;
            } else {
                nums[slow++] = nums[fast];
            }
        }
        return slow;//返回的是数组大小
    }
};

反转字符串

题目：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

具体代码：

class Solution {
public:
    void reverseString(vector<char>& s) {
        for(int i = 0, j = s.size() - 1; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }
};

替换数字

题目：给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。 例如，对于输入字符串 "a1b2c3"，函数应该将其转换为 "anumberbnumbercnumber"。

具体代码：

#include
using namespace std;
 
class solution{
public:
  void replaceDigit(string& s) {
      int oldLen = s.size();
      int count = 0;
      for(int i = 0; i < oldLen; i++) {
          if(s[i] >= '0' && s[i] <= '9') {
              count++; //记录数字出现的次数
          }
      }
      s.resize(oldLen + count * 5);//number虽然有6位，但是原来的数组中有一位
      int newLen = s.size();
      for(int i = oldLen - 1, j = newLen - 1; i < j; i--, j--) {
          if(s[i] <'0' || s[i] > '9') {
              s[j] = s[i];
          } else {
              s[j] = 'r';
              s[j - 1] = 'e';
              s[j - 2] = 'b';
              s[j - 3] = 'm';
              s[j - 4] = 'u';
              s[j - 5] = 'n';
              j -= 5;
          }
      }
  }  
};
int main() {
    solution sol;
    string s;
    while(cin>>s) {
        sol.replaceDigit(s);
        cout<
    }
}

反转字符串里的单词

题目：给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

具体代码：

class Solution {
public:
    void removeExtraSpaces(string& s){
        int slow = 0, fast = 0;
        while(s.size() > 0 && fast < s.size() && s[fast] == ' ') {
            fast++;
        }  
        for(; fast < s.size(); fast++) {
            if(fast - 1 > 0 && s[fast] ==  s[fast - 1] && s[fast] == ' ') {
                continue;
            }
            s[slow++] = s[fast];
        }
        if(slow - 1 > 0 && s[slow - 1] == ' ') {
            s.resize(slow - 1);
        } else {
            s.resize(slow);
        }
    }
 
    void reverse(string& s, int start, int end) {
        for(int i = start, j = end; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }
 
    string reverseWords(string s) {
        removeExtraSpaces(s);
        reverse(s, 0, s.size() - 1);
        bool entry = false;
        int start = 0, end = s.size() - 1;
        for(int i = 0; i < s.size(); i++) {
            if((i > 0 && s[i] != ' ' && s[i - 1] == ' ' ) || (!entry)){
                entry = true;
                start = i;
            } 
             if(entry && s[i] == ' ' && s[i - 1] != ' ') {
                entry = false;
                end = i - 1;
                reverse(s, start, end);
            }
            if(entry && i == s.size() - 1) {
                entry =false;
                end = i;
                reverse(s, start, end);
            }
        }
        return s;
    }
};

翻转链表

题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

具体代码：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = NULL;
        ListNode* cur = head;
        while(cur != NULL) {
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};

删除链表的倒数第N个结点

题目：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

具体代码：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0);
        ListNode* fast = dummyHead;
        ListNode* slow = dummyHead;
        dummyHead->next = head;
        while(n-- && fast != NULL) {
            fast = fast->next;
        }
        fast = fast->next;
        while(fast != NULL) {
            fast = fast->next;
            slow = slow->next;
        }
        ListNode* tmp = slow->next;
        slow->next = slow->next->next;
        delete tmp;
        ListNode* result = dummyHead->next;
        delete dummyHead;
        return result;
    }
};

链表相交

题目：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

具体代码：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA = headA;
        ListNode* curB = headB;
        int lenA = 0;
        int lenB = 0;
        while(curA != NULL) {
            curA = curA->next;
            lenA++;
        }
        while(curB != NULL) {
            curB = curB->next;
            lenB++;
        }
        curA = headA;
        curB = headB;
        if(lenB > lenA) {
            swap(lenA, lenB);
            swap(curA, curB);
        }
        int n = lenA - lenB;
        while(n-- && curA != NULL) {
            curA = curA->next;
        }
        while(curA != NULL) {
            if(curA == curB) {
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
        return NULL;
    }
};

环形链表Ⅱ

题目：给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

具体代码：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) {
                ListNode* index1 = fast;
                ListNode* index2 = head;
                while(index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index1;
            }
        }
        return NULL;
    }
};

三数之和

题目：给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

具体代码：

class Solution {
public:
    vectorint>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vectorint>> result;
        int n = nums.size();
        for(int i = 0; i < nums.size(); i++) {
            if(nums[0] > 0) {
                return result;
            }
            if(i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = n - 1;
            while(left < right) {
                if(nums[i] + nums[left] + nums[right] > 0) {
                    right--;
                } else if(nums[i] + nums[left] + nums[right] < 0) {
                    left++;
                } else {
                    result.push_back({nums[i], nums[left], nums[right]});
                    while(left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while(left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    right--;
                    left++;
                }
            }
        }
        return result;
    }
};

四数之和

题目：给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）

具体代码：

class Solution {
public:
    vectorint>> fourSum(vector<int>& nums, int target) {
        int n = nums.size();
        vectorint>> result;
        sort(nums.begin(), nums.end());
 
        for(int k = 0; k < n; k++) {
            if(target >= 0 && nums[k] > target) {
                return result;
            }
            if(k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for(int i = k + 1; i < n; i++) {
                if(target >= 0 && nums[k] + nums[i] > target) {
                    break;
                }
                if(i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int left = i + 1;
                int right = n - 1;
                while(left < right) {
                    if((long)nums[k] + nums[i] + nums[left] + nums[right] > target) {//可能超出int能表示的数的范围，所以转换为long类型
                        right--;
                    } else if((long)nums[k] + nums[i] + nums[left] + nums[right] < target) {
                        left++;
                    } else {
                        result.push_back({nums[k], nums[i], nums[left], nums[right]});
                        while(left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        while(left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        left++;
                        right--;
                    }
                }
            }
        }
        return result;
    }
};

总结

双指针法并不隶属于某一种数据结构，在数组，链表，字符串都用到了双指针法。

双指针法的关键优势在于在一个for循环下可以使用两个指针完成两个for循环的事情。

字符串

• 在反转字符串中，使用双指针法，定义两个指针（也可以说是索引下标），一个从字符串前面，一个从字符串后面，两个指针同时向中间移动，并交换元素。时间复杂度是O(n)。
• 在替换数字中介绍使用双指针填充字符串的方法，思路就是首先扩充数组到每个数字替换成"number"之后的大小。然后双指针从后向前替换数字。为什么要从后向前填充，从前向后填充不行么？从前向后填充就是O(n^2)的算法了，因为每次添加元素都要将添加元素之后的所有元素向后移动。其实很多数组（字符串）填充类的问题，都可以先预先给数组扩容成带填充后的大小，然后再从后向前进行操作。

• 在反转字符串里的单词中，使用双指针法，用O(n)的时间复杂度完成字符串删除类的操作，因为题目要删除冗余空格。在删除冗余空格的过程中，如果不注意代码效率，很容易写成了O(n^2)的时间复杂度。其实使用双指针法O(n)就可以搞定。主要还是用erase用的比较随意，一定要注意for循环下用erase的情况，一般可以用双指针写效率更高！

链表

• 在翻转链表中，只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表。
• 在链表中求环，是双指针在链表里最经典的应用，在环形链表中讲解了如何通过双指针判断是否有环，而且还要找到环的入口。使用快慢指针（双指针法），分别定义 fast 和 slow指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。那么找到环的入口，只要再进行一些简单的数学推理即可。

N数之和

• 哈希法可以解决两数之和的问题，但是哈希法并不适用于三数之和！因此可以使用双指针法提高解题效率。四数之和，其实思路是一样的，在三数之和的基础上再套一层for循环，依然使用双指针法。对于三数之和使用双指针法就是将原本暴力O(n^3)的解法，降为O(n^2)的解法，四数之和的双指针解法就是将原本暴力O(n^4)的解法，降为O(n^3)的解法。五数之和同理。

除了链表一些题目一定要使用双指针，其他题目都是使用双指针来提高效率，一般是将O(n^2)的时间复杂度，降为 O(n)