专栏首页Mybatis学习leetcode 双指针算法专题

leetcode 双指针算法专题

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

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

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode-算法-双指针-第17天

    存在一个按升序排列的链表,给你这个链表的头节点 head ,请你删除链表中所有存在数字重复情况的节点,只保留原始链表中 没有重复出现 的数字。返回同样按升序排列...

    布衣者
  • LeetCode-算法-双指针-第5天

    给定一个头结点为 head 的非空单链表,返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。 具体题目链接

    布衣者
  • LeetCode-算法-双指针-第4天

    编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。 不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O...

    布衣者
  • LeetCode-算法-双指针-第3天

    给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 示例:

    布衣者
  • LeetCode-算法-双指针-第2天

    给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。 请你设计时间复杂度为 O(n) 的算法解决本...

    布衣者
  • LeetCode-算法-双指针-第18天

    给定 S 和 T 两个字符串,当它们分别被输入到空白的文本编辑器后,判断二者是否相等,并返回结果。 # 代表退格字符。注意:如果对空文本输入退格字符,文本继续为...

    布衣者
  • LeetCode-双指针

    使用双指针,一个指针指向值较小的元素,一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历,指向较大元素的指针从尾向头遍历。

    LittlePanger
  • 算法一招鲜——双指针问题

    本文首发于知乎专栏——前端面试题汇总,大家可以通过文章底部的阅读原来来访问原文地址

    用户1687375
  • LeetCode 系列——双指针问题 。

    关于 LeetCode 系列有段时间没有逐题更新了 ,还是想到一题一题的刷有些凌乱 。如前段时间的推文所说 ,准备系统的讲讲数据结构相关知识点 。

    小小詹同学
  • 双指针问题-LeetCode 88、125(双指针,大小写转换)

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

    算法工程师之路
  • 算法学习|双指针

    微笑的小小刀
  • 双指针算法练习(一)

    双指针算法是指的在遍历过程中,我们给定两个指针在相同或者相向方向遍历,在数组有序的情况下,使我们的算法复杂度降低。

    生信编程日常
  • LeetCode分类刷题:双指针(Two Pointers)

    双指针(Two Pointers)一直是程序员面试中的一个必须准备的主题, 面试中双指针出现的次数比较多,主要由于在工作中指针经常用到,指针问题能够直接反应面试...

    ACM算法日常
  • 算法攻关-双指针笔记

    双指针目前LC上涉及83道题,属于面试的一个高频范围区。我们根据标签分类是可以获取到一部分信息笔试考察范围点的。目前LC上一共是1989道题。概率为83/198...

    小诚信驿站
  • LeetCode | 使用双指针解决11号题

    第4题号还有二分查找和分治算法,算法比较复杂。那我就接着做下一道题号,第11题号。

    我脱下短袖
  • 双指针技巧直接秒杀五道算法题

    本文是一两年前发过的 一篇文章,当时没多少人看,现在由于账号迁移的原因公众号里都搜索不到了,我就重新加工了一下,并且添加了新内容,直接套双指针技巧秒杀 5 道算...

    labuladong
  • 算法篇:双指针之接雨水

    接雨水的题目在leetcode上面出现了两次,不过解法却很不相同,一类是简单的双指针使用场景;一类是栈的典型实用。

    灰子学技术
  • 看完互联网大佬的「LeetCode 刷题手册」, 手撕了 400 道 Leetcode算法题

    程序员小熊
  • 二分问题-LeetCode 69、167、92(二分,牛顿法,双指针)

    实现 int sqrt(int x) 函数。 计算并返回 x 的平方根,其中 x 是非负整数。 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

    算法工程师之路

扫码关注云+社区

领取腾讯云代金券