leetcode 双指针算法专题

Albert_xiong

发布于 2021-06-21 17:56:03

5190

发布于 2021-06-21 17:56:03

一、什么叫做双指针算法？

双指针是一种方法，一种思想一种技巧，也谈不上什么特别的算法，在二分查找中经常使用这个技巧，具体就是用两个变量动态的存储两个或者多个的结点，来方便我们进行一些操作，通常使用在线性结构中，比如说数组或者是链表。在我们遇到像数组，链表这类数据结构的算法题目的时候，应该要想得到双指针的来解决问题。特别是链表类的题目，经常需要用到两个或多个指针配合来记忆链表上的节点，完成某些操作。链表这种数据结构也是树形结构和图的原型，所以有时候在关于图和树形结构的算法题目中也会用到双指针。

1、快慢指针

1）计算链表的中点：快慢指针从头节点出发，每轮迭代中，快指针向前移动两个节点，慢指针向前移动一个节点，最终当快指针到达终点的时候，慢指针刚好在中间的节点。 2）判断链表是否有环：如果链表中存在环，则在链表上不断前进的指针会一直在环里绕圈子，且不能知道链表是否有环。使用快慢指针，当链表中存在环时，两个指针最终会在环中相遇。 3）判断链表中环的起点：当我们判断出链表中存在环，并且知道了两个指针相遇的节点，我们可以让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。 4）求链表中环的长度：只要相遇后一个不动，另一个前进直到相遇算一下走了多少步就好了 5）求链表倒数第k个元素：先让其中一个指针向前走k步，接着两个指针以同样的速度一起向前进，直到前面的指针走到尽头了，则后面的指针即为倒数第k个元素。（严格来说应该叫先后指针而非快慢指针）

2、碰撞指针

一般都是排好序的数组，否则无序的话这两个指针的位置也没有什么意义。特别注意两个指针的循环条件在循环体中的变化，小心右指针跑到左指针左边去了。常用来解决的问题有

1）加粗样式二分查找问题 2）n数之和问题：比如两数之和问题，先对数组排序然后左右指针找到满足条件的两个数。如果是三数问题就转化为一个数和另外两个数的两数问题。以此类推。 3）反转数组

3、滑动窗口法

两个指针，一前一后组成滑动窗口，并计算滑动窗口中的元素的问题。

这类问题一般包括 1）字符串匹配问题 2）子数组问题

二、具体相关leetcode习题

1) leetcode 1. 两数之和

这个题目比较简单，不需要用到双指针，一般在用双指针的时候，需要有序数组，先排序。这题目有几种思路，首先我想到的就是利用暴力方法，直接算。看代码：

嵌套循环 -> 第二层为什么是i+1开始呢？因为比如说题目中的例子（0号位置和1号位置分别是2和7相加等于9满足条件，那么从i=1开始遍历的时候，j就不能从0开始了，不然就重复了，所以从i的下一位开始遍历）

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if nums[i]+nums[j]==target:
                    return i,j

双指针的方法如下： 首先对这个数组先进行一次拷贝然后对拷贝的数组进行排序定义两个指针，一个指向首部，一个指向尾部现在就开始利用双指针的方法对该数组进行遍历，条件是（i<j）如果找到了两个数字加上等于 target的值的就结束while循环下一步就是对找到的这个数字对他在原数组也就是nums里面进行索引值的查找最后返回找到的这两个数字在原数组中的索引

在这里要注意的一点就是想要利用双指针进行遍历前提是对这个数组进行排序 python中的sort（）方法

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        temp=nums.copy()
        temp.sort()
        i=0
        j=len(nums)-1
        while i<j:
            if (temp[i]+temp[j])>target:
                j=j-1
            elif (temp[i]+temp[j])<target:
                i=i+1
            else:
                break
        p=nums.index(temp[i])
        print(nums.pop(p))
        k=nums.index(temp[j])
        if k>=p:
            k=k+1
        return [p,k]

2）leetcode 167. 两数之和 II - 输入有序数组

