Python算法思想

---

一 枚举算法

核心思想：
将问题所有可能的答案枚举，根据条件判断是否合适，合适则保留，否则丢弃。

经典案例-1（判断阿姆斯特朗数）

题目：如果一个n位正整数等于其各位数字的n次方之和，则称该数为阿姆斯特朗数。例如1^3 + 5^3 + 3^3 = 153。
获取1000以内的阿姆斯特朗数。

def is_armstrong(num: int) -> bool:""""""num_str = str(num)num_str_len = len(num_str)sum = 0for n in num_str:sum += int(n) ** num_str_lenif sum == num:return Truereturn Falseif __name__ == '__main__':""""""res = []for i in range(1, 1000):if is_armstrong(i):res.append(i)print(res)  # [1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407]

经典案例-2（解百鸡问题）

题目：公鸡5文钱一只，母鸡3文钱一只，小鸡3只一文钱，用100文钱买一百只鸡，其中公鸡，母鸡，小鸡都必须要有。 问：公鸡，母鸡，小鸡要买多少只刚好凑足100文钱。

lp = 5
mp = 3
sp = 1/3res = []for i in range(1, 20):for j in range(1, 34):for k in range(1, 300):if i + j + k == 100 and lp * i + mp * j + sp * k == 100:res.append((i, j, k))print(res)    # [(4, 18, 78), (8, 11, 81), (12, 4, 84)]

二 递归算法

核心思想：
是将一个复杂问题分解成多个相似的子问题，并通过递归调用函数自身来解决这些子问题，最终通过合并子问题的解来得到原问题的解。

经典案例-1（n的阶乘）

# n的阶乘，示例：5! = 5 x 4 x 3 x 2 x 1
def num_factorial(num):""""""if num == 1:    # 终止条件return 1return num * num_factorial(num-1)    # num-1 接近终止条件num_factorial(5)    # 120

经典案例-2（斐波那契数列）

题目：请你编写一个生成器函数，并返回一个可以生成 斐波那契数列 的生成器对象。
斐波那契数列 的递推公式为 Xn = Xn-1 + Xn-2 。
这个数列的前几个数字是 0, 1, 1, 2, 3, 5, 8, 13 。

def fibonacci(n: int) -> int:""""""if n == 0 or n == 1:return nres = fibonacci(n-1) + fibonacci(n-2)return resfibonacci(7)    # 13

经典案例-3（二叉树遍历(DFS)）

# Definition for a binary tree node.
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef preorder_traversal(root: TreeNode, res: list) -> list:""""""res.append(root.val)if root.left is not None:preorder_traversal(root.left, res)if root.right is not None:preorder_traversal(root.right, res)return resdef inorder_traversal(root: TreeNode, res: list) -> list:""""""if root.left is not None:inorder_traversal(root.left, res)res.append(root.val)if root.right is not None:inorder_traversal(root.right, res)return resdef postorder_traversal(root: TreeNode, res: list) -> list:""""""if root.left is not None:postorder_traversal(root.left, res)if root.right is not None:postorder_traversal(root.right, res)res.append(root.val)return res# 二叉树前序遍历（根，左，右）
def preorderTraversal(root: TreeNode) -> list:""""""res = []if root is not None:preorder_traversal(root, res)    # 递归函数return res# 二叉树中序遍历（左，根，右）    
def inorderTraversal(root: TreeNode) -> list:""""""res = []if root is not None:inorder_traversal(root, res)    # 递归函数return res# 二叉树后序遍历（左，右，根）
def postorderTraversal(root: TreeNode) -> list:""""""res = []if root is not None:postorder_traversal(root, res)    # 递归函数return resif __name__ == '__main__':""""""# root = TreeNode{val: 1, left: TreeNode{val: 2, left: None, right: None}, right: TreeNode{val: 3, left: None, right: None}}root = TreeNode(val=1)node2 = TreeNode(val=2)node3 = TreeNode(val=3)root.left = node2root.right = node3preorderTraversal(root)     # [1, 2, 3]inorderTraversal(root)      # [2, 1, 3]postorderTraversal(root)    # [2, 3, 1]

经典案例-4（二叉树遍历(BFS)）

# Definition for a binary tree node.
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef breadth_first_traversal(level_nodes: list, res: list):""""""new_level_nodes = []for node in level_nodes:res.append(node.val)# 收集新层级的树节点if node.left is not None:new_level_nodes.append(node.left)if node.right is not None:new_level_nodes.append(node.right)if new_level_nodes:breadth_first_traversal(new_level_nodes, res)# 广度优先遍历
def breadthFirstTraversal(root: TreeNode):""""""res = []level_nodes = []if root is not None:level_nodes.append(root)breadth_first_traversal(level_nodes, res)    # 递归函数return resif __name__ == '__main__':""""""root = TreeNode(val="A")node2 = TreeNode(val="B")node3 = TreeNode(val="D")node4 = TreeNode(val="C")node5 = TreeNode(val="E")node6 = TreeNode(val="F")node7 = TreeNode(val="H")node8 = TreeNode(val="I")node9 = TreeNode(val="J")node10 = TreeNode(val="K")node11 = TreeNode(val="L")node12 = TreeNode(val="M")root.left, root.right = node2, node3node2.left = node4node3.left, node3.right = node5, node6node4.left, node4.right = node7, node8node5.left, node5.right = node9, node10node6.left, node6.right = node11, node12res = breadthFirstTraversal(root)print(res)    # ['A', 'B', 'D', 'C', 'E', 'F', 'H', 'I', 'J', 'K', 'L', 'M']

