• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

LeetCode解题记录(双指针专题)

开发技术 开发技术 4小时前 1次浏览

1. 算法解释

双指针主要用于遍历数组,两个指针指向不同的元素,从而协同完成任务。也可以延伸到多个数组的多个指针。

若两个指针指向同一数组,遍历方向相同且不会相交,则也称为滑动窗口(两个指针包围的区域即为当前的窗口),经常用于区间搜索。

若两个指针指向同一数组,但是遍历方向相反,则可以用来进行搜索,待搜索的数组往往是排好序的。

对于 C++ 语言,指针还可以玩出很多新的花样。一些常见的关于指针的操作如下。

1.1 指针与常量

LeetCode解题记录(双指针专题)

1.2 指针函数与函数指针

static string Blog_Adress = "https://www.cnblogs.com/wanghongyang/"

// addition是指针函数,一个返回类型是指针的函数
int* addition(int a, int b) {
	int* sum = new int(a + b);
	return sum;
}
int subtraction(int a, int b) {
	return a - b;
}
// 这里第三个参数,接收函数指针
int operation(int x, int y, int (*func)(int, int)) {
	return (*func)(x, y);
}

int main() {
	// minus是函数指针,指向函数的指针
	int (*minus)(int, int) = subtraction;
	int* m = addition(1, 2);
	int n = operation(3, *m, minus);

	cout << "*m: " << *m << "   " << "n: " << n << endl;
	return 0;
}

函数指针,需要大家了解

运行结果为

LeetCode解题记录(双指针专题)

2. 两数之和

167. 两数之和 II – 输入有序数组

给定一个已按照 升序排列 的整数数组 numbers ,请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ,所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。

示例 1

输入:numbers = [2,7,11,15], target = 9
输出:[1,2]
解释:2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

示例 2

输入:numbers = [2,3,4], target = 6
输出:[1,3]

示例 3

输入:numbers = [-1,0], target = -1
输出:[1,2]

提示:

2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers 按 递增顺序 排列
-1000 <= target <= 1000
仅存在一个有效答案

题解

因为数组已经排好序,我们可以采用方向相反的双指针来寻找这两个数字,一个初始指向最小的元素,即数组最左边,向右遍历;一个初始指向最大的元素,即数组最右边,向左遍历

  • 如果两个指针指向元素的和等于给定值,那么它们就是我们要的结果。
  • 如果两个指针指向元素的和小于给定值,我们把左边的指针右移一位,使得当前的和增加一点。
  • 如果两个指针指向元素的和大于给定值,我们把右边的指针左移一位,使得当前的和减少一点。

证明

可以证明,对于排好序且有解的数组,双指针一定能遍历到最优解。证明方法如下:假设最

优解的两个数的位置分别是 lr。我们假设在左指针在 l 左边的时候,右指针已经移动到了 r

此时两个指针指向值的和小于给定值,因此左指针会一直右移直到到达 l。同理,如果我们假设

在右指针在 r 右边的时候,左指针已经移动到了 l;此时两个指针指向值的和大于给定值,因此

右指针会一直左移直到到达 r。所以双指针在任何时候都不可能处于 (l,r) 之间,又因为不满足条

件时指针必须移动一个,所以最终一定会收敛在 lr

代码

static string Blog_Adress = "https://www.cnblogs.com/wanghongyang/"
class Solution {
public:
	vector<int> twoSum(vector<int>& numbers, int target) {
		int l = 0, r = numbers.size() - 1, sum;

		while (l < r) {
			sum = numbers[l] + numbers[r];
			if (sum == target) {
				break;
			}
			if (sum < target) {
				++l;
			}
			else {
				--r;
			}
		}

		// 这里是因为题目要求下标从1开始
		return vector<int>{l + 1, r + 1};
	}
};

执行结果

LeetCode解题记录(双指针专题)

3. 合并两个有序数组

88. 合并两个有序数组

给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n,这样它就有足够的空间保存来自 nums2 的元素。

示例 1:

输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出:[1,2,2,3,5,6]

示例 2:

