1806. 还原排列的最少操作步数

难度

• Easy
• Medium
• Hard

思路

首先尝试模拟，结果真能过。

看题解，更巧妙的做法是利用下标规律来模拟。

代码

class Solution:
    def reinitializePermutation(self, n: int) -> int:
        origin = [i for i in range(n)]
        perm = list(origin)
        ans = 0
        while ans == 0 or perm != origin:
            ans += 1
            arr = [0 for _ in range(n)]
            for i in range(n):
                if (i & 1) == 0: arr[i] = perm[i // 2]
                else: arr[i] = perm[n // 2 + (i -1) // 2]
            perm = list(arr)
        return ans

class Solution:
    def reinitializePermutation(self, n: int) -> int:
        # 下标模拟
        ans, idx = 0, 1
        while True:
            ans += 1
            if idx < (n >> 1): idx <<= 1
            else:
                idx = (idx << 1) - n + 1
            if idx == 1: return ans