这个题目和leetcode 1 略微有点不同，这题给你的条件就是这个数组就是已经排序了的数组，所以对于原数组，不需要进行排序，也就是说对原来的数组不需要跟leetcode 1一样，先进行数组的拷贝，在进行排序，算法思路如下：其实代码也比较好理解，这里就不解释了…依旧是双指针，首尾往中间遍历

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        if not numbers:
            return []

        #利用双指针
        #首指针
        i = 0
        high = len(numbers)-1 

        #开始进行循环
        while i<=high:
           
            if numbers[i] + numbers[high] == target:
                return [i+1,high+1]
            if numbers[i] + numbers[high] > target:
                high-=1
            if numbers[i] + numbers[high] < target:
                i +=1
    
        return[-1,-1]

3）leetcode 633. 平方数之和

对于这道题，依旧是利用双指针的方法去结题，观察题目，问你是否存在两个数等于某个定值，和上一道题相比，也类似，只是这道题多了平方。定义首尾指针，往中间靠拢，尾部的数字最好是定义为c的开根号，如果为c的开根号，那么正好等于和正好等于c嘛！然后就是类似于上两题的双指针遍历了啊

class Solution(object):
    def judgeSquareSum(self, c):
        """
        :type c: int
        :rtype: bool
        """
        i  = 0
        j  = int(c**0.5)

        while i<=j:
            if i**2+j**2==c:  
                return True
            if i**2+j**2>c:
                j-=1
            if i**2+j**2<c:
                i+=1
        return False

4）leetcode 26. 删除排序数组中的重复项

这个b站的视频我觉得讲的很形象，看后面的即可

这里用到了先后指针，和快慢指针区别开来（容易混淆）用一段动画解释这个算法吧…哈哈哈 1、起初，爸爸和儿子都在起点上，爸爸先走一步…让儿子拿着篮子在原地先等候…

2、老爸向前走一步，发现和第一次一样，又是草莓，就没搭理继续向前走

3、现在找到的是哈密瓜，诶，和之前的不一样了，让儿子向前走一步，把哈密瓜给了儿子…

4、老爸又向前走一步，是哈密瓜和之前的一样，没有捡，再往前一步，还是哈密瓜，还是不敢捡，那就再走一步… 5、老爸继续往前走，看到了西瓜，心里乐开花，赶紧让儿子向前一步，把西瓜给了儿子…

以下是代码部分：

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        #运用快慢指针
        slow = 0
        for i in range(1,len(nums)):
            if nums[slow] != nums[i]:
                slow+=1
                nums[slow]=nums[i]
        return slow+1

5）leetcode 345. 反转字符串中的元音字母

一开始看到这个题目的时候，题目其实我都没看懂，其实也就是意思说从前面走，从后面走，只要遇到了元音字母就将这两个字母调换，题目还考虑了一个隐含的条件，那就是大写字母不要忘记啦！！ 还要注意的就是python中一些特定的API函数的用法…

代码解释：先将字符串转成列表定义首尾指针进行遍历最后一个API函数："".join(string) 将列表转成字符串

class Solution(object):
    def reverseVowels(self, s):
        """
        :type s: str
        :rtype: str
        """

        if (len(s)==0):
            return ""
        if (len(s)==1):
            return s
        yuanyin = "aeiou"
        string = list(s)
        # print(string)

        i = 0
        j = len(string)-1
        while i<j:
            if string[i].lower() not in yuanyin:
                i+=1
            if string[j].lower() not in yuanyin:
                j-=1
            if string[i].lower() in yuanyin and string[j].lower() in yuanyin:
                string[i],string[j] = string[j],string[i]
                i+=1
                j-=1
        return "".join(string)

6）leetcode 125. 验证回文串

这个题目，只考虑字母和数字字符，要求我们要知道一个API函数 isalnum() 返回值是True 或者 False

我的思路是先将这个字符串转成纯数字或者字母的形式： result = "".join(ch.lower() for ch in s if ch.isalnum()) 再利用双指针收尾进行遍历其中lower()是将大写字母转成小写当遍历当两个指针对应的位置，不相等时，直接返回False ,如果相等，首指针加一，尾指针减一，继续判断条件，直到循环结束…这一题还是比较简单的

