2022/03/17 Thu 15:17    2022/11/16 Wed 23:31

这一块是自己不怎么熟悉的部分，所以是需要后续来发力的，这里只是做了整理，不代表是自己的知识内容。
参考链接：https://www.cnblogs.com/kyoner/p/11087755.html
快慢指针:解决主要解决链表中的问题，比如典型的判定链表中是否包含环
左右指针:主要解决数组（或者字符串）中的问题，比如二分查找。

一、快慢指针的常见算法

快慢指针一般都初始化指向链表的头结点 head，前进时快指针 fast 在前，慢指针 slow 在后，巧妙解决一些链表中的问题。

1、判定链表中是否含有环

单链表的特点是每个节点只知道下一个节点，所以一个指针的话无法判断链表中是否含有环的。
如果链表中不包含环，那么这个指针最终会遇到空指针 null 表示链表到头了，这还好说，可以判断该链表不含环。

2、已知链表中含有环，返回这个环的起始位置

3、寻找链表的中点

4、寻找链表的倒数第 k 个元素

二、左右指针的常用算法

左右指针在数组中实际是指两个索引值，一般初始化为 left = 0, right = nums.length - 1 。

1、二分查找

前文 二分查找算法详解 有详细讲解，这里只写最简单的二分算法，旨在突出它的双指针特性：

2、两数之和

3、反转数组

4、滑动窗口算法

双指针(对撞指针)

包含几道leetcode题目：

  • 167 有序数组的 Two Sum 2 (easy)
  • 633 两数的平方和(easy)
  • 345 反转元音字符(easy)
  • 125 验证回文串(easy)
  • 680 回文字符串(easy)
  • 344 反转字符串(easy)
  • 11 盛最多水容器(medium)

167. 有序数组的two sum 2 ( easy )

题目链接： https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/

解法： 采用头尾指针

解题思路：

由于数组为有序数组，因此利用头尾指针进行处理，头尾元素之和大于目标值，尾指针向前移动， 如果大于目标值，首指针向后移动

  1. 先判断输入数组是否为空
  2. 设置首尾指针分别指向首尾元素
  3. 判断首尾指针对应的元素之和与目标值之间的关系：
    1. 如果大于目标值： 尾指针前移，继续判断
    2. 如果小于目标值： 头指针后移， 继续判断
    3. 等于目标值： 返回头尾指针（由于题目要求从1开始，因此首尾指针均需要加1）

此题也可以采用hash表解决，后边章节再进行介绍

解题代码：

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        if not numbers: return []  #输入列表不存在，返回空值
        start, end = 0, len(numbers)-1  #头尾指针

        while start < end:  #保证尾指针在头指针后边
            _sum = numbers[start] + numbers[end]
            if  _sum < target:  #小于目标值，首指针后移
                start += 1
            elif _sum > target: #大于目标值，尾指针前移
                end -= 1
            else:               #等于目标值，返回结果
                return [start + 1, end + 1]
        return []

633. 两数的平方和(easy)

题目链接：https://leetcode-cn.com/problems/sum-of-square-numbers/

解法： 采用头尾指针

解题思路同上题差不多，因此此处不再赘述。

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        assert c >= 0
        start, end = 0, int(sqrt(c)) #设置首尾指针
        while start <= end:
            _sum = start **2 + end **2
            if _sum > c: end -= 1
            elif _sum < c: start += 1
            else: return True
        return False

345. 反转元音字符(easy)

题目链接：https://leetcode-cn.com/problems/reverse-vowels-of-a-string/

解法： 采用头尾指针

同前边的方法一样，采用首尾指针，不再赘述

class Solution:
    def reverseVowels(self, s: str) -> str:
        if len(s)<1: return s
        s = list(s)
        start, end = 0, len(s)-1
        vowels = set('aeiouAEIOU')
        while start < end:
            if s[start] in vowels and s[end] in vowels:
                s[start], s[end] = s[end], s[start]
                start += 1
                end -= 1
            elif s[start] in vowels: end -= 1
            elif s[end] in vowels: start += 1
            else: 
                start +=1
                end -= 1
        return ''.join(s)

