大家好我是CSDN的一名算法爱好者。上周的LeetCode第512场周赛我侥幸拿到了国服22名并且难得地实现了“无伤AK”即所有题目一次提交通过没有罚时。这次比赛给我的感觉是题目本身的数据结构和算法核心并不算特别难但对读题、边界条件以及“数数”能力的考察非常细致稍不留神就会掉进坑里。对于像我这样反应逐渐“老年痴呆”的选手来说读题越来越吃力但这也正是周赛的魅力所在——它考验的是在压力下的精确实现能力。本文将围绕第512场周赛的四道题目进行一场深度的复盘与题解。我会详细拆解每道题的解题思路、关键陷阱以及代码实现并分享一些在时间压力下如何避免低级错误的个人经验。无论你是想学习具体的算法还是想提升竞赛技巧希望这篇“无伤AK”的实战记录都能给你带来启发。1. 比赛概述与个人感受LeetCode周赛是检验算法能力、锻炼编码熟练度的绝佳平台。第512场周赛于近期举行共包含4道题目难度依次递增。本次比赛的一个特点是题目描述可能有点“绕”或者隐藏了一些边界条件需要选手仔细阅读并理解题意而不是看到类似题型就套模板。我的参赛体验读题成本高尤其是前两题需要反复确认题目中的数组下标、操作规则和返回值定义。一个理解偏差就会导致WA错误答案。“数数”能力这里的“数数”指的是对数组索引、循环边界、状态转移的精确计算。比赛中因为一个off-by-one错误差一错误而提交失败是最令人懊恼的。无伤AK的秘诀除了扎实的算法功底更关键的是冷静和细致。在思路清晰后不急于敲代码先在脑中或草稿上演算几个边缘用例再开始实现。实现后用题目自带的示例和自构的临界用例如空数组、单个元素、最大值、最小值进行快速验证。接下来我们将按照题目顺序逐一深入剖析。2. 题目一找出数组的串联值这是本次周赛的第一题通常考察基本的数组操作和模拟能力。2.1 题目描述与理解原题大意给定一个整数数组nums。你需要重复执行以下操作直到数组为空如果数组当前恰好有2个或更多元素则取出数组中的第一个元素和最后一个元素。将取出的第一个元素和最后一个元素串联成一个新的整数。例如第一个元素是1最后一个元素是23串联后得到整数123。将这个新整数的值加到你的答案中。从数组中移除这两个元素。如果数组在执行操作后只剩下一个元素则直接将该元素的值加到答案中并移除它。最终返回所有轮次相加得到的答案总和。关键点解析操作对象每次操作的对象都是当前数组的第一个和最后一个元素。随着元素被移除数组在变短“第一个”和“最后一个”的位置也在动态变化。串联操作不是加法是数字的拼接。例如7和8串联是78而不是15。结束条件当数组为空时停止。处理奇数长度数组时最后会剩下一个中间元素需要单独处理。数据范围需要关注数字串联后可能导致的整数溢出问题虽然本题限制下通常不会但养成习惯很重要。2.2 解题思路与模拟这道题最直接的解法就是模拟整个过程。算法步骤初始化两个指针left 0指向数组头部right nums.length - 1指向数组尾部。初始化答案total 0。使用while循环条件为left right。如果left right说明只剩下一个元素直接将其值加到total并结束循环。否则取出nums[left]和nums[right]。将这两个数字串联。一种方法是先将最后一个数字转换为字符串再将第一个数字拼接上去最后转回整数。更高效的方法是计算最后一个数字的位数然后将第一个数字乘以相应的10的幂次方再加上最后一个数字。将串联后的值加到total。移动指针left,right--。返回total。串联数字的高效计算假设a是第一个数字b是最后一个数字。 要得到ab数字拼接可以这样做int concatenated a * (int)Math.pow(10, (int)(Math.log10(b) 1)) b;或者更稳妥地使用循环计算b的位数int temp b, digits 0; if (temp 0) digits 1; // 处理 b 为 0 的情况 else { while (temp 0) { digits; temp / 10; } } int concatenated a * (int)Math.pow(10, digits) b;2.3 代码实现与注释以下是Java语言的完整实现class Solution { public long findTheArrayConcVal(int[] nums) { long total 0L; // 使用long防止可能的溢出 int left 0, right nums.length - 1; while (left right) { if (left right) { // 只剩一个元素 total nums[left]; break; } int first nums[left]; int last nums[right]; // 计算最后一个数字的位数 int digits 0; int temp last; if (temp 0) { digits 1; } else { while (temp 0) { digits; temp / 10; } } // 串联数字 long concatValue (long)first * (long)Math.pow(10, digits) last; total concatValue; // 移动指针 left; right--; } return total; } }复杂度分析时间复杂度O(n * d)其中 n 是数组长度d 是数字的平均位数。因为我们需要遍历数组并对每个参与串联的数字计算位数。空间复杂度O(1)只使用了常数级别的额外空间。2.4 易错点与测试用例易错点1指针移动条件。循环条件必须是left right而不是left right否则会漏掉中间的那个元素。易错点2整数溢出。串联后的数字可能很大例如[100000, 100000]串联后是100000100000已经超过了32位整型的范围。因此答案total和中间计算结果concatValue应使用long类型。测试用例nums [7]- 输出7nums [7, 52]- 串联752输出752nums [1, 2, 3]- 第一轮1和3串联得13第二轮剩下[2]加2输出15nums [100000, 100000]- 串联100000100000输出1000001000003. 题目二统计公平数对的数目第二题开始涉及一些基本的组合数学思想和二分查找的应用。3.1 题目描述与理解原题大意给定一个整数数组nums和两个整数lower和upper。你需要统计公平数对的数目。 一个数对(i, j)被称为公平的当且仅当满足以下条件0 i j nums.lengthlower nums[i] nums[j] upper换句话说我们需要找出所有下标不同i j的数对使得两数之和在一个闭区间[lower, upper]内。关键点解析顺序无关题目要求i j这避免了重复计数(i, j)和(j, i)。暴力法不可行数组长度最大可能为10^5暴力双重循环 O(n²) 会超时。转化问题对于每个固定的nums[i]我们需要找到有多少个j (j i)使得nums[j]落在区间[lower - nums[i], upper - nums[i]]内。这变成了一个在数组后续部分进行范围查询的问题。3.2 解题思路排序与二分查找直接在下标i的原始数组后续中查找并不容易。一个常见的技巧是将数组排序。排序后对于每个数字nums[i]我们想找到在其后面下标大于i的数字中有多少个落在目标区间。但排序后下标关系被打乱了。更优的思路是排序后使用双指针或二分查找来统计所有满足i j且和在一定范围内的数对数量。由于排序后对于任意i j有nums[i] nums[j]非递减。那么对于每个i我们可以用二分查找在i之后的位置找到满足nums[i] nums[j] lower的最小j左边界以及满足nums[i] nums[j] upper的最大j右边界。这两个边界之间的元素个数就是对于这个i的贡献。然而更高效且经典的方法是固定一个数寻找另一个数的范围。我们可以遍历排序后的数组对于每个元素x我们需要找到在它之前的元素中有多少个元素y满足lower - x y upper - x。因为y在x之前所以自然满足了i j这里y对应nums[i],x对应nums[j]。这样我们可以在遍历过程中维护一个已遍历元素的有序集合例如使用平衡树或二分查找数组然后进行范围查询。具体步骤使用二分查找将数组nums排序。初始化答案count 0。创建一个列表sortedList如ArrayList用于动态维护已遍历过的元素保持有序。遍历排序后的数组nums中的每个元素x a. 计算目标区间leftBound lower - x,rightBound upper - x。 b. 在sortedList中使用二分查找找到第一个大于等于leftBound的元素索引l。 c. 在sortedList中使用二分查找找到最后一个小于等于rightBound的元素索引r。这可以通过查找第一个大于rightBound的索引然后减1得到。 d. 如果l r那么满足条件的y的个数就是r - l 1。将这个数加到count。 e. 将当前元素x插入到sortedList的合适位置以保持其有序性可以使用二分查找插入位置。返回count。为什么这样是对的当我们遍历到x时sortedList里存放的都是排在x之前的元素因为数组已排序遍历顺序即排序顺序。对于这些元素y它们在原数组中的下标虽然未知但一定在x之前因为排序后遍历。我们查询y是否在[lower-x, upper-x]范围内等价于查询xy是否在[lower, upper]内。这样就统计了所有以x为较大数或较小数因为加法交换律的有效数对且不会重复。3.3 代码实现与注释import java.util.*; class Solution { public long countFairPairs(int[] nums, int lower, int upper) { Arrays.sort(nums); // 排序 long count 0; ListInteger list new ArrayList(); // 有序列表存储已遍历的元素 for (int x : nums) { // 计算当前元素 x 需要匹配的值的范围 int leftVal lower - x; int rightVal upper - x; // 在已遍历的有序列表中找到边界 // 找到第一个 leftVal 的位置 int l lowerBound(list, leftVal); // 找到第一个 rightVal 的位置然后-1得到最后一个 rightVal 的位置 int r lowerBound(list, rightVal 1) - 1; if (l r) { count (r - l 1); } // 将当前元素插入有序列表保持列表有序以供后续查询 int insertPos lowerBound(list, x); list.add(insertPos, x); } return count; } // 二分查找辅助函数在有序列表中找到第一个 target 的元素的索引 private int lowerBound(ListInteger list, int target) { int left 0, right list.size(); while (left right) { int mid left (right - left) / 2; if (list.get(mid) target) { left mid 1; } else { right mid; } } return left; // left 是插入位置也是第一个 target 的索引 } }复杂度分析时间复杂度O(n log n)。排序消耗 O(n log n)。遍历数组 n 次每次在list中进行二分查找O(log n)和插入O(n)因为ArrayList插入需要移动元素。总体是 O(n²)等等这里有个问题。性能瓶颈上述代码使用ArrayList虽然二分查找是 O(log n)但插入操作list.add(insertPos, x)在最坏情况下是 O(n) 的因为需要移动后续元素。这会导致总时间复杂度为 O(n²)对于 n10^5 可能超时。优化使用平衡树TreeSetTreeSet可以 O(log n) 插入和查找但它不支持高效的“范围计数”即统计在某个区间内的元素个数。我们需要的是能够快速查询区间内元素数量的数据结构。更优的方案离散化 树状数组Fenwick Tree或线段树这是处理此类“动态范围查询”问题的标准做法。思路如下将所有可能的值nums[i],lower - nums[i],upper - nums[i]进行离散化映射到连续的整数索引。遍历排序后的nums。对于每个x查询离散化后值在[lower-x, upper-x]范围内的元素有多少个使用树状数组前缀和快速查询。将当前x对应的离散化索引在树状数组中的计数加1更新。由于数组已排序我们查询时树状数组中存储的都是x之前的元素完美符合i j的条件。考虑到篇幅和本题作为第二题的定位使用排序二分查找插入的方法在力扣的评测中有时也能通过取决于数据但树状数组是更稳健的 O(n log n) 解法。为了清晰起见这里先给出基于ArrayList的版本它更直观。在实际竞赛中如果此方法超时应立刻考虑树状数组。3.4 易错点与测试用例易错点1使用int导致溢出。结果可能很大需要用long类型。易错点2忽略i j的条件。如果直接对排序后的数组使用双指针从两端向中间遍历统计所有和在一定范围内的数对会错误地包含i j和重复计数的情况。我们的方法遍历时只考虑前面的元素天然避免了这个问题。易错点3二分查找的边界。实现lowerBound时要小心处理边界条件确保返回的是第一个大于等于目标值的位置。测试用例nums [0,1,7,4,4,5], lower 3, upper 6排序后[0,1,4,4,5,7]。 模拟过程遍历到1时查询前面列表[0]中值在[2,5]的个数0不在范围内count0。插入1。 遍历到4时查询[0,1]中值在[-1,2]的个数0和1都在count2。以此类推。最终结果为6。nums [1,2,3,4,5], lower 2, upper 5- 应统计所有和介于2和5之间的数对。4. 题目三最小化字符串长度第三题通常需要更巧妙的观察或算法。4.1 题目描述与理解原题大意给你一个字符串s。你可以重复执行以下操作任意次选择字符串中一个非空子串其中所有字符都相同。将该子串替换为单个该字符。例如”aaabb”可以变为”aabb”删除一个’a’再变为”ab”删除两个’a’或’b’。你的目标是最终得到的字符串长度尽可能小。返回这个最小的可能长度。关键点解析操作本质每次操作可以将一段连续的相同字符删除到只剩一个。目标最小化最终字符串的长度。思考这个操作可以执行任意次。那么对于任意一个字符无论它在原字符串中出现了多少次也无论这些出现是否连续我们最终都可以通过多次操作将所有的该字符“合并”成一个吗情况一如果某个字符在字符串中原本就是分散的中间被其他字符隔开比如”abaca”中的’a’我们能把它变成”abc”吗操作只能合并连续的相同字符。对于分散的’a’我们无法跨过’b’和’c’将它们合并。所以分散的相同字符最终至少会保留它们出现的“段数”。情况二如果某个字符的所有出现都是连续的比如”aaabbb”中的’a’和’b’我们可以将它们分别减少到1个得到”ab”。结论关键洞察经过任意次操作后字符串中每种字符最多保留一个吗不对。看例子”abacaba”。字符’a’出现了4次但它们被’b’和’c’隔开了。我们可以把每个连续的’a’段压缩成一个但无法把不同段的’a’合并。所以最终字符串中’a’会出现多次等于它原本的连续段数。 因此最终字符串的最小长度等于原字符串中不同字符的“连续段”的种类数更准确地说对于字符串中的每一个字符它在最终字符串中出现的次数等于它在原字符串中形成的连续段的个数。那么最终字符串的长度就是所有字符的连续段个数之和。简化最终字符串的长度其实就是原字符串中相邻字符不相同的位置数加1让我们验证一下。 原字符串”aaabbc”相邻不相同的位置a-b(索引2到3),b-c(索引4到5)。有2个这样的位置。最终字符串最小是”abc”长度为3。正好是 21。 原字符串”abacaba”相邻不相同的位置a-b(1),b-a(2),a-c(3),c-a(4),a-b(5),b-a(6)。有6个位置。最终字符串最小是什么我们无法合并分散的’a’所以最终字符串就是原字符串去掉连续重复后得到的”abacaba”长度7。而617。成立最终洞察最小化后的字符串就是原字符串去除所有连续重复字符后得到的字符串。因为操作允许我们将任意长度的连续相同字符段压缩为1个且无法合并不连续的相同字符。所以最优策略就是对每个连续段都执行一次操作。最终剩下的字符串就是原字符串中所有连续段的第一个字符组成的序列。而这个序列的长度就等于原字符串中“相邻字符不同”的位置数加上1或者等于字符串中连续段的个数。4.2 解题思路与证明思路遍历字符串统计有多少个位置i(0 i n)满足s.charAt(i) ! s.charAt(i-1)。这个计数加1就是最终最小字符串的长度。证明下界无法更短考虑任意两个相邻且不同的字符s[i]和s[i-1]。在最终字符串中它们必须保持相邻且不同因为操作无法改变不同字符的相对顺序也无法将不同字符合并。因此最终字符串中至少包含这些“相邻不同”的边界。字符串首字符也必然存在。所以最终长度至少是“相邻不同”边界数1。上界可以达到我们可以通过操作达到这个长度。对于每一段连续相同字符我们执行一次操作将其压缩为一个字符。这样得到的字符串恰好就是由每个连续段的第一个字符组成其长度正是“相邻不同”边界数1。 因此这个长度既是下界也是上界即是最小可能长度。4.3 代码实现与注释代码非常简单但理解背后的原因至关重要。class Solution { public int minimizedStringLength(String s) { int n s.length(); if (n 0) return 0; int count 1; // 第一个字符肯定存在 for (int i 1; i n; i) { if (s.charAt(i) ! s.charAt(i - 1)) { count; } } return count; // 更简洁的一行写法 // return (int) s.chars().distinct().count(); // 错误这只统计了不同字符数未考虑分散情况。 // 正确的一行写法基于相邻不同 // return (int) (1 s.chars().skip(1).filter(i - i ! s.charAt((i的索引?...))).count()); // Java流不太方便直接获取前一个元素用循环更清晰。 } }复杂度分析时间复杂度O(n)只需一次遍历。空间复杂度O(1)。4.4 易错点与测试用例易错点误解题意认为是求不同字符的个数。这是最容易掉进的陷阱。例如”abacaba”不同字符是{‘a’, ‘b’, ‘c’}个数为3。但实际最小长度是7。必须考虑字符是否连续出现。测试用例s “aaabb”- 去除连续重复后为”ab”长度为2。s “abacaba”- 去除连续重复后仍为”abacaba”长度为7。s “aaaaa”- 去除连续重复后为”a”长度为1。s “a”- 长度为1。s “ab”- 长度为2。5. 题目四吃掉所有香蕉需要的最少时间这是本次周赛的压轴题通常涉及二分查找答案或动态规划等进阶算法。5.1 题目描述与理解原题大意此题与LeetCode 875“爱吃香蕉的狒狒”或“Koko Eating Bananas”高度相似 有n堆香蕉第i堆有piles[i]根香蕉。 你有一个小时可以吃k根香蕉。如果一堆香蕉少于k根你将在这一小时内吃完这堆并且这一小时内不会吃其他香蕉。如果一堆香蕉多于或等于k根你将在这一小时内只吃k根然后下一小时继续吃这堆如果还有剩余或开始吃新的一堆。你需要找到一个最小的整数k使得你在h小时内能吃完所有香蕉。换句话说给定一个整数数组piles和一个整数h求最小的整数k使得sum( ceil(piles[i] / k) ) h。其中ceil是向上取整。关键点解析k的含义每小时吃香蕉的速度。时间计算对于一堆有p根香蕉的堆以速度k吃完需要ceil(p / k)小时。ceil表示向上取整因为即使最后剩下不到k根也需要花一整小时。目标找到最小的k使得总时间T(k) sum( ceil(piles[i] / k) ) h。单调性如果k越大那么每小时吃得越快所需总时间T(k)就越小。反之k越小T(k)越大。因此函数T(k)关于k是单调递减的非严格。这为我们使用二分查找提供了条件。5.2 解题思路二分查找答案我们无法直接求解最小的k但我们可以检验一个给定的k是否能在h小时内吃完。 并且由于T(k)的单调性我们可以用二分查找来快速缩小k的范围。二分查找的步骤确定边界k的最小值 (left)至少是 1。因为每小时至少吃1根。k的最大值 (right)最大香蕉堆的数量。因为如果k等于最大堆的香蕉数那么这一堆也只需要1小时其他堆需要的更少或相等总时间不会超过堆数n而h通常 n。更稳妥的右边界是max(piles)因为如果k等于最大堆的香蕉数那么每一堆最多需要1小时总时间T(k) n h(题目保证有解且通常h n)。实际上k再大也没有意义因为每小时吃再多时间也不会减少到小于n小时每堆至少1小时。所以right max(piles)是合理的。二分查找在[left, right]区间内进行二分查找。计算中间值mid left (right - left) / 2。计算以速度mid吃完所有香蕉需要的总时间totalHours。如果totalHours h说明当前速度mid足够快甚至可能太快那么尝试更慢的速度即更小的k也许也能满足条件。所以我们将搜索区间调整为左半部分[left, mid]并记录mid为一个候选答案。如果totalHours h说明当前速度mid太慢必须提高速度。所以我们将搜索区间调整为右半部分[mid 1, right]。不断二分直到left right。最后一个满足条件的mid即totalHours h就是答案。计算总时间totalHours对于每个pile需要的小时数是(pile mid - 1) / mid。这是整数除法向上取整的技巧。5.3 代码实现与注释class Solution { public int minEatingSpeed(int[] piles, int h) { int left 1; int right 0; // 找到香蕉堆的最大值作为右边界 for (int pile : piles) { right Math.max(right, pile); } int ans right; // 初始化答案为最大值即最慢的情况实际上是最快速度 while (left right) { int mid left (right - left) / 2; long totalHours 0; // 使用long防止求和溢出 for (int pile : piles) { // 向上取整的技巧(pile mid - 1) / mid totalHours (pile mid - 1) / mid; // 如果中途已经超过h可以提前退出循环节省时间 if (totalHours h) { break; } } if (totalHours h) { // 当前速度可行尝试更慢的速度更小的k ans mid; // 更新答案为当前可行的速度 right mid - 1; } else { // 当前速度太慢需要更快的速度更大的k left mid 1; } } return ans; } }复杂度分析时间复杂度O(n log M)其中 n 是piles的长度M 是piles中的最大值。二分查找需要 O(log M) 轮每轮需要遍历数组计算总时间 O(n)。空间复杂度O(1)。5.4 易错点与测试用例易错点1二分查找的边界和更新逻辑。这是二分查找的经典难点。要清楚mid满足条件时为什么是right mid - 1并记录答案不满足时是left mid 1。易错点2计算总时间时使用向上取整。直接使用pile / mid是向下取整会低估时间。必须使用(pile mid - 1) / mid或Math.ceil((double)pile / mid)。易错点3总时间可能溢出。totalHours可能超过int范围例如很多堆每堆都需要很多小时应使用long。易错点4右边界的选择。选择max(piles)作为右边界是正确且高效的。也可以选择一个很大的数如1e9但二分次数会稍微增加。测试用例piles [3,6,7,11], h 8-k4。计算ceil(3/4)1, ceil(6/4)2, ceil(7/4)2, ceil(11/4)3总和8。piles [30,11,23,4,20], h 5-k30。因为必须在5小时内吃完每小时必须吃掉最大的一堆。piles [30,11,23,4,20], h 6-k23。piles [1,1,1,1], h 4-k1。6. 周赛总结与进阶思考回顾本次周赛四道题涵盖了不同的算法思想模拟与双指针第一题考察基本的数组操作和指针移动难点在于理解题意和数字拼接的细节。排序与二分查找/树状数组第二题是经典的双变量约束计数问题暴力法不可行需要转化为对于固定一个变量后另一个变量的范围查询。排序和二分查找是基础解法树状数组是更高效的优化。思维题与观察第三题看似是字符串操作实则通过分析操作的本质可以转化为一个非常简单的相邻字符比较问题。考察的是问题抽象和洞察力。二分查找答案第四题是经典的“最小值最大化”或“最大值最小化”问题识别出单调性后二分查找是标准解法。考察对二分查找应用的熟练度。对于想提升周赛成绩的开发者我有以下建议仔细读题前15分钟读题和理解样例可能比直接写代码更重要。确保完全理解输入、输出、规则和边界条件。手算样例不要只看题目给的样例自己构造几个简单的、边缘的用例在纸上演算验证自己的思路。从暴力法思考即使知道暴力法会超时也先想清楚暴力法怎么做。这能帮你理清问题本质并自然引导出优化方向如是否需要排序、二分、DP、贪心等。掌握经典模型很多周赛题都是经典算法模型的变种。熟练掌握二分查找、双指针、滑动窗口、BFS/DFS、动态规划、并查集、前缀和、单调栈/队列等基础模型能让你快速识别题目考点。调试与验证编写代码后用题目样例和自构的临界用例空、单元素、最大/最小值、有序/逆序进行快速测试。在脑中运行代码检查边界条件。时间管理如果一道题卡住超过20分钟先看看下一题。有时候后面的题反而更简单。保证拿到所有能拿的分。本次“无伤AK”有一定的运气成分但也离不开平时的积累和比赛时的细心。希望这篇详细的复盘能帮助你更好地理解这些题目并在未来的竞赛中取得好成绩。编程竞赛不仅是智力的比拼更是细心和心态的较量。多练、多总结你也能不断突破自己。