一、链表

1.1、总结一些常见的链表操作

1.1.1、链表翻转

def reverse(self, l: ListNode) -> ListNode:
# 链表翻转
pre, cur = None, l
while cur:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
return pre

1.1.2、找到链表的中间节点/将链表分割为两部分

def split(self, head : ListNode) -> ListNode:
# 将链表从中间划分为两部分
slow, fast = head, head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
post_list = slow.next
slow.next = None
return post_list

1.1.3、合并两个有序链表

def merge(self, head1: ListNode, head2: ListNode) -> ListNode:
# 合并两个已排序链表
dummy = ListNode(-1, None)
p = dummy
p1, p2 = head1, head2
while p1 and p2:
if p1.val <= p2.val:
p.next = p1
p = p1
p1 = p1.next
else:
p.next = p2
p = p2
p2 = p2.next
if p1:
p.next = p1
if p2:
p.next = p2
return dummy.next

1.2、总结一些注意事项

1、求链表的中间节点后者求链表的倒数第k个节点，都是用快慢指针来解决；
2、链表排序，一般使用归并排序来解决；
3、如果操作可能会改变链表的表头，应该声明指向链表head的dummy节点，最后返回dummy.next；

1.3、题目汇总（按出现频率）

1.3.1、剑指 Offer II 025. 链表中的两数相加

剑指 Offer II 025. 链表中的两数相加.

# Definition for singly-linked list.
# class ListNode:
#
def __init__(self, val=0, next=None):
#
self.val = val
#
self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
l1 = self.reverse(l1)
l2 = self.reverse(l2)
p1, p2 = l1, l2
while p1:
if p2:
p1.val += p2.val
p2 = p2.next
if not p1.next:
p1.next = p2
break
p1 = p1.next
l1 = self.carry(l1)
l1 = self.reverse(l1)
return l1
def reverse(self, l: ListNode) -> ListNode:
# 链表翻转
pre, cur = None, l
while cur:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
return pre
def carry(self, l: ListNode) -> ListNode:
# 进位
p = l
while p:
if p.val >= 10:
if not p.next:
# 末位进位
p.next = ListNode(0)
p.next.val += 1
# 正常位进位
p.val %= 10
p = p.next
return l

1.3.2、剑指 Offer II 024. 反转链表

剑指 Offer II 024. 反转链表.

# 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 = head
while cur:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
return pre

1.3.3、剑指 Offer II 026. 重排链表

剑指 Offer II 026. 重排链表.

# Definition for singly-linked list.
# class ListNode:
#
def __init__(self, val=0, next=None):
#
self.val = val
#
self.next = next
class Solution:
def reorderList(self, head: ListNode) -> None:
l1, l2 = self.midNode(head)
l2 = self.reverse(l2)
l1 = self.merge(l1, l2)
def midNode(self, head: ListNode) -> ListNode:
# 返回链表中间元素/将链表从中间分为两个链表
slow, fast = head, head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# 如果是奇数链表 返回中间元素后一个元素
return slow返回中间元素

midN = slow.next
slow.next = None
return head, midN
def reverse(self, head: ListNode) -> ListNode:
# 链表翻转
pre = None
cur = head
while cur:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
return pre
def merge(self, l1: ListNode, l2: ListNode) -> ListNode:
# 合并两个链表（len(l1)>=len(l2)） 
head = l1
while l1 and l2:
l1_temp, l2_temp = l1.next, l2.next
l1.next = l2
l1 = l1_temp
l2.next = l1
l2 = l2_temp
return head

1.3.4、剑指 Offer II 021. 删除链表的倒数第 n 个结点

剑指 Offer II 021. 删除链表的倒数第 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(-1, head)
slow, fast = dummy, head
for i in range(n):
# 快指针先走n步
fast = fast.next
# 再快慢指针一起走 直到快指针走到链表末尾 此时慢指针刚好走到倒数第n个节点前一个节点
while fast:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return dummy.next

1.3.5、剑指 Offer II 027. 回文链表

剑指 Offer II 027. 回文链表.

# Definition for singly-linked list.
# class ListNode:
#
def __init__(self, val=0, next=None):
#
self.val = val
#
self.next = next
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
# 方法一、数组存储 时间O(n)
空间O(n)
# mapp = []
# while head:
#
mapp.append(head.val)
#
head = head.next
# return mapp == mapp[::-1]
# 方法二、快慢指针切割 + 翻转 + 比较
时间O(n)
空间O(1)
pre_list, post_list = self.find_pre_post_list(head)
reverse_post_list = self.reverse(post_list)
p1, p2 = pre_list, reverse_post_list
# 比较两个链表是否相同 且 len(pre_list) >= len(reverse_post_list)
while p1 and p2:
if p1.val != p2.val:
return False
p1 = p1.next
p2 = p2.next
return True
# 快慢指针找到链表的中心节点 并将链表按中心节点切割为前后两个链表 
# 偶数：前后链表长度相等
奇数：前链表长度大于后链表
def find_pre_post_list(self, head: ListNode) -> ListNode:
slow, fast = head, head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
post_list = slow.next
slow.next = None
pre_list = head
return pre_list, post_list
# 翻转单链表
def reverse(self, head: ListNode) -> ListNode:
pre = None
cur = head
while cur:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
return pre

1.3.6、剑指 Offer II 077. 链表排序

剑指 Offer II 077. 链表排序.

# Definition for singly-linked list.
# class ListNode:
#
def __init__(self, val=0, next=None):
#
self.val = val
#
self.next = next
class Solution:
def sortList(self, head: ListNode) -> ListNode:
# 归并排序
时间O(nlogn)，空间O(logn)
if not head or not head.next: return head
post_list = self.split(head)
head = self.sortList(head)
post_list = self.sortList(post_list)
return self.merge(head, post_list)
def split(self, head : ListNode) -> ListNode:
# 将链表从中间划分为两部分
slow, fast = head, head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
post_list = slow.next
slow.next = None
return post_list
def merge(self, head1: ListNode, head2: ListNode) -> ListNode:
# 合并两个已排序链表
dummy = ListNode(-1, None)
p = dummy
p1, p2 = head1, head2
while p1 and p2:
if p1.val <= p2.val:
p.next = p1
p = p1
p1 = p1.next
else:
p.next = p2
p = p2
p2 = p2.next
if p1:
p.next = p1
if p2:
p.next = p2
return dummy.next

1.3.7、剑指 Offer II 022. 链表中环的入口节点

剑指 Offer II 022. 链表中环的入口节点.

