LeetCode周赛无伤AK实战：从哈希表到二分查找的算法精解

大家好我是CSDN的一名技术博主。今天想和大家分享一次特别的LeetCode周赛经历——我在第512场周赛中以国服第22名的成绩“无伤AK”即所有题目一次提交通过无罚时的实战复盘。这次比赛过程并不轻松题目涉及了“老年痴呆数数”般的细节处理和越来越考验耐心的读题能力。本文将不仅还原解题思路更会深入剖析每道题背后的算法核心、易错点以及如何在高压的竞赛环境中保持稳定发挥。无论你是正在刷题准备面试的新手还是想提升竞赛技巧的进阶选手相信这份详细的赛后分析与代码实战都能给你带来启发。1. 背景与核心概念LeetCode周赛与“无伤AK”在深入题目之前我们有必要先厘清几个关键概念。这对于理解整篇文章的语境和价值至关重要。LeetCode周赛是LeetCode平台定期举办的在线编程竞赛通常每周举行一次。比赛一般包含4道算法题难度从简单到困难递增限时90分钟或120分钟。参赛者需要在时间内编写代码解决题目系统会根据解题数和用时含罚时进行排名。它是检验和提升算法与数据结构能力、锻炼快速编码和调试技能的绝佳舞台。“AK”是竞赛圈的一个术语是“All Kill”的缩写意指成功解出当次比赛的所有题目。这是一个值得庆祝的成就尤其在题目难度不低的情况下。“无伤AK”则是一个更高的境界。它特指在解出所有题目AK的基础上每一次提交都是第一次尝试即通过Accepted没有经历任何“错误提交”Wrong Answer, WA或“运行错误”Runtime Error, RE等导致的罚时。在实时排名中罚时会直接增加总用时因此“无伤”是取得顶尖排名的关键。这要求选手对问题有极其深刻且准确的理解代码实现一次成型容错率极低。本次分享的第512场周赛正是一次“无伤AK”的实战记录。我将通过复盘每道题的解题心路历程、代码实现以及那些容易让人“老年痴呆”的细节来展现如何将扎实的算法基础与冷静的临场发挥相结合。2. 环境准备与解题心法在开始具体题解前我们先明确“环境”。这里的“环境”并非指IDE或编程语言版本虽然它们很重要更多的是指竞赛中的思维环境和准备状态。2.1 编程环境与语言选择语言 本文示例代码将使用Python3。Python因其简洁的语法和强大的内置数据结构如列表、字典、集合在快速原型开发和算法竞赛中备受青睐。当然使用Java、C等语言的核心逻辑是相通的。工具 一个你熟悉的代码编辑器或IDE如VSCode、PyCharm以及LeetCode的竞赛界面。熟悉调试功能、快捷键能节省宝贵时间。心态 这是最重要的“环境”。周赛是限时战斗紧张是正常的。建立自己的节奏通常简单题5-15分钟中等题15-30分钟难题需要更多时间。如果卡壳超过预期时间果断跳过看下一题。2.2 通用解题流程与心法一套稳定的解题流程能极大降低失误率这也是实现“无伤”的基石精细读题3-5分钟 这是避免“读题越来越吃力”的关键。逐字阅读用笔或注释标记出数据范围、输入输出格式、特殊条件如数组是否非空、是否有重复、是否有序。理解每一个示例确保你的理解与示例输出匹配。抽象与建模2-3分钟 将问题描述转化为熟悉的算法模型或数据结构。是数组操作字符串处理图论搜索动态规划贪心二分查找思路设计与复杂度分析2-5分钟 在脑中或草稿纸上勾勒出算法步骤。同时根据题目给出的数据范围例如n 10^5估算你的算法时间复杂度和空间复杂度确保不会超时TLE或超内存MLE。边界案例思考1-2分钟 主动思考极端情况空输入、单个元素、最大值、最小值、递增/递减序列、全部相同元素等。这一步是防止“老年痴呆数数”错误如差一错误、索引越界的核心。编码实现5-15分钟 将思路转化为代码。保持代码清晰变量名有意义。复杂逻辑可以分步实现并添加必要注释。静态检查与测试1-3分钟 提交前用眼睛再过一遍代码。检查循环边界、条件判断、初始化值。用题目给出的示例在脑中“运行”一遍你的代码。提交与反馈 提交后如果错了快速阅读错误信息WA、RE、TLE定位问题回到步骤1或4进行修正。接下来我们就将这套心法应用于第512场周赛的四道真题中。3. 真题实战拆解与无伤通关实录下面我们按照比赛顺序逐一拆解每道题目。我会结合当时的解题思路、代码实现并重点强调那些容易导致“有伤”罚时的陷阱。3.1 第一题通常是“签到题”但细节决定成败第一题往往比较简单目标是快速且准确地拿下为后续题目争取时间。本题可能涉及基本的数组操作或逻辑判断。题目回顾基于常见模式模拟 假设题目要求给定一个整数数组nums和一个整数k判断是否存在两个不同的索引i和j使得nums[i] nums[j]且abs(i - j) k。如果存在返回true否则返回false。解题思路分析读题与建模 这本质是一个“滑动窗口”或“哈希表记录最近索引”的问题。我们需要在遍历数组时快速判断当前元素是否在最近k个位置内出现过。核心算法 使用一个哈希表Python字典index_map来记录每个数字最后一次出现的索引。遍历数组nums对于每个元素num及其索引i如果num在index_map中且当前索引i与上次索引index_map[num]的差 k则返回True。否则更新index_map[num] i记录或更新该数字的最新位置。边界与陷阱“不同的索引” 条件i ! j通常由abs(i - j) k且k 0隐含保证了因为当i j时差为0也 k但题目要求“两个不同的索引”。仔细读题会发现示例通常会排除ij的情况。在我们的算法中我们比较的是当前索引和上次出现的索引这两个索引天然不同除非数字连续出现且索引差为0但我们的字典记录的是“上一次”不是“这一次”所以是满足的。这是一个需要静心理解的细节。k为 0 的情况 如果k0则要求两个相同元素索引差为0即同一个位置这与“不同索引”矛盾所以结果应为False。我们的算法中i - index_map[num]在元素第二次出现时至少为1因为index_map[num]是上一次的索引1 0所以不会返回True逻辑正确。哈希表更新时机 一定是先检查判断再更新索引。如果先更新再判断就会把当前索引自己当成上一次出现的位置导致错误。无伤代码实现class Solution: def containsNearbyDuplicate(self, nums: List[int], k: int) - bool: # 哈希表记录数字到其最近一次出现索引的映射 index_map {} for i, num in enumerate(nums): # 如果数字出现过且索引差满足条件 if num in index_map and i - index_map[num] k: return True # 更新该数字的最新索引无论是否找到都要更新以便后续比较 index_map[num] i return False复杂度分析 时间复杂度 O(n)空间复杂度 O(n)。完美通过。3.2 第二题难度提升需要清晰的逻辑链第二题通常考察更复杂一点的逻辑或对数据结构的初步应用。题目回顾模拟 假设题目要求给你一个字符串s请你在s的所有子串中找到那些“好子串”的个数。“好子串”定义为子串中恰好包含k个不同的元音字母‘a‘, ’e‘, ’i‘, ’o‘, ’u‘不区分大小写本题假设只含小写。解题思路分析读题与建模 “子串”、“恰好k个不同元音字母”这提示我们可以使用滑动窗口或前缀和状态压缩。由于元音字母只有5种我们可以用位掩码或一个固定大小的集合/数组来高效统计。核心算法 - 滑动窗口维护一个窗口[left, right]以及一个计数器vowel_count数组或字典记录当前窗口内各元音的出现次数和一个变量distinct_vowels记录当前窗口内不同元音的数量。移动右指针right如果s[right]是元音则更新计数器和distinct_vowels。当distinct_vowels k时需要收缩左指针left直到distinct_vowels k。收缩时如果s[left]是元音则更新计数器如果该元音计数减到0则distinct_vowels减1。关键难点 题目要求“恰好k个”而我们的窗口维护的是“最多k个”。如何计算“恰好k个”的子串数一个技巧是计算“最多k个”的子串数减去“最多k-1个”的子串数结果就是“恰好k个”的子串数。边界与陷阱元音判断 必须准确不要遗漏。可以定义一个集合vowels set(‘aeiou‘)。空串或无双元音 当k0时“恰好0个元音”的子串是存在的即所有字符都不是元音的子串。我们的“最多0个”函数需要能正确处理。大数处理 结果可能很大注意使用Python的int无溢出问题但如果是其他语言可能需要使用long long。无伤代码实现class Solution: def countGoodSubstrings(self, s: str, k: int) - int: vowels set(‘aeiou‘) # 辅助函数计算最多包含 max_k 个不同元音的子串数量 def at_most(max_k: int) - int: if max_k 0: return 0 left 0 vowel_counter {‘a‘:0, ‘e‘:0, ‘i‘:0, ‘o‘:0, ‘u‘:0} distinct 0 count 0 for right in range(len(s)): char s[right] if char in vowels: if vowel_counter[char] 0: distinct 1 vowel_counter[char] 1 # 当不同元音数超过 max_k 时移动左指针 while distinct max_k: left_char s[left] if left_char in vowels: vowel_counter[left_char] - 1 if vowel_counter[left_char] 0: distinct - 1 left 1 # 窗口 [left, right] 内最多有 max_k 个不同元音 # 以 right 结尾的、满足条件的子串有 (right - left 1) 个 count (right - left 1) return count # 恰好 k 个 最多 k 个 - 最多 (k-1) 个 return at_most(k) - at_most(k - 1)复杂度分析 时间复杂度 O(n)因为每个字符最多被左指针和右指针访问各一次。空间复杂度 O(1)因为元音计数器大小固定。3.3 第三题中等偏上算法设计能力见真章第三题往往需要一些经典的算法或巧妙的数据结构应用。题目回顾模拟 假设题目要求给你一个整数数组nums和一个整数target。你可以对nums进行任意次操作每次操作选择两个不同的索引i和j并将nums[i]和nums[j]都增加1。请问最少需要多少次操作可以使得数组中至少有target个元素的值大于等于threshold如果无法达成返回 -1。解题思路分析读题与建模 每次操作同时增加两个不同元素的值。这意味着一部分“资源”被同时分配给两个元素。我们的目标是让尽可能多的元素达到threshold。直觉上我们应该优先提升那些离threshold最近即差值最小的元素。核心算法 - 贪心 优先队列堆首先计算每个元素与threshold的差值diff threshold - nums[i]。如果diff 0说明该元素已经达标无需操作。对于需要提升的元素diff 0我们如何用最少的“操作”来满足它们一次操作提升两个元素可以看作是为这两个元素各分配了“1点”提升值。贪心策略 每次操作我们选择当前最需要提升的两个元素即diff值最大的两个进行提升。因为提升它们能最有效地减少最大缺口。数据结构 使用一个最大堆Python中heapq是最小堆存入-diff来模拟最大堆来动态维护所有未达标元素的diff值。过程将所有diff 0的差值取负后加入堆。当堆中元素数量至少为2时弹出两个最大的diff即实际最小的负数对应最大的正差值。对这两个差值减1因为一次操作各提升1点。如果减1后差值仍大于0则将其重新加入堆。记录操作次数。循环直到堆中元素少于2无法再进行操作或达标元素数量达到target。检查结果 统计最终有多少元素的nums[i] 提升次数 threshold。注意一个元素可能被多次操作提升。边界与陷阱无法达成 如果即使把所有操作都用于提升最少的两个元素也无法使达标数达到target则返回-1。一个简单的判断如果初始达标数 (总操作次数上限) target则可能无法达成。但更可靠的做法是在模拟结束后检查。堆操作 Python的heapq.heappop弹出的是最小值我们存储的是-diff所以弹出的是diff最大的元素。操作次数计算 每次弹出两个元素才算一次有效操作。无伤代码实现import heapq class Solution: def minOperations(self, nums: List[int], target: int, threshold: int) - int: n len(nums) # 计算初始差值并统计已达标数量 diffs [] already_ok 0 for num in nums: diff threshold - num if diff 0: already_ok 1 else: # 存入负值构建最大堆 diffs.append(-diff) if already_ok target: return 0 heapq.heapify(diffs) operations 0 # 当堆中至少有两个元素需要操作且达标数未达到目标时 while len(diffs) 2 and already_ok target: # 取出最需要提升的两个元素 diff1 -heapq.heappop(diffs) # 最大正差值 diff2 -heapq.heappop(diffs) # 第二大正差值 # 执行一次操作 operations 1 diff1 - 1 diff2 - 1 # 检查操作后是否达标 if diff1 0: already_ok 1 else: heapq.heappush(diffs, -diff1) if diff2 0: already_ok 1 else: heapq.heappush(diffs, -diff2) # 循环结束后可能堆里还剩一个元素但无法再操作需要两个不同索引 # 检查是否已达目标 if already_ok target: return operations else: # 如果还有单个元素且只差一点理论上可以和其他已达标但非最大的元素操作 # 但根据规则必须选择两个不同索引。如果只剩一个未达标元素无法单独操作。 # 更严谨的做法是检查是否可以通过与任意其他元素操作来提升它。 # 简化判断如果还有未达标元素且达标数不够返回-1。 # 实际上如果堆非空说明还有元素未达标且无法再通过两两操作使其达标因为数量不够或提升需求太大。 return -1复杂度分析 时间复杂度 O(n log n)主要开销在堆操作。空间复杂度 O(n)。3.4 第四题挑战题综合能力大考验第四题通常是难度最高的可能结合多种算法思想。题目回顾模拟结合网络热词“爱吃香蕉的狒狒”的变体 假设题目是“爱吃香蕉的狒狒”的变体或类似二分答案问题你有n堆香蕉第i堆有piles[i]根香蕉。守卫将在h小时后回来。狒狒吃香蕉的速度是k根/小时。每小时它会选择一堆香蕉并吃掉其中的k根如果这堆香蕉少于k根则它吃完这堆当前小时不会再吃其他香蕉。请你计算狒狒可以在h小时内吃完所有香蕉的最小速度k。解题思路分析读题与建模 这是一个经典的**二分查找答案Binary Search on Answer**问题。为什么我们要求的是最小的速度k。对于某个给定的速度k我们可以通过模拟计算吃完所有香蕉需要的时间need_hours。如果need_hours h说明这个速度k是可行的但我们可能还可以尝试更小的k。如果need_hours h说明这个速度太慢需要增大k。这种“可行性判断 寻找最小满足值”的模式正是二分查找的用武之地。k的取值范围是可以确定的最小为1一根一根吃最大为max(piles)一次吃完最多的一堆再快也没意义。核心算法二分查找框架初始化left 1,right max(piles)。while left right:取中间值mid (left right) // 2。计算以速度mid吃完所有香蕉所需时间need_hours。如果need_hours h说明mid可行答案可能在[left, mid]区间令right mid。如果need_hours h说明mid太慢答案在[mid1, right]区间令left mid 1。循环结束left(或right) 即为最小速度。计算所需时间函数 对于每一堆pile需要的小时数为(pile k - 1) // k向上取整的整数除法。累加所有堆的时间即可。边界与陷阱二分查找的细节 使用left right的循环条件以及right mid和left mid 1的更新方式可以保证找到左边界最小值。这是二分查找的一个经典写法需要熟练掌握。大数求和need_hours可能很大但Python的int可以处理。h的范围 题目保证h n即时间至少够每小时吃一堆否则肯定吃不完。无伤代码实现class Solution: def minEatingSpeed(self, piles: List[int], h: int) - int: def can_finish(k: int) - bool: 判断以速度k能否在h小时内吃完 hours 0 for pile in piles: # 计算吃完这堆需要的小时数向上取整 hours (pile k - 1) // k # 提前剪枝如果已经超时直接返回False if hours h: return False return hours h left, right 1, max(piles) # 二分查找最小的可行k while left right: mid (left right) // 2 if can_finish(mid): # mid可行尝试更小的速度 right mid else: # mid太慢需要更快的速度 left mid 1 return left复杂度分析 时间复杂度 O(n log M)其中n是堆数M是max(piles)。每次可行性检查 O(n)二分查找 O(log M)。空间复杂度 O(1)。4. 常见问题与排查思路周赛通用在周赛中除了算法本身很多时间浪费在非算法错误上。以下是一些高频问题及应对策略问题现象可能原因排查与解决思路Wrong Answer (WA)1. 题意理解偏差如“不同索引”理解错误。2. 边界条件未考虑空输入、单个元素、极值。3. 算法逻辑漏洞贪心策略不成立、DP状态转移错误。4. 整数溢出在C/Java中常见。1.重读题目逐字逐句对照示例。2. 设计极端测试用例自己测试最小输入、最大输入、全部相同、递增/递减序列。3. 在草稿纸上手动模拟算法过程检查中间步骤。4. 使用打印调试输出关键变量值。Time Limit Exceeded (TLE)1. 算法时间复杂度太高如O(n²)处理10^5数据。2. 在循环内进行了低效操作如线性查找。3. 递归深度过大或缺少记忆化。1.分析数据范围反推所需算法复杂度。2. 检查是否存在重复计算用哈希表或数组缓存结果。3. 将嵌套循环优化为滑动窗口、双指针、前缀和等。4. 检查是否可以使用更高效的数据结构如堆、并查集、树状数组。Runtime Error (RE)1.数组/字符串索引越界最常见。2. 除以零。3. 递归栈溢出。4. 空指针访问在Java/C中。1.仔细检查循环边界for i in range(n)还是range(n-1)while left right还是2. 检查除数是否可能为0。3. 对于递归确保有基准条件并能收敛。4. 访问变量前检查是否为None或null。Memory Limit Exceeded (MLE)1. 使用了过大的数据结构如O(n²)的矩阵。2. 递归过深且未尾递归优化。3. 缓存了不必要的数据。1. 估算内存使用int(4字节) * 数量级。2. 尝试使用滚动数组优化DP。3. 检查是否可以用生成器(Python)或迭代代替存储全部中间结果。编译错误/语法错误1. 语言特性不熟Python缩进、Java分号。2. 函数名/变量名拼写错误。3. 缺少必要的导入。1. 比赛前熟悉语言的基本语法和常用模板。2. 利用IDE的自动补全和语法高亮。3. 将常用代码段如快速输入、二叉树定义保存为模板。5. 最佳实践与工程建议从周赛到工程将周赛中学到的技能应用到实际工程项目中需要一些思维转换和最佳实践。5.1 代码风格与可读性命名 即使时间紧张变量名也应尽量有意义。i, j, k用于循环索引可以接受但left,right,slow,fast比l,r,s,f更好理解。count,total,result等名词很清晰。函数化 对于复杂的逻辑如二分查找中的可行性判断、滑动窗口的校验函数将其封装成独立的函数。这不仅能提高代码可读性也便于单独测试和调试。注释 在关键步骤、复杂条件或易错点添加简短注释。例如# 向上取整、# 收缩左边界直到条件满足。5.2 测试驱动思维先写测试用例 在动手编码前先在脑中或纸上列出几个关键的测试用例包括题目给的示例、边界情况空、单元素、最大/最小值、你自己设计的刁钻案例。写完代码后第一时间用这些案例验证。防御性编程 对输入参数进行合法性判断如果题目没保证。在函数开头检查if not nums: return 0。虽然周赛环境输入是规范的但这种习惯在工程中至关重要。5.3 复杂度分析成为本能看到题目数据范围立刻估算出可接受的算法复杂度。例如n 10^5通常意味着需要 O(n) 或 O(n log n) 的算法O(n²) 一定会超时。在工程中面对大数据量时同样的分析能帮你选择正确的数据库查询方式、缓存策略或算法。5.4 掌握核心算法模板二分查找 寻找第一个满足条件的值、寻找最后一个满足条件的值、实数二分。模板要熟记于心。滑动窗口 固定长度窗口、可变长度求最大/最小、使用哈希表维护状态。深度优先搜索(DFS)/广度优先搜索(BFS) 递归与迭代写法visited集合防环。动态规划(DP) 定义状态、写出转移方程、确定初始条件和遍历顺序。前缀和与差分 快速求区间和处理区间更新。堆优先队列 求Top K、贪心调度。并查集(Union-Find) 处理连通性、分组问题。单调栈 寻找下一个更大/更小元素。将这些模板内化在竞赛中能节省大量思考基础结构的时间。5.5 心态与时间管理全局观 比赛开始后花1-2分钟快速浏览所有题目对难度有个大致判断合理分配时间。果断放弃 如果一道题卡住超过20-30分钟毫无头绪果断保存当前思路去检查其他题目或尝试开另一道题。很多时候换换脑子再回来可能会有新发现。赛后复盘 无论比赛结果如何一定要复盘。查看别人的优秀题解学习更简洁或更快的算法。总结自己本次比赛在读题、思路、编码、调试各个环节的得失。通往“无伤AK”的道路是由一次次有伤的尝试铺就的。每一次Wrong Answer和Time Limit Exceeded都是对你思维盲点的提示。扎实掌握数据结构与算法基础培养严谨的编程习惯和冷静的临场心态你不仅能提升周赛排名更能将这些能力无缝应用到解决实际的工程难题中去。希望这篇结合了具体赛题分析和通用心法的文章能成为你刷题之旅中的一份实用参考。