125. 验证回文串(easy)

题目链接：https://leetcode-cn.com/problems/valid-palindrome/

解法： 首尾指针

注意： 题目中忽略大小写，因此采用lower(), 题目中忽略非字母数字字符，因此采用isalnum()

  • 与前边几道题不一样的地方就是，先忽略非字母数字字符，然后忽略大小写，再进行比较。
class Solution:
    def isPalindrome(self, s: str) -> bool:
        if len(s) <= 1: return True
        start, end = 0, len(s)-1
        while start < end:
            if s[start].isalnum() and s[end].isalnum():
                if s[start].lower() == s[end].lower(): 
                    start += 1
                    end -=1
                    continue
                else: return False
            elif s[start].isalnum(): end -= 1
            elif s[end].isalnum() : start += 1
            else:
                start += 1
                end -= 1
        return True

680. 验证回文字符串2(easy)

题目链接：https://leetcode-cn.com/problems/valid-palindrome-ii/

解法： 首尾指针

注意： 与前那边几道题不同的是，中间可以忽略一个字符，因此当比较到出现不同的字符时，需要比较两组，一组为start+1到end之间的字符，另一组为[start end-1]之间的字符是否为回文串

class Solution:
    def validPalindrome(self, s: str) -> bool:
        if len(s) < 2: return True

        def isPalindrome(s, start, end):
            while start < end:
                if s[start] == s[end]:
                    start += 1
                    end -= 1
                    continue
                else: return False
            return True

        start, end = 0, len(s)-1
        while start < end:
            if s[start] == s[end]:
                start += 1
                end -= 1
                continue
            else: 
                return isPalindrome(s, start+1, end) or isPalindrome(s, start, end-1)
        return True

344. 反转字符串(easy)

题目链接：https://leetcode-cn.com/problems/reverse-string/

解法：首尾指针

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        if not s: return []
        start, end = 0, len(s)-1
        while start < end:
            s[start], s[end] = s[end], s[start]
            start += 1
            end -= 1

11.盛最多水的容器(medium)

题目链接：https://leetcode-cn.com/problems/container-with-most-water/

解法：首尾指针

class Solution:
    def maxArea(self, height: List[int]) -> int:
        if len(height)<2: return 0
        start, end = 0, len(height)-1
        max_area = 0  #存储最大面积
        while start < end:
            area = (end - start) * min(height[start], height[end])
            max_area = max(area, max_area)   #更新最大的面积
            if height[start] < height[end]:
                start += 1  #高度较低的那一端向前移动，寻找较高的高度
            else:
                end -= 1
        return max_area

双指针(快慢指针)

包含几道leetcode题目：

  • 141 判断列表是否存在环(easy)
  • 283 移动零(easy)
  • 27 移除元素(easy)
  • 26 删除排序数组中的重复项(easy)
  • 80 删除排序数组中的重复项 II(medium)

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:
        if not head or head.next == None:
            return False
        slow, faster = head, head.next
        while slow and faster:
            if slow == faster: return True
            slow = slow.next
            if faster.next: faster = faster.next.next
            else: return False
        return False

此题也可使用hash表，建立一个hash表存储访问过的节点，当出现重复访问的节点，说明出现环

283. 移动零(easy)

题目链接：https://leetcode-cn.com/problems/move-zeroes/

解法： 快慢指针

利用快慢指针，慢指针指向零元素，快指针指向非零元素，将快慢指针对应的元素交换

1. 定义快慢指针
2. 如果慢指针指向非零元素，慢指针后移，快指针后移
3. 如果慢指针指向零元素，快指针指向非零元素，二者交换，快慢指针均后移
4. 如果慢指针指向零， 快指针指向零元素， 快指针后移

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        slower, faster = 0, 0 #快指针指向不为零的元素，慢指针指向零元素，满足条件就交换
        while faster < len(nums):
            if nums[slower] != 0:
                slower += 1
            elif nums[faster] != 0:
                nums[slower],  nums[faster] = nums[faster], nums[slower]
                slower += 1
            faster += 1

