目录
136. 只出现一次的数字（简单）
思路一：暴力哈希表（入门解法）
思路二：异或运算（最优解）
72. 编辑距离（中等）
核心思想：动态规划
状态转移方程
边界条件
代码实现
总结与反思
最近刷到了两道很有代表性的题目：72. 编辑距离（中等）和136. 只出现一次的数字（简单）。一道是经典的动态规划，一道是利用位运算的巧解。把它们放在一起复盘，能很直观地感受到算法思想的不同魅力。
136. 只出现一次的数字（简单）
这道题的描述很简单：给一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
思路一：暴力哈希表（入门解法）
最容易想到的方法就是用哈希表统计每个数字出现的次数，最后遍历哈希表，找到次数为 1 的那个。
python
运行
def singleNumber(nums): count = {} for num in nums: count[num] = count.get(num, 0) + 1 for k, v in count.items(): if v == 1: return k- 时间复杂度：O(n)
- 空间复杂度：O(n)
这个方法虽然能解决问题，但题目还有一个进阶要求：不使用额外空间。这时候，就该轮到位运算登场了。
思路二：异或运算（最优解）
这里用到了异或（XOR）的几个关键性质：
a ^ a = 0（任何数和自身异或结果为 0）a ^ 0 = a（任何数和 0 异或结果为自身）- 异或运算满足交换律和结合律
所以，把数组里所有数字都异或起来，成对出现的数字都会互相抵消为 0，最后剩下的就是那个只出现一次的数字。
python
运行
def singleNumber(nums): result = 0 for num in nums: result ^= num return result- 时间复杂度：O(n)
- 空间复杂度：O(1)
这种解法利用了位运算的特性，将空间复杂度降到了极致，是真正的 “优雅” 解法。
72. 编辑距离（中等）
这道题是动态规划的经典代表：给定两个字符串word1和word2，计算将word1转换成word2所使用的最少操作数。你可以对字符串进行三种操作：插入、删除、替换。
核心思想：动态规划
我们定义dp[i][j]表示将word1的前i个字符，转换为word2的前j个字符所需的最少操作数。
状态转移方程
当
word1[i-1] == word2[j-1]时：这两个字符相同，不需要任何操作，所以dp[i][j] = dp[i-1][j-1]。当
word1[i-1] != word2[j-1]时：我们有三种操作可选，取其中操作数最少的一种：- 替换：把
word1[i-1]替换成word2[j-1]，操作数为dp[i-1][j-1] + 1。 - 删除：删掉
word1[i-1]，问题变成dp[i-1][j] + 1。 - 插入：在
word1中插入word2[j-1]，相当于word2回退一步，问题变成dp[i][j-1] + 1。
所以状态转移方程为：
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1- 替换：把
边界条件
dp[0][j] = j：word1为空，需要插入j次。dp[i][0] = i：word2为空，需要删除i次。
代码实现
python
运行
def minDistance(word1: str, word2: str) -> int: m, n = len(word1), len(word2) dp = [[0] * (n + 1) for _ in range(m + 1)] # 初始化边界 for i in range(m + 1): dp[i][0] = i for j in range(n + 1): dp[0][j] = j # 填充DP表 for i in range(1, m + 1): for j in range(1, n + 1): if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = min( dp[i-1][j-1], # 替换 dp[i-1][j], # 删除 dp[i][j-1] # 插入 ) + 1 return dp[m][n]- 时间复杂度：O(mn)
- 空间复杂度：O(mn)，可以优化为 O(min(m,n))
总结与反思
- 136. 只出现一次的数字这道题，核心在于跳出常规思维，利用位运算的特性来解决问题。它告诉我们，有时候一个巧妙的数学性质，能带来空间复杂度的质的飞跃。
- 72. 编辑距离则是典型的动态规划问题，它的难点在于如何将问题分解为子问题，并找到正确的状态转移方程。它锻炼的是我们拆解问题、寻找递推关系的能力。
)