双指针
🐛双指针🐛
转自：🔥【github】
- 19. 删除链表的倒数第N个节点
- 75.颜色分类
- 88.合并两个有序数组
- 167.两数之和II-输入有序数组
- 345.反转字符串中的元音字母
- 524.通过删除字母匹配到字典里最长单词
- 633.平方数之和
- 647.回文子串
- 680.验证回文字符串Ⅱ
- 5461.仅含1的子串数
删除链表的倒数第N个节点
leetcode给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
解题思路
- 使用快慢指针，让快指针提前先走n+1步，然后双指针再同时让前走，当快指针指到结尾时，慢指针指向要删除结点得前驱
- 为了让整个链表得删除操作都统一起来，所以加入了头节点
dummy,因为删除某个结点得操作需要它得前驱，而第一个结点没有前驱，所以加入头结点会更方便，删除操作与其他结点统一。 - 链表所谓删除结点，即前一个结点得next指针越过此结点，指向下一结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(-1);
dummy->next = head;
ListNode* slow = dummy;
ListNode* fast = dummy;
n++;
while (n--) {
fast = fast->next;
}
while (fast) {
slow = slow->next;
fast = fast->next;
}
slow->next = slow->next->next;
return dummy->next;
}
颜色分类
Leetcode给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
解题思路
- 一共三个指针，p0一直指向0的后一位，p2一直指向2的前一位，cur是用于遍历的指针。
- 本题属于荷兰旗帜问题：思想是遇到0就跟p0所指的数交换位置，遇到2就跟p2所指的数交换位置，遇到1就跳过。
- 注意：遇到2交换完位置后，cur指针不前进，因为要再次判断交换过来的数是0还是1。
- 注意2：while结束是
cur < p2而不是cur < nums.size()1
2
3
4
5
6
7
8
9void sortColors(vector<int>& nums) {
int p0 = 0, p2 = nums.size() - 1;
int cur = 0;
while (cur < p2) {
if (nums[cur] == 1) cur++;
else if (nums[cur] == 0) swap(nums[p0++], nums[cur++]);
else if (nums[cur] == 2) swap(nums[cur],nums[p2--]);
}
}
合并两个有序数组
leetcode给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
解题思路
- 合并有两种写法：while结束条件不同可分为写在while里和while外。
- 注意：数组的边界条件,对于链表指针
cur = NULL为结束，而数组是i = -1和i = size()为结束。 - 思路：从后往前插入num1，两个指针分别从后往前遍历两个数组，较大值插入num1中。
用&&与作为结束条件
- 意思是：当两个数组其中一个遍历结束时，结束while循环，所以还需要将另一个数组的剩余部分依次插入nums1。
1
2
3
4
5
6
7
8
9
10void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int p1 = m - 1, p2 = n - 1, cur = m + n - 1;
while ( p1 >= 0 && p2 >= 0){
nums1[cur--] = nums1[p1] > nums2[p2] ? nums1[p1--] : nums2[p2--];
}
if (p1 < 0) {
while (p2 >= 0)
nums1[cur--] = nums2[p2--];
}
}用||或作为结束条件
- 意思是，只要当两个数组全部遍历完后，才结束while循环，所以再循环体内就要考虑其中一个遍历结束后的操作。
1
2
3
4
5
6
7
8void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int p1 = m - 1, p2 = n - 1, cur = n + m - 1;
while(cur >= 0){
if (p1 < 0) nums1[cur--] = nums2[p2--];
else if (p2 < 0) nums1[cur--] = nums1[p1--];
else nums1[cur--] = nums1[p1] > nums2[p2] ? nums1[p1--] : nums2[p2--];
}
}
两数之和II-输入有序数组
Leetcode给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
解题思路
- 双指针相向遍历，
- 因为是有序数组，所以left指向小的数，right指向大的数，当两指针所指的数之和大于target，就前移right指针缩小大的数，当和小于target，就后移left指针，增大小的数。
1
2
3
4
5
6
7
8
9
10
11
12
13vector<int> twoSum(vector<int>& numbers, int target) {
int left = 0, right = numbers.size() - 1;
while (left < right) {
if (numbers[left] + numbers[right] == target){
return {left + 1, right + 1};
} else if (numbers[left] + numbers[right] < target) {
left++;
} else if (numbers[left] + numbers[right] > target) {
right--;
}
}
return {};
}
反转字符串中的元音字母
leetcode编写一个函数，以字符串作为输入，反转该字符串中的元音字母。
解题思路
- 首尾各一个指针，当都指向元音字母时，交换字符串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16bool isVolew(char ch){
if(ch=='a' || ch=='e'||ch=='i' || ch=='o'||ch=='u') return true;
if(ch=='A' || ch=='E'||ch=='I' || ch=='O'||ch=='U') return true;
return false;
}
string reverseVowels(string s) {
int left=0, right=s.size() - 1;
while (left < right) {
if (!isVolew(s[left])) ++left;
if (!isVolew(s[right])) --right;
if (isVolew(s[left]) && isVolew(s[right])) {
swap(s[left++], s[right--]);
}
}
return s;
}
通过删除字母匹配到字典里最长单词
leetcode给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。
示例
1 | |
解题思路
- 核心时判断一个字符串是不是另一个字符串的子序列，注意这里是子序列而不是子串，子序列是指每个字母在母串中的前后顺序不变。
- 使用双指针判断子序列，2各指针指向两个串，相同字母时指针后移，不同字母时只有母串指针后移，直到结束，看另一个指针是否指向结尾。
- 根据题意，要寻找最长的，所以一定要有一个变量储存当前最长值，然后不断进行比较。
- compare()函数可以根据字典顺序比较，<0表示字典顺序在前
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22string findLongestWord(string s, vector<string>& d) {
string longest = "";
for(int i = 0; i < d.size(); ++i){
if(d[i].size() < longest.size()) continue;
if(d[i].size() == longest.size() && longest.compare(d[i]) < 0) continue;
if(isSub(s, d[i])) longest = d[i];
}
return longest;
}
bool isSub(string s,string d){
int i=0, j=0;
while(i < s.size() && j < d.size()){
if(s[i] == d[j]){
i++;
j++;
}else{
i++;
}
}
return j == d.size();
}
平方数之和
Leetcode给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c。
解题思路
- a,b可以为0，所以左指针从0开始而不是1，右指针sqrt(c)开始,效率高。
- 因为a和b可能是同一个数，所以while里的l可以=r。
- 考虑s可能溢出，所以用r使用long型。
为什么防止s溢出要将r设置为long型：
- 问题在于计算过程中溢出了，计算式完全是以int运算来执行的，并且只有在运算完成之后，其结果才被提升为 long，而此时已经太迟：计算已经溢出。
- 解决方法使计算表达式的其中一个因子明确为long型，这样可以强制表达式中所有的后续计算都用long运算来完成，防止溢出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15bool judgeSquareSum(int c) {
int left = 0;
long right = sqrt(c);
while (left <= right) {
int sum = left * left + right * right;
if (sum < c) {
left++;
} else if (sum > c) {
right--;
} else if (sum == c){
return true;
}
}
return false;
}回文子串
Leetcode给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。示例
1
2
3输入: "aaa"
输出: 6
说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".解题思路
- 双指针应用：中心扩展
- 回文串特性：对称相同
- 回文串：奇数个数和偶数个数，因此有两种扩展：当前字符向两边扩展笔记，当前字符和下一个字符向两边扩展比较。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15int countSubstrings(string s) {
int cnt = 0;
for (int i = 0; s[i] != '\0'; ++i){
expand(s, i, i+1, cnt);
expand(s, i, i, cnt);
}
return cnt;
}
void expand(string s,int left,int right,int& cnt){
while (left >= 0 && right < s.size() && s[left] == s[right]){
left--;
right++;
cnt++;
}
}
680.验证回文字符串Ⅱ
Leetcode
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
解题思路
- 传统思路：遍历每个结点，判断剩余结点能否形成回文，时间复杂度O(n^2)
- 因为回文对称相等，所以从两头开始遍历，当遇到不相同时，再删除其中一个再进行判断
- 优化：一开始就是从两头遍历的，所以已经遍历过的地方一定是相等，所以在
isPalindrome()函数中不用从两头再重复遍历1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17bool validPalindrome(string s) {
int left = 0,right = s.size() - 1;
while (left < right) {
if (s[left] != s[right])
return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
left++; right--;
}
return true;
}
bool isPalindrome(string s,int left,int right){
while (left < right) {
if (s[left] != s[right]) return false;
left++;
right--;
}
return true;
}
仅含 1 的子串数
leetcode
给你一个二进制字符串 s（仅由 ‘0’ 和 ‘1’ 组成的字符串）。
返回所有字符都为 1 的子字符串的数目。
由于答案可能很大，请你将它对 10^9 + 7 取模后返回。
示例
1 | |
解题思路
- 刚开始想到用双指针，类似于滑动窗口的思想，每次窗口把连续的1框住，计算窗口中最大子串数。
- 滑动窗口思想，左右指针从0开始，先移动右指针，当右指针达到要求后，再移动左子针，直到左指针也满足一定要求，最后处理中间的字符，处理完继续移动右指针。
- 这里右指针的要求指向连续1的最后一位，即当
right指向1，而right+1指向0,然后开始移动左子针，直到做指针指向第一个1停，至此形成一个窗口，处理结束后记得更新左指针。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16int numSub(string s) {
int left = 0, right = 0;
long res = 0;
while (right + 1 <= s.size()) {
if (s[right] == '1' && s[right + 1] == '0' ||
s[right] == '1' && s[right + 1] == '\0') {
while (s[left] == '0') left++;
long len = right - left + 1;
res += (1 + len ) * len / 2;
res %= 1000000007;
left = right + 1;
}
right++;
}
return res;
} - 如果仔细发现当中的规律，1个1有1个子串，2个连续的有3个子串，3个连续的1有6个子串，n个连续的1有
1 + 2 + 3+...+n)个子串,即连续1每当增加一个1就会多加len(1)个子串。1
2
3
4
5
6
7
8
9
10
11
12
13int numSub(string s) {
int res = 0, len = 0;
for (auto& ch : s) {
if (ch == '1') {
len++;
res += len;
res %= 1000000007;
} else {
len = 0;
}
}
return res;
}
