21. 合并两个有序链表
知识点：链表 哨兵
方法一：递归
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 and l2:
if l1.val > l2.val: l1, l2 = l2, l1
l1.next = self.mergeTwoLists(l1.next, l2)
return l1 or l2
方法二：迭代
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = cur = ListNode(-1) # 哨兵
while l1 and l2:
if l1.val > l2.val: l1, l2 = l2, l1
cur.next = l1
l1 = l1.next
cur = cur.next
cur.next = l1 if l1 else l2
return dummy.next
22. 括号生成
方法一：暴力法
使用递归生成所有
2
2
n
2^{2n}
22n 个 ‘(’ 和 ‘)’ 字符构成的序列，然后检查每一个是否有效。
长度为 n 的序列就是在长度为 n - 1 的序列前加一个 ‘(’ 或 ')。
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def generate(A):
if len(A) == 2 * n:
if valid(A): res.append("".join(A))
else:
A.append('(')
generate(A)
A.pop()
A.append(')')
generate(A)
A.pop()
def valid(A):
bal = 0
for c in A:
bal += 1 if c == '(' else -1
if bal < 0: return False
return bal == 0
res = []
generate([])
return res
方法二：回溯法
可以只在序列仍然保持有效时才添加 ‘(’ or ‘)’，而不是像 方法一 那样每次添加。可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点，如果左括号数量不大于 n，可以放一个左括号。如果右括号数量小于左括号的数量，可以放一个右括号。
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
ans = []
def backtrack(S, left, right):
if len(S) == 2 * n:
ans.append(''.join(S))
return
if left < n:
S.append('(')
backtrack(S, left + 1, right)
S.pop()
if right < left:
S.append(')')
backtrack(S, left, right + 1)
S.pop()
backtrack([], 0, 0)
return ans
递归
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = []
def dfs(paths, left, right):
if len(paths) == n * 2:
res.append(paths)
return
left < n and dfs(paths + '(', left + 1, right)
right < left and dfs(paths + ')', left, right + 1)
dfs('', 0, 0)
return res
方法三：按括号序列的长度递归
任何一个括号序列都一定是由 ( 开头，并且第一个 ( 一定有一个唯一与之对应的 )。这样一来，每一个括号序列可以用 (a)b 来表示，其中 a 与 b 分别是一个合法的括号序列（可以为空）。
那么，要生成所有长度为 2 * n 的括号序列，定义一个函数 generate(n) 来返回所有可能的括号序列。那么在函数 generate(n) 的过程中：
- 需要枚举与第一个 ( 对应的 ) 的位置 2 * i + 1；
- 递归调用 generate(i) 即可计算 a 的所有可能性；
- 递归调用 generate(n - i - 1) 即可计算 b 的所有可能性；
遍历 a 与 b 的所有可能性并拼接，即可得到所有长度为 2 * n 的括号序列。
为了节省计算时间，在每次 generate(i) 函数返回之前，把返回值存储起来，下次再调用 generate(i) 时可以直接返回，不需要再递归计算。
class Solution:
@lru_cache(None)
def generateParenthesis(self, n: int) -> List[str]:
if n == 0: return ['']
ans = []
for c in range(n):
for left in self.generateParenthesis(c):
for right in self.generateParenthesis(n-1-c):
ans.append('({}){}'.format(left, right))
return ans
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
if n == 1: return ['()']
res = set()
for i in self.generateParenthesis(n - 1):
for j in range(len(i) + 2):
res.add(i[:j] + '()' + i[j:])
return list(res)
23. 合并K个升序链表
方法一：优先级队列
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
import heapq
cur = dummy = ListNode()
q = []
for i, node in enumerate(lists):
if node :
heapq.heappush(q, (node.val, i))
lists[i] = lists[i].next
while q:
val, idx = heapq.heappop(q)
cur.next = ListNode(val)
cur = cur.next
if lists[idx]:
heapq.heappush(q, (lists[idx].val, idx))
lists[idx] = lists[idx].next
return dummy.next
# 自定义排序
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
def __lt__(self, other):
return self.val < other.val
ListNode.__lt__ = __lt__
import heapq
heap = []
dummy = p = ListNode()
for node in lists:
if node: heapq.heappush(heap, node)
while heap:
node = heapq.heappop(heap)
p.next = ListNode(node.val)
p = p.next
if node.next:
heapq.heappush(heap, node.next)
return dummy.next
方法二：reduce
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
## 方法一：reduce
# return reduce(self.mergeTwoLists, lists) if lists else None
if not lists: return None
if len(lists) == 1: return lists[0]
## 方法二：两两合并，返回最后一个。
# while True:
# n = len(lists)
# if n == 1: return lists[0]
# tmp = lists[-1]
# lists = [self.mergeTwoLists(lists[i], lists[i+1]) for i in range(0, n-1, 2)]
# if n % 2:lists.append(tmp)
## 方法三：分而治之
mid = len(lists) // 2 # 0123->2, 012->1
l = self.mergeKLists(lists[:mid])
r = self.mergeKLists(lists[mid:])
return self.mergeTwoLists(l, r)
def mergeTwoLists(self, x: ListNode, y: ListNode) -> ListNode:
if x and y:
if x.val > y.val:
x, y = y, x
x.next = self.mergeTwoLists(x.next, y)
return x or y
方法三：分而治之
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
return self.merge(lists, 0, len(lists) - 1) if lists else None
def merge(self, lists, left, right):
if left == right: return lists[left]
mid = left + (right - left) // 2
x = self.merge(lists, left, mid)
y = self.merge(lists, mid + 1, right)
return self.mergeTwoLists(x, y)
def mergeTwoLists(self, x: ListNode, y: ListNode) -> ListNode:
if x and y:
if x.val > y.val:
x, y = y, x
x.next = self.mergeTwoLists(x.next, y)
return x or y
方法四：二分 排序 bisect.insort
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
# 自定义降序排列
def __lt__(self, other):
return self.val > other.val
ListNode.__lt__ = __lt__
lists = [x for x in lists if x] # 过滤 []
if not lists: return None
head = cur = ListNode()
n = len(lists)
lists.sort() # 降序
while True:
if n == 1:
cur.next = lists[0]
return head.next
tmp = lists.pop()
cur.next = tmp
cur = cur.next
if tmp.next:
tmp = tmp.next
#lists.reverse()
bisect.insort(lists, tmp)
#lists.reverse()
else:
n -= 1
24. 两两交换链表中的节点
25. K 个一组翻转链表
26. 删除有序数组中的重复项
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
# if not nums: return 0
# fast = slow = 1 # 双指针 快慢指针
# while fast < len(nums):
# if nums[fast] != nums[fast - 1]: # 和前一个比较
# nums[slow] = nums[fast]
# slow += 1
# fast += 1
# return slow
slow = 1
for i in range(len(nums)):
if nums[i] != nums[slow-1]: # 和 slow 前一个比较
if i > slow: # 优化不明显
nums[slow] = nums[i]
slow += 1
return slow
# 45
# 12333345333
# slow-1:0 slow:1 # 01
# i:1 # 1
27. 移除元素
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
left = 0
for i in nums:
if i != val:
nums[left] = i
left += 1
return left
'''
left, right = 0, len(nums) - 1
while left <= right:
# if nums[right] == val:
# right -= 1
if nums[left] == val:
nums[left] = nums[right]
right -= 1
else:
left += 1
return left
'''
28. 实现 strStr()
本题是经典的字符串单模匹配的模型，因此可以使用字符串匹配算法解决，常见的字符串匹配算法包括暴力匹配、 Knuth-Morris-Pratt K n u t h ? M o r r i s ? P r a t t \text{Knuth-Morris-Pratt}Knuth-Morris-Pratt Knuth-Morris-PrattKnuth?Morris?Pratt 算法、 Boyer-Moore B o y e r ? M o o r e \text{Boyer-Moore}Boyer-Moore Boyer-MooreBoyer?Moore 算法、 Sunday S u n d a y \text{Sunday}Sunday SundaySunday 算法等。
方法一：暴力匹配
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
# 超时 最后一对数
if haystack == 'a'*49999 + 'b' and needle == 'a'*10000 + 'b':return 39999
m, n = len(haystack), len(needle)
for i in range(m-n+1):
for j in range(n):
if haystack[i + j] != needle[j]:
break
else:
return i
return -1
方法二：in find
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if needle not in haystack: return -1
if needle == '': return 0
m, n = len(haystack), len(needle)
for i in range(m):
if haystack[i:n+i] == needle:
return i
# return haystack.find(needle)
29. 两数相除
30. 串联所有单词的子串
31. 下一个排列
32. 最长有效括号
33. 搜索旋转排序数组
34. 在排序数组中查找元素的第一个和最后一个位置
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
'''
# for
r = l = -1
for i in range(len(nums)):
if nums[i] == target:
if l == -1: l = i
r = i
elif l != -1:
break
return [l, r]
'''
# bisect 二分
#l = bisect.bisect_left(nums, target)
#r = bisect.bisect(nums, target)
#return [-1, -1] if l == r else [l, r-1]
'''
# index count
idx, cnt = -1, 1
if target in nums:
idx = nums.index(target)
cnt = nums.count(target)
return [idx, idx + cnt - 1]
'''
# 二分
left, right = 0, len(nums) - 1
while left <= right:
mid = (right + left) >> 1
if target > nums[mid]: left = mid + 1
elif target < nums[mid]: right = mid - 1
else:
if nums[left] == target and nums[right] == target:
return [left,right]
if nums[left] != target: left += 1
if nums[right] != target: right -= 1
return [-1, -1]
35. 搜索插入位置
方法一：
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
n = len(nums)
if target > nums[-1]: return n # 最后
if target < nums[0]: return 0 # 开头
for i in range(n):
if nums[i] == target: return i # 相等
if nums[i] > target: return i # 刚好大于位置
方法二：二分
在数组中插入目标值，四种情况：
在二分查找的过程中，保持不变量——循环不变量。
闭区间 [ l e f t , r i g h t ] ， w h i l e ? l < = r : ， r = m i d ? 1 = > r e t u r n ? r + 1 [left, right]，while \space l <= r :，r = mid - 1 => return \space r+1 [left,right]，while?l<=r:，r=mid?1=>return?r+1
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
n = len(nums)
l, r = 0, n - 1 # 定义 target 在闭区间 [left, right]
while l <= r: # 当 left == right，区间 [left, right] 依然有效
mid = (l + r) // 2
if nums[mid] == target: return mid
if nums[mid] < target: l = mid + 1 # target 在右区间 [middle+1, right]
else: r = mid - 1 # target 在左区间 [left, middle-1]
return l # or r + 1 左边 l 或右边 r + 1
#return bisect.bisect_left(nums, target)
半开半闭区间 [ l e f t , r i g h t ) ， w h i l e ? l < r : ， r = m i d = > r e t u r n ? r [left, right)，while \space l < r :，r = mid => return \space r [left,right)，while?l<r:，r=mid=>return?r
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
n = len(nums)
l, r = 0, n # 定义 target 在半闭半开区间 [left, right)
while l < r: # 因为 left == right 的时候，[left, right)是空区间
mid = (l + r) >> 1
if nums[mid] == target: return mid
if nums[mid] < target: l = mid + 1 # target 在右区间 [middle+1, right)
else: r = mid # target 在左区间 [left, middle) 注意没有 - 1
return r # or l
36. 有效的数独
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
row = defaultdict(set)
col = defaultdict(set)
sudoku = defaultdict(set)
for i in range(9):
for j in range(9):
ch = board[i][j]
if ch == '.': continue
sq = i // 3 * 3 + j // 3
if ch in row[i] or ch in col[j] or ch in sudoku[sq]:
return False
row[i].add(ch)
col[j].add(ch)
sudoku[sq].add(ch)
return True
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
# row = defaultdict(set)
col = defaultdict(set)
sudoku = defaultdict(set)
for i in range(9):
row = set()
for j in range(9):
ch = board[i][j]
if ch == '.': continue
sq = i // 3 * 3 + j // 3
if ch in row or ch in col[j] or ch in sudoku[sq]:
return False
row.add(ch)
col[j].add(ch)
sudoku[sq].add(ch)
return True
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
sudoku = defaultdict(set)
for i in range(9):
row = set()
col = set()
for j in range(9):
ch = board[i][j]
c = board[j][i]
sq = i // 3 * 3 + j // 3
if ch != '.':
if ch in row or ch in sudoku[sq]:
return False
else:
row.add(ch)
sudoku[sq].add(ch)
if c != '.':
if c in col:
return False
else:
col.add(c)
return True
37. 解数独
38. 外观数列
class Solution:
def countAndSay(self, n: int) -> str:
prev = '1x' # x 哨兵
for _ in range(n-1):
cur, start = '', 0
for i in range(1, len(prev)):
if prev[i] != prev[start]:
cur += str(i- start) + prev[start]
start = i
prev = cur + 'x'
return prev[:-1]