三 动态规划算法

核心思想：
将复杂问题分解为更小的子问题，并利用这些子问题的解来构造原问题的解，通过存储子问题的解来避免重复计算，从而提高计算效率。

动态规划算法的基本原理包括以下几个关键点：

1. 分解问题：将复杂问题分解为多个相互重叠的子问题，这些子问题之间有重叠，即一个子问题的解可以被多个其他子问题共享。
2. 存储子问题解：在求解过程中，将已经计算过的子问题的解存储起来，以便在后续计算中直接引用，避免重复计算。
3. 递推关系：通过构建最优解与这些子问题之间的递推关系，逐步求解原问题。动态规划通常采用自底向上的方式进行，通过迭代计算子问题并存储子问题的解，逐步求解更大规模的问题，直到求解出原问题。

经典案例-1（爬楼梯问题）

题目内容：可爱的小明特别喜欢爬楼梯，他有的时候一次爬一个台阶，有的时候一次爬两个台阶，有的时候一次爬三个台阶。如果这个楼梯有n个台阶，小明一共有多少种爬法呢？n值从键盘输入。
输入格式：输入一个整数n, (1 <= n < 46)。
输出格式：输出当楼梯阶数是n时的上楼方式总数。

# 输入样例：1
# 输出样例：1
# 输入样例：4
# 输出样例：7
# 输入样例：24
# 输出样例：1389537def f(steps: int):""""""if steps == 1:return 1if steps == 2:return 2if steps == 3:return 4res = f(steps-1) + f(steps-2) + f(steps-3)return resf(24)    # 1389537

经典案例-2（硬币兑换）

题目内容：面值有1元、2元、5元的硬币，兑换amounts元，最少用多少块硬币？

"""硬币兑换"""coins = [1, 2, 5]def f(n):""""""res = 0res_bak = []if n < 0:return -1if n == 0:return 0if n == 1 or n == 2 or n == 5:return 1for coin in coins:if f(n-coin) != -1:res_bak.append(f(n-coin))if res_bak:res = min(res_bak) + 1return resf(11)    # 3

经典案例-3（最长公共子序列）

题目内容：给定两个字符串text1和text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回0。

"""最长公共子序列"""def f(i, j):""""""if i == 0 or j == 0:return 0res = max(f(i-1, j), f(i, j-1))if text1[i-1] == text2[j-1]:res += 1return restext1 = "abcde"
text2 = "ace"
f(len(text1), len(text2))    # 3

四 回溯算法

核心思想：
是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

经典案例-1（0-1背包问题）

题目：有n种物品，每种物品只有1个。第i种物品价值为vi，重量为wi，i=1,2,…, n。问如何选择放入背包的物品，使得总重量不超过B, 而价值达到最大？
V = [12, 11, 9, 8]
W = [8, 6, 4, 3]
B = 13

"""0-1背包问题"""import copydef dfs(prefix: list):""""""w_sum = 0for p in prefix:w_sum += W[p]if w_sum > B:output.append(prefix[:-1])return Nonefor i in range(4):if i in prefix:continuenew_prefix = copy.deepcopy(prefix)new_prefix.append(i)dfs(new_prefix)if __name__ == '__main__':""""""V = [12, 11, 9, 8]W = [8, 6, 4, 3]B = 13output = []for i in range(4):dfs([i])v_max = 0for o in output:v = 0for i in o:v += V[i]if v > v_max:v_max = vprint(v_max)

经典案例-2（全排列）

题目：给定一个不含重复数字的整数数组nums，返回其所有可能的全排列。

"""全排列"""import copydef dfs(level, num, prefix, res):""""""if level > 3:return Noneif num in prefix:return Noneprefix = copy.deepcopy(prefix)prefix += [num]if level == 3:res.append(prefix)for n in nums:dfs(level+1, n, prefix, res)def allSort(nums):""""""res = []for n in nums:dfs(level=1, num=n, prefix=[], res=res)return resnums = [1, 2, 3]
allSort(nums)    # [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

经典案例-3（四皇后）

题目：按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

