目录
  1. 1. 前言
  2. 2. 167-两数之和II-输入有序数组
    1. 2.1. 题目
    2. 2.2. 题解
  3. 3. 633-平方数之和
    1. 3.1. 题目
    2. 3.2. 题解
  4. 4. 345-反转字符串中的元音字母
    1. 4.1. 题目
    2. 4.2. 题解
  5. 5. 680-验证回文字符串II※
    1. 5.1. 题目
    2. 5.2. 题解
  6. 6. 88-合并两个有序数组
    1. 6.1. 题目
    2. 6.2. 题解
  7. 7. 141-环形链表
    1. 7.1. 题目
    2. 7.2. 题解
  8. 8. 524-通过删除字母匹配到字典里最长单词※
    1. 8.1. 题目
    2. 8.2. 题解
leetcode-双指针

前言

 leetcode中可以用“双指针”法解决的经典题目。

  • 167-两数之和II-输入有序数组
  • 633-平方数之和
  • 345-反转字符串中的元音字母
  • 680-验证回文字符串II
  • 88-合并两个有序数组
  • 141-环形链表
  • 524-通过删除字母匹配到字典里最长单词

167-两数之和II-输入有序数组

题目

  • 难度:简单

  • 题目:给定一个已按照升序排列的有序数组,找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。

  • 说明:

    • 返回的下标值(index1 和 index2)不是从零开始的。
    • 你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。
  • 示例:

    输入: numbers = [2, 7, 11, 15], target = 9
    输出: [1,2]
    解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

题解

  • 注意:题目是升序排列数组。
  • 思路:使用双指针,一个指针指向值较小的元素,一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历,指向较大元素的指针从尾向头遍历。
    • 如果两个指针指向元素的和 sum == target,那么得到要求的结果;
    • 如果 sum > target,移动较大的元素,使 sum 变小一些;
    • 如果 sum < target,移动较小的元素,使 sum 变大一些。
  • 时间复杂度:O(N),数组最多遍历一遍。
  • 空间复杂度:O(1),使用额外两个指针。
class Solution(object):
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
i = 0
j = len(numbers) - 1
while i < j:
if numbers[i] + numbers[j] == target:
return i + 1, j + 1
elif numbers[i] + numbers[j] < target:
i += 1
else:
j -= 1
return None

633-平方数之和

题目

  • 难度:简单

  • 题目:给定一个非负整数 c ,你要判断是否存在两个整数 ab,使得a2+b2=ca^2+b^2=c

  • 示例:

    输入: 5
    输出: True
    解释: 1 * 1 + 2 * 2 = 5

    输入: 3
    输出: False

题解

  • 思路:可以看成是在元素为 0~target有序数组中查找两个数,使得这两个数的平方和为 target,如果能找到,则返回 true,表示 target 是两个整数的平方和。
  • 注意:本题和 167题类似,只有一个明显区别:一个是和为 target,一个是平方和为 target。本题同样可以使用双指针得到两个数,使其平方和为 target。
  • 关键:右指针的初始化,实现剪枝,从而降低时间复杂度。设右指针为 x,左指针固定为 0,为了使 02+x20^2 + x^2 的值尽可能接近target,我们可以将 x 取为 sqrt(target)。
  • 时间复杂度:O(sqrt(target)),最多遍历一遍0~sqrt(target)。
  • 空间复杂度:O(1),额外使用两个指针。
class Solution(object):
def judgeSquareSum(self, c):
"""
:type c: int
:rtype: bool
"""
if c < 0:
return False
i = 0
j = int(c ** 0.5)
while i <= j:
if i ** 2 + j ** 2 == c:
return True
elif i ** 2 + j ** 2 < c:
i += 1
else:
j -= 1
return False

345-反转字符串中的元音字母

题目

  • 难度:简单

  • 题目:编写一个函数,以字符串作为输入,反转该字符串中的元音字母。

  • 示例:

    输入: "hello"
    输出: "holle"

    输入: "leetcode"
    输出: "leotcede"
  • 说明:元音字母不包含字母"y"。

