示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载「魔术排列」是力扣 LCPLeetCode 竞赛平台系列中的一道中等难度模拟题收录于本仓库 lcp 目录 下的 LCP 23. 魔术排列。题目以「秋日市集魔术师」为背景抽象出一套固定的洗牌 按批次取牌规则要求判定是否存在某个批次大小 k使取数序列恰好等于给定的目标排列。本文完整继承题目定义与示例推演随后给出从规则推导出的关键剪枝、枚举 k 并模拟的判定算法以及 Python3 / Java / C / Go / TypeScript 五种参考实现与复杂度分析。题目速览魔术师的洗牌与取数规则魔术师的道具是分别写有数字1~N的 N 张卡牌小扣心中想好一个 N 张卡牌的排列target。初始排列顺序为1~N魔术师要找到一个数字 kk 1使卡牌经过下述特殊洗牌方式取走后取走顺序构成的「魔术取数排列」恰好等于target第一步洗牌将当前位于偶数位置下标自 1 开始的卡牌保持当前排列顺序放在位于奇数位置的卡牌之前。例如当前排列[1,2,3,4,5]偶数位置元素为[2,4]奇数位置元素为[1,3,5]洗牌后变为[2,4,1,3,5]。第二步取牌若当前卡牌数量小于等于 k则按排列顺序取走全部卡牌若当前卡牌数量大于 k则取走前 k 张卡牌剩余卡牌继续重复上述两步直至全部取走。最终需要回答是否存在这样的数字 k使得「魔术取数排列」恰好就是target。题目约束如下1 target.length N 5000题目保证target是1~N的一个排列即 1 到 N 各出现一次。在仓库的 LCP 系列索引 中本题被标记为中等难度标签为队列、数组、模拟正好概括了解题所需的核心手段用数组或队列维护卡牌序列并严格按照规则逐轮模拟。示例推演用 k 2 走通完整流程原文档给出了两个示例其中示例 1 包含完整的逐步推演是验证任何实现正确性的基准数据。示例 1target [2,4,3,1,5]N 5初始排列[1,2,3,4,5]选择 k 2轮次当前排列第一步洗牌后第二步取走剩余1[1,2,3,4,5][2,4,1,3,5]2,4[1,3,5]2[1,3,5][3,1,5]3,1[5]3[5][5]5空取走顺序拼成的「魔术取数排列」为2,4,3,1,5恰好等于target因此答案为true。示例 2target [5,4,3,2,1]无论 k 取何值都无法得到该排列答案为false。从规则出发的算法设计判定问题的本质这是一个存在性判定问题k 的取值范围是k 1且 N 张牌第一轮就会全部取完当 k N此时第一次洗牌后牌数 N k直接全部取走行为与 k N 完全一致因此只需枚举k ∈ [1, N]即可保证完备性。对每个候选 k过程是确定性的初始序列固定为1~N洗牌规则固定取牌数量固定。因此只要按规则模拟一遍把取走序列与target逐段比对若完全一致则该 k 满足条件若枚举完所有 k 都不满足则答案为false。关键剪枝魔术取数排列的首个元素恒为 2从规则可以直接推导出一个强力的必要条件n 2 时第一次洗牌前序列为[1,2,...,N]洗牌后偶数位元素2,4,6,...整体前移因此洗牌后序列的第一个元素恒为 2无论 k 取何值k 1第一轮取走的第一块必然包含这个首元素因此「魔术取数排列」的第一个元素恒为 2。结论当n 2且target[0] ! 2时直接返回false无需任何模拟。示例 2 中target[0] 5立即被此剪枝排除与题目给出的答案一致。当n 1时target只能是[1]任何 k 都满足恒为true。逐段匹配的模拟框架对固定 k模拟流程可以描述为维护当前序列arr初始为[1, 2, ..., N]执行洗牌偶数位置元素0-based 下标的1,3,5,...在前奇数位置元素0-based 下标的0,2,4,...在后取走块若len(arr) k则取走全部否则取走前 k 个将取走块与target中对应位置的片段比较不一致立即返回失败剩余部分成为新的arr回到第 2 步直到取完。第一个剪枝可以进一步物化为第一次洗牌的结果S1对所有 k 都是同一个序列[2,4,6,...,1,3,5,...]可以在外层循环前预处理一次随后对每个 k 的第一块比较直接使用S1[:k] target[:k]避免重复计算。同时模拟过程中一旦发现某一块与target对应片段不匹配就立刻剪枝不会继续无意义的后续轮次。复杂度分析对固定 k设轮数为r ceil(N/k)。第 j 轮开始时牌数为N - (j-1)k洗牌需要线性遍历当前序列全部轮次的洗牌总代价约为N (N-k) (N-2k) ... O(N²/k)所有块的比较总代价为O(N)。因此单个 k 的代价为O(N²/k)枚举全部 k 后总复杂度为Σ_{k1}^{N} O(N²/k) O(N² · log N)空间复杂度O(N)需要存储当前序列与洗牌结果。当N 5000时总操作量约为10⁸量级配合首元素剪枝与段比较提前退出C / Java / Go 可以轻松通过Python 采用切片构造洗牌序列也可获得较小的常数实际表现良好。多语言参考实现仓库中本题的解法章节目前标注为「本题暂无题解欢迎补充」以下为经过示例验证的参考实现可作为社区题解的一种补充思路与仓库中其他 LCP 题目的题解组织方式如 LCP 22. 黑白方格画 中「方法一 多语言 tabs」的结构保持一致。Python3from typing import List class Solution: def isMagic(self, target: List[int]) - bool: n len(target) def check(k: int) - bool: arr list(range(1, n 1)) i 0 # target 中已匹配的下标 while arr: # 洗牌偶数位置0-based 奇数下标在前 arr arr[1::2] arr[0::2] m len(arr) if m k: if arr ! target[i:]: return False i m arr [] else: if arr[:k] ! target[i : i k]: return False i k arr arr[k:] return True for k in range(1, n 1): if check(k): return True return FalseJavaclass Solution { public boolean isMagic(int[] target) { int n target.length; for (int k 1; k n; k) { if (check(target, k)) { return true; } } return false; } private boolean check(int[] target, int k) { int n target.length; int[] arr new int[n]; for (int i 0; i n; i) { arr[i] i 1; } int len n, idx 0; while (len 0) { // 洗牌偶数位置元素在前奇数位置元素在后 int[] next new int[len]; int p 0; for (int i 1; i len; i 2) next[p] arr[i]; for (int i 0; i len; i 2) next[p] arr[i]; // 取走前 k 张或全部 int take Math.min(k, len); for (int i 0; i take; i) { if (next[i] ! target[idx i]) return false; } idx take; len - take; for (int i 0; i len; i) arr[i] next[take i]; } return true; } }Cclass Solution { public: bool isMagic(vectorint target) { int n target.size(); for (int k 1; k n; k) { if (check(target, k)) return true; } return false; } bool check(vectorint target, int k) { int n target.size(); vectorint arr(n); iota(arr.begin(), arr.end(), 1); int len n, idx 0; while (len 0) { // 洗牌偶数位置1-based元素整体前移 vectorint next(len); int p 0; for (int i 1; i len; i 2) next[p] arr[i]; for (int i 0; i len; i 2) next[p] arr[i]; int take min(k, len); for (int i 0; i take; i) { if (next[i] ! target[idx i]) return false; } idx take; len - take; for (int i 0; i len; i) arr[i] next[take i]; } return true; } };Gofunc isMagic(target []int) bool { n : len(target) check : func(k int) bool { arr : make([]int, n) for i : range arr { arr[i] i 1 } idx : 0 for len(arr) 0 { // 洗牌偶数位置元素在前 next : make([]int, 0, len(arr)) for i : 1; i len(arr); i 2 { next append(next, arr[i]) } for i : 0; i len(arr); i 2 { next append(next, arr[i]) } take : k if len(next) take { take len(next) } for i : 0; i take; i { if next[i] ! target[idxi] { return false } } idx take arr next[take:] } return true } for k : 1; k n; k { if check(k) { return true } } return false }TypeScriptfunction isMagic(target: number[]): boolean { const n target.length; const check (k: number): boolean { let arr: number[] Array.from({ length: n }, (_, i) i 1); let idx 0; while (arr.length 0) { // 洗牌偶数位置元素在前 const next: number[] []; for (let i 1; i arr.length; i 2) next.push(arr[i]); for (let i 0; i arr.length; i 2) next.push(arr[i]); const take Math.min(k, next.length); for (let i 0; i take; i) { if (next[i] ! target[idx i]) return false; } idx take; arr next.slice(take); } return true; }; for (let k 1; k n; k) { if (check(k)) return true; } return false; }以上实现的关键点洗牌的双循环遍历先收集 0-based 奇数下标即 1-based 偶数位置再收集偶数下标天然实现「偶数位置在前」取块比较take min(k, 当前长度)块内逐元素与target对应片段比对任一不符立即终止剩余序列延续把next[take:]作为下一轮输入保证多轮迭代正确衔接。边界情况与正确性验证用题目示例验证上述算法示例 1target [2,4,3,1,5]。枚举到 k 2 时第一轮洗牌[1,2,3,4,5] - [2,4,1,3,5]取走[2,4]匹配target[0:2]剩余[1,3,5]洗牌为[3,1,5]取走[3,1]匹配target[2:4]剩余[5]洗牌后全部取走匹配target[4:5]。三段全部匹配返回true。示例 2target [5,4,3,2,1]target[0] 5 ! 2被首元素剪枝直接返回false即使不剪枝枚举所有 k 的模拟也都会失败。其他值得注意的边界n 1target只能是[1]取任意 k 1 即满足答案为truek n只进行一轮洗牌后全部取走target必须恰好等于S1 [2,4,6,...,1,3,5,...]k n第一轮即全部取走行为与 k n 完全一致因此枚举上界取 n 即可排列完整性由于target是1~N的排列、取走序列长度恒为 N只要每段都匹配最终长度必然一致无需额外校验。仓库中的组织方式与扩展阅读本题在仓库中的位置与关联资源如下LCP 23. 魔术排列题目完整文档解法章节当前标注「本题暂无题解欢迎补充」LCP 系列索引包含本题的题号、难度中等与标签队列、数组、模拟可快速检索整个 LCP 系列LCP 22. 黑白方格画相邻题目的题解示例展示了本仓库 LCP 题解的标准组织方式方法说明 思考推导 多语言 tabs可作为撰写本题题解时的格式参照。本文给出的参考实现以「枚举 k 模拟」为骨架配合「首元素恒为 2」「预处理 S1」「段比较提前退出」三个剪枝在N 5000的约束下复杂度为O(N² log N)空间O(N)能够覆盖题目全部测试数据。读者可对照示例自行运行验证也可以在此思路基础上探索更优的数学化判定方式。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐LCP 17「速算机器人」题解A/B 双变量迭代的模拟实现与多语言对照doocs/leetcodeLCP 17「速算机器人」题解A/B 双变量迭代的模拟实现与多语言对照doocs/leetcode 本文基于 doocs/leetcode 开源题解仓库中示例工程doocs/leetcode 的 LCP 系列题解全览力扣杯竞赛题的多语言解题指南doocs/leetcode 的 LCP 系列题解全览力扣杯竞赛题的多语言解题指南 本文围绕 doocs/leetcode 开源仓库中的 LCP 系列题解展开示例工程doocs/leetcode 题解精讲LeetCode 0006 Z 字形变换的模拟解法与多语言实现doocs/leetcode 题解精讲LeetCode 0006 Z 字形变换的模拟解法与多语言实现 本文基于 doocs/leetcode 仓库中 0006示例工程上一篇GTA5线上小助手免费的GTA5线上模式多功能辅助工具集5分钟从启动到全套搞定下一篇QKeyMapper 按键映射工具上手指南三步把手柄接进键鼠游戏免费开源创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考