import re
class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """

        if(len(s)==0):
            return True
        if(len(s)==1):
            return True
        result = "".join(ch.lower() for ch in s if ch.isalnum())
        # print(result)
        # List = list(result)
        # print(List)
        i = 0
        j = len(result) - 1
        print(j)

        while i<j:
            if result[i].lower() != result[j].lower():
                return False
            i+=1
            j-=1
        return True

7）leetcode 680. 验证回文字符串 Ⅱ

这个题目相比于上一道题难度要大一点，因为要判断改字符串是不是回文字符串，如果不是，删掉一个字符还是不是回文字符串，如果是，那就是，哈哈哈…

其实看了代码思路也比较简单了，先写一个函数判断这个字符串是不是回文字符串check(left, right) 双指针进行首尾遍历，如果相等，首指针加一，尾指针减一，继续判断如果不相等，将首指针加一，尾指针不变或者首指针不变，尾指针减一，来进行判断 check(left + 1, right) or check(left, right - 1)

class Solution(object):
    def validPalindrome(self, s):
        def check(left, right):
            # 判断是否是回文数
            while left < right:
                if s[left] != s[right]:
                    return False
                left += 1
                right -= 1
            return True
        
        # 定义指针，一个指向开始，一个指向末尾
        left, right = 0, len(s) - 1
        while left < right:
            # 指针所对应的字符相同时，指针往中间移动
            if s[left] == s[right]:
                left += 1
                right -= 1
            # 指针所对应的字符不同，考虑删除一个字符
            # 1. 删除当前左指针的字符，移动至后一位
            # 2. 删除当前右指针的字符，移动至前一位
            # 重新判断删除字符后，字符串是否是回文字符串
            else:
                return check(left + 1, right) or check(left, right - 1)
        return True

8）leetcode 88. 合并两个有序数组

反正其中有一种方法很简答，一行代码搞定…

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None Do not return anything, modify nums1 in-place instead.
        """
        nums1[:] = sorted(nums1[:m]+nums2)

这种方法就是：先创建一个空的列表然后一个指针对nums1进行遍历一个指针对nums2进行遍历，去比较他们的大小谁小，谁就放到temp中，然后指针记得移位置如果nums1已经遍历完了，那么就把nums2的元素append进temp中如果nums2已经遍历完了，那么就把nums1的元素append进temp中最后将temp数组赋值给 nums1数组

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None Do not return anything, modify nums1 in-place instead.
        """
        temp = []
        # print(temp)
        p1 = 0
        p2 = 0

        while p1 <m and p2 <n:
            if nums1[p1]<nums2[p2]:
                temp.append(nums1[p1])
                p1+=1
            else:
                temp.append(nums2[p2])
                p2+=1
        while p1<m:
            temp.append(nums1[p1])
            p1+=1
        while p2<n:
            temp.append(nums2[p2])
            p2+=1
        nums1[:] = temp[:]

9）leetcode 977. 有序数组的平方

创建一个全为0长度为n的列表双指针进行首尾遍历如果前面的平方大于后面的平方，那么就把前面的值加入到创建的列表中，然后这个数字较大的指针加一，以此类推

class Solution(object):
    def sortedSquares(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """

        #用双指针的做法
        #定义一个空的列表
        n = len(nums)
        temp = [0]*n
        
        #双指针
        i,j,pos = 0,n-1,n-1
        while i<=j and pos >=0:
            if nums[i]*nums[i] > nums[j]*nums[j]:
                temp[pos] = nums[i]*nums[i]
                i+=1
            else:
                temp[pos] = nums[j]*nums[j]
                j-=1
            pos-=1
        return temp

10） leetcode 141. 环形链表

这个时候就用到了快慢指针的方法，一个指针走一格，另一个指针走两格，如果两个指针相等，那么证明一定有环！

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:

        #依然是快慢指针的解法
        fast , slow = head , head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True 
        return False

11）leetcode 142. 环形链表 II

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        slow,fast = head,head

        while True:

            #如果列表的尾部会为空
            if not (fast and fast.next):
                return 
            slow = slow.next
            fast = fast.next.next

            if fast == slow:
                break
        
        fast = head
        while fast!=slow:
            slow = slow.next
            fast = fast.next
        return fast

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-12-18 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度