题解

  • 思路:使用双指针,一个指针从头向尾遍历,一个指针从尾到头遍历,当两个指针都遍历到元音字符时,交换这两个元音字符。

    为了快速判断一个字符是不是元音字符,我们将全部元音字符添加到集合 HashSet 中,从而以 O(1) 的时间复杂度进行该操作。

  • 时间复杂度:O(N),最多遍历一遍字符串

  • 空间复杂度:O(1),额外使用两个指针

class Solution(object):
def reverseVowels(self, s):
"""
:type s: str
:rtype: str
"""
if not s :
return s
vowels = ['a','e','i','o','u','A','E','I','O','U']
i = 0
j = len(s) - 1
s = list(s)
while i <= j:
while i < j and s[i] not in vowels:
i += 1
while i < j and s[j] not in vowels:
j -= 1
s[i], s[j] = s[j], s[i]
i += 1
j -= 1
return ''.join(s)

680-验证回文字符串II※

题目

  • 难度:简单

  • 题目:给定一个非空字符串 s最多删除一个字符。判断是否能成为回文字符串。

  • 示例:

    输入: "aba"
    输出: True

    输入: "abca"
    输出: True
    解释: 你可以删除c字符。
  • 注意:字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。

题解

  • 回文串概念:指具有左右对称特点的字符串,例如 “abcba” 就是一个回文字符串。
  • 思路:使用双指针,令一个指针从左到右遍历,一个指针从右到左遍历,这两个指针同时移动一个位置,每次都判断两个指针指向的字符是否相同,如果都相同,字符串才是具有左右对称性质的回文字符串。
  • 关键
    • 处理删除一个字符。在使用双指针遍历字符串时,如果出现两个指针指向的字符不相等的情况,我们就试着删除一个字符,再判断删除完之后的字符串是否是回文字符串。
    • 在判断是否为回文字符串时,我们不需要判断整个字符串,因为左指针左边和右指针右边的字符之前已经判断过具有对称性质,所以只需要判断中间的子字符串即可。
    • 在试着删除字符时,我们既可以删除左指针指向的字符,也可以删除右指针指向的字符。
  • 时间复杂度:O(N),其中 n是字符串的长度。判断整个字符串是否是回文字符串的时间复杂度是 O(n),遇到不同字符时,判断两个子串是否是回文字符串的时间复杂度也都是 O(n)。
  • 空间复杂度:O(1),额外使用常量空间。
class Solution(object):
def validPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
if not s:
return False #题目要求非空,因此定义空串是非回文串
low = 0
high = len(s) - 1
while low < high:
if s[low] == s[high]:
low += 1
high -= 1
else:
return self.checkPalindrome(low + 1 , high, s) or self.checkPalindrome(low, high - 1, s)
return True

def checkPalindrome(self, low, high, s):
i = low #指向字符串第一个字符
j = high #指向字符串最后一个字符
while i < j:
if s[i] != s[j]:
return False
i += 1
j -= 1
return True

88-合并两个有序数组

题目

  • 难度:简单

  • 题目:给你两个有序整数数组 nums1nums2,请你将 nums2 合并到 nums1 中*,*使 nums1 成为一个有序数组。

  • 说明:

    • 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
    • 你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。
  • 示例:

    输入:
    nums1 = [1,2,3,0,0,0], m = 3
    nums2 = [2,5,6], n = 3

    输出: [1,2,2,3,5,6]

