Back to Leetcode

Readme

LCCUP/2020Fall/LCP23.魔术排列/Readme.md

latest1.0 KB
Original Source

LCP23. 魔术排列

本题的关键是看出k的取值。如果我们将第一步变化后的数组arr与target进行对比,求得它的公共前缀长度len,那么k只可能等于len。

target:2 4 9 x x x x
arr:    2 4 6 8 1 3 5 7

在上面的例子中,len=2. 如果k=3,那么第一回合之后,arr的前3个(即2,4,6)将会永远的保存下来作为最终序列的前3个。而这样的话就与target的第三个元素矛盾。

target:2 4 9 x x x x
arr:    2 | 4 6 8 1 3 5 7

在上面的例子中,len=2. 如果k=1,那么第一回合之后,arr的首元素被保存下来作为最终序列的第一个元素。arr剩余的部分[4,6,8,1,3,5,7]将会参与新的回合的操作。但是我们发现,第二回合结束后,必然是6排在arr的首位继而被保存为最终序列的第二个元素。这样就与target的第二个元素矛盾。

综上所述,k只可能是len。注意,接下来只需要模拟一遍洗牌的操作(所有操作细节都已知),来判断target是否是最终序列。