输入:nums1 = [1], m = 1, nums2 = [], n = 0
输出:[1]

提示:

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[i] <= 109

题解

因为这两个数组已经排好序,我们可以把两个指针分别放在两个数组的末尾,即 nums1 的 m − 1 位和 nums2 的 n − 1 位。每次将较大的那个数字复制到 nums1 的后边,然后向前移动一位。

因为我们也要定位 nums1 的末尾,所以我们还需要第三个指针,以便复制。

在以下的代码里,我们直接利用 mn 当作两个数组的指针,再额外创立一个 pos 指针,起始位置为 m +n−1。每次向前移动 mn 的时候,也要向前移动 pos。这里需要注意,如果 nums1的数字已经复制完,不要忘记把 nums2 的数字继续复制;如果 nums2 的数字已经复制完,剩余nums1 的数字不需要改变,因为它们已经被排好序。

注意 这里我们使用了

++ 和–的小技巧:a++ 和 ++a 都是将 a 加 1,但是 a++ 返回值为 a,而++a 返回值为 a+1。如果只是希望增加 a 的值,而不需要返回值,则推荐使用 ++a,其运行速度会略快一些。

代码

static string Blog_Adress = "https://www.cnblogs.com/wanghongyang/"
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        // 这里m--返回的是m,但是m实际上已经减小了
        int pos = m-- + n-- -1;

        while(m>=0&&n>=0){
            nums1[pos--] = nums1[m] > nums2[n]?nums1[m--]:nums2[n--];
        }
        while(n>=0){
            nums1[pos--] = nums2[n--];
        }

    }
};

执行结果

LeetCode解题记录(双指针专题)

4. 快慢指针

142. 环形链表 II

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意,pos 仅仅是用于标识环的情况,并不会作为参数传递到函数中。

说明:不允许修改给定的链表。

进阶:

你是否可以使用 O(1) 空间解决此题?

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

输入:head = [1,2], pos = 0c
输出:返回索引为 0 的链表节点
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

输入:head = [1], pos = -1
输出:返回 nullc
解释:链表中没有环。

提示:

链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105c
pos 的值为 -1 或者链表中的一个有效索引

题解

结论

对于链表找环路的问题,有一个通用的解法—─快慢指针(Floyd判圈法)。给定两个指针,分别命名为 slow和 fast,起始位置在链表的开头。每次fast 前进两步,slow前进一步。如果fast可以走到尽头,那么说明没有环路;如果fast 可以无限走下去,那么说明一定有环路,且一定存在一个时刻slow和fast相遇。当slow和 fast第一次相遇时,我们将fast重新移动到链表开头,并让 slow和fast每次都前进一步。当slow和 fast第二次相遇时,相遇的节点即为环路的开始点。