27. 移除元素(easy)

题目链接：https://leetcode-cn.com/problems/remove-element/

解法：快慢指针

### 类似于上一题将等于val的元素移动至末尾
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        if not nums: return 0
        slower, faster = 0, 0
        while faster < len(nums):
            if nums[slower] != val: slower += 1
            elif nums[faster] != val: 
                nums[slower], nums[faster] = nums[faster], nums[slower]
                slower += 1
            faster += 1
        return slower        

## 由于本题要求直接删除元素，不需要像移动零元素那样，直接覆盖即可
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        if not nums: return 0
        slower, faster = 0, 0
        while faster < len(nums):
            nums[slower] = nums[faster]
            if nums[slower] == val: 
                faster += 1
                continue
            slower += 1
            faster += 1
        return slower

26. 删除排序数组中的重复项(easy)

题目链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

解法： 快慢指针

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not  nums: return 0
        # 慢指针指向待写入元素的位置，快指针遍历数组
        slower, faster = 0, 0
        while faster< len(nums):
        #当快指针指向的元素与慢指针不同时，说明相同的元素已经遍历结束，此时将慢指针后移，将快指针的元素写入慢指针位置，保留一个元素
            if nums[slower] != nums[faster]:
                slower += 1
                nums[slower] = nums[faster]
            faster += 1
        return slower + 1

80. 删除排序数组中的重复项 II(medium)

题目链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii/

解法：快慢指针

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums: return 0
        flag = True
        slower, faster = 0, 1
        while faster <len(nums):
            if nums[slower] != nums[faster]:
                slower += 1
                nums[slower] = nums[faster]
                flag = True
            else:
                if flag:
                    slower += 1
                    nums[slower] = nums[faster]
                    flag = False
            faster += 1 
        return slower + 1

其他双指针

包含几道leetcode题目：

    1. 归并有序数组(easy)
    1. 最长的子序列(medium)

88. 归并有序数组(easy)

题目链接：https://leetcode-cn.com/problems/merge-sorted-array/

解法： 三个指针（类似于首尾指针）

将两个有序数组合并，必须执行in_place操作
解题思路：
* 设计三个指针，分别指向nums1的末尾，nums2的末尾，合成之后数组的末尾
* 然后比较两个数组最大值，然后填入合成之后数组的末尾

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        #三个指针，从后向前进行插入
        s1, s2, end =m-1, n-1, m + n -1
        while s1 >=0 and s2 >=0:
            if nums1[s1] <= nums2[s2]:
                nums1[end] = nums2[s2]
                s2 -= 1
            else:
                nums1[end] = nums1[s1]
                s1 -= 1
            end -= 1
        if s2 >= 0:
            nums1[:s2+1] = nums2[:s2+1]

524. 最长的子序列(medium)

题目链接：https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting/submissions/

解法： 双指针

class Solution:
    def findLongestWord(self, s: str, d: List[str]) -> str:
        if not s or not d: return ''       
        S = ''  # 保存结果字符串
        ## 循环遍历list字符串列表，将一个指针p2指向子字符串的开头
        for _s in d:
        ## 在比较的过程中，将找到的子串存储，然后在下一次找到后更新子串与子串的长度
            p2 = 0
            for p1 in range(len(s)):
                if p2 < len(_s) and s[p1] == _s[p2]:
                    p2 += 1
                    continue
            ## 判断是否找到对应的字符串，如果第一次找到字串，保存结果
            if p2 == len(_s) and not S:
                S = _s
            ## 如果是不是第一次找到满足条件的子串，比较长度保留较长的，子串长度相等的，保存字典序较小的
            elif p2 == len(_s):
                if len(S) > len(_s):
                    continue
                elif len(S) < len(_s):
                    S = _s
                else:
                    if S < _s: continue
                    else: S = _s
        return S
ToTOP
2018 bear