企业官网建设流程全解析

AmazonCrackedResource第2周刷题解析：Trapping Rain Water、Word Ladder，攻克亚马逊最经典难题

【免费下载链接】AmazonCrackedResourceA List of frequently asked questions in Amazon's Online Assessment and Interviews项目地址: https://gitcode.com/gh_mirrors/am/AmazonCrackedResource

AmazonCrackedResource 是一份精心整理的亚马逊在线测评（Online Assessment）与面试高频题清单，帮你系统完成 5 周 50 道经典 LeetCode 刷题计划。本文聚焦第 2 周刷题解析，重点拆解亚马逊最经典的两大难题：Trapping Rain Water（接雨水）和 Word Ladder（单词接龙），带你用最简单的思路攻克它们。

什么是 AmazonCrackedResource 刷题清单

这个仓库的核心就是一份结构化的刷题计划，全部资料集中在 [CrackAmazonResource.md] 中：

• 50 道高频题：覆盖亚马逊 OA 与面试反复出现的经典题
• 5 周计划：每周 10 题，节奏明确，避免"不知从哪刷起"
• 状态追踪表：每题可标记Done ✅ | In Progress 🕓 | Skipped ❌，配合难度评级 Easy ~ Hard，进度一目了然

使用方式很简单：按周推进，做完一题就在表格里更新状态，坚持 5 周即可完成整套计划。

第 2 周刷题清单：这 10 道亚马逊高频题怎么安排

第 2 周的 10 道题在 [CrackAmazonResource.md] 的 "Problems for Week 2" 表格中列出：

其中 Trapping Rain Water 和 Word Ladder 是亚马逊面试的"常客"，也是本阶段公认的 Hard 分水岭，下面逐一拆解。

Trapping Rain Water 接雨水：双指针 O(n) 快速解法

题目直觉：水为什么能留下来

给定一排柱子，每根柱子高度不同。下雨后，两栋"楼"之间能接住多少水？关键规律只有一条：某个位置的水深，等于它左侧最高柱与右侧最高柱的较小值，减去它自身高度。谁矮，水就按谁算。

最快解法：左右双指针

• 左右指针从两端向中间收缩，left_max、right_max分别记录两侧最大值
• 每一步只移动"较矮一侧"的指针，因为它的水位已被确定
• 时间复杂度O(n)，空间复杂度O(1)——一次遍历、零额外数组

💡 面试提示：这道题的精髓在于"先说清思路再写码"。建议先手绘两个柱子夹住矮柱的示意图，解释"短板效应"，再推导双指针的正确性，比直接上代码更能拿高分。

Word Ladder 单词接龙：BFS 求最短转换路径

本质：把字典变成一张图

起点是 beginWord，终点是 endWord，每一步只能改一个字母，且新单词必须出现在 wordList 中。把每个单词看作节点、"相差一个字母"看作边，问题就变成了无权图上的最短路径问题——这正是 BFS 的主场。

BFS 搜索的四个关键步骤

1. 建图或按层枚举：可将字典中所有单词两两比较建边（O(N²·M)），或更聪明地用"通配模式"如h*t分组，把复杂度压到 O(N·M²)
2. 起点入队，记录步数从 1 开始（包含起点本身）
3. 逐层扩展：每层处理当前层所有单词，每次只替换一个字母位，若在字典中且未访问过，则入队
4. 提前终止：第一次弹出 endWord 时立即返回层数，这一定是最短路径

⚠️ 易错点：beginWord本身不在 wordList 里、找不到路径时返回 0、visited 集合要防止 A→B→A 死循环——这三点是面试中最常踩的坑。

用这份计划完成 5 周亚马逊刷题

• 节奏建议：每天 2 题，周末复盘错题，第 2 周这两道 Hard 题各预留半天
• 进度管理：坚持在 [CrackAmazonResource.md] 的表格中更新状态，5 周后你的仓库就是一份可展示的刷题履历
• 进阶资源：项目 [README.md] 中还整理了 DSA 资源指南、简历筛选技巧、系统设计等配套学习入口，License 采用 MIT（见 [LICENSE]），可自由使用与 Fork

记住项目里的这句名言："First, solve the problem. Then, write the code."想清楚再动手，正是攻克亚马逊经典难题的捷径。

【免费下载链接】AmazonCrackedResourceA List of frequently asked questions in Amazon's Online Assessment and Interviews项目地址: https://gitcode.com/gh_mirrors/am/AmazonCrackedResource