详解

 static string Blog_Adress = "https://www.cnblogs.com/wanghongyang/"
 
 原理:首先初始化快指针 fast = head.next.next 和 slow = head.next,
    此时快指针走的路长为2, m慢指针走的路长为1,之后令快指针每次走两步,
    慢指针每次走一步,这样快指针走的路长始终是慢指针走的路长的两倍,
    若不存在环,直接返回None,
    若存在环,则 fast 与 slow 肯定会在若干步之后相遇;
    
    性质1:
        设从head需要走 a 步到达环的入口,如果环存在的话,
        再走 b 步可以再次到达该入口(即环的长度为b),
        如果存在环的话,上述描述的 快指针 fast 和 
        慢指针slow 必然会相遇,且此时slow走的路长
        小于 a + b(可以自行证明),设其为 a + x,
        当快慢指针相遇时,快指针已经至少走完一圈环了,
        不妨设相遇时走了完整的m圈(m >= 1),有:
        
        快指针走的路长为 a + mb + x
        慢指针走的路长为 a + x
        
        由于快指针fast 走的路长始终是慢指针的 2倍,所以:
        
        a + mb + x = 2(a + x)
        
        化简可得:
        
        a = mb - x  -------------  (*)
    
    当快指针与慢指针相遇时,由于 <性质1> 的存在,
    可以在链表的开头初始化一个新的指针,
    称其为 detection, 此时 detection 距离环的入口的距离为 a,
    
    此时令 detection 和 fast 每次走一步,
    会发现当各自走了 a 步之后,两个指针同时到达了环的入口,理由分别如下:
    
    detection不用说了,走了a步肯定到刚好到入口
    fast已经走过的距离为 a + mb + x,当再走 a 步之后,
    fast走过的总距离为 2a + mb + x,带入性质1的(*)式可得:
    2a + mb + x = a + 2mb,会发现,fast此时刚好走完了
    整整 2m 圈环,正好处于入口的位置。
    
    基于此,我们可以进行循环,直到 detection 和 
    fast 指向同一个对象,此时指向的对象恰好为环的入口。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        // 1.判断是否有环
        if(head==NULL){
            return NULL;
        }
        // 创建两个快慢指针
        ListNode* fast = head;
        ListNode* slow = head;
        // 进行循环判断
        while(fast!=NULL && fast->next!=NULL){
            // fast走两步
            fast = fast->next->next;
            // slow走一步
            slow = slow->next;
            // 当fast=slow时,证明有环,跳出循环
            if(fast==slow){
                break;
            }
        }

        // 将无环的情况返回NULL
        if(fast==NULL||fast->next==NULL){
            return NULL;
        }


        // 如果有环,则将fast返回到头节点
        fast = head;
        while(fast!=slow){
            // fast与slow都一步一个节点
            fast = fast->next;
            slow = slow->next;
        }
        // 当fast与slow相遇时,则为入环的第一个节点
        return fast;

    }
};

还有一种写法

ListNode *detectCycle(ListNode *head) {
	ListNode *slow = head, *fast = head;
	// 判断是否存在环路
	do {
		if (!fast || !fast->next) return nullptr;
		fast = fast->next->next;
		slow = slow->next;
	} while (fast != slow);
	// 如果存在,查找环路节点
	fast = head;
	while (fast != slow){
		slow = slow->next;
		fast = fast->next;
	}
	return fast;
}

执行结果

LeetCode解题记录(双指针专题)

5. 平方数之和

633. 平方数之和

思路

两种方法

1)双指针

由于a,b两个数的范围在0到根号C之间,因此,我们用两个指针指向左边和右边

如果

  • 平方和大于c,则右边的指针减1
  • 平方和小于c,则左边的指针加1
  • 平方和等于c,则返回true

代码

class Solution {
public:
	bool judgeSquareSum(int c) {
		long r = 0, l = (int)sqrt(c), sum;
		while (r <= l) {
			sum = r * r + l * l;
			if (sum == c) {
				return true;
			}
			if (sum < c) {
				++r;
			}
			else {
				--l;
			}
		}
		return false;
	}
};

执行结果

LeetCode解题记录(双指针专题)

2)枚举法

简单来说就是先找一个数a,然后另外一个数就是根号下C-a*a,然后把这个数取整,计算平方和,等于c就返回true,否则返回false

下面放上官方的代码,很好理解

class Solution {
public:
    bool judgeSquareSum(int c) {
        for (long a = 0; a * a <= c; a++) {
            double b = sqrt(c - a * a);
            if (b == (int)b) {
                return true;
            }
        }
        return false;
    }
};


6. 验证回文字符串

680. 验证回文字符串 Ⅱ

题解

题目要求最多删一个字符,所以情况比较简单,我们可以用双指针把删除一个字符后出现的两种情况写出来就好。

双指针分别为head 和 tail。 head从左往右遍历,tail从右往左遍历。

遇到s[head] != s[tail]时,就分化为两种情况即

  • head = head + 1, tail = tail
  • head = head, tail = tail – 1
  • 分别从这两种情况进行判断即可,如果还有不等情况,那么就返回false。

代码

