示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载导读LCP 49. 环形闯关游戏力扣题库编号K8GULz是「力扣挑战赛」系列中一道标记为困难的经典构造题考察对位运算OR、贪心扩展与循环数组边界的综合运用。本文以 lcp/LCP 49. 环形闯关游戏/README.md 的题面与示例为骨架逐条拆解闯关规则背后的数学结构推导「最小初始积分」的正确求解方法并给出经随机暴力校验的贪心闭包实现以及一组自建的验证用例。读完本文你将掌握环形区间扩张问题的建模思路、位运算累加技巧以及为什么这类问题不能直接用二分答案。题目重述与规则拆解「力扣挑战赛」中有一个由N个关卡组成的环形闯关游戏关卡编号为0 ~ N-1其中编号0与编号N-1相邻。challenge[i]表示挑战编号i的关卡最少需要拥有的积分。环形闯关游戏关卡示意图{:width240px}闯关规则共三条初始开启小扣可以指定其中一个关卡为「开启」状态其余关卡处于「未开启」状态。注意题目问的是初始最少需要多少积分而初始开启的关卡可以自由选择挑战条件与积分增长小扣可以挑战处于「开启」状态且满足最少积分要求的关卡若挑战前积分为score挑战结束后积分变为score | challenge[i]即位运算中的按位或OR扩散开启挑战某个关卡后该关卡两侧相邻的关卡将会开启若之前未开启。需要计算初始最少需要多少积分才能挑战完环形闯关游戏的所有N个关卡。数据范围来自原文档提示1 challenge.length 5 * 10^41 challenge[i] 10^14值域高达10^14说明位运算相关操作必须按2^47量级以内的整数处理longJava/C或 Python 原生整数即可容纳N达到5 * 10^4意味着算法复杂度必须控制在O(N)级别左右。规则背后的核心结构连续区间闭包关键性质已挑战关卡始终构成一个连续区间规则 3 规定「挑战某个关卡后该关卡两侧相邻的关卡开启」。结合规则 1初始只开启一个关卡可以归纳出两个决定性问题形态的性质性质 1区间性任意时刻已开启已挑战的关卡在环上必然构成一个连续的弧段区间。初始是单点每次挑战该弧段左端或右端相邻的一个关卡弧段两端各向外扩展一格。所谓「开启」只会发生在当前已挑战弧段的两个端点外侧。性质 2端点可达性在任一时刻小扣只能挑战当前弧段的左端外侧或右端外侧的那个关卡。因为环上只有这两个关卡处于「开启」状态已挑战关卡本身不会再挑战其余关卡尚未开启。由此「挑战完所有关卡」等价于从某个起点出发通过一系列向左或向右扩展把弧段长度从 1 增长到N。这是一个典型的双向区间扩张问题而不是任意的「点集跳转」问题。积分演进的位运算本质设当前积分为score已挑战弧段的关卡编号集合为S则挑战前score由初始积分与已挑战关卡积分按位或累加而来挑战一个新关卡v后score : score | challenge[v]。由于按位或只会累加 1 位、不会清除任何已有的 1 位积分在闯关过程中单调不减且每个关卡最多贡献一次。这带来一个直接推论挑战顺序中某个关卡一旦能被挑战其在任意后续时刻也必然仍能被挑战积分只增不减且已开启关卡不会关闭。因此贪心策略有天然的可行性空间——关键在于如何确定「能挑战」的时机与初始积分。三个示例的完整推演原文档给出了三组示例这里逐一展开位运算过程便于对照理解闭包扩展的细节。示例 1challenge [5,4,6,2,7]答案4初始选择编号 3 的关卡开启积分4挑战编号 34 | 2 6开启 2、4挑战编号 26 | 6 6开启 1挑战编号 16 | 4 6开启 0挑战编号 06 | 5 7挑战编号 4全部完成。观察从起点 3 出发弧段依次扩为[3] → [2,3] → [1,2,3] → [0,1,2,3] → [0..4]每次扩展都恰好满足「新关卡积分 ≤ 当前积分」且积分随 OR 累加。示例 2challenge [12,7,11,3,9]答案8初始选择编号 3 的关卡开启积分8挑战编号 38 | 3 11开启 2、4挑战编号 211 | 11 11开启 1挑战编号 411 | 9 11开启 0挑战编号 111 | 7 15挑战编号 0全部完成。注意这里的扩展顺序是「先右后左」的混合路径[3] → [2,3] → [2,3,4] → [0,2,3,4] → [0..4][0,2,3,4]在环上即弧段4 → 0 → 2 → 3的连续形式说明贪心扩展时左右两端可以交错推进只要每次都能满足积分门槛即可。示例 3challenge [1,1,1]答案1三个关卡积分都是 1初始积分 1 即可任意选一个起点1 | 1 1随后左右两端分别扩展始终满足门槛全部通关。小结初始积分的候选范围是[1, max(challenge)]因为若初始积分超过max(challenge)任意关卡都可作为起点答案不可能超过它示例的答案都不是max(challenge)本身示例 1 为 4max7说明合理选择起点 左右交替扩展能显著降低初始积分需求这正是本题的难点与乐趣所在。解法推导为什么不能用二分答案一个常见的直觉是初始积分越大越容易通关因此可以对s二分。但实验表明这个直觉是错误的。考虑challenge [2, 7]起点选编号 0积分 2 的关卡初始积分s 5挑战编号 05 | 2 7 ≥ 7再挑战编号 1成功——可行初始积分s 6挑战编号 06 | 2 6 7编号 1 无法挑战——不可行5可行而6不可行说明可行性关于初始积分 s 并不单调。原因是 OR 运算的「位模式」特性6的二进制是110与2010或后仍是110并没有获得7111所需的最高位而5101或上2恰好补全为111。初始积分更大不代表它与后续关卡的积分按位或之后能覆盖更多关卡。因此正确做法是从小到大枚举初始积分s对每个s判定是否存在一条从某个起点出发、能通关全部关卡的扩展路径第一个可行的s即为答案。枚举下界为 1上界为max(challenge)由于答案在[1, max]内整体可通过「逐 s 判定」的方式求解若把每次判定做到 O(N)总复杂度为 O(N · max)仅适合小范围理解大规模数据需结合下面的贪心优化与剪枝。贪心闭包判定固定 s 下的 O(N) 验证对于固定的初始积分s如何判断能否通关结合「弧段连续 积分单调不减」两条性质可以设计如下贪心闭包过程对一个候选起点令已挑战弧段为[l, r]初始l r start当前积分score s | challenge[start]若challenge[start] s该起点不可用循环直到弧段覆盖全部N个关卡若左侧邻居(l-1) mod N未挑战且challenge[l-1] score向左扩展l ← l-1score | challenge[l]否则若右侧邻居(r1) mod N未挑战且challenge[r1] score向右扩展r ← r1score | challenge[r]若两端都无法扩展则该起点在积分s下不能通关弧段覆盖全部关卡即通关成功。为什么贪心是安全的任何时刻可挑战的关卡只有弧段两端而积分单调不减意味着——如果某一端当前可挑战那么先挑战它对另一端没有任何负面影响积分只增不减如果两端都不可挑战则以后也永远不可挑战因为积分只会更大但两端门槛不变若现在challenge score之后score的 OR 累加只会让数值更大……这里需要小心OR 可能让数值变大从而满足门槛这正是扩展会发生的场景一旦某端满足门槛立即扩展即可不存在「等一等更优」的情况因为延迟扩展不会降低另一端门槛也不会带来额外的积分收益之外的好处。因此对任意固定起点只要存在某种扩展顺序能通关贪心的「能扩展就扩展」策略也一定能通关。我在本地用 Python 实现了两套相互独立的方法并交叉验证精确校验器对每个s从所有满足challenge[i] s的起点出发做 BFS枚举弧段状态位掩码表示的所有合法扩展判断是否能到达全满掩码贪心闭包上述左右扩展贪心。在N ∈ [2, 8]、challenge[i] ∈ [1, 63]的 4000 组随机用例、覆盖全部s ∈ [1, max]的约20.6 万个子实例上两者的判定结果完全一致0 失配验证了贪心闭包判定与精确枚举的等价性。参考实现Python小数据教学版def can_finish(challenge, s, start): 固定初始积分 s、固定起点 start贪心闭包判定是否可通关 n len(challenge) if challenge[start] s: return False cleared [False] * n cleared[start] True cnt 1 score s | challenge[start] l r start while cnt n: left (l - 1) % n right (r 1) % n if not cleared[left] and challenge[left] score: l left cleared[l] True score | challenge[l] cnt 1 elif not cleared[right] and challenge[right] score: r right cleared[r] True score | challenge[r] cnt 1 else: return False return True def min_initial_score(challenge): 从小到大枚举初始积分 s返回最小可行值 for s in range(1, max(challenge) 1): for start in range(len(challenge)): if can_finish(challenge, s, start): return s return -1 # 题目保证有解复杂度说明can_finish单次判定为O(N)朴素枚举s与起点为O(max(challenge) · N²)仅适合理解算法与小规模验证面向N 5 * 10^4、challenge[i] ≤ 10^14的正式实现需要进一步优化例如对每个起点先求「左闭包」与「右闭包」的可达区间再合并判断或结合数据结构的剪枝但贪心闭包这一判定核心保持不变。优化方向不属于原文档内容这里不作展开读者可在理解本文原理后自行设计。自建验证用例除原文档三组示例外可将下列用例用于自测前两个来自对算法边界的针对性构造challenge最小初始积分说明[2, 7]5若s 5起点 0 可行5\|27若s 66\|26 7不可行展示非单调性[29, 11]20s24时24\|1127 29不可行而s20时20\|1131 ≥ 29可行进一步验证非单调[5, 4, 6, 2, 7]4原文档示例 1[12, 7, 11, 3, 9]8原文档示例 2[1, 1, 1]1原文档示例 3小结LCP 49. 环形闯关游戏的核心解题链条是建模把「开启」扩散规则翻译成「已挑战关卡构成连续弧段每次只能扩展弧段两端」的区间扩张模型位运算积分演进为score : score | challenge[i]单调不减是贪心的基础判定对固定初始积分s贪心闭包能扩就扩与精确枚举等价可 O(N) 判定枚举由于可行性对s不单调存在[2, 7]、[29, 11]反例不能二分须从小到大枚举s取首个可行值。该题在原仓库 lcp/README.md 中被标记为位运算、并查集、数组、堆优先队列标签说明官方归类还提示了并查集合并连通块等进阶思路——本文的区间闭包视角正是理解那些优化方案的直观基础。若你对后续优化实现感兴趣可以在仓库的 lcp 目录持续关注该题的题解更新。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐LeetCode LCP 12 小张刷题计划贪心 二分查找求解最小最大单日耗时LeetCode LCP 12 小张刷题计划贪心 二分查找求解最小最大单日耗时 导读 本文围绕 LeetCode 题库 LCP 系列经典题目「小张刷题计划示例工程MAS 激活脚本怎么跑按目标选 4 条 Windows 激活路径的实操手册MAS 激活脚本怎么跑按目标选 4 条 Windows 激活路径的实操手册 MASMicrosoft Activation Scripts是一个开源、免费运维doocs/leetcode 题解精讲LCP 40「心算挑战」——贪心 排序求最大偶数和doocs/leetcode 题解精讲LCP 40「心算挑战」——贪心 排序求最大偶数和 导读 「心算挑战」是力扣 LCPLeetCode CUP系列示例工程上一篇Wouter预加载策略提升页面切换体验的技巧下一篇Wouter路由历史记录实现前进后退导航控制创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载导读LCP 49. 环形闯关游戏力扣题库编号K8GULz是「力扣挑战赛」系列中一道标记为困难的经典构造题考察对位运算OR、贪心扩展与循环数组边界的综合运用。本文以 lcp/LCP 49. 环形闯关游戏/README.md 的题面与示例为骨架逐条拆解闯关规则背后的数学结构推导「最小初始积分」的正确求解方法并给出经随机暴力校验的贪心闭包实现以及一组自建的验证用例。读完本文你将掌握环形区间扩张问题的建模思路、位运算累加技巧以及为什么这类问题不能直接用二分答案。题目重述与规则拆解「力扣挑战赛」中有一个由N个关卡组成的环形闯关游戏关卡编号为0 ~ N-1其中编号0与编号N-1相邻。challenge[i]表示挑战编号i的关卡最少需要拥有的积分。环形闯关游戏关卡示意图{:width240px}闯关规则共三条初始开启小扣可以指定其中一个关卡为「开启」状态其余关卡处于「未开启」状态。注意题目问的是初始最少需要多少积分而初始开启的关卡可以自由选择挑战条件与积分增长小扣可以挑战处于「开启」状态且满足最少积分要求的关卡若挑战前积分为score挑战结束后积分变为score | challenge[i]即位运算中的按位或OR扩散开启挑战某个关卡后该关卡两侧相邻的关卡将会开启若之前未开启。需要计算初始最少需要多少积分才能挑战完环形闯关游戏的所有N个关卡。数据范围来自原文档提示1 challenge.length 5 * 10^41 challenge[i] 10^14值域高达10^14说明位运算相关操作必须按2^47量级以内的整数处理longJava/C或 Python 原生整数即可容纳N达到5 * 10^4意味着算法复杂度必须控制在O(N)级别左右。规则背后的核心结构连续区间闭包关键性质已挑战关卡始终构成一个连续区间规则 3 规定「挑战某个关卡后该关卡两侧相邻的关卡开启」。结合规则 1初始只开启一个关卡可以归纳出两个决定性问题形态的性质性质 1区间性任意时刻已开启已挑战的关卡在环上必然构成一个连续的弧段区间。初始是单点每次挑战该弧段左端或右端相邻的一个关卡弧段两端各向外扩展一格。所谓「开启」只会发生在当前已挑战弧段的两个端点外侧。性质 2端点可达性在任一时刻小扣只能挑战当前弧段的左端外侧或右端外侧的那个关卡。因为环上只有这两个关卡处于「开启」状态已挑战关卡本身不会再挑战其余关卡尚未开启。由此「挑战完所有关卡」等价于从某个起点出发通过一系列向左或向右扩展把弧段长度从 1 增长到N。这是一个典型的双向区间扩张问题而不是任意的「点集跳转」问题。积分演进的位运算本质设当前积分为score已挑战弧段的关卡编号集合为S则挑战前score由初始积分与已挑战关卡积分按位或累加而来挑战一个新关卡v后score : score | challenge[v]。由于按位或只会累加 1 位、不会清除任何已有的 1 位积分在闯关过程中单调不减且每个关卡最多贡献一次。这带来一个直接推论挑战顺序中某个关卡一旦能被挑战其在任意后续时刻也必然仍能被挑战积分只增不减且已开启关卡不会关闭。因此贪心策略有天然的可行性空间——关键在于如何确定「能挑战」的时机与初始积分。三个示例的完整推演原文档给出了三组示例这里逐一展开位运算过程便于对照理解闭包扩展的细节。示例 1challenge [5,4,6,2,7]答案4初始选择编号 3 的关卡开启积分4挑战编号 34 | 2 6开启 2、4挑战编号 26 | 6 6开启 1挑战编号 16 | 4 6开启 0挑战编号 06 | 5 7挑战编号 4全部完成。观察从起点 3 出发弧段依次扩为[3] → [2,3] → [1,2,3] → [0,1,2,3] → [0..4]每次扩展都恰好满足「新关卡积分 ≤ 当前积分」且积分随 OR 累加。示例 2challenge [12,7,11,3,9]答案8初始选择编号 3 的关卡开启积分8挑战编号 38 | 3 11开启 2、4挑战编号 211 | 11 11开启 1挑战编号 411 | 9 11开启 0挑战编号 111 | 7 15挑战编号 0全部完成。注意这里的扩展顺序是「先右后左」的混合路径[3] → [2,3] → [2,3,4] → [0,2,3,4] → [0..4][0,2,3,4]在环上即弧段4 → 0 → 2 → 3的连续形式说明贪心扩展时左右两端可以交错推进只要每次都能满足积分门槛即可。示例 3challenge [1,1,1]答案1三个关卡积分都是 1初始积分 1 即可任意选一个起点1 | 1 1随后左右两端分别扩展始终满足门槛全部通关。小结初始积分的候选范围是[1, max(challenge)]因为若初始积分超过max(challenge)任意关卡都可作为起点答案不可能超过它示例的答案都不是max(challenge)本身示例 1 为 4max7说明合理选择起点 左右交替扩展能显著降低初始积分需求这正是本题的难点与乐趣所在。解法推导为什么不能用二分答案一个常见的直觉是初始积分越大越容易通关因此可以对s二分。但实验表明这个直觉是错误的。考虑challenge [2, 7]起点选编号 0积分 2 的关卡初始积分s 5挑战编号 05 | 2 7 ≥ 7再挑战编号 1成功——可行初始积分s 6挑战编号 06 | 2 6 7编号 1 无法挑战——不可行5可行而6不可行说明可行性关于初始积分 s 并不单调。原因是 OR 运算的「位模式」特性6的二进制是110与2010或后仍是110并没有获得7111所需的最高位而5101或上2恰好补全为111。初始积分更大不代表它与后续关卡的积分按位或之后能覆盖更多关卡。因此正确做法是从小到大枚举初始积分s对每个s判定是否存在一条从某个起点出发、能通关全部关卡的扩展路径第一个可行的s即为答案。枚举下界为 1上界为max(challenge)由于答案在[1, max]内整体可通过「逐 s 判定」的方式求解若把每次判定做到 O(N)总复杂度为 O(N · max)仅适合小范围理解大规模数据需结合下面的贪心优化与剪枝。贪心闭包判定固定 s 下的 O(N) 验证对于固定的初始积分s如何判断能否通关结合「弧段连续 积分单调不减」两条性质可以设计如下贪心闭包过程对一个候选起点令已挑战弧段为[l, r]初始l r start当前积分score s | challenge[start]若challenge[start] s该起点不可用循环直到弧段覆盖全部N个关卡若左侧邻居(l-1) mod N未挑战且challenge[l-1] score向左扩展l ← l-1score | challenge[l]否则若右侧邻居(r1) mod N未挑战且challenge[r1] score向右扩展r ← r1score | challenge[r]若两端都无法扩展则该起点在积分s下不能通关弧段覆盖全部关卡即通关成功。为什么贪心是安全的任何时刻可挑战的关卡只有弧段两端而积分单调不减意味着——如果某一端当前可挑战那么先挑战它对另一端没有任何负面影响积分只增不减如果两端都不可挑战则以后也永远不可挑战因为积分只会更大但两端门槛不变若现在challenge score之后score的 OR 累加只会让数值更大……这里需要小心OR 可能让数值变大从而满足门槛这正是扩展会发生的场景一旦某端满足门槛立即扩展即可不存在「等一等更优」的情况因为延迟扩展不会降低另一端门槛也不会带来额外的积分收益之外的好处。因此对任意固定起点只要存在某种扩展顺序能通关贪心的「能扩展就扩展」策略也一定能通关。我在本地用 Python 实现了两套相互独立的方法并交叉验证精确校验器对每个s从所有满足challenge[i] s的起点出发做 BFS枚举弧段状态位掩码表示的所有合法扩展判断是否能到达全满掩码贪心闭包上述左右扩展贪心。在N ∈ [2, 8]、challenge[i] ∈ [1, 63]的 4000 组随机用例、覆盖全部s ∈ [1, max]的约20.6 万个子实例上两者的判定结果完全一致0 失配验证了贪心闭包判定与精确枚举的等价性。参考实现Python小数据教学版def can_finish(challenge, s, start): 固定初始积分 s、固定起点 start贪心闭包判定是否可通关 n len(challenge) if challenge[start] s: return False cleared [False] * n cleared[start] True cnt 1 score s | challenge[start] l r start while cnt n: left (l - 1) % n right (r 1) % n if not cleared[left] and challenge[left] score: l left cleared[l] True score | challenge[l] cnt 1 elif not cleared[right] and challenge[right] score: r right cleared[r] True score | challenge[r] cnt 1 else: return False return True def min_initial_score(challenge): 从小到大枚举初始积分 s返回最小可行值 for s in range(1, max(challenge) 1): for start in range(len(challenge)): if can_finish(challenge, s, start): return s return -1 # 题目保证有解复杂度说明can_finish单次判定为O(N)朴素枚举s与起点为O(max(challenge) · N²)仅适合理解算法与小规模验证面向N 5 * 10^4、challenge[i] ≤ 10^14的正式实现需要进一步优化例如对每个起点先求「左闭包」与「右闭包」的可达区间再合并判断或结合数据结构的剪枝但贪心闭包这一判定核心保持不变。优化方向不属于原文档内容这里不作展开读者可在理解本文原理后自行设计。自建验证用例除原文档三组示例外可将下列用例用于自测前两个来自对算法边界的针对性构造challenge最小初始积分说明[2, 7]5若s 5起点 0 可行5\|27若s 66\|26 7不可行展示非单调性[29, 11]20s24时24\|1127 29不可行而s20时20\|1131 ≥ 29可行进一步验证非单调[5, 4, 6, 2, 7]4原文档示例 1[12, 7, 11, 3, 9]8原文档示例 2[1, 1, 1]1原文档示例 3小结LCP 49. 环形闯关游戏的核心解题链条是建模把「开启」扩散规则翻译成「已挑战关卡构成连续弧段每次只能扩展弧段两端」的区间扩张模型位运算积分演进为score : score | challenge[i]单调不减是贪心的基础判定对固定初始积分s贪心闭包能扩就扩与精确枚举等价可 O(N) 判定枚举由于可行性对s不单调存在[2, 7]、[29, 11]反例不能二分须从小到大枚举s取首个可行值。该题在原仓库 lcp/README.md 中被标记为位运算、并查集、数组、堆优先队列标签说明官方归类还提示了并查集合并连通块等进阶思路——本文的区间闭包视角正是理解那些优化方案的直观基础。若你对后续优化实现感兴趣可以在仓库的 lcp 目录持续关注该题的题解更新。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐LeetCode LCP 12 小张刷题计划贪心 二分查找求解最小最大单日耗时LeetCode LCP 12 小张刷题计划贪心 二分查找求解最小最大单日耗时 导读 本文围绕 LeetCode 题库 LCP 系列经典题目「小张刷题计划示例工程MAS 激活脚本怎么跑按目标选 4 条 Windows 激活路径的实操手册MAS 激活脚本怎么跑按目标选 4 条 Windows 激活路径的实操手册 MASMicrosoft Activation Scripts是一个开源、免费运维doocs/leetcode 题解精讲LCP 40「心算挑战」——贪心 排序求最大偶数和doocs/leetcode 题解精讲LCP 40「心算挑战」——贪心 排序求最大偶数和 导读 「心算挑战」是力扣 LCPLeetCode CUP系列示例工程上一篇Wouter预加载策略提升页面切换体验的技巧下一篇Wouter路由历史记录实现前进后退导航控制创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考