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

4小时前力扣题解21

一、问题理解

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

将卡牌偶数位置的牌移到奇数位置牌前面
每次取前k张牌，剩余牌重复上述过程
判断是否存在k值使得最终取牌顺序等于目标排列

二、解决思路

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

观察洗牌后的第一个元素必须是target[0]，这可以缩小k的可能范围
但最直观的方法是直接模拟整个过程

三、关键步骤详解

‌洗牌操作‌：

将当前排列的偶数下标元素(1-based)提取出来
再将奇数下标元素接在后面
例如[1,2,3,4,5] → [2,4,1,3,5]

‌取牌操作‌：

每次取前k张牌加入结果
剩余牌继续洗牌
直到所有牌被取完

‌验证匹配‌：

在取牌过程中实时检查是否与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;
    }
};