static string Blog_Adress = "https://www.cnblogs.com/wanghongyang/"
class Solution {
public:
    bool validPalindrome(string s) {
        if (s.empty() || s.size() == 1)
            return true;

        int length = s.size();
        int head = 0, tail = length - 1;

        while (head < tail) //正常双指针判断回文字符串
        {
            if (s[head] == s[tail])
            {
                ++head;
                --tail;
            }
            else
                break; //从分歧点退出
        }

        // 因为如果是正常退出,即head>=tail
        if (head >= tail) //如果是正常退出
            return true;

        //情况1
        int new_head = head + 1, new_tail = tail;
        int flag1 = true, flag2 = true;
        while (new_head < new_tail)
        {
            if (s[new_head] == s[new_tail])
            {
                ++new_head;
                --new_tail;
            }
            else
            {
                flag1 = false;
                break;
            }
        }

        //情况2
        new_head = head;
        new_tail = tail - 1;
        while (new_head < new_tail)
        {
            if (s[new_head] == s[new_tail])
            {
                ++new_head;
                --new_tail;
            }
            else
            {
                flag2 = false;
                break;
            }
        }

        //由于对两种情况进行遍历,所以只要有一种能满足回文,那就可以!
        return flag1 || flag2;
    }
};

执行结果

LeetCode解题记录(双指针专题)

7. 删除字母匹配到字典里最长单词

524. 通过删除字母匹配到字典里最长单词

参考链接

题解

双指针,但是在使用双指针前需要对被查找集合做排序

1,根据题目要求,先将dictionary的字符串按照字符串的长度从大到小排序,且字符串符合字典序,进行排序,目的是为了接下查找时,dictionary中第一个符合条件字符串的即为题目要求的答案。

2,定义并初始化,字符串s的长度s_len,dictionary的长度d_len,dictionary中字符串的长度ds_len,指向字符串s的指针s_ptr,指向dictionary中第i个字符串的指针ds_ptr。

3,for循环遍历dictionary中所以字符串,获取当前dictionary中第i个的字符串的长度

4,while循环使用双指针,比较字符串s是否包含当前第i个dictionary中的字符串,
如果包含,则d_ptr遍历到dictionary中第i个的字符串的末尾,即d_ptr == ds_len – 1,返回dictionary[i]即为答案,即返回长度最长且字典序最小的字符串。
如果不包含,则d_ptr未遍历到dictionary中第i个的字符串的末尾,且s_ptr遍历到字符串s的末尾

5,退出当前while循环,即将遍历dictionary中的第i+1个字符串,双指针归零为下一个while循环做准备

6,如果退出for循环,则表示答案不存在,则返回空字符串。

代码

class Solution {
public:
	string findLongestWord(string s, vector<string>& dictionary) {
		//字符串的长度从大到小排序,且字符串符合字典序
		auto cmp = [&](string& a, string& b)
		{
			if (a.size() == b.size()) {
				return a < b;
			}
			return a.size() > b.size();
		};

		sort(dictionary.begin(), dictionary.end(), cmp);

		int s_len = s.size(), d_len = dictionary.size(), ds_len = 0;
		int s_ptr = 0, d_ptr = 0;

		//双指针方法,遍历字典
		for (int i = 0; i < d_len; ++i)
		{
			ds_len = dictionary[i].size();   //当前字典的字符串的长度

			while (s_ptr < s_len && d_ptr < ds_len)
			{
				if (s[s_ptr] == dictionary[i][d_ptr])   //存在相等的字母
				{
					if (d_ptr == ds_len - 1)    //且已经到达当前字符串的末尾,即存在,因为已经排序,所以第一个符合条件的即为答案
					{
						return dictionary[i];
					}

					//当前字典的字符串的下一个字母
					++d_ptr;
				}
				//匹配被查找字符串的下一个字母
				++s_ptr;
			}

			//比较字典的下一个字符串,被查找字符串的s_ptr归零
			s_ptr = 0;
			//进行字典的下一个字符串比较,d_ptr归零
			d_ptr = 0;
		}

		return "";
	}
};

运行结果

LeetCode解题记录(双指针专题)

8. 总结

这个系列让我了解到双指针的一些题目场景,了解了双指针的使用,然后双指针的部分就到这里,下期开始写二分查找


程序员灯塔
转载请注明原文链接:LeetCode解题记录(双指针专题)
喜欢 (0)