LeetCode刷题实战：面积计算、位运算与图论技巧

1. LeetCode刷题方法论从面积计算到图论实战作为一名经历过数百场算法面试的老兵我深知LeetCode刷题中记不住解题思路的痛苦。本文将分享我在面积计算、位运算和图论三类题型中的实战笔记重点剖析那些容易遗忘却高频出现的核心算法思想。不同于简单的题解罗列我会结合工程实践中的优化思维带你理解每种解法背后的数学本质和编码技巧。1.1 二维问题的降维打击术1.1.1 投影法解矩形面积问题当遇到3047题这类矩形面积计算时菜鸟通常会陷入复杂的二维坐标判断。而老手会立即想到投影降维——将二维问题拆解为两个独立的一维问题。这种思路源自计算机图形学中的碰撞检测优化def largestSquareArea(bottomLeft, topRight): ans 0 for i in range(len(bottomLeft)): x1, y1 bottomLeft[i] r_x1, r_y1 topRight[i] for j in range(i 1, len(bottomLeft)): x2, y2 bottomLeft[j] r_x2, r_y2 topRight[j] # X轴投影重叠长度 dx min(r_x1, r_x2) - max(x1, x2) # Y轴投影重叠长度 dy min(r_y1, r_y2) - max(y1, y2) ans max(ans, min(dx, dy)) return ans ** 2关键洞察当dx或dy为负时说明对应轴无重叠。该方法将O(n²)的复杂度常数项降低为原来的1/2在ACM竞赛中这种优化可能决定生死。1.1.2 集合论在栅栏问题中的妙用面对栅栏移除问题直接双重循环的O(mn)解法在大数据量时必然超时。这时需要转换思路——将问题抽象为集合求交集def maximizeSquareArea(m, n, hFences, vFences): def get_intervals(fences, size): fences sorted([1] fences [size]) return {fences[j] - fences[i] for i in range(len(fences)) for j in range(i1, len(fences))} h_intervals get_intervals(hFences, m) v_intervals get_intervals(vFences, n) max_side max(h_intervals v_intervals, default0) return (max_side ** 2) % (10**9 7) if max_side else -1这里利用Python集合的哈希特性将时间复杂度从O(mn)降到O(mn)。注意边界处理原始栅栏位置1和m/n必须包含在内。1.2 单调栈的魔法从柱状图到矩阵1.2.1 二维矩阵的降维处理85题最大矩形问题本质上是84题柱状图的扩展。精妙之处在于如何将矩阵逐行转化为柱状图// Java版矩阵预处理 for (char[] row : matrix) { for (int i 0; i n; i) { height[i] (row[i] 1) ? height[i] 1 : 0; } // 调用柱状图解法... }这种预处理的时间复杂度是O(mn)是后续操作的基础成本。注意Java中字符比较用单引号与Python不同。1.2.2 单调栈的双重妙用维护单调递增栈时需要处理两种边界情况左边界栈空时取-1右边界遍历结束时强制处理剩余栈def largestRectangleArea(heights): st [-1] # 哨兵节点 heights.append(0) # 右边界哨兵 ans 0 for right in range(len(heights)): while len(st) 1 and heights[st[-1]] heights[right]: mid st.pop() left st[-1] ans max(ans, heights[mid] * (right - left - 1)) st.append(right) return ans踩坑记录我曾因忘记处理右边界导致WAWrong Answer。后来总结出双哨兵技巧——左右各加一个0高度柱保证所有有效高度都能出栈。2. 位运算的奇技淫巧2.1 位模式分析的通用解法构造最小位运算数组问题时发现一个关键规律a | (a1) b的逆运算等价于找到b的最右侧0位并将其后的第一个1置0。例如b 11 (1011) → a 9 (1001) b 7 (0111) → a 3 (0011)通用解法涉及位掩码生成def minBitwiseArray(nums): for i in range(len(nums)): if nums[i] 2: # 特殊case nums[i] 1 else: mask (~nums[i] -~nums[i]) 1 nums[i] ^ mask return nums这里运用了位运算三大技巧~x -~x获取最右侧0位 1定位到需要翻转的bit^执行特定位翻转3. 图论算法的工程实践3.1 Dijkstra算法的变形应用3650题边反转问题展示了经典算法的灵活应用。我们需要构建双权图原始边权重为w反向边权重为2w。这比传统Dijkstra多了一层状态处理def minCost(n, edges): graph [[] for _ in range(n)] for u, v, w in edges: graph[u].append((w, v)) # 原始边 graph[v].append((2*w, u)) # 反向边 heap [(0, 0)] dist [float(inf)] * n dist[0] 0 while heap: cost, u heapq.heappop(heap) if u n-1: return cost if cost dist[u]: continue for w, v in graph[u]: if cost w dist[v]: dist[v] cost w heapq.heappush(heap, (dist[v], v)) return -1性能优化使用Fibonacci堆可以将时间复杂度从O(E VlogV)优化到O(E VlogV)但在LeetCode数据规模下普通优先队列足够。3.2 Floyd算法的字符转换应用2976题字符串转换问题展示了Floyd算法在字符级处理的价值。建立26x26的转移矩阵后三重循环的简洁实现def minimumCost(source, target, original, changed, cost): INF float(inf) dp [[INF]*26 for _ in range(26)] for i in range(26): dp[i][i] 0 # 相同字符无需转换 for o, c, w in zip(original, changed, cost): u, v ord(o)-97, ord(c)-97 dp[u][v] min(dp[u][v], w) for k in range(26): for i in range(26): for j in range(26): dp[i][j] min(dp[i][j], dp[i][k] dp[k][j]) total 0 for s, t in zip(source, target): if s t: continue u, v ord(s)-97, ord(t)-97 if dp[u][v] INF: return -1 total dp[u][v] return total调试心得初始时忘记初始化对角线为0导致相同字符转换计算错误。Floyd算法中dp[i][i] 0的初始化至关重要。4. 算法学习的高效实践策略根据三年刷题经验我总结出三条黄金法则题型归类法建立自己的题型分类体系如本文的三大类每类总结3-5种解题模板弱点标记法对反复出错的题目打标签如单调栈边界定期专项突破五遍刷题法第一遍独立思考看题解第二遍闭卷实现第三遍多种解法对比第四遍教别人解题第五遍三个月后复习以本文的柱状图问题为例我的解题模板包含预处理步骤高度数组处理哨兵技巧左右边界处理单调栈维护规则while循环条件最后分享一个私藏技巧用functools.lru_cache记忆化搜索解决DP问题时记得对参数做哈希处理。例如将列表转为元组否则会因为可变参数导致缓存失效。这个坑我花了整整一天才排查出来。