题解

  • 思路:使用双指针,一个指向nums1的最后一个数字,另一个指向nums2的最后一个数字,需要从尾开始遍历,否则在 nums1 上归并得到的值会覆盖还未进行归并比较的值。
  • 时间复杂度:O(n + m),最多需要遍历一遍nums1和nums2。
  • 空间复杂度:O(1),额外使用两个指针
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.
"""
n1 = m - 1 #nums1最后一个数字
n2 = n - 1 #nums2最后一个数字
n0 = n + m - 1 #nums1最后一个位置的下标
while n1 >= 0 and n2 >= 0:
if nums2[n2] > nums1[n1]:
nums1[n0] = nums2[n2]
n2 -= 1
else:
nums1[n0] = nums1[n1]
n1 -= 1
n0 -= 1
#将nums2剩余的数字合并到nums1中
nums1[ : n2 + 1] = nums2[ : n2 + 1]

141-环形链表

题目

  • 难度:简单

  • 题目:给定一个链表,判断链表中是否有环。为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

  • 示例:

    输入:head = [3,2,0,-4], pos = 1
    输出:true
    解释:链表中有一个环,其尾部连接到第二个节点。

    输入:head = [1,2], pos = 0
    输出:true
    解释:链表中有一个环,其尾部连接到第一个节点。

    输入:head = [1], pos = -1
    输出:false
    解释:链表中没有环。
  • 进阶:你能用 O(1)(即,常量)内存解决此问题吗?

题解

  • 思路:使用双指针,一个指针每次移动一个节点,一个指针每次移动两个节点,如果存在环,那么这两个指针一定会相遇。
  • 时间复杂度:O(N),让我们将 n 设为链表中结点的总数。为了分析时间复杂度,我们分别考虑下面两种情况。
    • 链表中没有环:快指针将会首先到达尾部,其时间取决于列表的长度,也就是 O(n)。
    • 链表中有环:
      • 我们将慢指针的移动过程划分为两个阶段:非环部分与环形部分:
        • 慢指针在走完非环部分阶段后将进入环形部分:此时,快指针已经进入环中==N迭代次数=非环部分长度=N
        • 两个指针都在环形区域中:考虑两个在环形赛道上的运动员,快跑者每次移动两步而慢跑者每次只移动一步。其速度的差值为 1,因此需要经过\frac{二者之间距离}{速度差值} 次循环后,快跑者可以追上慢跑者。这个距离几乎就是"环形部分长度 K" 且速度差值为 1,我们得出这样的结论=K迭代次数=近似于环形部分长度K
      • 因此,在最糟糕的情况下,时间复杂度是:O(N+K),也就是O(N)
  • 空间复杂度:O(1),额外使用两个指针
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if not head:
return head
fast = slow = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
return True
return False

524-通过删除字母匹配到字典里最长单词※

题目

  • 难度:中等

  • 题目:给定一个字符串和一个字符串字典,找到字典里面最长的字符串,该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个,返回长度最长且字典顺序最小的字符串。如果答案不存在,则返回空字符串。

  • 示例:

    输入:
    s = "abpcplea", d = ["ale","apple","monkey","plea"]
    输出:
    "apple"


    输入:
    s = "abpcplea", d = ["a","b","c"]
    输出:
    "a"
  • 说明:

    • 所有输入的字符串只包含小写字母。
    • 字典的大小不会超过 1000。
    • 所有输入的字符串长度不会超过 1000。

题解

  • 字典序:字母序,表示英文单词在字典中的先后顺序,在计算机领域中扩展成两个任意字符串的大小关系。
  • 思路:通过删除字符串 s 中的一个字符能得到字符串 t,可以认为 t 是 s 的子序列,我们可以使用双指针来判断一个字符串是否为另一个字符串的子序列。
  • 时间复杂度:O(n * x),这里n是列表d中字符串的数目,x是字符串平均长度。
  • 空间复杂度:O(x),使用了变量ans。
class Solution(object):
def findLongestWord(self, s, d):
"""
:type s: str
:type d: List[str]
:rtype: str
"""
ans = ""
n = len(d)
m = len(s)
for i in range(n):
j = k = 0
while j < m and k < len(d[i]):
if s[j]==d[i][k]:
k += 1
j += 1
if k==len(d[i]):
if (len(d[i]) > len(ans)) or (len(d[i])==len(ans) and d[i] < ans):
ans = d[i]
return ans
文章作者: Lesy
文章链接: https://lesylin.com/2020/06/24/leetcode-%E5%8F%8C%E6%8C%87%E9%92%88/
文章声明: 转载请注明文章链接
打赏
  • 微信
  • 支付宝

Comment