企业官网建设流程全解析

1. 贪心算法与LeetCode高频题解

在算法面试中，贪心算法就像一位精明的商人，永远在当下做出最优选择。这种"局部最优导致全局最优"的思想，看似简单却暗藏玄机。LeetCode Hot 100中的贪心题目，正是各大厂面试官最青睐的考察点——它们能快速检验候选人解决问题的直觉和代码实现能力。

我刷过三遍Hot 100贪心题，发现这些题目存在明显的解题模式。比如分配问题常用双指针，区间问题往往需要排序预处理，而跳跃游戏这类题目则存在隐藏的贪心性质。掌握这些套路后，原本需要30分钟苦思的题目，现在5分钟就能写出AC代码。

2. 贪心算法核心思想解析

2.1 贪心选择性质

贪心算法的核心在于每个局部决策都不依赖后续选择。就像玩俄罗斯方块时，我们总是优先消除最下方的行——这个决定不需要知道下一个方块是什么形状。在代码实现上，这通常表现为：

def greedy_choice(inputs): inputs.sort() # 常见预处理 res = 0 for item in inputs: if can_select(item): # 局部最优判断 res += process(item) return res

2.2 最优子结构特征

当一个问题的最优解包含其子问题的最优解时，就具备贪心算法的适用条件。例如在"找零钱"问题中，用最少的硬币凑出金额n的解，必然包含凑出金额n-d（d为某个硬币面值）的最优解。

注意：不是所有问题都满足贪心条件。比如硬币面值为[1,3,4]时，凑6元的最优解是两枚3元硬币，但贪心会选择4+1+1。

3. Hot 100经典题型深度剖析

3.1 区间调度类问题

这类问题的共同点是需要处理多个区间，典型代表是LC 435（无重叠区间）和LC 452（用最少数量的箭引爆气球）。解题模板如下：

1. 按结束时间排序（证明见《算法导论》）
2. 选择最早结束的区间
3. 排除与之冲突的区间
4. 重复步骤2-3

def eraseOverlapIntervals(intervals): intervals.sort(key=lambda x: x[1]) end = float('-inf') count = 0 for s, e in intervals: if s >= end: end = e else: count += 1 return count

3.2 分配类问题

LC 455（分发饼干）和LC 135（分发糖果）代表这类问题。关键在于排序后使用双指针进行贪心匹配：

def findContentChildren(g, s): g.sort() s.sort() i = j = 0 while i < len(g) and j < len(s): if s[j] >= g[i]: i += 1 j += 1 return i

3.3 跳跃游戏系列

LC 55（能否跳到终点）和LC 45（最少跳跃次数）是贪心思想的绝佳体现。解题时需要维护当前能到达的最远位置：

def canJump(nums): max_reach = 0 for i in range(len(nums)): if i > max_reach: return False max_reach = max(max_reach, i + nums[i]) return True

4. 贪心算法解题四步法

4.1 问题转化

首先判断问题是否具有贪心性质。例如LC 134（加油站问题）可以转化为寻找累加和的最低点：

def canCompleteCircuit(gas, cost): total = curr = start = 0 for i in range(len(gas)): diff = gas[i] - cost[i] total += diff curr += diff if curr < 0: start = i + 1 curr = 0 return start if total >= 0 else -1

4.2 贪心策略设计

对于LC 376（摆动序列），我们只需要统计极值点的数量：

def wiggleMaxLength(nums): if len(nums) < 2: return len(nums) prediff = nums[1] - nums[0] count = 2 if prediff != 0 else 1 for i in range(2, len(nums)): diff = nums[i] - nums[i-1] if (diff > 0 and prediff <= 0) or (diff < 0 and prediff >= 0): count += 1 prediff = diff return count

4.3 正确性证明

以LC 621（任务调度器）为例，其最优解为(max_count - 1) * (n + 1) + same_max。可以通过构造法证明：

