两道 LeetCode 题的复盘笔记：从「只会暴力」到「懂优化」

目录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任何数和自身异或结果为 0a ^ 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] jword1为空需要插入j次。dp[i][0] iword2为空需要删除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. 编辑距离则是典型的动态规划问题它的难点在于如何将问题分解为子问题并找到正确的状态转移方程。它锻炼的是我们拆解问题、寻找递推关系的能力。