前往
大廳
主題

LeetCode - 1806. Minimum Number of Operations to Reinitialize a Permutation 解題心得

Not In My Back Yard | 2024-02-13 12:00:14 | 巴幣 0 | 人氣 65

題目連結:


題目意譯:
你被給定一個偶數 n。你一開始有著一個大小為 n 的排列 perm,其中 perm[i] == i(索引值從 0 開始)。

在一次操作中,你將會創造一個新的陣列 arr,而對於每一個 i 值:
    如果 i % 2 == 0,則 arr[i] = perm[i / 2];
    如果 i % 2 == 1,則 arr[i] = perm[n / 2 + (i - 1) / 2]。
你將會以 arr 的內容取代掉 perm 原本的內容。

回傳最小的非零所需操作數,使得 perm 經過這些操作後回到 perm 一開始的數值。

限制:
2 ≦ n ≦ 1000
n 為偶數。



範例測資:
範例 1:
輸入: n = 2
輸出: 1
解釋: 一開始,perm = [0,1]。
在第 1 次操作之後,perm = [0,1]
所以其只需要 1 次操作。

範例 2:
輸入: n = 4
輸出: 2
解釋: 一開始,perm = [0,1,2,3]。
在第 1 次操作之後,perm = [0,2,1,3]
在第 2 次操作之後,perm = [0,1,2,3]
所以其只需要 2 次操作。

範例 3:
輸入: n = 6
輸出: 4


解題思維:
按照類似這題的分組方式來將索引值分成若干組。當然,這個分組方式是藉由本題的定義。例如如果 n = 6,則索引值 1 、 3 、 4 、 2 是一組的(這些數字按照「計算」的順序陳列)。

而所求為每一組的元素個數之最小公倍數(因為要讓所有元素回到原位,則需要每一組都各自回到原位)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作