力扣刷题-python-双指针（数组、链表、字符串、N数之和）_双指针实现力扣问题总结 python

1.双指针

双指针用的太多了，但是双指针又不属于任何一个数据结构，所以单独拿一天来总结它。

2.数组篇

27. 移除元素 - 力扣（LeetCode） (leetcode-cn.com)
快慢指针法

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        slow=0
        for fast in range(len(nums)):
            if nums[fast]!=val: 
                nums[slow]= nums[fast]
                slow+=1
        return slow
1
2
3
4
5
6
7
8

26. 删除有序数组中的重复项 - 力扣（LeetCode） (leetcode-cn.com)

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        slow=0
        for fast in range(len(nums)):
            if not fast or nums[fast]-nums[fast-1]:
                nums[slow]=nums[fast]
                slow+=1
        return slow
1
2
3
4
5
6
7
8
9
10
11
12
'
运行
运行

283. 移动零 - 力扣（LeetCode） (leetcode-cn.com)

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        #将不是0 的全部移到前面去

        slowIndex=0
        for fastIndex in range(len(nums)):
            if nums[fastIndex]:
                  nums[fastIndex], nums[slowIndex] =  nums[slowIndex], nums[fastIndex] 
                  slowIndex+=1
1
2
3
4
5
6
7
8
9
10
11
12
13
'
运行
运行

844. 比较含退格的字符串 - 力扣（LeetCode） (leetcode-cn.com)

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
           def recover(s:list)->list:
               slowIndex =0
               for fastIndex in range(len(s)):
                   if s[fastIndex]!= '#' :
                       s[slowIndex]= s[fastIndex]
                       slowIndex += 1
                   elif slowIndex: slowIndex-=1
               return s[0:slowIndex]

           return recover(list(s))==recover(list(t))
1
2
3
4
5
6
7
8
9
10
11
12
'
运行
运行

977. 有序数组的平方 - 力扣（LeetCode） (leetcode-cn.com)

class Solution(object):
    def sortedSquares(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n=len(nums)
        left,right=0,n-1
        res= [0]*n

        for i in range(n-1,-1,-1):
            leftp= nums[left]**2
            rightp= nums[right]**2

            if leftp> rightp: 
                left+=1
                res[i]=leftp
            else:
                right-=1
                res[i]=rightp
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
'
运行
运行

3.链表篇

206. 反转链表 - 力扣（LeetCode） (leetcode-cn.com)

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        left, right = None, head
        while right:
            right.next, left, right  =  left, right,right.next
        return left
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
'
运行
运行

142. 环形链表 II - 力扣（LeetCode） (leetcode-cn.com)

# 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:
        fast= slow =head

        while fast and fast.next and fast.next.next:
            fast= fast.next.next#fast 为2倍  slow为常速
            slow= slow.next

            if fast==slow:  #找到后和head放出的指针相遇 为入口
                p=head
                while slow!=p:
                    p= p.next
                    slow= slow.next
                return p
        return None
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode） (leetcode-cn.com)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        nhead= ListNode(0,head)  #虚拟节点 可以减少很多不必要的判断
        #slow 等fast走到n 才开始
        slow=fast=nhead
        while fast.next:
            n-=1
            fast= fast.next
            if n<0: slow= slow.next
        slow.next = slow.next.next

        return nhead.next     
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

面试题 02.07. 链表相交 - 力扣（LeetCode） (leetcode-cn.com)

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

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        #有一个比较厉害的想法 就是走完自己走别人 如果相交 比如是起始节点
        pa, pb= headA, headB
        while pa!=pb:
           pa= pa.next if pa else headB
           pb= pb.next if pb else headA
        return pa
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4.字符串篇

344. 反转字符串 - 力扣（LeetCode） (leetcode-cn.com)

class Solution(object):
    def reverseString(self, s):
        """
        :type s: List[str]
        :rtype: None Do not return anything, modify s in-place instead.
        """

        left, right = 0, len(s)-1
        while left< right:
            s[left], s[right] = s[right], s[left]
            left+=1
            right-=1
1
2
3
4
5
6
7
8
9
10
11
12
'
运行
运行

剑指 Offer 05. 替换空格 - 力扣（LeetCode） (leetcode-cn.com)

class Solution:
    def replaceSpace(self, s: str) -> str:
        countk=2*s.count(' ')
        s=list(' '*countk+s)
        slow=0 
        for i in range(countk,len(s)):
            if s[i] !=' ': 
                s[slow]=s[i]
                slow+=1
            else:
                s[slow:slow+3]='%20'
                slow+=3
        return ''.join(s)
1
2
3
4
5
6
7
8
9
10
11
12
13
'
运行
运行

5.N数之和篇

15. 三数之和 - 力扣（LeetCode） (leetcode-cn.com)

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        #双指针法
        nums.sort()
        res=set()
        n= len(nums)
        for i  in range(n):
            if nums[i] > 0:break        
            if i >= 1 and nums[i] == nums[i- 1]:continue
            left, right = i+1,  n-1
            while left < right :
                if nums[left] +nums[right] +nums[i]> 0:
                     right-= 1
                elif nums[left] +nums[right] +nums[i]< 0:
                     left+= 1
                else:
                     #if [nums[i],nums[left],nums[right]] not in res:
                     res.add((nums[i],nums[left],nums[right]))  #用集合加元组消除重复
                     right-= 1
                     left+= 1
        return [list(_) for _ in res]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
'
运行
运行

18. 四数之和 - 力扣（LeetCode） (leetcode-cn.com)

# 双指针法
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        
        nums.sort()
        n = len(nums)
        res = []
        for i in range(n):
            if nums[i] > target//4:break        #最小的数值大于平均值 是要跳出循环的
            if i >= 1 and nums[i] == nums[i- 1]:continue  #当前数为前面的重复数
            for k in range(i+1, n):
                if k > i + 1 and nums[k] == nums[k-1]: continue
                p = k + 1
                q = n - 1

                while p < q:
                    if nums[i] + nums[k] + nums[p] + nums[q] > target: q -= 1
                    elif nums[i] + nums[k] + nums[p] + nums[q] < target: p += 1
                    else:
                        res.append([nums[i], nums[k], nums[p], nums[q]])
                        while p < q and nums[p] == nums[p + 1]: p += 1
                        while p < q and nums[q] == nums[q - 1]: q -= 1
                        p += 1
                        q -= 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

6.总结

把之前做过的题又重新做了一遍，感觉除了链表必须用双指针外，其他大部分是为了降低时间复杂度。