"""四皇后"""import copydef get_oblique_value(cdn: tuple):""""""coordinates = []for i in range(1, 4):if cdn[0] - i >= 0 and cdn[1] - i >= 0:coordinates.append((cdn[0] - i, cdn[1] - i))if cdn[0] - i >= 0 and cdn[1] + i < 4:coordinates.append((cdn[0] - i, cdn[1] + i))if cdn[0] + i < 4 and cdn[1] - i >= 0:coordinates.append((cdn[0] + i, cdn[1] - i))if cdn[0] + i < 4 and cdn[1] + i < 4:coordinates.append((cdn[0] + i, cdn[1] + i))return coordinatesdef dfs(index: tuple, g: list, q_num: int):""""""if index > 15:if q_num == 4:output.append(g)return Nonerow = seq[index][0]col = seq[index][1]row_l = [s for s in g[row]]col_l = [g[n][col] for n in range(4)]coordinates = get_oblique_value(seq[index])oblique_l = [g[cdn[0]][cdn[1]] for cdn in coordinates]new_g = copy.deepcopy(g)dfs(index+1, new_g, q_num)if "Q" in row_l or "Q" in col_l or "Q" in oblique_l:return Nonenew_g = copy.deepcopy(g)s_list = list(new_g[row])s_list[col] = "Q"new_g[row] = "".join(s_list)q_num += 1dfs(index+1, new_g, q_num)if __name__ == '__main__':""""""g = ["....", "....", "....", "...."]seq = []for i in range(4):for j in range(4):seq.append((i, j))output = []dfs(0, g, 0)print(output)    # [['..Q.', 'Q...', '...Q', '.Q..'], ['.Q..', '...Q', 'Q...', '..Q.']]

经典案例-4（数独）

题目：编写一个程序，通过填充空格来解决数独问题。
数独的解法需遵循如下规则：
1.数字1-9在每一行只能出现一次。
2.数字1-9在每一列只能出现一次。
3.数字1-9在每一个以粗实线分割的3x3宫内只能出现一次。
数独部分空格已填入数字，空白格用 “.” 表示。

"""数独"""import copydef get_nine(blank: tuple, board: list):""""""blank_nine = []if blank[0] in (0, 1, 2):if blank[1] in (0, 1, 2):for r in range(0, 3):for c in range(0, 3):if board[r][c] != ".":blank_nine.append(board[r][c])elif blank[1] in (3, 4, 5):for r in range(0, 3):for c in range(3, 6):if board[r][c] != ".":blank_nine.append(board[r][c])else:for r in range(0, 3):for c in range(6, 9):if board[r][c] != ".":blank_nine.append(board[r][c])elif blank[0] in (3, 4, 5):if blank[1] in (0, 1, 2):for r in range(3, 6):for c in range(0, 3):if board[r][c] != ".":blank_nine.append(board[r][c])elif blank[1] in (3, 4, 5):for r in range(3, 6):for c in range(3, 6):if board[r][c] != ".":blank_nine.append(board[r][c])else:for r in range(3, 6):for c in range(6, 9):if board[r][c] != ".":blank_nine.append(board[r][c])else:if blank[1] in (0, 1, 2):for r in range(6, 9):for c in range(0, 3):if board[r][c] != ".":blank_nine.append(board[r][c])elif blank[1] in (3, 4, 5):for r in range(6, 9):for c in range(3, 6):if board[r][c] != ".":blank_nine.append(board[r][c])else:for r in range(6, 9):for c in range(6, 9):if board[r][c] != ".":blank_nine.append(board[r][c])return blank_ninedef dfs(blank_index: int, board: list):""""""if blank_index >= blanks_len:output.append(board)return None# print(blanks[blank_index], blank_index)blank_row = board[blanks[blank_index][0]]blank_col = [board[k][blanks[blank_index][1]] for k in range(9)]blank_nine = get_nine(blanks[blank_index], board)for i in range(1, 10):if str(i) in blank_row or str(i) in blank_col or str(i) in blank_nine:continuen_board = copy.deepcopy(board)n_board[blanks[blank_index][0]][blanks[blank_index][1]] = str(i)dfs(blank_index+1, n_board)def sudoku(board):""""""global blanksblanks = []for i in range(9):for j in range(9):if board[i][j] == ".":blanks.append((i, j))global blanks_lenblanks_len = len(blanks)global outputoutput = []dfs(0, board)return output[0]if __name__ == '__main__':""""""board = [["5", "3", ".", ".", "7", ".", ".", ".", "."],["6", ".", ".", "1", "9", "5", ".", ".", "."],[".", "9", "8", ".", ".", ".", ".", "6", "."],["8", ".", ".", ".", "6", ".", ".", ".", "3"],["4", ".", ".", "8", ".", "3", ".", ".", "1"],["7", ".", ".", ".", "2", ".", ".", ".", "6"],[".", "6", ".", ".", ".", ".", "2", "8", "."],[".", ".", ".", "4", "1", "9", ".", ".", "5"],[".", ".", ".", ".", "8", ".", ".", "7", "9"],]sudoku(board)# [#     ['5', '3', '4', '6', '7', '8', '9', '1', '2'],#     ['6', '7', '2', '1', '9', '5', '3', '4', '8'],#     ['1', '9', '8', '3', '4', '2', '5', '6', '7'],#     ['8', '5', '9', '7', '6', '1', '4', '2', '3'],#     ['4', '2', '6', '8', '5', '3', '7', '9', '1'],#     ['7', '1', '3', '9', '2', '4', '8', '5', '6'],#     ['9', '6', '1', '5', '3', '7', '2', '8', '4'],#     ['2', '8', '7', '4', '1', '9', '6', '3', '5'],#     ['3', '4', '5', '2', '8', '6', '1', '7', '9']# ]