- 柯摩的刷题日记
- 1️⃣ 数据结构篇
- 📚 1️⃣.1️⃣ 二叉树
- 📚 1️⃣.2️⃣ 链表
- 📚 1️⃣.3️⃣ 栈和队列
- 📚 1️⃣.4️⃣ 优先级队列 (堆)
0️⃣1️⃣2️⃣3️⃣4️⃣5️⃣6️⃣7️⃣8️⃣9️⃣🔟🔢*️⃣🆕🆒🆗🆙
刷题路径：
algorithm-pattern 练习题 —> LeetCode 精选 TOP 面试题(一个半月) —> 剑指 offer(半个月)
- 掌握二叉树递归与非递归遍历
- 理解 DFS 前序遍历与分治法
- 理解 BFS 层次遍历
前序遍历：先访问根节点，再前序遍历左子树，再前序遍历右子树 中序遍历：先中序遍历左子树，再访问根节点，再中序遍历右子树 后序遍历：先后序遍历左子树，再后序遍历右子树，再访问根节点。
- 注意点
- 以根访问顺序决定是什么遍历
- 左子树都是优先右子树
def preorder_rec(root):
if root is None:
return
visit(root)
preorder_rec(root.left)
preorder_rec(root.right)
return
def inorder_rec(root):
if root is None:
return
inorder_rec(root.left)
visit(root)
inorder_rec(root.right)
return
def postorder_rec(root):
if root is None:
return
postorder_rec(root.left)
postorder_rec(root.right)
visit(root)
returnclass Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
preorder = []
if root is None:
return preorder
s = [root]
while len(s) > 0:
node = s.pop()
preorder.append(node.val)
if node.right is not None:
s.append(node.right)
if node.left is not None:
s.append(node.left)
return preorderclass Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
s, inorder = [], []
node = root
while len(s) > 0 or node is not None:
if node is not None:
s.append(node)
node = node.left
else:
node = s.pop()
inorder.append(node.val)
node = node.right
return inorderclass Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
s, postorder = [], []
node, last_visit = root, None
while len(s) > 0 or node is not None:
if node is not None:
s.append(node)
node = node.left
else:
peek = s[-1]
if peek.right is not None and last_visit != peek.right:
node = peek.right
else:
last_visit = s.pop()
postorder.append(last_visit.val)
return postorder- 注意点
- 核心就是：根节点必须在右节点弹出之后，再弹出
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func preorderTraversal(root *TreeNode) []int {
result := make([]int, 0)
dfs(root, &result)
return result
}
// V1：深度遍历，结果指针作为参数传入到函数内部
func dfs(root *TreeNode, result *[]int) {
if root == nil {
return
}
*result = append(*result, root.Val)
dfs(root.Left, result)
dfs(root.Right, result)
}// V2：通过分治法遍历
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []
left_result = self.preorderTraversal(root.left)
right_result = self.preorderTraversal(root.right)
return [root.val] + left_result + right_result- 注意点：
- DFS 深度搜索（从上到下） 和分治法区别：前者一般将最终结果通过指针参数传入，后者一般递归返回结果最后合并
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
levels = []
if root is None:
return levels
bfs = collections.deque([root])
while len(bfs) > 0:
levels.append([])
level_size = len(bfs)
for _ in range(level_size):
node = bfs.popleft()
levels[-1].append(node.val)
if node.left is not None:
bfs.append(node.left)
if node.right is not None:
bfs.append(node.right)
return levels先分别处理局部，再合并结果。
适用场景
-
快速排序
-
归并排序
-
二叉树相关问题
分治法模板
-
递归返回条件
-
分段处理
-
合并结果
func traversal(root *TreeNode) ResultType {
// nil or leaf
if root == nil {
// do something and return
}
// Divide
ResultType left = traversal(root.Left)
ResultType right = traversal(root.Right)
// Conquer
ResultType result = Merge from left and right
return result
}// V2：通过分治法遍历二叉树
func preorderTraversal(root *TreeNode) []int {
result := divideAndConquer(root)
return result
}
func divideAndConquer(root *TreeNode) []int {
result := make([]int, 0)
// 返回条件(null & leaf)
if root == nil {
return result
}
// 分治(Divide)
left := divideAndConquer(root.Left)
right := divideAndConquer(root.Right)
// 合并结果(Conquer)
result = append(result, root.Val)
result = append(result, left...)
result = append(result, right...)
return result
}func MergeSort(nums []int) []int {
return mergeSort(nums)
}
func mergeSort(nums []int) []int {
if len(nums) <= 1 {
return nums
}
// 分治法：divide 分为两段
mid := len(nums) / 2
left := mergeSort(nums[:mid])
right := mergeSort(nums[mid:])
// 合并两段数据
result := merge(left, right)
return result
}
func merge(left, right []int) (result []int) {
// 两边数组合并游标
l := 0
r := 0
// 注意不能越界
for l < len(left) && r < len(right) {
// 谁小合并谁
if left[l] > right[r] {
result = append(result, right[r])
r++
} else {
result = append(result, left[l])
l++
}
}
// 剩余部分合并
result = append(result, left[l:]...)
result = append(result, right[r:]...)
return
}- 注意点
- 递归需要返回结果用于合并
func QuickSort(nums []int) []int {
// 思路：把一个数组分为左右两段，左段小于右段，类似分治法没有合并过程
quickSort(nums, 0, len(nums)-1)
return nums
}
// 原地交换，所以传入交换索引
func quickSort(nums []int, start, end int) {
if start < end {
// 分治法：divide
pivot := partition(nums, start, end)
quickSort(nums, 0, pivot-1)
quickSort(nums, pivot+1, end)
}
}
// 分区
func partition(nums []int, start, end int) int {
p := nums[end]
i := start
for j := start; j < end; j++ {
if nums[j] < p {
swap(nums, i, j)
i++
}
}
// 把中间的值换为用于比较的基准值
swap(nums, i, end)
return i
}
func swap(nums []int, i, j int) {
t := nums[i]
nums[i] = nums[j]
nums[j] = t
}- 注意点
- 快排由于是原地交换所以没有合并过程 传入的索引是存在的索引（如：0、length-1 等），越界可能导致崩溃。
1️⃣ 104. Maximum Depth of Binary Tree
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。
简单题，常规思路，分治法
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if root is None:
return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))1️⃣ 105. 平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
分治法，左边平衡 && 右边平衡 && 左右两边高度 <= 1
class Solution(object):
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
def depth(root):
if root == None:
return 0, True
dl, bl = depth(root.left)
dr, br = depth(root.right)
return max(dl, dr) + 1, bl and br and abs(dl- dr) <2
_, out = depth(root)
return out1️⃣ 124. 二叉树中的最大路径和
给定一个非空二叉树，返回其最大路径和。
思路：分治法。最大路径的可能情况：左子树的最大路径，右子树的最大路径，或通过根结点的最大路径。其中通过根结点的最大路径值等于以左子树根结点为端点的最大路径值加以右子树根结点为端点的最大路径值再加上根结点值，这里还要考虑有负值的情况即负值路径需要丢弃不取。
class Solution(object):
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.maxPath = float('-inf')
def largest_path_ends_at(node):
if node is None:
return float('-inf')
e_l = largest_path_ends_at(node.left)
e_r = largest_path_ends_at(node.right)
self.maxPath = max(self.maxPath, node.val +
max(0, e_l)+max(0, e_r), e_l, e_r)
return node.val + max(e_l, e_r, 0)
largest_path_ends_at(root)
return self.maxPath1️⃣ 236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
思路：分治法，有左子树的公共祖先或者有右子树的公共祖先，就返回子树的祖先，否则返回根节点
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root is None:
return None
if root == p or root == q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left is not None and right is not None:
return root
elif left is not None:
return left
elif right is not None:
return right
else:
return None1️⃣ 103. 二叉树的锯齿形层序遍历
给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
思路：在BFS迭代模板上改用双端队列控制输出顺序
class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
levels = []
if root is None:
return levels
s = collections.deque([root])
start_from_left = True
while len(s) > 0:
levels.append([])
level_size = len(s)
if start_from_left:
for _ in range(level_size):
node = s.popleft()
levels[-1].append(node.val)
if node.left is not None:
s.append(node.left)
if node.right is not None:
s.append(node.right)
else:
for _ in range(level_size):
node = s.pop()
levels[-1].append(node.val)
if node.right is not None:
s.appendleft(node.right)
if node.left is not None:
s.appendleft(node.left)
start_from_left = not start_from_left
return levels1️⃣ 98. 验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
- 思路1：中序遍历后检查输出是否有序，缺点是如果不平衡无法提前返回结果。
- 思路2：分治法，一个二叉树为合法的二叉搜索树当且仅当左右子树为合法二叉搜索树且根结点值小于右子树最小值大于左子树最大值。缺点是若不用迭代形式实现则无法提前返回，而迭代实现又比较复杂。
- 思路3：利用二叉搜索树的性质，根结点为左子树的右边界，右子树的左边界，使用先序遍历自顶向下更新左右子树的边界并检查是否合法，迭代版本实现简单且可以提前返回结果。
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
if root is None:
return True
s = [(root, float('-inf'), float('inf'))]
while len(s) > 0:
node, low, up = s.pop()
if node.left is not None:
if node.left.val <= low or node.left.val >= node.val: # up更新为左子树的值
return False
s.append((node.left, low, node.val))
if node.right is not None:
if node.right.val <= node.val or node.right.val >= up: # low更新为右子树的值
return False
s.append((node.right, node.val, up))
# 考虑一个有父节点和两个子节点的右节点，它要大于父节点并且要小于右节点
return True1️⃣ 701. 二叉搜索树中的插入操作
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。
思路：找到最后一个叶子节点满足插入条件即可。
class Solution:
def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
if root is None:
return TreeNode(val)
node = root
while True:
if val > node.val:
if node.right is None:
node.right = TreeNode(val)
return root
else:
node = node.right
else:
if node.left is None:
node.left = TreeNode(val)
return root
else:
node = node.left1️⃣ 83. 删除排序链表中的重复元素
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
常规思路
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if head is None:
return head
current = head
while current.next is not None:
if current.next.val == current.val:
current.next = current.next.next
else:
current = current.next
return head1️⃣ 82. 删除排序链表中的重复元素 II
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
思路：链表头结点可能被删除，所以用 dummy node 辅助删除，current用来删除重复的第一个节点，peek删除重复的节点的第二个至第n个，最后判断peek是否删除过，还是最后删除一下。
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if head is None:
return head
dummy = ListNode(next=head)
current, peek = dummy, head
find_dup = False
while peek.next is not None:
if peek.next.val == peek.val:
find_dup = True
peek.next = peek.next.next
else:
if find_dup:
find_dup = False
current.next = current.next.next
else:
current = current.next
peek = peek.next
if find_dup:
current.next = current.next.next
return dummy.next1️⃣ 206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
- 思路一：直接手动反转，tmp一直往后指，head不断更新最新的节点
- 思路二：采用递归，next的next指向自己，自己的next指向空
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if head is None:
return head
tail = head
while tail.next is not None:
# put tail.next to head
tmp = tail.next
tail.next = tail.next.next
tmp.next = head
head = tmp
return headclass Solution:
def reverseList(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
rev_next = self.reverseList(head.next)
head.next.next = head
head.next = None
return rev_next1️⃣ 92. 反转链表 II
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
- 思路：先找到 m 处, 再反转 n - m 次即可，核心点就是start处，要使用curr.next而不是start
class Solution:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
if head is None:
return head
n -= m
curr = dummy = ListNode(next=head)
while m > 1:
curr = curr.next
m -= 1
start = curr.next
while n > 0:
tmp = start.next
start.next = tmp.next
tmp.next = curr.next # 这里不能用start，下面同样，主要是需要curr.next来连接，虽然start一直在变，而curr.next一直指着第一个start
curr.next = tmp
n -= 1
return dummy.next1️⃣ 21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
- 思路：定义一个dummy，再用tail作为其移动指针，按照顺序连接
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
tail = dummy = ListNode()
while l1 is not None and l2 is not None:
if l1.val > l2.val:
tail.next = l2
l2 = l2.next
else:
tail.next = l1
l1 = l1.next
tail = tail.next
if l1 is None:
tail.next = l2
else:
tail.next = l1
return dummy.next1️⃣ 86. 分隔链表
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
- 思路：将大于 x 的节点，放到另外一个链表，最后连接这两个链表，当头节点不确定的时候，使用哑巴节点
class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
p = l = ListNode()
q = s = ListNode(next=head)
while q.next is not None:
if q.next.val < x:
q = q.next
else:
p.next = q.next
q.next = q.next.next
p = p.next
p.next = None
q.next = l.next
return s.next
1️⃣ 148. 排序链表
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
- 思路：归并排序，slow-fast找中点
- 找中间节点方法：快慢指针，判断 fast 及 fast.Next 是否为 None 值
- 递归 mergeSort 需要断开中间节点，mid.next = None
- 递归返回条件为 head 为 None 或者 head.Next 为 None
class Solution:
def _merge(self, l1, l2): # 合并两个有序链表
tail = l_merge = ListNode()
while l1 is not None and l2 is not None:
if l1.val > l2.val:
tail.next = l2
l2 = l2.next
else:
tail.next = l1
l1 = l1.next
tail = tail.next
if l1 is not None:
tail.next = l1
else:
tail.next = l2
return l_merge.next
def _findmid(self, head): # 找链表的中间节点
slow, fast = head,head.next
while fast is not None and fast.next is not None:
fast = fast.next.next
slow = slow.next
return slow
def sortList(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
mid = self._findmid(head) # 先找中间节点
tail = mid.next # tail指向下一半的第一个节点
mid.next = None # 断开两个链表
return self._merge(self.sortList(head),self.sortList(tail)) # 递归合并两个区间
1️⃣ 143. 排序链表
给定一个单链表 L：L→L→…→L__n→L 将其重新排列后变为： L→L__n→L→L__n→L→L__n→…
- 思路：找到中点断开，翻转后面部分，然后左一个右一个地合并链表
- 逆转链表的快速写法
- 通过快慢指针找到中间节点，再左右开弓
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
# 逆转链表的快捷写法
prev, curr = None, head
while curr is not None:
curr.next,prev,curr = prev,curr,curr.next
return prev
def reorderList(self, head: ListNode) -> None:
"""
Do not return anything, modify head in-place instead.
"""
if head is None or head.next is None or head.next.next is None:
return
slow, fast = head, head.next
while fast is not None and fast.next is not None:
fast = fast.next.next
slow = slow.next
h, m = head, slow.next
slow.next = None
m = self.reverseList(m)
while h is not None and m is not None: # 左边链表一个，右边链一个地接合
p = m.next
m.next = h.next
h.next = m
h = h.next.next
m = p
return
1️⃣ 141. 环形链表
给定一个链表，判断链表中是否有环。
- 思路：快慢指针，快慢指针相同则有环
- 证明：如果有环每走一步快慢指针距离会减 1
- 空间复杂度 O(1) 最优
- 时间复杂度 O(n) 但循环次数小于等于 n
class Solution:
def hasCycle(self, head: ListNode) -> bool:
slow = fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if fast == slow:
return True
return False
1️⃣ 142. 环形链表 II
给定一个链表，返回链表开始入环的第一个节点. 如果链表无环，则返回
null。
- 思路：快慢指针，快慢相遇之后，慢指针回到头，快慢指针步调一致一起移动，再次相遇点即为入环点。
- 指针比较时直接比较对象，不要用值比较，链表中有可能存在重复值情况
- 第一次相交后，快指针需要从下一个节点开始和头指针一起匀速移动
- 时间复杂度 O(n) 但循环次数小于等于 n
- fast 如果初始化为 head.Next 则中点在 slow.Next
- fast 初始化为 head,则中点在 slow
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
slow = fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow == fast:
slow = head
while fast != slow:
fast = fast.next
slow = slow.next
return slow
return None
1️⃣ 234. 回文链表
请判断一个链表是否为回文链表。
- 思路：O(1) 空间复杂度的解法需要破坏原链表
- 找中点
- 反转后半个list
- 判断回文
- 在实际应用中往往还需要复原（后半个list再反转一次后拼接），操作比较复杂
- 可以采用只取值比较的做法
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
s = []
slow = fast = head
while fast is not None and fast.next is not None:
s.append(slow.val)
slow = slow.next
fast = fast.next.next
if fast is not None: # 中点是slow，如果是双数节点数，下一半的开头在slow.next
slow = slow.next
while len(s) > 0:
if slow.val != s.pop():
return False
slow = slow.next
return True
1️⃣ 138. 复制带随机指针的链表
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的 深拷贝。
- 思路：利用collections.defaultdict()创造hash table，存储 random 指针的连接关系
import collections
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if head is None:
return None
parent = collections.defaultdict(list) # 创造hash表结构
out = Node(0)
o, n = head, out
while o is not None:
n.next = Node(o.val) # 复制next结构
n = n.next
if o.random is not None:
parent[o.random].append(n) # 存储random表
o = o.next
o, n = head, out.next
while o is not None:
if o in parent:
for p in parent[o]: # o, n 同步后移，然后对parent[o]中所有值进行连接
p.random = n # 这里指向n是因为o,n同步移动，所以n跟o在同样的位置
o = o.next
n = n.next
return out.next
1️⃣ 155. 最小栈
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
- 思路：用元组来存储栈中的元素，第一个值为插入的值，第二个值为最小值，随着插入不断更新，保证当前最小值在栈顶即可。
import collections
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
def push(self, val: int) -> None:
if len(self.stack) > 0:
self.stack.append((val,min(val,self.stack[-1][1])))
else:
self.stack.append((val,val))
def pop(self) -> None:
return self.stack.pop()[0]
def top(self) -> int:
return self.stack[-1][0]
def getMin(self) -> int:
return self.stack[-1][1]
1️⃣ 150. 逆波兰表达式求值
波兰表达式计算 > 输入: ["2", "1", "+", "3", "*"] > 输出: 9 解释: ((2 + 1) * 3) = 9
- 思路：通过栈保存原来的元素，遇到表达式弹出运算，再推入结果，重复这个过程
import collections
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
# 去掉括号后表达式无歧义
# 遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。
def comp(or1, op, or2):
if op == '+':
return or1 + or2
if op == '-':
return or1 - or2
if op == '*':
return or1 * or2
if op == '/':
abs_result = abs(or1) // abs(or2)
return abs_result if or1 * or2 > 0 else -abs_result
stack = []
for token in tokens:
if token in ['+', '-','*', '/']:
or2 = stack.pop()
or1 = stack.pop()
stack.append(comp(or1,token,or2))
else:
stack.append(int(token))
return stack[0] 1️⃣ 394. 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。 s = "3[a]2[bc]", 返回 "aaabcbc". s = "3[a2[c]]", 返回 "accaccacc". s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
- 思路：通过两个栈进行操作，一个用于存数，另一个用来存字符串
class Solution:
def decodeString(self, s: str) -> str:
stack_str = [''] # 栈初始化为字符串一定要注意
stack_num = []
num = 0
for c in s:
if c >= '0' and c <= '9':
num = num * 10 + int(c)
elif c == '[':
stack_num.append(num)
stack_str.append('')
num = 0
elif c == ']':
cur_str = stack_str.pop()
stack_str[-1] += cur_str * stack_num.pop() # 这里有一种情况："3[a2[c]]"括号里包括号，所以一定要先弹出，再合并，最后输出第一个元素
else:
stack_str[-1] += c
return stack_str[0]1️⃣ 94. 二叉树的中序遍历
给定一个二叉树，返回它的中序遍历。
- 思路：不断往左子树前进，进栈，若左子树为空，那么就弹出栈顶元素打印，再进行右子树进栈。
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
inorder, stack = [], []
node = root
while len(stack) > 0 or node is not None:
if node is not None:
stack.append(node)
node = node.left
else:
node = stack.pop()
inorder.append(node.val)
node = node.right
return inorder
1️⃣ 133. 克隆图
给你无向连通图中一个节点的引用，请你返回该图的深拷贝（克隆）。
- 思路：BFS
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
if node is None:
return None
visited = {node:Node(node.val,[])}
bfs = collections.deque([node])
while len(bfs) > 0:
curr = bfs.popleft()
curr_copy = visited[curr]
for n in curr.neighbors:
if n not in visited:
visited[n] = Node(n.val, [])
bfs.append(n)
curr_copy.neighbors.append(visited[n])
return visited[node]
1️⃣ 200. 岛屿数量
给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
- 思路：沉岛思想：如果遇到一块陆地，DFS往四个方向搜索，把经过的陆地标记为湖水（沉岛，避免重复遍历）
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
def dfs_iter(i, j): # 非递归
dfs = []
dfs.append((i, j))
while len(dfs) > 0:
i, j = dfs.pop()
if grid[i][j] == '1':
grid[i][j] = '0'
if i-1 >= 0:
dfs.append((i-1, j))
if j-1 >= 0:
dfs.append((i, j-1))
if i+1 < m:
dfs.append((i+1, j))
if j+1 < n:
dfs.append((i, j+1))
return
def dfs(grid, i, j): # 递归
if not 0 <= i < m or not 0 <= j < n or grid[i][j] == '0': # 判断是否在某个范围之外 not 用法 很新奇
return # 碰到水或者出界
grid[i][j] = '0' # 将访问过的陆地标记为水面
dfs(grid, i-1, j) # 向上
dfs(grid, i+1, j) # 向下
dfs(grid, i, j-1) # 向左
dfs(grid, i, j+1) # 向右
num_island = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
num_island += 1
# dfs_iter(i, j)
dfs(grid, i, j)
return num_island 1️⃣ 84. 柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。
- 思路一：必会暴力法，比较每个以 i 开始 j 结束的最大矩形，A(i, j) = (j - i + 1) * min_height(i, j)，时间复杂度 O(n^2) 无法 AC。
- 思路二：包含当前 bar 最大矩形的边界为左边第一个高度小于当前高度的 bar 和右边第一个高度小于当前高度的 bar。暂时没看懂
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
max_area = 0
n = len(heights)
for i in range(n):
min_height = heights[i]
for j in range(i, n):
min_height = min(min_height, heights[j])
max_area = max(max_area, min_height * (j - i + 1))
return max_areaclass Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
n = len(heights)
stack = [-1]
max_area = 0
for i in range(n):
while len(stack) > 1 and heights[stack[-1]] > heights[i]:
h = stack.pop()
max_area = max(max_area, heights[h] * (i - stack[-1] - 1))
stack.append(i)
while len(stack) > 1:
h = stack.pop()
max_area = max(max_area, heights[h] * (n - stack[-1] - 1))
return max_area1️⃣ 232. 用栈实现队列
使用栈实现队列
- 两个栈，一个进，一个出
- cache负责进数据，out负责出数据
- 当out为空时，将cache一股脑都倒进去，再弹出顶层元素
- 当out不为空时，就弹出它顶层元素
class MyQueue:
def __init__(self):
"""
Initialize your data structure here.
"""
self.cache = []
self.out = []
def push(self, x: int) -> None:
"""
Push element x to the back of queue.
"""
self.cache.append(x)
def pop(self) -> int:
"""
Removes the element from in front of queue and returns that element.
"""
if len(self.out) == 0:
while len(self.cache) > 0:
self.out.append(self.cache.pop())
return self.out.pop()
def peek(self) -> int:
"""
Get the front element.
"""
if len(self.out) > 0:
return self.out[-1]
else:
return self.cache[0]
def empty(self) -> bool:
"""
Returns whether the queue is empty.
"""
return len(self.cache) == 0 and len(self.out) == 0