"""
# 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:
# 快慢指针
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return None

1.3.8、剑指 Offer II 078. 合并排序链表

剑指 Offer II 078. 合并排序链表.

# Definition for singly-linked list.
# class ListNode:
#
def __init__(self, val=0, next=None):
#
self.val = val
#
self.next = next
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
# 方法一、两两合并
k-1次合并
# if len(lists) == 0: return None
# head = lists[0]
# for i in range(1, len(lists)):
#
if lists[i]:
#
head = self.merge(head, lists[i])
# return head
# 方法一、分治法 将k个链表两两合并成k/2个，再将k/2个链表两两合并成k/4个，循环直至合成1个链表
log(k)次合并
# 递归终止条件 当lists中小于两个的时候 无法拆分 返回 
if len(lists) == 0: return None
if len(lists) == 1: return lists[0]
mid = len(lists) // 2
L = self.mergeKLists(lists[:mid])
R = self.mergeKLists(lists[mid:])
return self.merge(L, R)
def merge(self, head1: ListNode, head2: ListNode) -> ListNode:
# 合并两个升序链表
dummy = ListNode(-1, None)
p = dummy
p1, p2 = head1, head2
while p1 and p2:
if p1.val <= p2.val:
p.next = p1
p = p1
p1 = p1.next
else:
p.next = p2
p = p2
p2 = p2.next
if p1:
p.next = p1
if p2:
p.next = p2
return dummy.next

1.3.9、剑指 Offer II 023. 两个链表的第一个重合节点

剑指 Offer II 023. 两个链表的第一个重合节点.

# Definition for singly-linked list.
# class ListNode:
#
def __init__(self, x):
#
self.val = x
#
self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
if not headA or not headB: return None
pa, pb = headA, headB
while pa != pb:
if not pa:
pa = headB
else:
pa = pa.next
if not pb:
pb = headA
else:
pb = pb.next
return pa

1.3.10、剑指 Offer II 029. 排序的循环链表

剑指 Offer II 029. 排序的循环链表.

"""
# Definition for a Node.
class Node:
def __init__(self, val=None, next=None):
self.val = val
self.next = next
"""
class Solution:
def insert(self, head: 'Node', insertVal: int) -> 'Node':
# 情况1：head=[1,2,5]
insertVal=2~5 包括2、5
# 情况2：head=[3,5,2]
insertVal=(>5 or <2)
# 情况3：head=[2,3,4]
insertVal=(<=2 or >=4)

if not head:
newNode = Node(insertVal)
newNode.next = newNode
return newNode
pre, p = head, head.next
while p != head:
# 情况1 + 情况2
if (pre.val <= insertVal and insertVal <= p.val) or
(pre.val > p.val and (insertVal<p.val or insertVal>pre.val)):
pre.next = Node(insertVal, p)
return head
pre = p
p = p.next
# 情况3
pre.next = Node(insertVal, p)
return head

其他题目

这两道题个人认为目前做的意义不大，先记录一下，后面可能会解决：

1.3.11、剑指 Offer II 028. 展平多级双向链表（经典）

剑指 Offer II 028. 展平多级双向链表.

视频讲解.

"""
# Definition for a Node.
class Node:
def __init__(self, val, prev, next, child):
self.val = val
self.prev = prev
self.next = next
self.child = child
"""
class Solution:
def flatten(self, head: 'Node') -> 'Node':
if not head: return None
cur_node = head
while cur_node:
if cur_node.child:
next_node = cur_node.next
cur_node.next = cur_node.child
cur_node.next.prev = cur_node
cur_node.child = None
child_node = cur_node.next
end_child_node = None
while child_node:
end_child_node = child_node
child_node = child_node.next
end_child_node.next = next_node
if next_node: next_node.prev = end_child_node
cur_node = cur_node.next
return head

1.3.12、剑指 Offer II 031. 最近最少使用缓存（经典 hashMap+双向链表）

剑指 Offer II 031. 最近最少使用缓存.

class ListNode:
def __init__(self, key, val):
self.key = key
self.val = val
self.pre = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.curSize = 0
# 构建hashmap
# key: key
val: ListNone 
self.ListNodeMap = dict()
# 初始化双向链表 首位节点都为空且相连
self.head = ListNode(-1, -1)
self.tail = ListNode(-1, -1)
self.head.next = self.tail
self.tail.next = self.head
def get(self, key: int) -> int:
if key in self.ListNodeMap:
node = self.ListNodeMap[key]
self.moveToHead(node)
return node.val
else:
return -1
def put(self, key: int, value: int) -> None:
if key in self.ListNodeMap:
node = self.ListNodeMap[key]
node.val = value
self.moveToHead(node)
else:
curNode = ListNode(key, value)
self.ListNodeMap[key] = curNode
self.addToHead(curNode)
def moveToHead(self, node):
# remove from cur pos
node.pre.next = node.next
node.next.pre = node.pre
# insert node into head pre
node.next = self.head.next
self.head.next.pre = node
self.head.next = node
node.pre = self.head
def addToHead(self, node):
self.curSize += 1
node.next = self.head.next
self.head.next.pre = node
self.head.next = node
node.pre = self.head
if self.curSize > self.capacity:
delete_node = self.tail.pre
temp_node = self.tail.pre.pre
temp_node.next = self.tail
self.tail.pre = temp_node
self.curSize -= 1
self.ListNodeMap.pop(delete_node.key)
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

二、树

2.1、一些模板

2.1.1、前序遍历

递归式写法：

# Definition for a binary tree node.
# class TreeNode(object):
#
def __init__(self, val=0, left=None, right=None):
#
self.val = val
#
self.left = left
#
self.right = right
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
def dfs(root):
if not root: return
res.append(root.val)
dfs(root.left)
dfs(root.right)
dfs(root)
return res

迭代式写法：

# Definition for a binary tree node.
# class TreeNode(object):
#
def __init__(self, val=0, left=None, right=None):
#
self.val = val
#
self.left = left
#
self.right = right
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
stack, cur = [], root
while stack or cur:
while cur:
stack.append(cur)
res.append(cur.val)
cur = cur.left
cur = stack.pop()
cur = cur.right
return res

2.1.2、中序遍历

递归式写法：

# Definition for a binary tree node.
# class TreeNode(object):
#
def __init__(self, val=0, left=None, right=None):
#
self.val = val
#
self.left = left
#
self.right = right
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
def dfs(root):
if not root: return
dfs(root.left)
res.append(root.val)
dfs(root.right)
dfs(root)
return res

迭代式写法：

# Definition for a binary tree node.
# class TreeNode(object):
#
def __init__(self, val=0, left=None, right=None):
#
self.val = val
#
self.left = left
#
self.right = right
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
stack, cur = [], root
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res

2.1.3、后序遍历

递归式写法：

# Definition for a binary tree node.
# class TreeNode(object):
#
def __init__(self, val=0, left=None, right=None):
#
self.val = val
#
self.left = left
#
self.right = right
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
def dfs(root):
if not root: return
dfs(root.left)
dfs(root.right)
res.append(root.val)
dfs(root)
return res

迭代式写法：

# Definition for a binary tree node.
# class TreeNode(object):
#
def __init__(self, val=0, left=None, right=None):
#
self.val = val
#
self.left = left
#
self.right = right
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
stack, cur = [], root
while stack or cur:
while cur:
stack.append(cur)
res.append(cur.val)
cur = cur.right
cur = stack.pop()
cur = cur.left
return res[::-1]

2.1.4、层次遍历

一层一层输出：[ [3]，[9，20]，[15，7] ]

# Definition for a binary tree node.
# class TreeNode:
#
def __init__(self, val=0, left=None, right=None):
#
self.val = val
#
self.left = left
#
self.right = right
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
res, queue = [], [root]
while queue:
arr, size = [], len(queue)
while size:
cur = queue.pop(0)
arr.append(cur.val)
if cur.left: queue.append(cur.left)
if cur.right: queue.append(cur.right)
size -= 1
res.append(arr)
return res

简化版输出：[3, 9, 20, 15, 7]

# Definition for a binary tree node.
# class TreeNode:
#
def __init__(self, val=0, left=None, right=None):
#
self.val = val
#
self.left = left
#
self.right = right
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
res, queue = [], [root]
while queue:
cur = queue.pop(0)
res.append(cur.val)
if cur.left: queue.append(cur.left)
if cur.right: queue.append(cur.right)
return res

2.1.5、二叉搜索树

性质：
1、左子树上所有节点的值均小于它的根节点
2、 右子树上所有节点的值均大于它的根节点
3、左右子树也分别是二叉搜索树

二叉搜索树中序遍历=排序

2.2、题目汇总（按出现频率）

2.2.1、剑指 Offer II 044. 二叉树每层的最大值（层次）

剑指 Offer II 044. 二叉树每层的最大值.

# Definition for a binary tree node.
# class TreeNode:
#
def __init__(self, val=0, left=None, right=None):
#
self.val = val
#
self.left = left
#
self.right = right
class Solution:
def largestValues(self, root: TreeNode) -> List[int]:
if not root: return []
res, queue = [], [root]
while queue:
maxValue, size = float('-inf'), len(queue)
while size:
cur = queue.pop(0)
if cur.val > maxValue: maxValue = cur.val
if cur.left: queue.append(cur.left)
if cur.right: queue.append(cur.right)
size -= 1
res.append(maxValue)
return res

2.2.2、剑指 Offer II 046. 二叉树的右侧视图（层次）

剑指 Offer II 046. 二叉树的右侧视图.

# Definition for a binary tree node.
# class TreeNode:
#
def __init__(self, val=0, left=None, right=None):
#
self.val = val
#
self.left = left
#
self.right = right
class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
if not root: return []
res, queue = [], [root]
while queue:
size = len(queue)
while size:
cur = queue.pop(0)
if size == 1:
res.append(cur.val)
if cur.left: queue.append(cur.left)
if cur.right: queue.append(cur.right)
size -= 1
return res

2.2.3、剑指 Offer II 047. 二叉树剪枝（后序）

剑指 Offer II 047. 二叉树剪枝.

# Definition for a binary tree node.
# class TreeNode:
#
def __init__(self, val=0, left=None, right=None):
#
self.val = val
#
self.left = left
#
self.right = right
class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
if not root: return []
res, queue = [], [root]
while queue:
size = len(queue)
while size:
cur = queue.pop(0)
if size == 1:
res.append(cur.val)
if cur.left: queue.append(cur.left)
if cur.right: queue.append(cur.right)
size -= 1
return res

2.2.4、剑指 Offer II 056. 二叉搜索树中两个节点之和（二叉搜索树+中序遍历）

剑指 Offer II 056. 二叉搜索树中两个节点之和.

# Definition for a binary tree node.
# class TreeNode:
#
def __init__(self, val=0, left=None, right=None):
#
self.val = val
#
self.left = left
#
self.right = right
class Solution:
def findTarget(self, root: TreeNode, k: int) -> bool:
if not root: return False
res = []
def dfs(root):
if not root: return None
dfs(root.left)
res.append(root.val)
dfs(root.right)
dfs(root)
left, right = 0, len(res) - 1
while left < right:
if res[left] + res[right] == k: return True
elif res[left] + res[right] < k: left += 1
else: right -= 1
return False

2.2.5、剑指 Offer II 049. 从根节点到叶节点的路径数字之和

剑指 Offer II 049. 从根节点到叶节点的路径数字之和.

# Definition for a binary tree node.
# class TreeNode:
#
def __init__(self, val=0, left=None, right=None):
#
self.val = val
#
self.left = left
#
self.right = right
class Solution:
def sumNumbers(self, root: TreeNode) -> int:
if not root: return 0
res = 0
def dfs(node, path_sum):
nonlocal res
if not node: return None
if not node.left and not node.right:
res += path_sum * 10 + node.val
dfs(node.left, path_sum * 10 + node.val)
dfs(node.right, path_sum * 10 + node.val)
dfs(root, 0)
return res

2.2.6、剑指 Offer II 050. 向下的路径节点之和（前序 / 前缀和？）

剑指 Offer II 050. 向下的路径节点之和.

# Definition for a binary tree node.
# class TreeNode:
#
def __init__(self, val=0, left=None, right=None):
#
self.val = val
#
self.left = left
#
self.right = right
class Solution:
def pathSum(self, root: TreeNode, targetSum: int) -> int:
# 求整棵树符合条件的个数
if not root: return 0
def dfs(node, path_sum):
# 求以当前节点为根节点的树有几个符合条件
if not node: return 0
ret = 0
if path_sum + node.val == targetSum: ret += 1
ret += dfs(node.left, path_sum + node.val)
ret += dfs(node.right, path_sum + node.val)
return ret
res = 0
res += dfs(root, 0)
res += self.pathSum(root.left, targetSum)
res += self.pathSum(root.right, targetSum)
return res

2.2.7、剑指 Offer II 051. 节点之和最大的路径（后序）

剑指 Offer II 051. 节点之和最大的路径.

# Definition for a binary tree node.
# class TreeNode:
#
def __init__(self, val=0, left=None, right=None):
#
self.val = val
#
self.left = left
#
self.right = right
# 这道题要考虑清楚：1、更新最大路径和需要比较什么？
#
2、往上走需要比较什么？
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
self.maxValue = float('-inf')
def dfs(node):
if not node: return 0
left_max = max(dfs(node.left), 0)
# 当前节点左子树最大路径和
right_max = max(dfs(node.right), 0)
# 当前节点右子树最大路径和
node_max = left_max + right_max + node.val
# 当前节点为根节点的子树最大路径和
self.maxValue = max(self.maxValue, node_max)
# 用当前节点为根节点的子树最大路径和挑战最大值
# 当前节点比较完毕 要往上走 需要返回当前子树的最大路径和（往上走的 node.val+left/right）
ret = max(max(left_max, right_max) + node.val, 0)
return ret
dfs(root)
return self.maxValue

2.2.8、剑指 Offer II 053. 二叉搜索树中的中序后继(迭代中序)

剑指 Offer II 053. 二叉搜索树中的中序后继.

# Definition for a binary tree node.
# class TreeNode:
#
def __init__(self, x):
#
self.val = x
#
self.left = None
#
self.right = None
class Solution:
def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
stack, cur = [], root
pre = None
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
if pre == p: return cur
pre = cur
cur = cur.right

2.2.9、剑指 Offer II 045. 二叉树最底层最左边的值（层次/前序）

剑指 Offer II 045. 二叉树最底层最左边的值.

# Definition for a binary tree node.
# class TreeNode:
#
def __init__(self, val=0, left=None, right=None):
#
self.val = val
#
self.left = left
#
self.right = right
class Solution:
def findBottomLeftValue(self, root: TreeNode) -> int:
# 法一、层次遍历
时O(n)
空间O(1)
res, queue = float('-inf'), [root]
while queue:
size = len(queue)
for i in range(size):
cur = queue.pop(0)
if i == 0: res = cur.val
if cur.left: queue.append(cur.left)
if cur.right: queue.append(cur.right)
return res
# 法二、前序
类似求树的最大深度
if not root.left and not root.right: return root.val
maxDepth = 1
res = float('-inf')
def dfs(node, curDepth):
nonlocal maxDepth
nonlocal res
if not node: return
if not node.left and not node.right and curDepth > maxDepth:
maxDepth = curDepth
res = node.val
dfs(node.left, curDepth+1)
dfs(node.right, curDepth+1)
dfs(root, 1)
return res

2.2.10、剑指 Offer II 054. 所有大于等于节点的值之和（二叉搜索树+反中序）

剑指 Offer II 054. 所有大于等于节点的值之和.

# Definition for a binary tree node.
# class TreeNode:
#
def __init__(self, val=0, left=None, right=None):
#
self.val = val
#
self.left = left
#
self.right = right
class Solution:
def convertBST(self, root: TreeNode) -> TreeNode:
cur_sum = 0
def dfs(node):
nonlocal cur_sum
if not node: return
dfs(node.right)
cur_sum += node.val
node.val = cur_sum
dfs(node.left)
dfs(root)
return root

2.2.11、剑指 Offer II 052. 展平二叉搜索树（中序二叉搜索树）

注意：python当中树的题目最好不要有太多的指针指向操作，可能会超时。

剑指 Offer II 052. 展平二叉搜索树.

# Definition for a binary tree node.
# class TreeNode:
#
def __init__(self, val=0, left=None, right=None):
#
self.val = val
#
self.left = left
#
self.right = right
class Solution:
def increasingBST(self, root: TreeNode) -> TreeNode:
# 1、中序遍历 存储顺序节点 再创建展平搜索树
时间O(n) 空间O(n)
if not root: return None
res = []
def dfs(node):
if not node: return
dfs(node.left)
node.left = None
# 这里如果删除 就会超时 
res.append(node)
dfs(node.right)
dfs(root)
dummy = TreeNode(-1)
cur = dummy
for i in range(len(res)):
cur.right = res[i]
cur.left = None
cur = res[i]
return dummy.right
# 2、中序遍历 边遍历边创建展平搜索树
if not root: return None
dummy = TreeNode(-1)
pre = dummy
def dfs(node):
if not node: return
nonlocal pre
dfs(node.left)
# pre.right = node
# 这样写会超时
# pre.left = None
# pre = None
pre.right = TreeNode(node.val)
# 注意这里要直接创建
如果用指针指向就会超时
pre = pre.right
dfs(node.right)
dfs(root)
return dummy.right

其他题目

下面是一些关于定义类的树题目，先记录一下，后面可能会解决：

2.2.12、剑指 Offer II 043. 往完全二叉树添加节点（层次遍历）

剑指 Offer II 043. 往完全二叉树添加节点.

视频讲解.

# Definition for a binary tree node.
# class TreeNode:
#
def __init__(self, val=0, left=None, right=None):
#
self.val = val
#
self.left = left
#
self.right = right
class CBTInserter:
def __init__(self, root: TreeNode):
self.root = root
self.parentQueue = []
# 存放可以插入的父亲元素（左节点为空或右节点为空）
queue = []
queue.append(root)
while queue:
cur = queue.pop(0)
# 找到了一个可以插入的节点
if not cur.left or not cur.right: self.parentQueue.append(cur)
if cur.left: queue.append(cur.left)
if cur.right: queue.append(cur.right)
def insert(self, v: int) -> int:
parentNode = self.parentQueue[0]
curNode = TreeNode(v)
if not parentNode.left:
parentNode.left = curNode
else:
parentNode.right = curNode
# 注意这里要检测完right之后才能pop出这个节点
self.parentQueue.pop(0)
self.parentQueue.append(curNode)
return parentNode.val
def get_root(self) -> TreeNode:
return self.roo

2.2.13、剑指 Offer II 048. 序列化与反序列化二叉树（经典）

剑指 Offer II 048. 序列化与反序列化二叉树.

视频讲解.

# Definition for a binary tree node.
# class TreeNode(object):
#
def __init__(self, x):
#
self.val = x
#
self.left = None
#
self.right = None
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
res = []
def dfs(node):
if not node: res.append('#')
else:
res.append(str(node.val))
dfs(node.left)
dfs(node.right)
dfs(root)
return ' '.join(res)
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
data = list(data.split(' '))
def dfs():
if data[0] == '#':
data.pop(0)
return None
else:
cur = TreeNode(str(data.pop(0)))
cur.left = dfs()
cur.right = dfs()
return cur
return dfs()

2.2.14、剑指 Offer II 055. 二叉搜索树迭代器（经典）

剑指 Offer II 055. 二叉搜索树迭代器.（经典）

视频讲解.

# Definition for a binary tree node.
# class TreeNode:
#
def __init__(self, val=0, left=None, right=None):
#
self.val = val
#
self.left = left
#
self.right = right
# 二叉树中序遍历迭代式写法
# def preorderTraversal(self, root):
#
res = []
#
stack, cur = [], root
#
while stack or cur:
#
while cur:
#
stack.append(cur)
#
cur = cur.left
#
cur = stack.pop()
#
res.append(cur.val)
#
cur = cur.right
#
return res
class BSTIterator:
def __init__(self, root: TreeNode):
self.stack = []
# 走到树的最左边节点
self.pushTowardLeft(root)
def next(self) -> int:
if not self.stack: return False
curNode = self.stack.pop()
val = curNode.val
# 走到curNode.right这颗子树的最左边节点
self.pushTowardLeft(curNode.right)
return val
def hasNext(self) -> bool:
return len(self.stack) > 0
def pushTowardLeft(self, node):
while node:
self.stack.append(node)
node = node.left

三、搜索：回溯+DFS+BFS

3.1、回溯(不包括树)

3.1.1、模板

回顾下多叉树的遍历模板：

def dfs(root):
if not root: return
for child in root.children：
dfs(child )

回溯算法的模板和多叉树的遍历模板很相似

result= []
def backtracking(路径, 选择列表):
if(满足终止条件):
result.append(路径)
# 收集结果
return
for 选择 in 选择列表:
做选择
backtracking(路径, 选择列表)
回溯操作/撤销操作

组合类问题：

子集类问题：

1. [1, 2, 3]

3.1.2、题目汇总

3.1.2.1、剑指 Offer II 079. 所有子集（子集）

剑指 Offer II 079. 所有子集.

class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
if not nums: return []
def dfs(start_index, path, res):
if path not in res:
res.append(copy.deepcopy(path))
# 这里还要向下遍历 所以先不return
for i in range(start_index, len(nums)):
path.append(nums[i])
dfs(i+1, path, res)
path.pop()
start_index = 0
path, res = [], []
dfs(start_index, path, res)
return res

3.1.2.2、剑指 Offer II 080. 含有 k 个元素的组合（组合）

剑指 Offer II 080. 含有 k 个元素的组合.

class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
if not n or not k: return []
def dfs(start, path, res, target):
if target == 0:
# 这里找到符合的之后不需要再往下遍历了 后续肯定不符合
res.append(copy.deepcopy(path))
return
for i in range(start, n+1):
if target > 0:
path.append(i)
dfs(i+1, path, res, target-1)
path.pop()
start = 1
path, res = [], []
dfs(start, path, res, k)
return res

3.1.2.3、剑指 Offer II 081. 允许重复选择元素的组合（组合）

剑指 Offer II 081. 允许重复选择元素的组合.

class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
if not candidates: return []
def dfs(start_index, path, res, target):
if target == 0:
res.append(copy.deepcopy(path))
return
for i in range(start_index, len(candidates)):
if candidates[i] <= target:
# or target>0
但是这样会有冗余的dfs
path.append(candidates[i])
# 对于无重复数字的数组
# 如果同一个数字可以重复使用 那么传入下一层的start_index=i
# 如果同一个数字不允重复使用 那么传入下一层的start_index=i+1
dfs(i, path, res, target-candidates[i])
path.pop()
start_index = 0
path, res = [], []
dfs(start_index, path, res, target)
return res

3.1.2.4、剑指 Offer II 082. 含有重复元素集合的组合（难 经典 组合）

剑指 Offer II 082. 含有重复元素集合的组合.

class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
# 可能含有重复数字的数组

# 每个数字只能在每个组合中用一次
# 有重复数字的不重复组合 先排序
if not candidates: return []
def dfs(start_index, path, res, target):
if target == 0:
res.append(copy.deepcopy(path))
return
for i in range(start_index, len(candidates)):
# 剪枝1：如果当前数大于target，就不需要再往下走了
if candidates[i] <= target:
# 剪枝2 如果当前层有两一样的数 直接跳过后面那个数 因为前面一个执行过了（避免同一层遍历两个相同的数）
# i == start_index 说明是进入当前层的第一个元素 马上就会执行dfs进入一层了
# 当进入到最底层，再回溯重新进入当前层的时候 才会i>start_index 
if i>start_index and candidates[i]==candidates[i-1]: continue
path.append(candidates[i])
# 进入下一层 当前数字已经执行过了 直接从i+1开始执行就好了
dfs(i+1, path, res, target-candidates[i])
path.pop()
candidates.sort()
start_index = 0
path, res = [], []
dfs(start_index, path, res, target)
return res

3.1.2.5、剑指 Offer II 083. 没有重复元素集合的全排列（排列）

剑指 Offer II 083. 没有重复元素集合的全排列.

 # 不含重复元素的数组进行全排列
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
if not nums: return []
def dfs(path, res):
if path not in res and len(path) == len(nums):
res.append(copy.deepcopy(path))
return
for i in range(len(nums)):
if nums[i] not in path:
path.append(nums[i])
dfs(path, res)
path.pop()
path, res = [], []
dfs(path, res)
return res

3.1.2.6、剑指 Offer II 084. 含有重复元素集合的全排列 （难 经典 排列）

剑指 Offer II 084. 含有重复元素集合的全排列 .

class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
# 含有重复元素的集合进行全排列
[1,2,2,3]
# 当前层不可以使用重复的数字且每个元素仅可以使用1次
[1,2(idx=1),3] [1,2(idx=2),3] 
# 下一层可以使用重复的数字每个元素仅能使用1次
[1,2(idx=1),2(idx=2)]
if not nums: return []
def dfs(path, res, used):
if path not in res and len(path) == len(nums):
res.append(copy.deepcopy(path))
return
for i in range(len(nums)):
if used[i] == 1: continue
path.append(nums[i])
used[i] = 1
dfs(path, res, used)
path.pop()
used[i] = 0
path, res = [], []
used = [0 for i in range(len(nums))]
nums.sort()
dfs(path, res, used)
return res

3.1.2.7、剑指 Offer II 085. 生成匹配的括号（经典 难）

剑指 Offer II 085. 生成匹配的括号 .

class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def dfs(left, right, cur_str, n, res):
if left == n and right == n:
# 满足条件 加入res
res.append(cur_str)
return
if left < n:
# 遍历当前层 相当于模板中的for
dfs(left+1, right, cur_str+'(', n, res)
if left > right:
dfs(left, right+1, cur_str+')', n, res)
cur_str = ""
# 当前字符
left = 0
# 当前字符左括号个数
right = 0
# 当前字符串右括号个数
res = []
# 存放所有满足条件的字符串
dfs(left, right, cur_str, n, res)
return res

3.1.2.8、剑指 Offer II 086. 分割回文子字符串（切割）

剑指 Offer II 086. 分割回文子字符串.

class Solution:
def partition(self, s: str) -> List[List[str]]:
if not s: return []
def dfs(start_index, path, res):
if start_index == len(s):
res.append(path[::])
return
for i in range(start_index, len(s)):
# start~i 是当前层取的字符串
if s[start_index:i+1] == s[start_index: i+1][::-1]:
# if check(start_index, i):
path.append(s[start_index:i+1])
dfs(i+1, path, res)
path.pop()
start_index = 0
path, res = [], []
dfs(start_index, path, res)
return res

3.1.2.9、剑指 Offer II 087. 复原 IP （经典 切割）

剑指 Offer II 087. 复原 IP .

class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
if len(s) > 12 or len(s) < 4: return []
# 不加会超时
def isMeeting(s):
# 不满足的情况
# 1、长度<1 或者 长度>3
# 2、长度不为1 且 开头第一个字符是0
# 3、长度=3 且 数字>255
if len(s) < 1 or len(s) > 3: return False
if len(s) != 1 and s[0] == '0': return False
if len(s) == 3:
count = int(s[0]) * 100 + int(s[1]) * 10 + int(s[2])
if count > 255: return False
return True
def dfs(start_index, path, res):
if len(path) == 3 and isMeeting(s[start_index:]):
res.append('.'.join(path + [s[start_index:]]))
return
for i in range(start_index, len(s)):
if isMeeting(s[start_index: i+1]):
path.append(s[start_index: i+1])
dfs(i+1, path, res)
path.pop()
path, res = [], []
dfs(0, path, res)
return res

3.1.2.10、剑指 Offer II 102. 加减的目标值（适合dp）

剑指 Offer II 102. 加减的目标值 .

# 回溯写法1、超时
这种写法相当于建一个二叉树，每个分支都会走到叶子节点
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
self.res = 0
if not nums: return 0
def dfs(cur_index, path_sum):
if cur_index == len(nums):
if path_sum == target:
self.res += 1
return
dfs(cur_index+1, path_sum+nums[cur_index])
dfs(cur_index+1, path_sum-nums[cur_index])
cur_index = 0
path_sum = 0
dfs(cur_index, path_sum)
return self.res
# 回溯写法2、不超时
这种写法相当于建立一个二叉树当前节点的值等于左节点的值+右节点的值 不会还是会走到叶子节点
但是我们可以用一个字典来记录每个节点的值 这样避免大量重复计算
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
mapp = {}
def solve(index, target):
if (index, target) in mapp:
return mapp[(index, target)]
if index == len(nums):
if target == 0: return 1
return 0
one = solve(index+1, target-nums[index])
two = solve(index+1, target+nums[index])
mapp[(index, target)] = one + two
return one + two
return solve(0, target)

3.1.2.11、剑指 Offer II 051. 节点之和最大的路径

剑指 Offer II 051. 节点之和最大的路径

# Definition for a binary tree node.
# class TreeNode:
#
def __init__(self, val=0, left=None, right=None):
#
self.val = val
#
self.left = left
#
self.right = right
# 这道题要考虑清楚：1、更新最大路径和需要比较什么？
#
2、往上走需要比较什么？
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
self.maxValue = float('-inf')
def dfs(node):
if not node: return 0
left_max = max(dfs(node.left), 0)
# 当前节点左子树最大路径和
right_max = max(dfs(node.right), 0)
# 当前节点右子树最大路径和
node_max = left_max + right_max + node.val
# 当前节点为根节点的子树最大路径和
self.maxValue = max(self.maxValue, node_max)
# 用当前节点为根节点的子树最大路径和挑战最大值
# 当前节点比较完毕 要往上走 需要返回当前子树的最大路径和（往上走的 node.val+left/right）
ret = max(max(left_max, right_max) + node.val, 0)
return ret
dfs(root)
return self.maxValue

3.2、DFS

3.2.1、模板

在这里插入代码片

3.2.2、题目汇总

3.2.2.1、剑指 Offer II 105. 岛屿的最大面积（二维矩阵）

剑指 Offer II 105. 岛屿的最大面积.

class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
row, col = len(grid), len(grid[0])
if row == 0 or col == 0: return 0
maxArea = 0
def dfs(i, j):
if not 0<=i<row or not 0<=j<col or grid[i][j] == 0: return
self.curArea += 1
grid[i][j] = 0
dfs(i-1, j)
dfs(i+1, j)
dfs(i, j-1)
dfs(i, j+1)
for i in range(row):
for j in range(col):
if grid[i][j] == 1:
self.curArea = 0
dfs(i, j)
if self.curArea > maxArea:
maxArea = self.curArea
return maxArea

3.2.2.2、剑指 Offer II 110. 所有路径（二维矩阵）

剑指 Offer II 110. 所有路径.

class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
path, res = [0], []
def dfs(x):
if x == len(graph)-1:
res.append(path[:])
return
for y in graph[x]:
path.append(y)
dfs(y)
path.pop()
dfs(0)
return res

3.2.2.3、剑指 Offer II 116. 省份数量（二维矩阵）

剑指 Offer II 116. 省份数量.

class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
visited = []
res = 0
def dfs(i):
for j in range(len(isConnected)):
if isConnected[i][j] == 1 and j not in visited:
visited.append(j)
dfs(j)
for i in range(len(isConnected)):
if i not in visited:
res += 1
visited.append(i)
dfs(i)
return res

3.2.2.4、剑指 Offer II 106. 二分图（图）

剑指 Offer II 106. 二分图.

3.3、BFS(不包括树)

3.3.1、模板

在这里插入代码片

3.3.2、题目汇总

四、双指针+二分查找

两者的区别：双指针这里总结的题都是前后一个个移动的，时间复杂度为O(n)；而二分总结的题都是用mid来实现的，时间复杂度为O(logn)

4.1、双指针

4.1.1、题目汇总

4.1.1.1、剑指 Offer II 006. 排序数组中两个数字之和

剑指 Offer II 006. 排序数组中两个数字之和.

class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left, right = 0, len(numbers) - 1
while left < right:
cur_sum = numbers[left] + numbers[right]
if cur_sum == target:
return [left, right]
elif cur_sum > target:
right -= 1
else:
left += 1
return []

4.1.1.2、剑指 Offer II 007. 数组中和为 0 的三个数

剑指 Offer II 007. 数组中和为 0 的三个数.

class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if not nums: return []
nums.sort()
res = []
for i in range(len(nums)-2):
target = 0 - nums[i]
left, right = i+1, len(nums)-1
while left < right:
sums = nums[left] + nums[right]
if sums == target and ([nums[i], nums[left], nums[right]] not in res):
res.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
elif sums > target:
right -= 1
else:
left += 1
return res

4.1.1.3、剑指 Offer II 018. 有效的回文

剑指 Offer II 018. 有效的回文.

class Solution:
def isPalindrome(self, s: str) -> bool:
if not s: return True
def check(x):
# 等价于
isalnum()
判断一个字符是否是字母或数字
return ('a'<=x and x<='z') or ('A'<=x and x<='Z') or ('0'<=x and x<='9')
left, right = 0, len(s) - 1
while left < right:
while not check(s[left]) and left < right:
left += 1
while not check(s[right]) and left < right:
right -= 1
if s[left].lower() != s[right].lower(): return False
left += 1
right -= 1
return True

4.1.1.4、剑指 Offer II 019. 最多删除一个字符得到回文

剑指 Offer II 019. 最多删除一个字符得到回文.

class Solution:
def validPalindrome(self, s: str) -> bool:
def check(x):
# 判断字符串x是否是回文串
left, right = 0, len(x) - 1
while left < right:
if x[left] != x[right]: return False
left += 1
right -= 1
return True
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return check(s[left+1:right+1]) or check(s[left:right])
left += 1
right -= 1
return True

4.2、二分查找

4.2.1、笔记+模板

1. 时间复杂度是O(logn)
2. 在已经排好序的数组中才能使用二分法
3. mid = left + (right-left) // 2 左中位数 先排除左区间 第一个模板
   mid = left + (right-left+1) // 2 右中位数 先排除右区间 第二个模板
4. 难点：边界条件
5. 下面两个模板思想：每一次都排除目前元素一定不在的那部分， 最后剩下的那个就是查找的元素

模板1：

def binary_search(nums, target):
# 在有序数组nums中查找值为target的元素下标
if not nums: return -1
left, right = 0, len(nums) - 1
# 循环终止条件写成：while (left < right) ，表示退出循环的时候只剩下一个元素
while left < right:
# 注意：在循环体内考虑如何缩减待搜索区间，或者说是在待搜索区间里排除一定不存在目标元素的区间
mid = left + (right - left) // 2
# 如果nums[mid] < target
说明不在左边
排除左区间0~mid
剩余区间 [mid+1,right]
left = mid+1说明排除左区间
if nums[mid] < target: left = mid + 1
# 如果nums[mid] >= target 说明不在右边
排除右区间mid+1~right
剩余区间 [0,mid]
else: right = mid
# 结束循环 left == right 
if nums[left] == target: return left
else: return -1

模板2：

def binary_search(nums, target):
# 在有序数组nums中查找值为target的元素下标
if not nums: return -1
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left + 1) // 2
# 如果nums[mid] > target 排除右区间[mid, right]
保留左区间[0,mid-1]
# right = mid - 1 说明排除有区间
if nums[mid] > target: right = mid - 1
# 如果nums[mid] <= target
排除左区间[0,mid-1] 保留右区间[mid,right]
else: left = mid
if nums[left] == target: return left
else: return -1

总结：拿到题，先按第一个模板的来写，写到if判断先删除左区间还是右区间的适合，就直到到底是按哪个模板了。

4.2.2、题目汇总

4.2.2.1、剑指 Offer II 068. 查找插入位置（经典）

剑指 Offer II 068. 查找插入位置.

class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
if not nums: return [target]
# 特例: 如果target比nums中最大的数还大 那么while循环结束后left对应的right的位置 错误 应该返回right后一个idx
#
如果target比nums中最小的数还小 那么while循环后left刚好就是返回的idx
if nums[-1] < target: return len(nums)
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
# 排除掉左边0~mid的情况
剩余空间 [mid+1,right]
if nums[mid] < target: left = mid + 1
# 排除掉右边mid~right的情况
剩余空间 [leftm,mid]
else: right = mid
return left

4.2.2.2、剑指 Offer II 072. 求平方根

剑指 Offer II 072. 求平方根.

class Solution:
def mySqrt(self, x: int) -> int:
if x == 0: return 0
left, right = 0, x // 2 + 1
while left < right:
mid = left + (right - left + 1) // 2
# 排除右区间>x的区域 因为>的肯定不满足条件
但是<x的话可能是结果 因为可以向下取整
# 比如3x3=9
x=10
3x3<10如果直接排除的话 就错了
# 比如3x3=9
x=8
排除右边[mid,right]部分 肯定不满足

if mid * mid > x:
right = mid - 1
# 如果<=x 那么还是排除左区间[0, mid-1]
# 比如3x3=9 x=10
[0, 2]
else:
left = mid
return left

4.2.2.3、剑指 Offer II 069. 山峰数组的顶部（经典）

剑指 Offer II 069. 山峰数组的顶部.

class Solution:
def peakIndexInMountainArray(self, arr: List[int]) -> int:
left, right = 0, len(arr) - 1
while left < right:
mid = left + (right - left) // 2
# 先排除升序的部分（左区间）
山峰肯定不在
if arr[mid] < arr[mid+1]: left = mid + 1
# 如果mid->mid+1是降序(> 依题意没有=的情况)
就排除掉降序区间[mid+1,right]
山峰肯定不在
else: right = mid
return left

4.2.2.4、剑指 Offer II 070. 排序数组中只出现一次的数字（难）

剑指 Offer II 070. 排序数组中只出现一次的数字.

class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
# 确保每次比较的都是偶数idx
if mid % 2 == 1: mid -= 1
# 例子：1122344
# 如果偶数index和它+1的奇数index相等 如index=2 此时mid=mid+1且mid左边是有偶数个数字
# 根据题目可知左区域必是满足条件的 那个单一元素一定不在左区域
# 所以排除左区域 [0,mid+1] 剩余右区域[mid+2,right]
if nums[mid] == nums[mid+1]:
left = mid + 2
else:
right = mid
return nums[left]

4.2.2.5、剑指 Offer II 073. 狒狒吃香蕉（经典）

剑指 Offer II 073. 狒狒吃香蕉.

class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
def checkEating(speed):
hours = 0
for p in piles:
# 如果不能整除//mid就是它的整数部分 +1就相当于是它的小数部分
# 如果刚好整除-1//mid就不能整除了 再+1就刚好起到整除的效果
hours += (p - 1) // speed + 1
if hours > h: return False
else: return True
left, right = 1, max(piles)
while left < right:
mid = left + (right - left) // 2
# 如果当前速度无法吃完 也就速度太慢了 那么比当前速度还小的速度肯定不行

# 所以先过滤左区间
所以left = mid + 1
所以要用第一个模板
if not checkEating(mid):
left = mid + 1
else:
right = mid
return left

五、滑动窗口

5.1、一些模板

5.1.1、定长滑动窗口模板

start = 0
# 定长滑动窗口模板
for end in range(len(s1), len(s2)+1):
比较定长窗口s2[start: end]是否满足题意
start += 1

5.1.2、不定长滑动窗口模板

 start = 0
cur_sum = 0
for end in range(len(nums)):
cur_sum += nums[end]
# end往后走
# start<=end这个条件可以看情况加
while cur_sum >= target and start<=end:
# 不满足条件
start可以往前走几步的条件
min_length = min(min_length, end - start + 1)
cur_sum -= nums[start]
# 相应的值也要变 减去start
start += 1
# start往前走
# 满足条件
end+1往后走

5.1.3、一些笔记

1. mapp1 = mapp2 mapp2变 mapp1也会变
   mapp1 = mapp2.copy() mapp2变 mapp1不变
2. mapp = set() 记录元素值 移除：mapp.remove(元素值) 添加：mapp.add(元素值)
   mapp = {} 记录元素值和个数（key:val） 移除：mapp[元素值] -= 1 添加：mapp[元素值] = 1
3. 尽量不要用[] 速度非常慢
4. set转list[] list(set)

5.2、题目汇总

5.2.1、剑指 Offer II 032. 有效的变位词

5.2.1、剑指 Offer II 032. 有效的变位词.

思路：直接把p对应的mapp固定，再滑动s更新mapp，实时比较两个mapp

class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if s == t: return False
if len(s) != len(t): return False
mapp1 = [0 for _ in range(26)]
mapp2 = [0 for _ in range(26)]
for i in range(len(s)):
mapp1[ord(s[i]) - ord('a')] += 1
mapp2[ord(t[i]) - ord('a')] += 1
return mapp1 == mapp2.append(i+1)

5.2.2、剑指 Offer II 014. 字符串中的变位词（固定窗口）

剑指 Offer II 014. 字符串中的变位词.

class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2): return False
mapp1 = [0 for _ in range(26)]
mapp2 = [0 for _ in range(26)]
for i in range(len(s1)):
mapp1[ord(s1[i])-ord('a')] += 1
mapp2[ord(s2[i])-ord('a')] += 1
if mapp1 == mapp2: return True
start = 0
for end in range(len(s1), len(s2)):
mapp2[ord(s2[end])-ord('a')] += 1
mapp2[ord(s2[start])-ord('a')] -= 1
if mapp1 == mapp2: return True
start += 1
return False

5.2.3、剑指 Offer II 015. 字符串中的所有变位词（固定窗口 难）

剑指 Offer II 015. 字符串中的所有变位词.

思路：直接把p对应的mapp固定，再滑动s更新mapp，实时比较两个mapp

class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
len1, len2 = len(s), len(p)
if len1 < len2: return []
mapp1 = [0 for _ in range(26)]
mapp2 = [0 for _ in range(26)]
res = []
for i in range(len2):
# 注：ord('b')-ord('a')=1
所以相减的0就代表了'a',1就代表了'b' 
mapp1[ord(s[i])-ord('a')] += 1
mapp2[ord(p[i])-ord('a')] += 1
if mapp1 == mapp2: res.append(0)
start = 0
for end in range(len2, len1):
mapp1[ord(s[end])-ord('a')] += 1
mapp1[ord(s[start])-ord('a')] -= 1
start += 1
if mapp1 == mapp2: res.append(start)
return res

5.2.4、剑指 Offer II 008. 和大于等于 target 的最短子数组（不定窗口）

剑指 Offer II 008. 和大于等于 target 的最短子数组.

class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
min_length = float('inf')
start = 0
cur_sum = 0
for end in range(len(nums)):
cur_sum += nums[end]
while cur_sum >= target:
min_length = min(min_length, end - start + 1)
cur_sum -= nums[start]
start += 1
if min_length == float('inf'): return 0
else: return min_length

5.2.5、剑指 Offer II 009. 乘积小于 K 的子数组(不定窗口)

剑指 Offer II 009. 乘积小于 K 的子数组.

class Solution:
def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
start = 0
cur_val = 1
res = 0
for end in range(len(nums)):
cur_val *= nums[end]
while cur_val >= k and start <= end:
# start <= end 好习惯就都写吧 写了总没错
cur_val /= nums[start]
start += 1
# 为什么是 end - start + 1?
# 例子：ABC -> ABCX
# 增加4个 X CX BCX ABCX
因为必须要以X为结尾
为什么?
# 因为像BC在以C为结尾时 已经算过了 
res += (end - start + 1)
return res

5.2.6、剑指 Offer II 016. 不含重复字符的最长子字符串(不定窗口)

剑指 Offer II 016. 不含重复字符的最长子字符串.

class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
start = 0
max_length = 0
mapp = set()
for end in range(len(s)):
while s[end] in mapp:
# 不满足条件
start向左移动
mapp.remove(s[start])
start += 1
max_length = max(max_length, end-start+1)
# 满足条件
end继续向右移动
mapp.add(s[end])
return max_length

5.2.7、剑指 Offer II 017. 含有所有字符的最短字符串(不定窗口)

剑指 Offer II 017. 含有所有字符的最短字符串.

class Solution:
def minWindow(self, s: str, t: str) -> str:
def isContains(window_dict, temp_dict):
# 判断当前窗口的dict是否包含t的dict
for each_key in temp_dict:
if window_dict[each_key] < temp_dict[each_key]: return False
return True
temp_dict = {t[0]: 1}
# 存放t中的所有元素 key:val
window_dict = {}
# 存放当前窗口的所有元素 key:val

for i in range(1, len(t)):
if t[i] not in temp_dict: temp_dict[t[i]] = 1
else: temp_dict[t[i]] += 1
for each_key in temp_dict:
if each_key not in window_dict:
window_dict[each_key] = 0
start = 0
min_length = float('inf')
res = ""
for end in range(len(s)):
if s[end] in window_dict:
# end向后移动 将end的值加入窗口
window_dict[s[end]] += 1
# 如果当前窗口dict包含t的dict 那么就可以移动start 缩小窗口 寻找最小长度和对应的字符
while isContains(window_dict, temp_dict):
if min_length > end - start + 1:
# 寻找最小长度的字符
min_length = end - start + 1
res = s[start: end+1]
if s[start] in window_dict:
# start向前移动之前要先判断 如果s[start]在当前窗口要-1
window_dict[s[start]] -= 1
start += 1
# start向后移动
return res

六、单调栈Stack（后进先出）+ 单调队列Queue（先进先出）

6.1、单调栈Stack（后进先出）

6.1.1、一些笔记

1. stack = [] 栈顶添加元素stack.append(x) 删除栈顶元素stack.pop()
2. 在列表的任意位置插入某个元素：a.insert(index,val)
3. stack = [1, 2, 3]
   stack.append(5) -> [1, 2, 3, 5]
   stack.pop() -> [1, 2, 3]

6.1.2、题目汇总

6.1.2.1、剑指 Offer II 036. 后缀表达式

剑指 Offer II 036. 后缀表达式.

class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for i in range(len(tokens)):
if tokens[i] not in ['+', '-', '*', '/']:
stack.append(int(tokens[i]))
else:
b = stack.pop()
a = stack.pop()
if tokens[i] == '+': stack.append(a + b)
elif tokens[i] == '-': stack.append(a - b)
elif tokens[i] == '*': stack.append(a * b)
else: stack.append(int(a / b))
return stack.pop()

6.1.2.2、剑指 Offer II 037. 小行星碰撞（难）

剑指 Offer II 037. 小行星碰撞.

class Solution:
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
stack = []
for i in range(len(asteroids)):
# 肯定不相撞 无条件压栈 
# 1、栈顶为空
# 2、栈顶元素和当前元素同向运动
# 3、栈顶元素往左运动
当前元素往右运动
if (not stack) or (stack[-1] * asteroids[i] > 0) or (stack[-1]<0 and asteroids[i]>0):
stack.append(asteroids[i])
# 相撞的唯一条件：当前元素向左 栈顶元素向右
elif asteroids[i]<0 and stack[-1]>0:
# 肯定相撞前提下，当前元素爆炸的条件：当前元素的abs<栈顶元素的abs
if abs(asteroids[i]) < abs(stack[-1]): continue
# 肯定相撞前提下，一起爆炸的条件：当前元素的abs=栈顶元素的abs
elif abs(asteroids[i]) == abs(stack[-1]): stack.pop()
# 肯定相撞前提下，栈顶元素爆炸的条件：当前元素的abs>栈顶元素的abs
else:
stack.pop()
# 栈顶元素爆炸
# 栈顶元素爆炸了，当前元素也不一定可以压栈，还要比较最新栈顶元素和当前元素的关系
# 栈顶连续爆炸且当前元素不爆炸的条件：栈顶不为空+栈顶元素向右且当前元素向左+abs栈顶元素<abs当前元素
while stack and (stack[-1]>0 and asteroids[i]<0) and abs(stack[-1])<abs(asteroids[i]):
stack.pop()
# 如果栈顶为空 则当前元素压栈 
if not stack: stack.append(asteroids[i])
else:
# 如果栈顶不为空 且两者同向 压栈
if asteroids[i] * stack[-1] > 0: stack.append(asteroids[i])
# 如果栈顶不为空 两者对向 且大小相同 同时爆炸
elif abs(asteroids[i]) == abs(stack[-1]): stack.pop()
# 如果栈顶不为空 两者对向 且当前更小 不做处理
elif abs(asteroids[i]) < abs(stack[-1]): continue
# 如果栈顶不为空 两者对向 且栈顶更小 栈顶弹出再压栈
else:
stack.pop()
stack.append(asteroids[i])
return stack

6.1.2.3、剑指 Offer II 038. 每日温度

剑指 Offer II 038. 每日温度.

class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
# 本质：求一维数组中每个元素的右侧第一个比它大的元素
res = [0 for i in range(len(temperatures))]
stack = []
# 存放每个元素的idx
for i in range(len(temperatures)):
# 栈不为空且栈顶元素小于当前元素：栈顶元素找到第一个比它大的元素了
while stack and temperatures[stack[-1]] < temperatures[i]:
res[stack[-1]] = i - stack[-1]
stack.pop()
# 如果栈等于空或者栈顶元素大于当前元素：压栈
stack.append(i)
return res

6.1.2.4、剑指 Offer II 039. 直方图最大矩形面积（难）

剑指 Offer II 039. 直方图最大矩形面积.

视频讲解： 小姐姐刷题-Leetcode 84 柱状图中最大的矩形.

class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
maxArea = 0
stack = []
heights.insert(0, 0)
# 头尾都插入0
heights.insert(len(heights), 0)
for i in range(len(heights)):
# 如果stack为空或者当前高度大于等于stack[-1]的高度
压栈
if not stack or heights[i]>=heights[stack[-1]]: stack.append(i)
# else: 两个都不满足
else:
while stack and heights[i]<heights[stack[-1]]:
h = heights[stack[-1]]
stack.pop()
w = i - stack[-1] - 1
maxArea = max(maxArea, w*h)
stack.append(i)
return maxArea

6.1.2.5、剑指 Offer II 040. 矩阵中最大的矩形（难）

剑指 Offer II 040. 矩阵中最大的矩形.

视频讲解： 剑指offer040 矩阵中的最大矩形.

class Solution:
def maximalRectangle(self, matrix: List[str]) -> int:
def largestRectangleArea(heights):
stack = []
max_area = 0
heights.insert(0, 0)
heights.append(0)
for i in range(len(heights)):
if not stack or heights[stack[-1]]<=heights[i]: stack.append(i)
else:
while heights[stack[-1]] > heights[i]:
h = heights[stack[-1]]
stack.pop()
w = i - stack[-1] - 1
max_area = max(max_area, w*h)
stack.append(i)
return max_area
if not matrix: return 0
row, col = len(matrix), len(matrix[0])
maxArea = 0
heights = [0 for i in range(col)]
# 初始化heights
for i in range(row):
for j in range(col):
if len(heights) != col:
# 如果不想等 说明进入过largestRectangleArea函数
insert了两个元素 要pop出来
heights.pop(0)
heights.pop()
if i == 0: heights[j] = int(matrix[i][j])
# 第一行直接赋值即可
else:
# 第二行就要开始进行叠加
if matrix[i][j] == '1':
heights[j] = int(matrix[i][j]) + heights[j]
# 如果当前元素等于0 那么h=0
因为上面的1在上一次就已经算过了
else:
heights[j] = 0
maxArea = max(maxArea, largestRectangleArea(heights))
# 计算直方图最大面积
return maxArea

6.2、单调队列Queue（先进先出）

6.2.1、一些笔记

1. queue = [1, 2, 3]
   queue.append(5) -> [1, 2, 3, 5]
   queue.pop(0) -> [2, 3, 5]

6.2.2、题目汇总

6.2.2.1、剑指 Offer II 041. 滑动窗口的平均值

剑指 Offer II 041. 滑动窗口的平均值.

class MovingAverage:
def __init__(self, size: int):
"""
Initialize your data structure here.
"""
self.windowSize = size
# 窗口大小
self.size = 0
# 多少个数字的和
self.queue = []
self.sum = 0
def next(self, val: int) -> float:
if len(self.queue) < self.windowSize:
self.queue.append(val)
self.sum += val
self.size += 1
return self.sum / self.size
else:
self.queue.append(val)
self.sum -= self.queue.pop(0)
self.sum += val
return self.sum / self.windowSize

6.2.2.2、剑指 Offer II 042. 最近请求次数

剑指 Offer II 042. 最近请求次数.

class RecentCounter:
def __init__(self):
self.count = 0
self.queue = []
def ping(self, t: int) -> int:
while self.queue and t - 3000 > self.queue[0]:
self.queue.pop(0)
self.count -= 1
self.queue.append(t)
self.count += 1
return self.count

七、前缀和

7.1、一些模板

7.1.1、常规前缀和/后缀和

常规的前缀和：从左往右加，左边界不动，有边界往右走，sum一直累加

# 前缀和
pre_sum = [0 for i in range(length)]
for i in range(length):
if i == 0: pre_sum[0] = nums[0]
else: pre_sum[i] = pre_sum[i-1] + nums[i]
# 后缀和
post_sum = [0 for i in range(length)]
for j in range(length-1, -1, -1):
if j == len(nums)-1: post_sum[j] = nums[j]
else:
post_sum[j] = post_sum[j+1] + nums[j]

7.1.2、一些笔记

1. 串s=[a,b,c,d,e,f,g]，求和为k的连续子串个数，我们不需要一个个的遍历所有的字串，只需要用一个字典dict存放每个元素对应的前缀和，再计算当前元素前缀和-k是否出现在字典dict中，如果出现dict[当前元素前缀和-k]就是到当前元素为止，和为k的字串个数。用前缀和的差的方式求和为k的子串个数。

7.2、题目汇总

7.2.1、剑指 Offer II 012. 左右两边子数组的和相等

剑指 Offer II 012. 左右两边子数组的和相等.

class Solution:
def pivotIndex(self, nums: List[int]) -> int:
# 方法一、前缀和+后缀和
length = len(nums)
pre_sum = [0 for i in range(length)]
post_sum = [0 for i in range(length)]
for i in range(length):
if i == 0: pre_sum[0] = nums[0]
else: pre_sum[i] = pre_sum[i-1] + nums[i]
for j in range(length-1, -1, -1):
if j == len(nums)-1: post_sum[j] = nums[j]
else:
post_sum[j] = post_sum[j+1] + nums[j]
for k in range(length):
if pre_sum[k] == post_sum[k]: return k
return -1
# 方法二、前缀和
length = len(nums)
pre_sum = 0
# 前缀和
total = 0
# 记录数组中元素总和
for i in range(length):
total += nums[i]
for j in range(length):
# 左边+右边+当前=total
if 2 * pre_sum + nums[j] == total: return j
pre_sum += nums[j]
return -1

7.2.2、剑指 Offer II 010. 和为 k 的子数组（难 经典）

剑指 Offer II 010. 和为 k 的子数组.

视频讲解.

class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
mapp = {0:1}
# 用于标记cur_sum=k的时候 出现第一个符合条件的连续子数组（cur-k=0）
cur_sum = 0
res = 0
for i in range(len(nums)):
cur_sum += nums[i]
# 记录前缀和
if cur_sum - k in mapp: res += mapp[cur_sum - k]
# 对每个元素都要执行这步 因为mapp当中要记录nums每个元素的前缀和
# 这样cur_sum-k如果在mapp中，那么说明数组中中间有连续子数组
个数就等于mapp[cur_sum-k]
if cur_sum not in mapp: mapp[cur_sum] = 1
else: mapp[cur_sum] += 1
return res

7.2.3、剑指 Offer II 011. 0 和 1 个数相同的子数组（经典）

剑指 Offer II 011. 0 和 1 个数相同的子数组.

视频讲解.

class Solution:
def findMaxLength(self, nums: List[int]) -> int:
l = len(nums)
pre_sum = [0 for i in range(l)]
mapp = {0: -1}
maxLength = 0
for i in range(l):
# 把0改为-1
if nums[i] == 0: nums[i] = -1
pre_sum[0] = nums[0]
for j in range(l):
# 求前缀和
pre_sum[j] = pre_sum[j-1] + nums[j]
for k in range(l):
# hash_map
key:val = 前缀和:当前前缀和第一次出现的index
if pre_sum[k] not in mapp: mapp[pre_sum[k]] = k
else: maxLength = max(maxLength, k - mapp[pre_sum[k]])
return maxLength

7.2.4、剑指 Offer II 013. 二维子矩阵的和（经典）

剑指 Offer II 013. 二维子矩阵的和.

class NumMatrix:
def __init__(self, matrix: List[List[int]]):
# 一维前缀和
row, col = len(matrix), len(matrix[0])
self.pre_sum = [[0]*(col+1) for i in range(row)]
for i in range(row):
for j in range(col):
self.pre_sum[i][j+1] = self.pre_sum[i][j] + matrix[i][j]
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
sum_region = 0
for i in range(row1, row2+1):
sum_region += (self.pre_sum[i][col2+1] - self.pre_sum[i][col1])
return sum_region

7.2.5、剑指 Offer II 071. 按权重生成随机数（前缀和+二分查找 题目怪怪的）

剑指 Offer II 071. 按权重生成随机数.

class Solution:
def __init__(self, w: List[int]):
self.pre_sum = [0 for _ in range(len(w))]
self.pre_sum[0] = w[0]
for i in range(1, len(w)):
self.pre_sum[i] = self.pre_sum[i-1] + w[i]
print(self.pre_sum)
def pickIndex(self) -> int:
r = random.randint(1, self.pre_sum[-1])
left, right = 0, len(self.pre_sum)
while left < right:
mid = left + (right - left) // 2
if self.pre_sum[mid] >= r: right = mid
else: left = mid+1
return right

八、位运算

视频学习.

8.1、笔记和模板

（A）位运算的使用场景：

1. 这部分的题目很多都是和比特位/二进制数相关的，如果看到相关的字眼，几乎可以无脑用位运算来写。

（B）一些常用的函数/方法
2. ord(‘a’)：求的是字符a的assci码；如：ord(‘b’)-ord(‘a’)=1
3. 5<<3 是把5的的比特位往左移3位；即：000…101 -> 000…101000；同理 5>>3 是把5的的比特位往右移3位；
比特位左移一位，对应的十进制数x2，如：2<<1：4 ；2<<2：8；3 << 1：6；3<<2：16
4. | 或运算 ：1|1=1 ；1|0=1；0|0=0

5. &与运算 ：1&1=1；1&0：0；0&0=0
   a & 1 = 1：可以用这个性质判断a的最后一位是不是1

6. 异或运算的三条定理：
   1 ^ 0=1；1 ^ 1=0；0 ^ 0 = 0;
   a)、任何一个数与其自己异或的结果都是0，即a^a=0
   b)、任何数字和0异或还是它本身，即a^0=a
   c)、异或运算有交换律: a^ b^ c = a^ c^ b ；a ^ b = c <=> a ^ c = b

7. 把二进制数字符串转换成整数：a=‘111’ ，int(a,2)=7

（C）二进制/比特位中计算1个数的几种方法：

1. 判断一个数a的比特位最后一位是不是1，用 a&1就能判断出，再将a>>1向右移动一位就再重复使用 a&1就能判断一个数的比特位上有几个1；
2. a&(a-1)得到的数 = a的比特位最后一个1取0后的数，也可以用来计算一个数比特位中1的个数；

（D）位求和操作：第5题二进制加法

8.2、题目汇总

8.2.1、剑指 Offer II 005. 单词长度的最大乘积

剑指 Offer II 005. 单词长度的最大乘积 .

视频讲解 .

class Solution:
def maxProduct(self, words: List[str]) -> int:
# 将字符串转换为bit数组 
# 例如bit[i]=00...011 表示words[i]中只有'a'、'b'字符
bits = [0 for _ in range(len(words))]
for i in range(len(words)):
for j in range(len(words[i])):
# 假设words[i][j]='c' 'c'的assic码-'a'的assic码=3
# 1 << 3表示将1的二进制左移3位 => 0000...100
# 0和任何事异或|等于原来的数
# 所以bits[i]就得到了原字符串的bit数组
# 这里其实是整数存放的 因为每个整数都可以转换为一个唯一的bit数
bits[i] |= 1 << ord(words[i][j]) - ord('a')
# 两两比较bit数组中的bit
res = 0
for i in range(len(words)-1):
for j in range(i+1, len(words)):
# 两个bit数相与&==0说明a和b没有相同的字符
if bits[i] & bits[j] == 0:
res = max(res, len(words[i])*len(words[j]))
return res

8.2.2、剑指 Offer II 003. 前 n 个数字二进制中 1 的个数

剑指 Offer II 003. 前 n 个数字二进制中 1 的个数 .

class Solution:
def countBits(self, n: int) -> List[int]:
# 思路1

def count_one1(x):
count = 0
while x:
# 看看最后一位是不是1
if x & 1: count += 1
x >>= 1
return count
# 思路2
def count_one2(x):
count = 0
while x:
count += 1
# a&(a-1)得到的数=a的比特位最后一个1取0后的数
x &= (x-1)
return count
res = []
for i in range(n+1):
res.append(count_one2(i))
return res

8.2.3、Leetcode 136. 只出现一次的数字（其他数都出现2次）

Leetcode 136. 只出现一次的数字 .

class Solution:
def singleNumber(self, nums: List[int]) -> int:
# 这道题异或的3个定律都用到了
# 任何数与0异或都是本身
res = 0
for num in nums:
# 任何数和自己异或都是0
# 异或具有交换律
res ^= num
return res

8.2.4、剑指 Offer II 004. 只出现一次的数字 （其他数都出现3次 难 经典）

剑指 Offer II 004. 只出现一次的数字 .

class Solution:
def singleNumber(self, nums: List[int]) -> int:
# 方法1、哈希
# mapp = dict()
# for i in range(len(nums)):
#
if nums[i] not in mapp: 
#
mapp[nums[i]] = True
#
else: mapp[nums[i]] = False
# for key, val in mapp.items():
#
if val == True: return key
# 方法2、位运算：& 与运算
res = 0
for i in range(32):
cur_num = 0
for num in nums:
# 计算第i位1的个数
cur_num += (num >> i) & 1
if cur_num % 3 == 1:
# 找到了
if i == 31:
res -= (1 << i)
else:
# 第i位=1 其他位都是3,说明最后的结果就第i位=1的数
res |= (1 << i)
return res

8.2.5、剑指 Offer II 002. 二进制加法（这道题没用位运算）

剑指 Offer II 002. 二进制加法 .

class Solution:
def addBinary(self, a: str, b: str) -> str:
res = ''
i, j = len(a)-1, len(b)-1
carry = 0
while i>=0 or j>=0:
# ord('1')=49
求1的assic码
x = ord(a[i]) - ord('0') if i>=0 else 0
y = ord(b[j]) - ord('0') if j>=0 else 0
cur_sum = x + y + carry
res += str((cur_sum % 2))
carry = cur_sum // 2
i -= 1
j -= 1
if carry != 0: res += str(carry)
return res[::-1]

8.2.6、剑指 Offer II 001. 整数除法（经典）

剑指 Offer II 001. 整数除法 .

视频学习 .

class Solution:
def divide(self, a: int, b: int) -> int:
min_int, max_int = -2**31, 2**31-1
if a == min_int and b == -1: return max_int
if b == 1: return a
flag = -1 if (a > 0 and b < 0) or (a < 0 and b > 0) else 1
if a > 0: a = - a
if b > 0: b = - b
res = 0
while a <= b:
# 因为现在都是负数
所以是<=
base = b
cnt = 1
# 倍数
while a <= base:
base <<= 1
# base x 2
cnt <<= 1
# cnt
x 2
base >>= 1
cnt >>= 1
res += cnt
a -= base
return flag * res

8.2.7、剑指 Offer II 067. 最大的异或（难）

剑指 Offer II 067. 最大的异或.

class Solution:
def findMaximumXOR(self, nums: List[int]) -> int:
res = 0
mask = 0
for i in range(30, -1, -1):
# 31位
mask |= (1 << i)
# 当前位的掩码
# 当前得到的所有前缀都放在这个哈希表中
s = set()
for num in nums:
s.add(mask & num)
# 先“贪心地”假设这个数位上是 “1” ，如果全部前缀都看完，都不符合条件，这个数位上就是 “0” 
temp = res | (1 << i)
# 遍历当前位所有的前缀 和 贪心的最大值 异或
a^max=b
b in s => 可以得到max 
for prefix in s:
if temp ^ prefix in s:
res = temp
break
return res

九、动态规划DP

9.2、题目汇总

9.2.1、剑指 Offer II 095. 最长公共子序列

剑指 Offer II 095. 最长公共子序列.

class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
if len(text1) == 0 or len(text2) == 0: return 0
max_len = 0
# dp[i][j]代表text[:i+1]和text[:j+1]的最长公共子序列
dp = [[0 for _ in range(len(text2)+1)] for _ in range(len(text1)+1)]
for i in range(1, len(text1)+1):
for j in range(1, len(text2)+1):
if text1[i-1] == text2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
if max_len < dp[i][j]: max_len = dp[i][j]
return max_len

9.2.2、剑指 Offer II 103. 最少的硬币数目

剑指 Offer II 103. 最少的硬币数目.

class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
# dp[j]代表装满容量为j的背包至少需要dp[j]个硬币
dp = [float('inf') for _ in range(amount+1)]
dp[0] = 0
for i in range(len(coins)):
for j in range(coins[i], amount+1):
if j >= coins[i]:
dp[j] = min(dp[j], dp[j-coins[i]]+1)
return dp[-1] if dp[-1] != float('inf') else -1

9.2.3、剑指 Offer II 096. 字符串交织（经典 难 ）

剑指 Offer II 096. 字符串交织.

class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
m, n = len(s1), len(s2)
if m + n != len(s3): return False
# dp[i][j]表示s1的前i个字符和s2的前j个字符是否是s3的钱i+j个字符
dp = [[False for _ in range(n+1)] for _ in range(m+1)]
dp[0][0] = True
for i in range(1, m+1):
dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]
for j in range(1, n+1):
dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]
for i in range(1, m+1):
for j in range(1, n+1):
# 两种情况：s3 i+j-1的idx上可能是s1的元素也可能是s2的元素
只要一个满足 就是True
dp[i][j] = (dp[i][j-1] and s2[j-1] == s3[i+j-1]) or (dp[i-1][j] and s1[i-1] == s3[i+j-1])
return dp[-1][-1]

9.2.4、剑指 Offer II 100. 三角形中最小路径之和（经典）

剑指 Offer II 100. 三角形中最小路径之和.

视频讲解.

class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
if not triangle or len(triangle)==0: return 0
for i in range(1, len(triangle)):
for j in range(len(triangle[i])):
if j == 0: triangle[i][j] += triangle[i-1][j]
elif j == i: triangle[i][j] += triangle[i-1][j-1]
else: triangle[i][j] += min(triangle[i-1][j], triangle[i-1][j-1])
return min(triangle[-1])

9.2.5、剑指 Offer II 020. 回文子字符串的个数

剑指 Offer II 020. 回文子字符串的个数.

class Solution:
def countSubstrings(self, s: str) -> int:
if len(s) < 2: return len(s)
res = 0
# dp[i][j]代表s[i:j+1]是否是回文子串
dp = [[False for _ in range(len(s))] for _ in range(len(s))]
for i in range(len(s)):
dp[i][i] = True
res += 1
for i in range(len(s)-2, -1, -1):
for j in range(i+1, len(s)):
if s[i] == s[j]:
if j - i < 2: dp[i][j] = True
else: dp[i][j] = dp[i+1][j-1]
if dp[i][j]: res += 1
return res

9.2.6、剑指 Offer II 094. 最少回文分割（难）

剑指 Offer II 094. 最少回文分割.

class Solution:
def minCut(self, s: str) -> int:
n = len(s)
# 记录s[i:j+1]是否是回文串
dp1 = [[True for _ in range(n)] for _ in range(n)]
for i in range(n-1, -1, -1):
for j in range(i+1, n):
dp1[i][j] = (dp1[i+1][j-1] and s[i] == s[j])
# 记录从0~i元素需要分割的最少次数
dp2 = [n for _ in range(n)]
for i in range(n):
if dp1[0][i] == True: dp2[i] = 0
else:
for j in range(i):
if dp1[j+1][i] == True:
# 最极端的情况 dp1[i-1][i]肯定是True的
dp2[i] = min(dp2[j]+1, dp2[i])
return dp2[-1]

9.2.7、剑指 Offer II 099. 最小路径之和

剑指 Offer II 099. 最小路径之和.

class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
row, col = len(grid), len(grid[0])
if row == 0 or col == 0 or not grid: return 0
if row == 1 or col == 1: return sum(grid[0])
# dp[i][j]代表从grid[0][0]到grid[i][j]的最小路径和
dp = grid
for i in range(1, row): dp[i][0] += dp[i-1][0]
for j in range(1, col): dp[0][j] += dp[0][j-1]
for i in range(1, row):
for j in range(1, col):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
return dp[-1][-1]

9.2.8、剑指 Offer II 088. 爬楼梯的最少成本

剑指 Offer II 088. 爬楼梯的最少成本.

class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
# dp[i]表示从0到i-1位置的最少花费体力
dp = [0 for _ in range(len(cost)+1)]
for i in range(2, len(cost)+1):
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2]+cost[i-2])
return dp[-1]

9.2.9、剑指 Offer II 097. 子序列的数目（经典）

剑指 Offer II 097. 子序列的数目.

class Solution:
def numDistinct(self, s: str, t: str) -> int:
if len(s) == 0: return 0
if len(t) == 0: return 1
# dp[i][j]表示s[:i]的子序列中t[:j]出现的个数
dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]
for i in range(len(s)):
dp[i][0] = 1
for i in range(1, len(s)+1):
for j in range(1, len(t)+1):
if s[i-1] == t[j-1]:
dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
else:
dp[i][j] = dp[i-1][j]
return dp[-1][-1]

9.2.10、剑指 Offer II 093. 最长斐波那契数列

剑指 Offer II 093. 最长斐波那契数列.

有点类似最长递增子序列

class Solution:
def lenLongestFibSubseq(self, arr: List[int]) -> int:
n = len(arr)
if n <= 2: return 0
res = 2
# 至少要3个数才能叫斐波那契额数列

mapp = dict()
for i, num in enumerate(arr):
mapp[num] = i
# dp[i][j]表示arr[i:j+1]的最长斐波那契数列长度
dp = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(i+1, n):
tar = arr[j] - arr[i]
dp[i][j] = 2
# 长度至少是2
if tar in mapp:
dp[i][j] = max(dp[i][j], dp[mapp[tar]][i] + 1)
res = max(res, dp[i][j])
return res if res > 2 else 0

9.2.11、剑指 Offer II 089. 房屋偷盗

剑指 Offer II 089. 房屋偷盗.

class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 0: return 0
if len(nums) == 1: return nums[0]
# dp[i]表示前i家能抢到的最大金额
dp = [0 for _ in range(len(nums))]
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[-1]

9.2.12、剑指 Offer II 090. 环形房屋偷盗

剑指 Offer II 090. 环形房屋偷盗.

class Solution:
def rob(self, nums: List[int]) -> int:
def help(nums):
if len(nums) == 0: return 0
if len(nums) == 1: return nums[0]
if len(nums) == 2: return max(nums)
dp = [0 for _ in range(len(nums))]
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[-1]
if len(nums) == 0: return 0
if len(nums) == 1: return nums[0]
# 不抢头
n1 = help(nums[1:])
# 不抢尾
n2 = help(nums[:-1])
# 不抢头 不抢尾
n3 = help(nums[1:-1])
return max(n1, n2, n3)

9.2.13、剑指 Offer II 091. 粉刷房子

剑指 Offer II 091. 粉刷房子.

视频讲解.

class Solution:
def minCost(self, costs: List[List[int]]) -> int:
dp = [[0 for _ in range(3)] for _ in range(len(costs))]
for i in range(3):
dp[0][i] = costs[0][i]
for i in range(1, len(costs)):
dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2])
dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2])
dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1])
return min(dp[-1])

9.2.14、剑指 Offer II 102. 加减的目标值

剑指 Offer II 102. 加减的目标值.

class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
if not nums or len(nums) == 0: return 0
nums_sum = sum(nums)
if (nums_sum-target) % 2 == 1: return 0
if target > nums_sum: return 0
bag_weight = (nums_sum-target) // 2
# dp[i]代表
dp = [0 for _ in range(bag_weight+1)]
dp[0] = 1
for i in range(len(nums)):
for j in range(bag_weight, nums[i]-1, -1):
if j >= nums[i]:
dp[j] += dp[j-nums[i]]
return dp[-1]

9.2.15、剑指 Offer II 098. 路径的数目

剑指 Offer II 098. 路径的数目.

class Solution:
def uniquePaths(self, m: int, n: int) -> int:
if m == 0 or n == 0: return 0
if m == 1 or n == 1: return 1
# dp[i][j]代表从start起始点到(i, j)位置的路径
dp = [[0 for _ in range(n)] for _ in range(m)]
for i in range(m): dp[i][0] = 1
for j in range(n): dp[0][j] = 1
for i in range(1, m):
for j in range(1, n):
dp[i][j] += dp[i-1][j]
dp[i][j] += dp[i][j-1]
return dp[-1][-1]

9.2.16、剑指 Offer II 092. 翻转字符

剑指 Offer II 092. 翻转字符.

class Solution:
def minFlipsMonoIncr(self, s: str) -> int:
n = len(s)
# dp表示s[i]处为‘0’时字符串s[0:i+1]单调递增最少的翻转次数
dp = [[n, n] for _ in range(n)]
# base case
if s[0] == '0':
dp[0][0] = 0
dp[0][1] = 1
else:
dp[0][0] = 1
dp[0][1] = 0
# 状态转移
for i in range(1, n):
if s[i] == '0':
# 以0结尾的话 dp[i][0]只能从dp[i-1][0]来
dp[i][0] = dp[i-1][0]
# 以0结尾 dp[i][1]可以从dp[i-1][0]和dp[i-1][1]来
dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + 1
else:
dp[i][0] = dp[i-1][0] + 1
dp[i][1] = min(dp[i-1][0], dp[i-1][1])
return min(dp[-1][0], dp[-1][1])

十、 排序

10.1、一些笔记

10.1.1、归并排序

def merge_sort(orign_list):
# 归并排序
# 例子 [3,7,6,5,9,1]
# 先拆成两半：[3,7,6] [5,9,1]
# 再拆分:
[3][7,6] [5][9,1]
# 再拆分:
[7][6]
[9][1]
# 开始合并：
[6,7]
[1,9]
#
[3,6,7]
[1,5,9]
#
[1,3,5,6,7,9] 
n = len(orign_list)
if n <= 1: return orign_list
idx = n // 2
first_list = merge_sort(orign_list[:idx])
second_list = merge_sort(orign_list[idx:])
first_idx = 0
second_idx = 0
res = []
while first_idx < len(first_list) and second_idx < len(second_list):
if first_list[first_idx] < second_list[second_idx]:
res.append(first_list[first_idx])
first_idx += 1
else:
res.append(second_list[second_idx])
second_idx += 1
res += first_list[first_idx:]
res += second_list[second_idx:]
return res

10.1.2、快排

10.1.3、堆排序 heapsort（重要）

大顶堆：是一颗完全二叉树，且所有父节点大于子节点。
存储结构：list；当前节点 i ，parent = (i-1) / 2，c1 = 2i + 1，c2 = 2i + 2

视频讲解.
csdn讲解.

自己实现：

def heapify(tree, n, i):
# 从第i个位置开始调整完全二叉树tree list->大顶堆
# 找到i的左右子节点
c1 = 2 * i + 1
c2 = 2 * i + 2
# 找到i、左子节点、右子节点谁更大
max_idx = i
if c1 < n and tree[c1] > tree[max_idx]: max_idx = c1
if c2 < n and tree[c2] > tree[max_idx]: max_idx = c2
# 调整
if max_idx != i:
tree[max_idx], tree[i] = tree[i], tree[max_idx]
heapify(tree, n, max_idx)
def build_heap(tree, n):
# 将一个无序的树list建成一个大顶堆
last_node = n - 1
# 最后一个节点
parent = (last_node - 1) // 2
# 最后一个节点对应的父节点
for i in range(parent, -1, -1):
heapify(tree, n, i)
def heap_sort(tree, n):
build_heap(tree, n)
for i in range(n-1, -1, -1):
# 把最大数tree[0]直接放在最后面 
tree[i], tree[0] = tree[0], tree[i]
# 再往下找次大的数
heapify(tree, i, 0)
return tree
tree = [2, 5, 3, 1, 10, 4]
heap_sort(tree, 6)
print(tree)
# [1, 2, 3, 4, 5, 10]

掉包实现:

import heapq
nums= [2, 3, 5, 1, 54, 23, 132]
# 一、建最小堆
# 方法1
tree = []
for num in nums:
heapq.heappush(tree, num)
# [1, 2, 5, 3, 54, 23, 132]
# 方法2
heapq.heapify(nums)
# [1, 2, 5, 3, 54, 23, 132]
# 二、访问堆内容
heapq.heappop()函数弹出堆中最小值
print(heapq.heappop(nums))
# 1
print(nums)
# [2, 5, 3, 54, 23, 132]
# 三、删除堆中最小元素并加入一个元素，将堆进行重新排列
可以使用heapq.heaprepalce() 函数
heapq.heapreplace(nums, 23)
# [3, 5, 23, 54, 23, 132]

10.1.4、计数排序

10.2、题目汇总

10.2.1、剑指 Offer II 058. 日程表

剑指 Offer II 058. 日程表.

class MyCalendar:
def __init__(self):
self.calendars = []
def book(self, start: int, end: int) -> bool:
for index, calendar in enumerate(self.calendars):
# end小于当前元素的start，不会和当前元素重叠，直接插入到当前元素的前面
if end <= calendar[0]:
self.calendars.insert(index, (start, end))
return True
# 三种相交情况 可以自己画个图
# 区间2的结尾>区间1的开始
区间2的开始<区间1的结尾
elif end > calendar[0] and start < calendar[1]: return False
# self.calendars一个都没插进去（没有插到任何元素前面 也没有重叠）
# 说明start>max(calendar[1]) 直接插在最后
self.calendars.append((start, end))
return True
# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(start,end)

10.2.2、剑指 Offer II 074. 合并区间（经典）

剑指 Offer II 074. 合并区间.

视频讲解.

class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if len(intervals) == 1: return intervals
intervals.sort()
cur_start, cur_end = intervals[0][0], intervals[0][1]
res = []
for i in range(1, len(intervals)):
if intervals[i][0] <= cur_end:
# 现在的区间右端点intervals[i][1]有可能会小于cur_end
cur_end = max(cur_end, intervals[i][1])
else:
res.append([cur_start, cur_end])
cur_start, cur_end = intervals[i][0], intervals[i][1]
if i == len(intervals) - 1:
res.append([cur_start, cur_end])
return res

10.2.3、剑指 Offer II 076. 数组中的第 k 大的数字（经典 最大堆）

剑指 Offer II 076. 数组中的第 k 大的数字.

class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
def heapify(tree, n, i):
c1, c2 = 2*i+1, 2*i+2
max_idx = i
if c1 < n and tree[c1] > tree[max_idx]: max_idx = c1
if c2 < n and tree[c2] > tree[max_idx]: max_idx = c2
if max_idx != i:
tree[max_idx], tree[i] = tree[i], tree[max_idx]
heapify(tree, n, max_idx)
def build_heap(tree, n):
last_node = n - 1
parent = (last_node - 1) // 2
for i in range(parent, -1, -1):
heapify(tree, n, i)
# 找第k个 那就不需要全部排列，只需要取出第k个就好了，所以这里用堆排序
n = len(nums)
build_heap(nums, n)
for i in range(n-1, n-k-1, -1):
nums[0], nums[i] = nums[i], nums[0]
heapify(nums, i, 0)
return nums[n-k]

10.2.4、剑指 Offer II 060. 出现频率最高的 k 个数字（经典 最小堆）

剑指 Offer II 060. 出现频率最高的 k 个数字.

class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
mapp = defaultdict(int)
for i in range(len(nums)):
mapp[nums[i]] += 1
arr = list(mapp.items())
def heapify(tree, n, i):
c1, c2 = 2*i+1, 2*i+2
min_idx = i
if c1<n and tree[c1][1] < tree[min_idx][1]: min_idx = c1
if c2<n and tree[c2][1] < tree[min_idx][1]: min_idx = c2
if min_idx != i:
tree[i], tree[min_idx] = tree[min_idx], tree[i]
heapify(tree, n, min_idx)
def build_heap(tree, n):
last_node = n - 1
parent = (last_node-1) // 2
for i in range(parent, -1, -1):
heapify(tree, n, i)
# 先将前k个数建最小堆
tree = arr[:k]
build_heap(tree, k)
for i in range(k, len(arr)):
if arr[i][1] > tree[0][1]:
tree[0] = arr[i]
heapify(tree, k, 0)
return [t[0] for t in tree]

10.2.5、剑指 Offer II 061. 和最小的 k 个数对（经典）

剑指 Offer II 061. 和最小的 k 个数对.

视频讲解.

class Solution:
def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
import heapq
m, n = len(nums1), len(nums2)
res = []
tree = [(nums1[i]+nums2[0], i, 0) for i in range(min(m, k))]
while tree and len(res)<k:
_, i, j = heapq.heappop(tree)
res.append([nums1[i], nums2[j]])
if j + 1 < n:
heapq.heappush(tree, (nums1[i]+nums2[j+1], i, j+1))
return res

10.2.6、剑指 Offer II 075. 数组相对排序（经典）

剑指 Offer II 075. 数组相对排序.

视频讲解.

class Solution:
def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
# 计数排序
# 先统计arr1中每个元素出现的次数
mapp = defaultdict(int)
for i in range(len(arr1)):
mapp[arr1[i]] += 1
# 再遍历arr2，将arr2出现的元素根据mapp中的次数先添加到res中
# arr2 中的元素各不相同 所以直接遍历arr2即可
res = []
for x in arr2:
# arr2 中的每个元素都出现在 arr1 中所以这里不需要判断添不添加
直接extend即可
res.extend([x for _ in range(mapp[x])])
mapp[x] = 0
# 统计mapp中还有哪些元素没有添加（没在arr2中出现的元素）
remain = []
for key, val in mapp.items():
if val != 0: remain.append(key)
# 对这些元素进行大小排序
因为根据题意没出现的元素要按照升序放在 arr1 的末尾
remain.sort()
# 再将这些元素根据出现次数依次添加到mapp中
for r in remain:
res.extend([r for _ in range(mapp[r])])
return res

十一、哈希表

11.1、题目汇总

11.1.1、剑指 Offer II 033. 变位词组（经典）

剑指 Offer II 033. 变位词组.

视频讲解.

class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
mapp = dict()
res = []
for i in range(len(strs)):
s = strs[i]
s = str(sorted(s))
# print(s)
if s not in mapp:
item = []
mapp[s] = item
mapp[s].append(strs[i])
for key, val in mapp.items():
res.append(val)
return res

11.1.2、剑指 Offer II 034. 外星语言是否排序

剑指 Offer II 034. 外星语言是否排序.

class Solution:
def isAlienSorted(self, words: List[str], order: str) -> bool:
mapp = dict((ch, index) for (index, ch) in enumerate(order))
def check(a, b):
i, j = 0, 0
while i<len(a) and j<len(b):
if mapp[a[i]] > mapp[b[j]]: return False
elif mapp[a[i]] < mapp[b[j]]: return True
else:
i += 1
j += 1
if i<len(a): return False
return True
start = 0
for end in range(1, len(words)):
if not check(words[start], words[end]): return False
start += 1
return True

11.1.3、Leetcode 217. 存在重复元素

Leetcode 217. 存在重复元素.

class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
mapp = set()
for i in range(len(nums)):
if nums[i] not in mapp:
mapp.add(nums[i])
else:
return True
return False

11.1.4、Leetcode 219. 存在重复元素 II

Leetcode 219. 存在重复元素 II.

class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
# 方法一、固定式滑动窗口 超时
def check(s):
s.sort()
for i in range(len(s)-1):
if s[i+1] == s[i]: return True
return False
if len(nums) < (k+1): return check(nums)
start = 0
for end in range(k+1, len(nums)+1):
if check(nums[start:end]): return True
start += 1
return False
# hash map思路
mapp = dict()
for i in range(len(nums)):
if nums[i] not in mapp:
mapp[nums[i]] = i
else:
if abs(mapp[nums[i]] - i) <= k: return True
else: mapp[nums[i]] = i
return False

11.1.5、剑指 Offer II 057. 值和下标之差都在给定的范围内(固定窗口) / 220. 存在重复元素 III（难 经典 桶+hash）

剑指 Offer II 057. 值和下标之差都在给定的范围内.

视频讲解.

class Solution:
def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
# 方法一、滑动窗口 超时
# def check(s):
#
s.sort()
#
for i in range(len(s)-1):
#
if abs(s[i+1] - s[i]) <= t: return True
#
return False
# if len(nums) < (k+1): return check(nums)
# start = 0
# for end in range(k+1, len(nums)+1):
#
if check(nums[start: end]): return True
#
start += 1
# return False
# 2、桶+hash
bucket_mapp = dict()
# 每个桶里面的元素相减都在[0,t]之间
bucket_size = t + 1
for i in range(len(nums)):
# 计算当前元素的桶id
bucket_id = nums[i] // bucket_size
# 如果当前桶中已经有元素了 说明满足条件abs(nums[i] - nums[j]) <= t
就返回True
if bucket_id in bucket_mapp: return True
# 当前桶没有元素就放进去
bucket_mapp[bucket_id] = nums[i]
# 检查当前桶和前一个桶的元素是否满足条件
if (bucket_id-1) in bucket_mapp and abs(bucket_mapp[bucket_id-1] - nums[i]) <= t: return True
# 检查当前桶和后一个桶的元素是否满足条件
if (bucket_id+1) in bucket_mapp and abs(bucket_mapp[bucket_id+1] - nums[i]) <= t: return True
# 如果i>=k 说明当前元素对应的桶中一定已经有一个元素了 删除那个元素 
# 要永远保证每个桶中只有一个元素
if i >= k:
bucket_mapp.pop(nums[i-k]//bucket_size)
return False

十二、前缀树/字典树trie

12.1、普通题目汇总

12.1.1、剑指 Offer II 062. 实现前缀树

剑指 Offer II 062. 实现前缀树.

leetcode 文字讲解.

class Trie:
def __init__(self):
self.children = [None for _ in range(26)]
self.isEnd = False
def insert(self, word: str) -> None:
cur_node = self
for c in word:
c = ord(c) - ord('a')
if not cur_node.children[c]:
# 当前char在不在
cur_node.children[c] = Trie()
cur_node = cur_node.children[c]
# 往下查 下一个char
# 如果没有就往下补 补到最后一个节点
# 如果有就一直往下查 查到最后一个节点
isEnd = True
cur_node.isEnd = True
def _searchPrefix(self, word):
# 查看前缀树中有没有以prefix为前缀的单词
cur_node = self
for c in word:
c = ord(c) - ord('a')
if not cur_node.children[c]: return None
cur_node = cur_node.children[c]
return cur_node
def search(self, word: str) -> bool:
# 查看前缀树中有没有单词word
node = self._searchPrefix(word)
# 前缀树中有以prefix为前缀的单词+这个单词的末尾str.isEnd=True => 前缀树中有单词word
return node is not None and node.isEnd
def startsWith(self, prefix: str) -> bool:
# 查看前缀树中有没有以prefix为前缀的单词
node = self._searchPrefix(prefix)
return True if node is not None else False

12.1.2、剑指 Offer II 063. 替换单词（经典）

剑指 Offer II 063. 替换单词.

leetcode 文字讲解.

class Trie():
def __init__(self):
self.children = [None for _ in range(26)]
self.isEnd = False
def insert(self, word):
# 在前缀树中插入word，但是如果前缀树中有词根相同且更短的单词，就不需要插入word 
cur_node = self
for c in word:
c = ord(c) - ord('a')
if cur_node.children[c] is None:
cur_node.children[c] = Trie()
cur_node = cur_node.children[c]
else:
cur_node
= cur_node.children[c]
if cur_node.isEnd == True: return
cur_node.isEnd = True
def searchPrefix(self, word):
# 在前缀树中查找word单词的最小前缀单词
如果没找到就返回word 
cur_node = self
res_prefix = ""
for char in word:
c = ord(char) - ord('a')
if cur_node.children[c] is None:
return word
else:
cur_node = cur_node.children[c]
res_prefix += char
if cur_node.isEnd == True: return res_prefix
return word
class Solution:
def replaceWords(self, dictionary: List[str], sentence: str) -> str:
T, res = Trie(), []
# 将所有的dictionary中的单词word插入前缀树中
# 但是如果前缀树中有词根相同且更短的单词，就不需要插入word
for prefix in dictionary:
T.insert(prefix)
# 在前缀树中查找sentence中每个单词（word）的最小前缀单词
如果没找到就返回原word 
# 这样也就实现了用dictionary中的单词替换sentence中单词的目的
for word in sentence.split():
# 将str中元素分开
res.append(T.searchPrefix(word))
return ' '.join(res)
# 将list中元素->str

12.1.3、剑指 Offer II 064. 神奇的字典（trie+bfs）

剑指 Offer II 064. 神奇的字典.

class Trie():
def __init__(self):
self.children = [None for _ in range(26)]
self.isEnd = False
def insert(self, word):
cur_node = self
for char in word:
c = ord(char) - ord('a')
if cur_node.children[c] is None:
cur_node.children[c] = Trie()
cur_node = cur_node.children[c]
cur_node.isEnd = True
def _search(self, root, word):
# 当前前缀树root有没有单词word
cur_node = root
for char in word:
c = ord(char) - ord('a')
if cur_node.children[c] is not None:
cur_node = cur_node.children[c]
else: return False
return True if cur_node.isEnd else False
def search(self, word):
cur_node = self
cur_word = word
for char in word:
c = ord(char) - ord('a')
# 比较cur_word[0]能否用cur_node.children替换
for i, child in enumerate(cur_node.children):
# 比较的永远是cur_word[0]
if child and c != i and self._search(child, cur_word[1:]):
return True
# cur_word[0]不能用cur_node替换 且 cur_node[c]不为空
if cur_node.children[c] is not None:
cur_node = cur_node.children[c]
cur_word = cur_word[1:]
else: return False
return
False
class MagicDictionary:
def __init__(self):
self.T = Trie()
def buildDict(self, dictionary: List[str]) -> None:
for word in dictionary:
self.T.insert(word)
def search(self, searchWord: str) -> bool:
return self.T.search(searchWord)

12.1.4、剑指 Offer II 065. 最短的单词编码（trie+dfs）

剑指 Offer II 065. 最短的单词编码.

class Trie():
def __init__(self):
self.children = [None for _ in range(26)]
self.isEnd = False
def insert(self, word):
cur_node =
self
for char in word:
c = ord(char) - ord('a')
if cur_node.children[c] is None:
cur_node.children[c] = Trie()
cur_node = cur_node.children[c]
cur_node.isEnd = True
def get_mini_length(self):
res = 0
def dfs(node, n):
nonlocal res
node_list = [nn for nn in node.children if nn is not None]
# 每条分支只能加一次
只有到分支结尾才能加

if node.isEnd == True and node_list == []:
res += n+1
# 每条分支都加上root #字符
for cur_node in node_list:
dfs(cur_node, n+1)
dfs(self, 0)
return res
class Solution:
def minimumLengthEncoding(self, words: List[str]) -> int:
T = Trie()
for word in words:
print(word[::-1])
T.insert(word[::-1])
return T.get_mini_length()

12.1.5、剑指 Offer II 066. 单词之和

剑指 Offer II 066. 单词之和.

class Trie():
def __init__(self):
self.children = [None for _ in range(26)]
self.val = 0
def insert(self, key, val):
cur_node =self
for char in key:
c = ord(char) - ord('a')
if cur_node.children[c] is None:
cur_node.children[c] = Trie()
cur_node = cur_node.children[c]
cur_node.val = val
def dfs(self, node):
if node is None: return 0
res = node.val
for child in node.children:
res += self.dfs(child)
return res
class MapSum:
def __init__(self):
self.T = Trie()
def insert(self, key: str, val: int) -> None:
self.T.insert(key, val)
def sum(self, prefix: str) -> int:
cur_node = self.T
for char in prefix:
c = ord(char) - ord('a')
if cur_node.children[c] is None: return 0
cur_node = cur_node.children[c]
return self.T.dfs(cur_node)

十三、普通题+设计类题

笔记

1. set 集合，相当于[]，但是执行速度比[]快，用法：a = set()
   添加一个元素：a.add(1) ，输出：{1}；
   添加多个元素：a.update({0, 2,4})，输出：{0, 1, 2, 4}
   删除一个指定元素：a.remove(2)，输出：{0, 1, 4} 如果元素不存在，则会发生错误
   删除一个指定元素： a.discard( x ) ，输出：{0, 1, 4} 如果元素不存在，不会发生错误
   删除第一个元素：a.pop()，输出：{1, 4}
   清空集合：a.clear()
   判断元素是否在集合中存在: if x in a:

13.1、普通题目汇总

13.1.1、剑指 Offer II 035. 最小时间差

剑指 Offer II 035. 最小时间差.

class Solution:
def findMinDifference(self, timePoints: List[str]) -> int:
def countMM(timePoint):
return int(timePoint[:2]) * 60 + int(timePoint[3:])
timePoints.sort()
min_val = float('inf')
first = countMM(timePoints[0])
pre = first
for i in range(1, len(timePoints)):
cur = countMM(timePoints[i])
min_val = min(min_val, cur - pre)
pre = cur
min_val = min(min_val, first+24*60-pre)
return min_val

13.2、设计类题目汇总

13.2.1、剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器

剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器.

from random import choice
class RandomizedSet():
def __init__(self):
"""
Initialize your data structure here.
"""
self.dict = {}
self.list = []
def insert(self, val: int) -> bool:
"""
Inserts a value to the set. Returns true if the set did not already contain the specified element.
"""
if val in self.dict:
return False
self.dict[val] = len(self.list)
self.list.append(val)
return True
def remove(self, val: int) -> bool:
"""
Removes a value from the set. Returns true if the set contained the specified element.
"""
if val in self.dict:
# move the last element to the place idx of the element to delete
last_element, idx = self.list[-1], self.dict[val]
self.list[idx], self.dict[last_element] = last_element, idx
# delete the last element
self.list.pop()
del self.dict[val]
return True
return False
def getRandom(self) -> int:
"""
Get a random element from the set.
"""
return choice(self.list)

最后

以上就是寂寞滑板为你收集整理的【剑指 Offer（专项突击版）前100题】一、链表二、树三、搜索：回溯+DFS+BFS四、双指针+二分查找五、滑动窗口六、单调栈Stack（后进先出）+ 单调队列Queue（先进先出）七、前缀和八、位运算九、动态规划DP十、 排序十一、哈希表十二、前缀树/字典树trie十三、普通题+设计类题的全部内容，希望文章能够帮你解决【剑指 Offer（专项突击版）前100题】一、链表二、树三、搜索：回溯+DFS+BFS四、双指针+二分查找五、滑动窗口六、单调栈Stack（后进先出）+ 单调队列Queue（先进先出）七、前缀和八、位运算九、动态规划DP十、 排序十一、哈希表十二、前缀树/字典树trie十三、普通题+设计类题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。