双指针
数组
15. 三数之和
15. 三数之和
# 描述：给定一个整数数组 nums。
# 要求：判断 nums 中是否存在三个元素 a、b、c，满足 a + b + c == 0。要求找出所有满足要求的不重复的三元组。
class Solution:
def threeSum(self, nums):
n = len(nums)
res = []
nums.sort()
for i in range(n):
left = i + 1
right = len(nums) - 1
# 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
if nums[i] > 0:
break
# 去重
if i >= 1 and nums[i] == nums[i - 1]:
continue
while left < right:
total = nums[i] + nums[left] + nums[right]
if total > 0:
right -= 1
elif total < 0:
left += 1
else:
res.append([nums[i], nums[left], nums[right]])
# 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
while left != right and nums[left] == nums[left + 1]:
left += 1
while left != right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
return res
18. 四数之和
18. 四数之和
# 给定一个整数数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a、b、c、d，使得 a + b + c + d = target
# 要求找出所有满足条件且不重复的四元组。
class Solution:
def fourSum(self, nums, target: int):
n = len(nums)
res = []
nums.sort()
for i in range(n):
# 对nums[i]去重
if i > 0 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
left = k + 1
right = n - 1
while left < right:
if nums[i] + nums[k] + nums[left] + nums[right] > target:
right -= 1
elif nums[i] + nums[k] + nums[left] + nums[right] < target:
left += 1
else:
res.append([nums[i], nums[k], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
return res
27. 移除元素
移除元素 【快慢指针】
class Solution:
def removeElement(self, nums, val: int) -> int:
slow = 0
fast = 0
n = len(nums)
while fast < n:
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow
字符串
125. 验证回文串
125. 验证回文串
# 描述：给定一个字符串 s。
# 要求：判断是否为回文串（只考虑字符串中的字母和数字字符，并且忽略字母的大小写）。
class Solution:
# 双指针
def isPalindrome(self, s: str) -> bool:
left = 0
right = len(s) - 1
while left < right:
if not s[left].isalnum():
left += 1
continue
if not s[right].isalnum():
right -= 1
continue
if s[left].lower() == s[right].lower():
left += 1
right -= 1
else:
return False
return True
def isPalindrome2(self, s: str) -> bool:
s1 = "".join(ch.lower() for ch in s if ch.isalnum())
return s1 == s1[::-1]
151. 反转字符串中的单词
反转字符串中的单词
class Solution:
# 移除多余空格
def trim(self, s):
left = 0
right = len(s) - 1
while left <= right and s[left] == " ":
left += 1
while left <= right and s[right] == " ":
right -= 1
res = []
while left <= right:
if s[left] != " ":
res.append(s[left])
elif res[-1] != " ":
res.append(s[left])
left += 1
return res
# 翻转字符串数组
def reverse(self, s, left, right):
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
return None
# 翻转每个单词
def reverse_each_word(self, l):
start = 0
end = 0
n = len(l)
while start < n:
while end < n and l[end] != " ":
end += 1
self.reverse(l, start, end - 1)
start = end + 1
end += 1
return None
def reverseWords(self, s: str) -> str:
l = self.trim(s)
self.reverse(l, 0, len(l) - 1)
self.reverse_each_word(l)
return "".join(l)
344. 反转字符串
反转字符串 【双指针？】
# 使用两个指针 left，right。left 指向字符数组开始位置，right 指向字符数组结束位置。
# 交换 s[left] 和 s[right]，将 left 右移、right 左移。
# 如果遇到 left == right，跳出循环
# 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题
class Solution:
def reverseString(self, s):
left = 0
right = len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
# 使用额外空间
def reverseString2(self, s):
res = []
for i in range(len(s) - 1, -1, -1):
res.append(s[i])
return res
链表
19. 删除链表的倒数第 N 个结点
19. 删除链表的倒数第 N 个结点
# 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:
dummy = ListNode(0)
dummy.next = head
# 删除倒数第 n 个，要先找倒数第 n + 1 个节点
x = self.findFromEnd(dummy, n + 1)
# 删掉倒数第 n 个节点
x.next = x.next.next
return dummy.next
def findFromEnd(self, head: ListNode, k: int):
p1 = head
# p1 先走 n 步
for i in range(k):
p1 = p1.next
p2 = head
# p1 和 p2 同时走 n - k 步
while p1:
p2 = p2.next
p1 = p1.next
# p2 现在指向第 n - k + 1 个节点，即倒数第 k 个节点
return p2
142. 环形链表 II
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:
# 快慢指针初始化指向 head
slow = fast = head
while fast and fast.next:
# 慢指针走一步，快指针走两步
slow = slow.next
fast = fast.next.next
# 快慢指针相遇，说明含有环
if slow == fast:
break
# fast 遇到空指针说明没有环
if fast is None or fast.next is None:
return None
slow = head
# 快慢指针同步前进，相交点就是环起点
while slow != fast:
slow = slow.next
fast = fast.next
return slow
206. 反转链表
206. 反转链表
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
pre = None
cur = None
while head:
cur = head.next # 抓手
head.next = pre # 反转
pre = head
head = cur # 往下走
return pre