class Solution {
public:
bool isMagic(vector<int>& target) {
}
};
LCP 23. 魔术排列
秋日市集上，魔术师邀请小扣与他互动。魔术师的道具为分别写有数字 1~N 的 N 张卡牌，然后请小扣思考一个 N 张卡牌的排列 target。
魔术师的目标是找到一个数字 k（k >= 1），使得初始排列顺序为 1~N 的卡牌经过特殊的洗牌方式最终变成小扣所想的排列 target，特殊的洗牌方式为：
k，则魔术师按排列顺序取走全部卡牌；若当前卡牌数量大于 k，则取走前 k 张卡牌，剩余卡牌继续重复这两个步骤，直至所有卡牌全部被取走；卡牌按照魔术师取走顺序构成的新排列为「魔术取数排列」，请返回是否存在这个数字 k 使得「魔术取数排列」恰好就是 target，从而让小扣感到大吃一惊。
示例 1：
输入：
target = [2,4,3,1,5]输出：
true解释：排列 target 长度为 5，初始排列为：1,2,3,4,5。我们选择 k = 2： 第一次：将当前排列 [1,2,3,4,5] 位于偶数位置的 [2,4] 置于奇数位置的 [1,3,5] 前，排列变为 [2,4,1,3,5]。取走前 2 张卡牌 2,4，剩余 [1,3,5]； 第二次：将当前排列 [1,3,5] 位于偶数位置的 [3] 置于奇数位置的 [1,5] 前，排列变为 [3,1,5]。取走前 2 张 3,1，剩余 [5]； 第三次：当前排列为 [5]，全部取出。 最后，数字按照取出顺序构成的「魔术取数排列」2,4,3,1,5 恰好为 target。
示例 2：
输入：
target = [5,4,3,2,1]输出：
false解释：无法找到一个数字 k 可以使「魔术取数排列」恰好为 target。
提示：
1 <= target.length = N <= 5000target 是 1~N 的一个排列。原站题解
golang 解法, 执行用时: 12 ms, 内存消耗: 5.9 MB, 提交时间: 2023-09-25 16:01:11
// 通过第一次洗牌找到k，然后一直比较下去
func isMagic(target []int) bool {
nums := make([]int, len(target))
for i := range nums {
nums[i] = i+1
}
nums = helper(nums)
// find k
k := 0
for k < len(nums) && nums[k] == target[k] {
k++
}
if k == 0 {
return false
}
for {
if k >= len(nums) {
return isSame(nums, target, len(nums))
}
if !isSame(nums, target, k) {
return false
}
nums = nums[k:]
target = target[k:]
nums = helper(nums)
}
return false
}
func isSame(nums, target []int, end int) bool {
for i := 0; i < end; i++ {
if nums[i] != target[i] {
return false
}
}
return true
}
func helper(nums []int) []int {
res := make([]int, len(nums))
idx := 0
for i := 1; i < len(nums); i+=2 {
res[idx] = nums[i]
idx++
}
for i := 0; i < len(nums); i+= 2 {
res[idx] = nums[i]
idx++
}
return res
}
cpp 解法, 执行用时: 8 ms, 内存消耗: 15.9 MB, 提交时间: 2023-09-25 16:00:13
class Solution {
public:
bool isMagic(vector<int>& target) {
vector<int> a;
int n = target.size(), j = 0;
for (int i = 2; i <= n; i += 2) a.push_back(i);
for (int i = 1; i <= n; i += 2) a.push_back(i);
int k = 0;
for (int i = 0; i < n; ++i) {
if (target[i] == a[i]) ++k, ++j;
else break;
}
if(k == 0) return false;
vector<int> b(a.begin() + k, a.end());
while (j < n) {
vector<int> tmp;
for (int i = 1; i < b.size(); i += 2) tmp.push_back(b[i]);
for (int i = 0; i < b.size(); i += 2) tmp.push_back(b[i]);
b.clear();
for (int i = 0; i < tmp.size(); ++i) {
if (i < k) {
if (target[j] != tmp[i]) return false;
++j;
}else b.push_back(tmp[i]);
}
}
return true;
}
};
python3 解法, 执行用时: 672 ms, 内存消耗: 16.6 MB, 提交时间: 2023-09-25 15:59:55
class Solution:
def shuffleCards(self, cards: List[int]) -> int:
'''洗牌过程'''
return cards[1::2] + cards[0::2]
def isMagic(self, target: List[int]) -> bool:
n = len(target)
cards = [i + 1 for i in range(n)]
cards = self.shuffleCards(cards)
# 根据第一次洗牌的结果，确定疑似 k 值
k = 0
while k < n:
if target[k] != cards[k]:
break
k += 1
if k == 0:
return False
# 此后迭代的更新、遍历当前 cards 和 剩余的 target 数组，判断依次取出的数字是不是都相等
while cards:
for i in range(min(k, len(cards))):
if cards.pop(0) != target.pop(0):
return False
cards = self.shuffleCards(cards)
return True