数据结构与算法(十) - 六大算法思想实战：从LeetCode看贪心、分治与动态规划

1. 贪心算法实战从局部最优到全局最优贪心算法就像我们平时做选择题时的直觉思维——每次只选当前看起来最好的选项。这种活在当下的策略虽然简单但在某些场景下却能产生惊人的效果。记得我第一次刷LeetCode的455. 分发饼干时发现只需要将孩子和饼干都排序然后从小到大匹配就能解决问题这种简洁的美感让我瞬间爱上了贪心算法。最优子结构是贪心算法的灵魂所在。就像搭积木如果每一块都放在当前最合适的位置最终整个结构就会稳固。LeetCode上的122. 买卖股票的最佳时机 II完美诠释了这一点只要今天股价比昨天高就交易这种局部最优操作累积起来就是全局最大利润。def maxProfit(prices): profit 0 for i in range(1, len(prices)): if prices[i] prices[i-1]: profit prices[i] - prices[i-1] return profit但贪心算法也有它的局限性。我在做134. 加油站时就踩过坑——起初以为只要选择油量最多的站点出发就行后来发现需要综合考虑gas和cost的累积关系。这时候就需要贪心选择性质的验证能否证明局部最优能导致全局最优如果不能那就需要换动态规划的思路。2. 分治算法精要化整为零的智慧分治算法就像管理大型项目的诀窍——把复杂任务拆分成小模块分别解决。我在处理23. 合并K个升序链表时最初尝试两两合并结果超时改用分治后效率直接提升到O(NlogK)。分治算法的三个关键步骤在实践中尤为重要分解像处理215. 数组中的第K个最大元素时我们通过快速选择的partition将数组一分为二解决递归处理子问题如归并排序中对子数组的排序合并将排序好的子数组合并就像拼图游戏的最后一步def mergeKLists(lists): if not lists: return None if len(lists) 1: return lists[0] mid len(lists)//2 left mergeKLists(lists[:mid]) right mergeKLists(lists[mid:]) return mergeTwoLists(left, right)分治算法的效率陷阱需要注意。我在做241. 为运算表达式设计优先级时发现直接分治会产生大量重复计算。这时候就需要加入备忘录优化或者考虑改用动态规划。这也引出了分治与DP的关键区别子问题是否独立。3. 动态规划进阶从记忆化到状态压缩动态规划(DP)是我认为最优雅的算法思想它教会我们记住过去优化未来。初学70. 爬楼梯时我惊讶于简单的斐波那契数列竟能解释如此多的问题。但随着问题复杂度的增加比如188. 买卖股票的最佳时机 IV就需要更精细的状态设计。DP三要素的实战应用状态定义在309. 最佳买卖股票时机含冷冻期中需要定义hold、sold、rest三种状态状态转移72. 编辑距离中每个操作对应不同的状态转移路径边界条件64. 最小路径和中第一行和第一列需要特殊处理def maxProfit(k, prices): if not prices: return 0 n len(prices) if k n//2: # 转换为无限次交易 return sum(max(0, prices[i]-prices[i-1]) for i in range(1,n)) dp [[[0]*2 for _ in range(k1)] for __ in range(n)] for i in range(n): for j in range(k,0,-1): if i 0: dp[i][j][1] -prices[i] else: dp[i][j][0] max(dp[i-1][j][0], dp[i-1][j][1]prices[i]) dp[i][j][1] max(dp[i-1][j][1], dp[i-1][j-1][0]-prices[i]) return dp[-1][k][0]对于空间优化我在做123. 买卖股票的最佳时机 III时发现通过滚动数组可以将空间从O(n)降到O(1)。这种优化在面试中常常是加分项但要注意不要过早优化而牺牲代码可读性。4. 三大算法对比解题思维模式剖析经过上百道LeetCode题目的锤炼我总结出一个算法选择决策树问题能否分解为独立子问题→ 分治局部最优能否保证全局最优→ 贪心是否存在重叠子问题→ 动态规划以322. 零钱兑换为例贪心解法优先用大面额在某些测试用例会失败如coins[1,3,4], amount6分治会重复计算相同amount的结果DP才是正解用dp[i]记录金额i的最小硬币数def coinChange(coins, amount): dp [float(inf)] * (amount 1) dp[0] 0 for coin in coins: for i in range(coin, amount1): dp[i] min(dp[i], dp[i-coin]1) return dp[amount] if dp[amount] ! float(inf) else -1在面试场景中我建议先明确说明算法选择理由。比如遇到53. 最大子数组和时可以这样分析贪心维护当前和小于0就重置O(n)时间O(1)空间分治递归求左右和跨中点的最大值O(nlogn)DPdp[i]表示以nums[i]结尾的最大和O(n)这种分析能力往往比直接写出代码更受面试官青睐。