[LCP 23. 魔术排列]
秋日市集上，魔术师邀请小扣与他互动。魔术师的道具为分别写有数字 1~N 的 N 张卡牌，然后请小扣思考一个 N 张卡牌的排列 target。
魔术师的目标是找到一个数字 k（k >= 1），使得初始排列顺序为 1~N 的卡牌经过特殊的洗牌方式最终变成小扣所想的排列 target，特殊的洗牌方式为：
- 第一步，魔术师将当前位于 偶数位置 的卡牌（下标自 1 开始），保持 当前排列顺序 放在位于 奇数位置 的卡牌之前。例如：将当前排列 [1,2,3,4,5] 位于偶数位置的 [2,4] 置于奇数位置的 [1,3,5] 前，排列变为 [2,4,1,3,5]；
- 第二步，若当前卡牌数量小于等于
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 <= 5000- 题目保证
target是1~N的一个排列。
package LeetCode;
import java.util.Arrays;
/**
* @ClassName LCP23
* @Description 通过模拟来做的，感觉有点麻烦
* @Author m
* @Version 1.0
*/
public class LCP23 {
public boolean isMagic(int[] target) {
int n = target.length;
int[] first = new int[n];
for (int i = 0; i < first.length; i++) {
first[i] = i+1;
}
//先通过第一次交换判断出K的最大值
first = change(first);
int maxLen = n;
for (int i = 0; i < n; i++) {
if(first[i] != target[i] ) {
maxLen = i;
break;
}
}
boolean isMagic = false;
//从大到小选取K的值，对每一个K的值模拟判断是否能构成Magic数组
outer : for (int len = maxLen; len > 0; len--) {
//选定长度为len，截取len后面的数组进入下一次模拟
int[] now = Arrays.copyOfRange(first , len, first.length);
int[] nowTarget = Arrays.copyOfRange(target , len, target.length);
inner : while (now.length > 0) {
now = change(now);
if(len > now.length){
len = now.length;
}
//对交换后数组前len位进行检查,如果与target不一致则说明该K不能满足要求
for (int i = 0; i < len; i++) {
if(now[i] != nowTarget[i]) {
break inner;
}
}
now = Arrays.copyOfRange(now, len ,now.length);
nowTarget = Arrays.copyOfRange(nowTarget, len ,nowTarget.length);
//最后的数组与target一致
if(now.length == 0) {
isMagic = true;
break outer;
}
}
}
return isMagic;
}
/**
* 将传入的数组按偶数位置在前奇数位置在后排列返回
* 例如传入【1，2，3，4，5】 返回【2，4，1，3，5】
* @param nums
* @return
*/
private int[] change(int[] nums) {
int len = nums.length;
int[] res = new int[len];
for (int i = 0; i < len / 2; i++) {
res[i] = nums[i*2+1];
}
for (int i = len/2; i < len; i++) {
res[i] = nums[(i-len/2)*2];
}
return res;
}
public static void main(String[] args) {
System.out.println(new LCP23().isMagic(new int[]{
2, 4, 3, 1, 5
}));
}
}