1. 出现次数最多的任务需要至少(max_count - 1)个完整周期
2. 每个周期长度至少为(n + 1)
3. 最后加上剩余的同频任务

4.4 边界条件处理

贪心算法特别需要注意边界情况。例如LC 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

看似简单，但需要确认：空数组、单元素数组、持续下跌等情况都能正确处理。

5. 高频易错点与调试技巧

5.1 典型错误案例

1. LC 406（根据身高重建队列）中忘记先按身高降序排序：

# 错误写法 people.sort(key=lambda x: x[1]) # 正确写法 people.sort(key=lambda x: (-x[0], x[1]))

2. LC 763（划分字母区间）中未及时更新区间终点：

# 易错点 for i in range(len(s)): end = max(end, last_pos[s[i]]) # 必须放在循环内

5.2 调试方法论

当贪心算法得不到正确解时：

1. 验证贪心选择性质：是否真的存在局部最优导致全局最优
2. 检查排序规则：有时需要二级排序（如先按x降序，再按y升序）
3. 打印中间状态：在关键决策点输出变量值

5.3 测试用例设计

针对贪心算法，必须测试：

1. 极端情况（空输入、单元素）
2. 完全有序和完全逆序
3. 存在多个相同极值的情况
4. 需要特殊处理的边界值

例如测试LC 135（分发糖果）时：

测试用例： [1,0,2] → 5 [1,2,2] → 4 [1,3,4,5,2] → 11

6. 贪心与其他算法的组合应用

6.1 贪心+优先队列

LC 253（会议室II）需要结合贪心和堆：

def minMeetingRooms(intervals): intervals.sort(key=lambda x: x[0]) heap = [] for s, e in intervals: if heap and heap[0] <= s: heapq.heappop(heap) heapq.heappush(heap, e) return len(heap)

6.2 贪心+动态规划

LC 1326（灌溉花园的最少龙头数）需要先预处理区间：

def minTaps(n, ranges): intervals = [] for i, r in enumerate(ranges): intervals.append([i-r, i+r]) intervals.sort() # 后续类似跳跃游戏解法

6.3 贪心+数学证明

LC 330（按要求补齐数组）需要数学推导：

def minPatches(nums, n): miss = 1 added = i = 0 while miss <= n: if i < len(nums) and nums[i] <= miss: miss += nums[i] i += 1 else: miss += miss added += 1 return added

7. 面试实战技巧

7.1 问题识别训练

快速判断贪心适用性的方法：

1. 问题是否要求"最大/最小数量"？
2. 是否可以通过排序简化问题？
3. 局部最优解是否能推导全局最优？

7.2 白板编码要点

1. 先明确说出贪心策略
2. 讨论排序规则的选择
3. 举例说明算法执行过程
4. 主动分析时间/空间复杂度

7.3 常见follow-up问题

1. 如何证明你的贪心策略是正确的？
2. 如果改变问题条件（如增加限制），算法如何调整？
3. 是否存在动态规划解法？效率对比如何？

8. 进阶学习路线

8.1 经典论文推荐

1. 《Greedy Algorithms》 - Borodin等
2. 《The Greedy Algorithm for the Symmetric TSP》 - Gamarnik等
3. 《A Greedy Heuristic for the Set-Covering Problem》 - Chvatal

8.2 OJ专项训练

建议刷题顺序：

1. 基础：LC 455, 860, 1005
2. 中等：LC 376, 402, 738
3. 困难：LC 316, 321, 330

8.3 实际工程应用

1. Huffman编码（数据压缩）
2. Dijkstra算法（最短路径）
3. Prim/Kruskal算法（最小生成树）

贪心算法就像算法世界里的快刀手，用简洁的代码解决复杂的问题。但记住——不是所有闪着金光的选择都能通向最优解，关键在于识别那些真正具备贪心性质的问题场景。我在面试中见过太多候选人强行套用贪心解法，最终陷入死胡同。真正的高手，懂得在适当的时机，用适当的方法。