精华内容
下载资源
问答
  • LeedCode上面的26题就可以用快慢指针解答 题目:给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。不要使用额外的数组空间,你必须在 原地 修改输入数组 并...

    双指针主要应用在有序数组中,设置两个指针,以一前一后或者一快一慢对数组元素进行检索或者数据修改。双指针算法可以对数组进行遍历,且算法复杂度低

    LeedCode上面的26题就可以用快慢指针解答

    题目:给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

     

    算法:

    class Solution:
    
        def removeDuplicates(self, nums: List[int]) -> int:
            i=0
    
            for j in range(len(nums)):
    
                if nums[j] != nums[i]:
    
                    i=i+1
    
                    nums[i] = nums[j]
    
            return(i+1)

    执行过程展示:

    例子:输入:nums=[0,1,1,2,3,3]

    1

    i=0;j=0

    nums[0] == nums[0]

    结果nums=[0,1,1,2,3,3]
    2

    i=0,j=1

    nums[1] != nums[0]

    i=1

    nums[1] = nums[1] 

    结果nums=[0,1,1,2,3,3]
    3

    i=1,j=2

    nums[2] == nums[1]

    结果nums=[0,1,1,2,3,3]
    4

    i=1,j=3

    nums[3] != nums[1]

    i=2

    nums[2] = nums[3] 

    结果nums=[0,1,2,2,3,3]
    5

    i=2,j=4

    nums[4] != nums[2]

    i=3

    nums[3] = nums[4]

    结果nums=[0,1,2,3,3,3]
    6

    i=3,j=5

    nums[5] == nums[3]

    结果nums=[0,1,2,3,3,3]

     

    最后返回 i=4,返回移除后数组为nums=[0,1,2,3]

     

    展开全文
  • class Node: def __init__(self, value=None, next_addr=None): self._value = value self._next_addr = next_addr @property def next_addr(self): return self._next_addr @next_addr.setter ...
  • 另一个常用的方法就是快慢指针法,快指针一次走两步,慢指针一次走一步,如果有闭环,那么快指针一定能追上慢指针(因为快指针相对慢指针一次走一步): 执行结果为: 时间复杂度都是O(n)但两种方法结果相差这么多...

    题目

    在这里插入图片描述
    在这里插入图片描述

    解题思路

    比较直的思路就是用列表储存遍历过的节点,然后看当前遍历的节点是否之前遍历过:
    在这里插入图片描述
    结果果然很拉闸:

    在这里插入图片描述
    另一个常用的方法就是快慢指针法,快指针一次走两步,慢指针一次走一步,如果有闭环,那么快指针一定能追上慢指针(因为快指针相对慢指针一次走一步):
    在这里插入图片描述

    执行结果为:
    在这里插入图片描述
    时间复杂度都是O(n)但两种方法结果相差这么多的原因应该是这样的,第一种暴力解法必须完整遍历完这个链表,而第二种快慢指针法最差的情况也就是完整遍历一次,很多情况下快指针可以在慢指针抵达链表尾之前追上慢指针,减少了运行时间。

    展开全文
  • Python链表中快慢指针的妙用,如找链表中间值,删除倒数第N个值,判断是否为环状链表等

    一、快慢指针的概念

    快慢指针中的快慢指的是移动的步长,即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2次,慢指针每次向前移动1次。

    如果我们要在上图链表中 删除value为10的节点,只需要设置两个指针,每一次移动后,快指针都会比慢指针多走一个节点,这就能形成一个指针间的差值,通过这个差值,来断开或者链接指针域,从而达到需要的结果。

    二、快慢指针的应用

    2.1 找中间值

    思路:

    设一个快指针 fast,设一个慢指针slow,假定快指针每次移动速度是慢指针的两倍,当快指针到达尾部节点指向None时,慢指针则处于链表的中间节点,从而确定中间节点的值。

    图示:

    在这里插入图片描述

    slow与fast指针都指向链表第一个节点,然后slow每次移动一个指针,fast每次移动两个指针。

    代码示例:

    class ListNode:
        def __init__(self, x, next=None):
            self.val = x
            self.next = next
    
    class Solution:
        def deleteNode(self, head: ListNode):
    
            slow = head  # 慢指针
            fast = head  # 快指针
    
    
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            print(slow.val)
    
    
    if __name__ == '__main__':
        a = ListNode(14, ListNode(23, ListNode(10, ListNode(35, ListNode(56, ListNode(59,ListNode(12,)))))))
        obj = Solution()
        Node = obj.deleteNode(a)
        
        
    # 结果为 35
    

    2.2 删除倒数第n个节点

    思路:

    1、删除倒数第n个节点,意味着需要获得 n-1的指针域以及n的指针域。

    2、设置快慢两个指针,先让快指针先走n+1步,然后再和慢指针一起走,当快指针为None时,慢指针刚好停留在 n-1的位置。

    图示:

    代码实例:

    # 快慢指针
    class ListNode:
        def __init__(self, x, next=None):
            self.val = x
            self.next = next
    
    class Solution:
        def kthToLast(self, head: ListNode, k: int) -> int:
    
            slow = head  # 慢指针
            fast = head  # 快指针
    
            while k+1 > 0:
                fast = fast.next
                k -= 1
    
            while fast.next is not None:
                fast = fast.next
                slow = slow.next
            slow.next = slow.next.next
    
            while head is not None:
                print(head.val)
                head = head.next
    
    if __name__ == '__main__':
        a = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5,)))))
        obj = Solution()
        Node = obj.kthToLast(a, 2)
    
        
        # 结果为 1,2,4,5
    

    2.3 判断是否为环状链表

    思路:

    快慢指针中,因为每一次移动后,快指针都会比慢指针多走一个节点,所以他们之间在进入环状链表后,不论相隔多少个节点,慢指针总会被快指针赶上并且重合,此时就可以判断必定有环。

    图示:

    如果fast指针遍历出None,则说明没有环。

    当slow指针和falst指针相同,则说明环有节点。

    代码示例:

    class Node:
        def __init__(self, val, next=None):
            self.val = val
            self.next = next
    
    def findbeginofloop(head):
        slow = head  # 慢指针
        fast = head  # 快指针
        if head is None:  # 判断链表是否为空
            return head
    
        while fast.next != None and fast.next.next != None:  # fastPtr的下一个节点和下下个节点都不为空
            slow = slow.next
            fast = fast.next.next
            if slow == fast:  # 两个指针相遇存在环结构
                print("存在环结构")
                break
    
    if __name__ == "__main__":
        node1 = Node(1)
        node2 = Node(2)
        node3 = Node(3)
        node4 = Node(4)
        node5 = Node(5)
        node1.next = node2
        node2.next = node3
        node3.next = node4
        node4.next = node5
        node5.next = node2
        findbeginofloop(node1)
    
    展开全文
  •   下面的快慢指针的关键是划分一个slow区间,这部分正是我们所需要的 26. 删除有序数组中的重复项 给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。 ...

    引言

      下面的快慢指针的关键是划分一个slow区间,这部分正是我们所需要的

    26. 删除有序数组中的重复项

    给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度
    不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

    class Solution:
        def removeDuplicates(self, nums: List[int]) -> int:
            """有序数组"""
            # 定义快慢指针
            slow = 0
            fast = 1
            while fast < len(nums):
                if nums[slow] == nums[fast]:
                    fast += 1
                else:
                    slow += 1
                    nums[slow] = nums[fast]
                    fast += 1
            return slow+1
    

    27. 移除元素

    给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
    不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
    元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

    思路:
    我们可以保留两个指针i和j,其中i是慢指针,j是快指针。当nums与给定的值相等时,递增j以跳过该元素。只要nums[j] != val ,我们就复制nums[j]到nums [i]并同时递增两个索引。重复这一过程,直到i到达数组的末尾,该数组的新长度为i。
    i为下面的slow指针
    j为下面的fast指针

    class Solution:
        def removeElement(self, nums: List[int], val: int) -> int:
            """
            时间复杂度为O(n)
            """
            slow = 0
            fast = 0
            while fast < len(nums):
                if nums[fast] == val:
                    fast += 1
                else:
                    nums[slow] = nums[fast]
                    slow += 1
                    fast += 1
        
            return slow
    

    在这里插入图片描述
    会发现内存消耗比较大,因为当开始出现var时,需要左移右侧所有元素,这一步耗时。发现题目中并没有说不能更改顺序,因此,可如下操作

    27. 移除元素—进阶

    当我们遇到nums[i] = val时,我们可以将当前元素与最后一个元素进行交换,并释放最后一个元素last-1。这实际上使数组的大小减少了1。

    class Solution:
        def removeElement(self, nums: List[int], val: int) -> int:
            """
            交换元素
            """
            i = 0 
            last = len(nums) - 1
            while i <= last:
                # 交换后的元素会再次与val比较
                if nums[i] == val:
                    nums[i] = nums[last]
                    last -= 1
                else:
                    i += 1
            return last+1
    

    在这里插入图片描述

    80. 删除有序数组中的重复项 II

    给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 最多出现两次 ,返回删除后数组的新长度。
    不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

    思路:

    遍历整个表:
    把当前的元素与它前面的对比,如果二者元素相同(为重复元素):此时统计重复的计数器count +=1。题目要求只保留2个重复的元素,
    这里需要加入重复元素个数的判断:
    这个元素正好重复了2次=>则进行保留。列表长度i+=1,然后nums[i]=nums[j];
    这个元素重复多于2次=>不进行任何操作。体现在程序上不做处理
    把当前的元素与它前面的对比,如果二者元素不同(为新元素):此时把当前这个结点(nums[i]添加到新表里面去,nums[i] = nums[j],表长i+1
    i为下面的slow
    j为下面的fast

    class Solution:
        def removeDuplicates(self, nums: List[int]) -> int:
            count = 1
            slow = 0
            fast = 1
            while fast < len(nums):
                # 两者元素相同(重复元素)
                if nums[slow] == nums[fast]:
                    count += 1
                    # 重复了两次
                    if count == 2:
                        slow += 1
                        nums[slow] = nums[fast]
                    # 重复超过了2次
                    else:
                        pass
                    fast += 1
                # 两者元素不同(新元素)
                else:
                    slow += 1
                    nums[slow] = nums[fast]
                    count = 1   # 重设统计个数
                    fast += 1
    
            return slow+1
    

    283. 移动零

    给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
    说明:
    必须在原数组上操作,不能拷贝额外的数组。
    尽量减少操作次数。

    class Solution:
        def moveZeroes(self, nums: List[int]) -> None:
            """
            Do not return anything, modify nums in-place instead.
            """
            slow,fast = 0,0
            # 双指针遍历寻找非零元素——慢指针用于存放非零元素,快指针用于寻找非零元素
            while fast < len(nums):
                if nums[fast] == 0:
                    fast += 1
                else:
                    nums[slow] = nums[fast]
                    slow += 1
                    fast += 1
            for i in range(slow,len(nums)):
                nums[i] = 0
    

    在这里插入图片描述

    845. 数组中的最长山脉

    我们把数组 A 中符合下列属性的任意连续子数组 B 称为 “山脉”:
    B.length >= 3
    存在 0 < i < B.length - 1 使得 B[0] < B[1] < … B[i-1] < B[i] > B[i+1] > … > B[B.length - 1]
    (注意:B 可以是 A 的任意子数组,包括整个数组 A。)
    给出一个整数数组 A,返回最长 “山脉” 的长度。
    如果不含有 “山脉” 则返回 0。

    示例:

    输入:[2,1,4,7,3,2,5]
    输出:5
    解释:最长的 “山脉” 是 [1,4,7,3,2],长度为 5

    思路:

    首先,固定山峰值,然后分别寻找左、右半边山脉的长度。
    A[left]< A[left+1],继续向左寻找
    A[right]< A[right-1],继续向右寻找
    如果以当前山峰的山脉长度比最长山脉长,更新最长山脉。
    注意:我们可以在只有当前点为山峰的情况(即 A[i-1] < A[i] and A[i+1]<A0),才在左右寻找最长山峰,这样可以大大降低搜索的次数。

    class Solution:
        def longestMountain(self, arr: List[int]) -> int:
            # 要求山脉长度大于3
            if len(arr) < 3:
                return 0
            res = 0
    
            for i in range(1,len(arr)-1):
                # 寻找山峰点
                if arr[i] > arr[i-1] and arr[i] > arr[i+1]:
                    left = i-1
                    right = i+1
                    # 左侧山脉
                    while left > 0 and arr[left-1] < arr[left]:
                        left -= 1
                    # 右侧山脉
                    while right < len(arr)-1 and arr[right+1] < arr[right]:
                        right += 1
                    # 如果当前山脉长度比最长山脉长度还长,则更新res
                    if right - left + 1 > res:
                        res = right - left + 1
            return res
    

    在这里插入图片描述


    如果对您有帮助,麻烦点赞关注,这真的对我很重要!!!如果需要互关,请评论或者私信!
    在这里插入图片描述


    展开全文
  • 【原链接】 1 链表简介 说起链表,我们脑海中浮现出它...快慢指针就是定义两根指针,移动的速度一快一慢,以此来制造出自己想要的差值。这个差值可以让我们找到链表上相应的节点。 如果现在对这里的简介不是很理解...
  • 快慢指针常用于解决链表数据结构的一些问题,判定链表是否有环是快慢指针的经典应用。由于单链表中每个节点只指向下一个节点, 只用一个指针无法判断链表中是否含有环。我们可以用两个指针fast和slow,其中fast指针...
  • 如果链表中有某个节点,可以通过连续跟踪next指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数pos来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果pos是-1,则在该链表中没有环。注意...
  • python中一般用List或字符串做数据 比如以下程序(来源Github,地址最下)用来解决:(Leetcode 167) 地址:https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/ 给定一个已按照升序排列的有序...
  • 题目链接 ... 题目描述 ...首先我们通过【leetcode-Python】-快慢指针-141. Linked List Cycle判断链表中是否有环,fast指针一次走两步,slow指针一次走一步,如果发现fast指针和slow指针相遇则跳出.
  • 快慢指针 定义:  快慢指针中的快慢指的是移动的步长,即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2,慢指针每次向前移动1次。 一定会相遇的证明 1、如果链表没有环,那么快指针比慢指针先...
  • python指针

    2020-06-28 19:24:51
    一、快慢指针 两个指针,分别以不同的步长移动 1.可以用来移动列表内的元素 例如,给定一个列表 nums = [1,0,2,0,3] 将0移动到列表的末尾 快指针 f 慢指针 s 初始值都为0 此时快指针所对应的元素不为0,快慢指针...
  • 【leetcode】快慢指针 (in python

    千次阅读 2018-10-22 14:24:13
    依次循环下去,如果链表存在环,那么快慢指针一定会有相等的时候。 为了便于理解,你可以想象在操场跑步的两个人,一个快一个慢,那么他们一定会相遇(无论他们的起始点是不是在操场)。 【题141】 题目描述 判断一...
  • 法1_快慢指针 假设慢指针速度1,快指针速度2 那么在环的某位置快能追上慢 假设环之前距离为a,而环被相遇点分割,由两部分 x1 x2构成 那么 a+x1 = n(x1+x2) 所以 a = (n-1)x1+nx2 = (n-1)(x1+x2)+x2 所以如果分别以...
  • python指针

    2020-12-03 21:29:39
    双指针技巧再分为两类,一类是**「快慢指针」,一类是「左右指针」**。前者解决主要解决链表中的问题,比如典型的判定链表中是否包含环;后者主要解决数组(或者字符串)中的问题,比如二分查找。 一、快慢指针的...
  • 快慢指针

    2019-10-30 12:35:03
    快慢指针    快慢指针中的快慢指的是移动的步长,即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2,慢指针每次向前移动1次。快慢指针的应用(1)判断单链表是否存在环 &...
  • class Node: def __init__(self, value=None, next_addr=None): self._value = value self._next_addr = next_addr @property def next_addr(self): return self._next_addr @next_addr.setter ...
  • 题目链接 ... 题目描述 给定一个链表,删除链表...此题可以借助快慢指针,一次遍历就得到结果。fast指针先走n步,指向第n个节点(头节点为第1个节点)。slow指针指向头节点。那么fast和slow指针中间隔着n-1个节点。fast指
  • 快慢指针专题

    2020-06-22 21:24:37
    快慢指针专题 针对的题型 快慢指针主要针对以下两种类型的题目,其中第一种比较常见 判断链表或数组是否有环或与环相关的问题 寻找中点 与双指针的区别: ​ 快慢指针:像单链表这样的数据结构,指针只能进行单向...
  • class Node: def __init__(self, value=None, next_addr=None): self._value = value self._next_addr = next_addr @property def next_addr(self): return self._next_addr @next_addr.setter ...
  • 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
  • 一个快指针,一个慢指针。一直跑下去,如果有相等,就说明有循环。 可以想象两个人在操场上绕圈跑步,一个跑得快,一个跑得慢,一直跑下去肯定有一个节点相遇。 思路清晰,代码很容易。 # Definition for singly-...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,280
精华内容 912
关键字:

python快慢指针

python 订阅