力扣LCP23题：魔术排列的模拟解决方案

一、问题理解

题目描述了一个魔术洗牌过程：

1. 将卡牌偶数位置的牌移到奇数位置牌前面

2. 每次取前k张牌，剩余牌重复上述过程

3. 判断是否存在k值使得最终取牌顺序等于目标排列

二、解决思路

1. ‌暴力尝试法‌：尝试所有可能的k值(1到n)，模拟洗牌和取牌过程，检查是否匹配目标排列。

2. ‌优化思路‌：

• 观察洗牌后的第一个元素必须是target[0]，这可以缩小k的可能范围

• 但最直观的方法是直接模拟整个过程

三、关键步骤详解

1. ‌洗牌操作‌：

• 将当前排列的偶数下标元素(1-based)提取出来

• 再将奇数下标元素接在后面

• 例如[1,2,3,4,5] → [2,4,1,3,5]

2. ‌取牌操作‌：

• 每次取前k张牌加入结果

• 剩余牌继续洗牌

• 直到所有牌被取完

3. ‌验证匹配‌：

• 在取牌过程中实时检查是否与target匹配

• 一旦发现不匹配立即终止当前k的尝试

四、完整代码

class Solution {
public:
    bool isMagic(vector<int>& target) {
        int n = target.size();
        // 生成初始排列1~n
        vector<int> initial(n);
        for(int i = 0; i < n; i++) initial[i] = i + 1;
       
        // 尝试所有可能的k值(1到n)
        for(int k = 1; k <= n; k++) {
            vector<int> current = initial;
            vector<int> result;
            bool valid = true;
           
            while(!current.empty()) {
                // 第一步：洗牌操作
                vector<int> shuffled;
                // 先放偶数位置(索引1,3,...，对应下标0,2,...)
                for(int i = 1; i < current.size(); i += 2) {
                    shuffled.push_back(current[i]);
                }
                // 再放奇数位置(索引0,2,...，对应下标0,2,...)
                for(int i = 0; i < current.size(); i += 2) {
                    shuffled.push_back(current[i]);
                }
               
                // 第二步：取牌操作
                int take = min(k, (int)shuffled.size());
                for(int i = 0; i < take; i++) {
                    result.push_back(shuffled[i]);
                    // 检查是否与target匹配
                    if(result.size() > target.size() ||
                       result[result.size()-1] != target[result.size()-1]) {
                        valid = false;
                        break;
                    }
                }
                if(!valid) break;
               
                // 剩余牌继续处理
                current = vector<int>(shuffled.begin() + take, shuffled.end());
            }
           
            if(valid && result == target) {
                return true;
            }
        }
       
        return false;
    }
};

五、代码解析

1. ‌初始化‌：生成初始排列1~n

2. ‌k值尝试‌：遍历所有可能的k值(1到n)

3. ‌洗牌模拟‌：

• 分离偶数和奇数位置元素

• 合并成新排列

4. ‌取牌验证‌：

• 取前k张牌

• 检查是否与target对应位置匹配

5. ‌结果判断‌：如果完全匹配则返回true

‌