经典题目
排序
🚩冒泡排序 — 逐个比较，最大的后移
1
2
3
4
5
6
def bubbleSort(nums):
for i in range(len(nums)):
# Last i elements are already in place
for j in range(len(nums)-i-1):
if nums[j] > nums[j+1]:
nums[j], nums[j+1] = nums[j+1], nums[j]
选择排序 — 遍历选择最小的，放到最前
🚩插入排序（熟悉） — 发现小数字，向前交换
简单排序里，插入排序最好（样本小且基本有序时，效率较高，效果好）
1
2
3
4
5
6
7
8
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
for ind in range(1,len(nums)):
i = ind
while i > 0 and nums[i] < nums[i-1]:
nums[i], nums[i-1] = nums[i-1], nums[i]
i -= 1
return nums
希尔排序 — 改进的插入排序，间隔由大到小排序
🚩 归并排序（掌握）
最坏情况效果最好
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def merge_sort(self, nums, l, r):
if l == r:
return
mid = (l + r) // 2
self.merge_sort(nums, l, mid)
self.merge_sort(nums, mid + 1, r)
tmp = []
i, j = l, mid + 1
while i <= mid or j <= r:
if i > mid or (j <= r and nums[j] < nums[i]):
tmp.append(nums[j])
j += 1
else:
tmp.append(nums[i])
i += 1
nums[l: r + 1] = tmp
def sortArray(self, nums: List[int]) -> List[int]:
self.merge_sort(nums, 0, len(nums) - 1)
return nums
🚩 快速排序 （掌握）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
def partition(nums, left_bound, right_bound):
pivot = nums[right_bound]
l,r = left_bound, right_bound - 1
while l <= r:
while l <= r and nums[l] <= pivot:
l += 1
while l <= r and nums[r] > pivot:
r -= 1
if l < r:
nums[l], nums[r] = nums[r], nums[l]
# 注意要把轴放在中间, 因为最后一次循环一定是走的l++，即当前l和r指向的是大值，互换l和锚点
nums[l], nums[right_bound] = nums[right_bound], nums[l]
return l
def quick_sort(nums, left_bound, right_bound):
if left_bound>=right_bound:
return
mid = partition(nums, left_bound, right_bound)
quick_sort(nums, left_bound, mid - 1)
quick_sort(nums, mid + 1, right_bound) # 注意是mid+1
quick_sort(nums, 0, len(nums)-1)
return nums
快速排序是每个程序员都应当掌握的排序算法。当然我们接触的第一个排序算法可能是插入排序或者冒泡排序，但数据量一旦超过几万，插入和冒泡的性能会非常差。这时时间复杂度的渐进优势就表现出来了。 平均情况下快速排序的时间复杂度是Θ(𝑛lg𝑛)，最坏情况是𝑛2，但通过随机算法可以避免最坏情况。由于递归调用，快排的空间复杂度是Θ(lg𝑛)。时间复杂度$O(nlogn)$，空间复杂度$O(logn)$。
步骤：
- 找基准
- 分区
- 递归
快速排序算法其实很简单，采用分治策略。步骤如下：
- 选取一个基准元素（pivot)
- 比pivot小的放到pivot左边，比pivot大的放到pivot右边
- 对pivot左边的序列和右边的序列分别递归的执行步骤1和步骤2
基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。 算法描述: 快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:
- 从数列中挑出一个元素,称为 “基准”(pivot);
- 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
- 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
二叉树
✅ 07. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
1
2
3
4
5
6
7
8
9
10
11
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
2️⃣
细节
在中序遍历中对根节点进行定位时，一种简单的方法是直接扫描整个中序遍历的结果并找出根节点，但这样做的时间复杂度较高。我们可以考虑使用哈希表来帮助我们快速地定位根节点。对于哈希映射中的每个键值对，键表示一个元素（节点的值），值表示其在中序遍历中的出现位置。在构造二叉树的过程之前，我们可以对中序遍历的列表进行一遍扫描，就可以构造出这个哈希映射。在此后构造二叉树的过程中，我们就只需要 O(1) 的时间对根节点进行定位了。
1
2
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
1
2
3
4
5
6
7
8
9
10
11
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not preorder or not inorder:
return None
root_val = preorder[0]
ind = inorder.index(root_val)
print(ind)
root = TreeNode(root_val)
root.left = self.buildTree(preorder[1:ind+1], inorder[:ind])
root.right = self.buildTree(preorder[ind+1:], inorder[ind+1:])
return root
官解（使用了set）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
def recur(root, left, right):
if left > right: return # 递归终止
node = TreeNode(preorder[root]) # 建立根节点
i = dic[preorder[root]] # 划分根节点、左子树、右子树
node.left = recur(root + 1, left, i - 1) # 开启左子树递归
node.right = recur(i - left + root + 1, i + 1, right) # 开启右子树递归
return node # 回溯返回根节点
dic, preorder = {}, preorder
for i in range(len(inorder)):
dic[inorder[i]] = i
return recur(0, 0, len(inorder) - 1)
🚩(30m)剑指 Offer 26. 树的子结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
def compare(nodeA,nodeB):
# B 被遍历空，返回True
if not nodeB:
return True
# 防止 A.val 报错, 值不同，返回False
if not nodeA or nodeA.val != nodeB.val:
return False
# 继续递归遍历后续子树是否相同
return compare(nodeA.left, nodeB.left) or compare(nodeA.right, nodeB.right)
if not A or not B:
return False
# 通过递归将A的结点分别和B进行比较，这里的 or 具有阻断效应，后面的递归调用不执行，直接向上返回
return compare(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right, B)
2️⃣ 注意：
这里的 or 具有阻断效应，后面的递归调用不执行，直接向上返回
链表
🚩206. 反转链表
反转一个单链表。
1
2
3
4
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
# 申请两个节点，pre和 cur，pre指向None
pre = None
cur = head
# 遍历链表，while循环里面的内容其实可以写成一行
# 这里只做演示，就不搞那么骚气的写法了
while cur:
# 记录当前节点的下一个节点
tmp = cur.next
# 然后将当前节点指向pre
cur.next = pre
# pre和cur节点都前进一位
pre = cur
cur = tmp
return pre
🚩（20m） 递归解法 + 迭代
1
2
3
4
5
6
7
8
9
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
# digui
if not head or not head.next: # 只有当前节点
return head
last = self.reverseList(head.next) # 拆解为子问题
head.next.next = head
head.next = None
return last
1
2
3
4
5
6
7
8
9
# 迭代
if not head: # 只有当前节点
return head
pre, cur = None, head
while cur:
tmp = cur.next
cur.next = pre
pre, cur = cur, tmp
return pre
dfs
✅ 46. 全排列
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
1
输入: [1,2,3]输出:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
✅（5m）
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def helper(path, nums):
if len(path) == len(nums):
res.append(path)
for i in nums:
if i not in path:
helper(path+[i], nums)
res = []
path = []
helper(path, nums)
return res
总结：
- 在basecase里，注意，满足条件了就要return出去
- 组合问题需要做选择前添加判断，跳过不满足条件的选择
✅(20m)79. 单词搜索
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
1
# 示例board =[ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']]给定 word = "ABCCED", 返回 true给定 word = "SEE", 返回 true给定 word = "ABCB", 返回 false
✅（20m）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def check(i: int, j: int, k: int) -> bool:
if board[i][j] != word[k]:
return False
if k == len(word) - 1:
return True
visited.add((i, j))
result = False
for di, dj in directions:
newi, newj = i + di, j + dj
if 0 <= newi < len(board) and 0 <= newj < len(board[0]):
if (newi, newj) not in visited:
if check(newi, newj, k + 1):
result = True
break
visited.remove((i, j))
return result
h, w = len(board), len(board[0])
visited = set()
for i in range(h):
for j in range(w):
if check(i, j, 0):
return True
return False
🚩12. 矩阵中的路径
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径(路径中的字母用加粗标出)。
[[“a”,”b”,”c”,”e”], [”s”,”f”,”c”,”s”], [“a”,”d”,”e”,”e”]]
但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
1
示例 1：输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"输出：true示例 2：输入：board = [["a","b"],["c","d"]], word = "abcd"输出：false
1
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]word = "ABCCED"
2️⃣
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def dfs(i, j, k):
if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k] or (i,j) in visited: return False
if k == len(word) - 1: return True
visited.add((i,j))
res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
visited.remove((i,j))
return res
for i in range(len(board)):
for j in range(len(board[0])):
visited = set()
if dfs(i, j, 0): return True
return False
