两数之和
解法1：两次循环暴力求和，时间复杂度O(n^2)，空间复杂度O(1)
class Solution:
def twoSum(self, nums: list[int], target: int) -> list[int]:
for i in range(len(nums) -1):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []
解法2：一次循环，利用字典存放target-current的差值比较，时间复杂度O(n)，空间复杂度O(n)
class Solution:
def twoSum(self, nums: list[int], target: int) -> list[int]:
temp = dict()
for k, v in enumerate(nums):
if target - v in temp:
return [temp[target - v], k]
else:
temp[v] = k
return []
三数之和
三数之和是两数之和的升级版，需要返回所有的结果并不能重复
使用三重循环在LeetCode可能会超时，所以不列出该解法了
解法1：两次循环，相加取反后，使用两数之和的解法2相同的思路处理，时间复杂度O(n^2)，空间复杂度O(n)
class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
if len(nums) < 3:
return []
# 先行排序，便于后续逻辑处理
nums.sort()
# 使用set类型，便于过滤掉重复值
result = set()
for k, v in enumerate(nums[:-2]):
# 最小值大于0，可以直接退出了
if v > 0:
break
# 连续两个或两个以上相同值，不再重复计算
if k >= 1 and v == nums[k - 1]:
continue
d = {}
for x in nums[k + 1:]:
# x在之前的相加取反中存在，说明累加=0
if x not in d:
d[-v - x] = 1
else:
# 这里是排序过的，且累加=0，所以x >= -v-x >= v，可以直接通过set去重
result.add((v, -v - x, x))
return list(result)
解法2：两次循环（外层循环加双指针夹逼），比解法1少开了一个字典的空间，时间复杂度O(n^2)，空间复杂度O(1)
class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
length = len(nums)
if length < 3:
return []
nums.sort()
result = []
for i in range(length - 2):
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, length - 1
while left < right:
# 累加大于0，最大值减少一点
if nums[i] + nums[left] + nums[right] > 0:
right -= 1
# 累加小于0，最小值增加一点
elif nums[i] + nums[left] + nums[right] < 0:
left += 1
else:
# 累加等于0，推入到结果集
result.append((nums[i], 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 result
反转链表
解法1：使用迭代的方式将链表反转，时间复杂度O(n)，空间复杂度O(1)
# 参数定义
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
prev, current = None, head
while current:
next = current.next
current.next = prev
prev = current
current = next
return prev
解法2：递归，TODO
两两翻转链表中的节点
解法1：使用迭代的方式交换节点，时间复杂度O(n)，空间复杂度O(1)
# 参数
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
# 添加一个空头
resultList = ListNode()
resultList.next = head
# current遍历的时候用
current = resultList
# 空->1->2->3->4->5
while current.next and current.next.next:
# 值赋值
f = current
s = current.next
t = current.next.next
# 引用赋值
# 空->2
f.next = t
# 1->3
s.next = t.next
# 2->1
t.next = s
# 把上面的串起来就是 空->2->1->3
# 标杆往后移动2位，继续循环，.next的赋值会影响resultList，直接赋值不会
current = current.next.next
return resultList.next
解法2：递归，TODO
k个一组翻转链表
这题是翻转列表的升级版，每k次进行一次反转列表，然后把头尾再接回去
解法1：使用迭代的方式交换节点，时间复杂度O(n)（虽然是嵌套循环，但是外层循环的步长是常数k），空间复杂度O(1)
# 参数
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
prev = result = ListNode(next=head)
while head:
tail = prev
# 先把尾指针移到k的位置，没有则不需要翻转直接返回
for i in range(k):
tail = tail.next
if not tail:
return result.next
# 暂存下一步指针
next = tail.next
# 反转节点，并返回新的头尾指针
head, tail = self.reverse(head, tail)
# 把头指针挂上去，尾指针接上下一段
prev.next = head
tail.next = next
# 迭代
prev = tail
head = next
# 链表长度刚好是k的整数倍，从这里返回
return result.next
# 反转链表
def reverse(self, head: ListNode, tail: ListNode):
prev, cur = None, head
while prev != tail:
next = cur.next
cur.next = prev
prev = cur
cur = next
return tail, head
判断链表是否有环
解法1：利用set判断节点是否存在，存在则有环，时间复杂度O(n)，空间复杂度O(n)
# 参数
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
s = set()
while head:
if head in s:
return True
else:
s.add(head)
head = head.next
return False
解法2：判断快慢指针是否相撞，因为只有一个后继指针，如果有环，快慢指针必定相撞，时间复杂度O(n)，空间复杂度O(1)
# 参数
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
f = s = head
while f and f.next:
f = f.next.next
s = s.next
if f == s:
return True
return False
判断链表是否有环，有环则返回入口节点，否则返回None
解法1：同上题解法1，第一次与set中节点重复的点就是入口点
# 参数
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
s = set()
while head:
if head in s:
return head
else:
s.add(head)
head = head.next
return None
解法2：快慢指针法，相撞点未必是入口点
- 假设无环段为a，有环段为b，快指针为f（每次走2步），慢指针是s（每次走1步），n为环数
- 则：1.f=2s 2.f=s+nb
- 推导出：1.s=nb 3.f=2nb
- 如果让指针从头部走到环入口，则：步数k=a+nb
- 刚好s=nb，所以让慢指针再走a步就是环入口
# 参数
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
f = s = head
while True:
if not f or not f.next:
return None
f = f.next.next
s = s.next
if f == s:
break
while head != s:
head = head.next
s = s.next
return head
比较含退格的字符串
解法1：利用list来模拟队列，时间复杂度O(n)，空间复杂度O(n)
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
return self.back(s) == self.back(t)
def back(self, s: str):
arr = []
for i in s:
if i == '#':
len(arr) > 0 and arr.pop()
else:
arr.append(i)
return ''.join(arr)
解法2：双指针，TODO
用栈实现队列
解法1：两个list模拟2个栈，实现先进后出到先进先出
class MyQueue:
def __init__(self):
self.__stack1 = []
self.__stack2 = []
def push(self, x: int) -> None:
self.__stack1.append(x)
def pop(self) -> int:
if len(self.__stack2) == 0:
for i in range(len(self.__stack1)):
self.__stack2.append(self.__stack1.pop())
return self.__stack2.pop()
def peek(self) -> int:
if len(self.__stack2) == 0:
for i in range(len(self.__stack1)):
self.__stack2.append(self.__stack1.pop())
if len(self.__stack2) > 0:
return self.__stack2[-1]
def empty(self) -> bool:
if len(self.__stack1) == 0 and len(self.__stack2) == 0:
return True
else:
return False
用队列实现栈
解法1：两个list模拟2个队列，实现先进后出到先进先出
class MyStack:
def __init__(self):
self.__queue1 = []
self.__queue2 = []
# self.__queue2每次push的时候都是空的，保证每次append都在第一个
# 然后利用queue1和queue2互换，实现每次self.__queue1出队列的都是最新append的那个
def push(self, x: int) -> None:
self.__queue2.append(x)
while self.__queue1:
self.__queue2.append(self.__queue1.pop(0))
self.__queue1, self.__queue2 = self.__queue2, self.__queue1
def pop(self) -> int:
return self.__queue1.pop(0)
def top(self) -> int:
if self.__queue1:
return self.__queue1[0]
def empty(self) -> bool:
return not self.__queue1
有效的括号
解法1：利用栈实现左右括号的完全匹配，时间复杂度O(n)，空间复杂度O(n)
class Solution:
def isValid(self, s: str) -> bool:
d = {")": "(", "]": "[", "}": "{"}
stack = []
for i in s:
if i in ("(", "[", "{"):
stack.append(i)
elif i in d:
if not stack or stack[-1] != d.get(i):
return False
else:
stack.pop()
return not stack
数据流中的第K大元素
解法1：利用优先队列来实现，时间复杂度O(logn)，空间复杂度O(n)
import heapq
class KthLargest:
def __init__(self, k: int, nums: list[int]):
self.q = nums
self.k = k
heapq.heapify(self.q)
for _ in range(len(self.q) - k):
heapq.heappop(self.q)
def add(self, val: int) -> int:
if len(self.q) < self.k:
heapq.heappush(self.q, val)
elif val > self.q[0]:
heapq.heappushpop(self.q, val)
return self.q[0]
滑动窗口最大值
解法1：利用双关队列，从大到小，比对索引，时间复杂度O(n)，空间复杂度O(n)
from collections import deque
class Solution:
def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
result, q = [], deque()
for i, v in enumerate(nums):
# 移动到窗口后面，判断窗口的第0个是否失效
if i >= k and queue[0] <= i - k:
q.popleft()
# 最右边的元素小于当前元素，丢弃掉
while q and nums[q[-1]] <= v:
q.pop()
# 每次都把当前元素的索引推入队列
q.append(i)
# 窗口K拉满后，就开始往结果集中推入最大值了
if i >= k - 1:
result.append(nums[q[0]])
return result
有效的字母异位词
解法1：分别排序，比较相等，时间复杂度O(logn)，空间复杂度O(n)
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
return sorted(s) == sorted(t)
解法2：字典计数法，比较字典是否相等，时间复杂度O(n)，空间复杂度O(n)
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
return self.calc(s) == self.calc(t)
def calc(self, s):
d = dict()
for i, v in enumerate(s):
d[v] = d.get(v, 0) + 1
return d
解法3：字典计数法的变形，时间复杂度O(n)，空间复杂度O(n)
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
d1 = [0] * 26
d2 = [0] * 26
if len(s) != len(t):
return False
for i in range(len(s)):
d1[ord(s[i]) - 97] += 1
d2[ord(t[i]) - 97] += 1
return d1 == d2