循環の術（【LeetCode】189. Rotate Array 関連）
「循環の術」はLeetcodeの問題を解く際に、かなーり強い味方になります。
数学の公式のように使い方を覚えちゃいましょう！
簡単なのに、けっこう強力ですぜぇ！
問題
整数配列 nums が与えられたとき、配列の最初から順番にk回アクセスしてください。
例 1：
入力:
nums = [19,5,77]
k = 3
出力:
k=1 のとき nums[0] = 19
k=2 のとき nums[1] = 5
k=3 のとき nums[2] = 77
例 2：
入力:
nums = [19,5,77]
k = 7
出力:
k=1 のとき nums[0] = 19
k=2 のとき nums[1] = 5
k=3 のとき nums[2] = 77
k=4 のとき nums[0] = 19
k=5 のとき nums[1] = 5
k=6 のとき nums[2] = 77
k=7 のとき nums[0] = 19
こんなの余裕じゃないっすかー。
解法（実装）
package main
import "fmt"
func circulate(nums []int, k int) {
for i := 0; i < k; i++ {
fmt.Printf("k=%dのとき nums[%d] = %d\n", i+1, i, nums[i])
}
}
func main() {
// 例 1
nums1 := []int{19, 5, 77}
k1 := 3
fmt.Println("=== 例1 ===")
circulate(nums1, k1)
// 例 2
nums2 := []int{19, 5, 77}
k2 := 7
fmt.Println("=== 例2 ===")
circulate(nums2, k2)
}
main.go 実行結果
=== 例1 ===
k=1のとき nums[0] = 19
k=2のとき nums[1] = 5
k=3のとき nums[2] = 77
=== 例2 ===
k=1のとき nums[0] = 19
k=2のとき nums[1] = 5
k=3のとき nums[2] = 77
panic: runtime error: index out of range [3] with length 3
goroutine 1 [running]:
main.circulate({0xc0000a4ef0, 0x3, 0xc0000a4f20?}, 0x7)
/home/m_ebina/leetcode/circulate/main.go:8 +0x11c
main.main()
/home/m_ebina/leetcode/circulate/main.go:25 +0x108
exit status 2
はい、余裕じゃなかったですね。
k=4のとき nums[3]を参照しにいきますので、与えられた配列の範囲外にアクセスしているのでダメですね。アクセスするインデックスが要素数を越えた場合は最初に戻るのがポイントですね。
それをどのようにして表現するのか？
再度、整理してみましょう。
nums[0] → OK
nums[1] → OK
nums[2] → OK
nums[3] → NG 範囲外。例2のように nums[0]になるように変換できないか？
つまり、配列のインデックスに着目して下記のように変換したい。
3 → 0
4 → 1
5 → 2
6 → 0
7 → 1
上記をずっと見つめていると、何やら循環していることに気付けるでしょう。
0 → 1 → 2 → 0 → 1 → 2 → 0 → 1 → 2 → …
循環（周期）させたい場合は「剰余（余り）」を使います。
下記の表を見てください。
| インデックス | 要素数 | 余り |
|---|---|---|
| 0 | 3 | 0 |
| 1 | 3 | 1 |
| 2 | 3 | 2 |
| 3 | 3 | 0 |
| 4 | 3 | 1 |
| 5 | 3 | 2 |
| 6 | 3 | 0 |
| 7 | 3 | 1 |
例）インデックス 5の場合
5 ÷ 3 = 1 余り 2
→ 2に着目している
ではこの余りである2は何を意味しているかというと、
「スタート地点（インデックスが0）からどのくらい進んでいるか？」を表しています。
インデックスは進んだ総数になります。
インデックス 5（進んだ総数 5）の場合は下記になります。
|_|_|_|
0 1 2
↑
start
--------------
|_|_|_|
0 1 2
↑
スタート地点から1進んだ（総数 1）
--------------
|_|_|_|
0 1 2
↑
スタート地点から2進んだ（総数 2）
--------------
|_|_|_|
0 1 2
↑
スタート地点から0進んだ（総数 3）
--------------
|_|_|_|
0 1 2
↑
スタート地点から1進んだ（総数 4）
--------------
|_|_|_|
0 1 2
↑
スタート地点から2進んだ（総数 5）
--------------
つまり、インデックス 5（進んだ総数 5）はスタート地点から2進んだ位置にあると言えます。
まとめ
定着をかねて、ちょいと簡単な練習問題です。
■ 練習1
要素が3の配列(nums)に順番に10回読み取る場合は、何番目の位置にいるか？
→ 10 % 3
→ 1（つまり、nums[1]の位置）
■ 練習2
要素が5の配列(nums)に順番に13回読み取る場合は、何番目の位置にいるか？
→ 13 % 5
→ 3（つまり、nums[3]の位置）
■ 練習3
要素が100の配列(nums)に順番に250回読み取る場合は、何番目の位置にいるか？
→ 250 % 100
→ 50（つまり、nums[50]の位置）
おぉー！！
大きい数字のときに威力を発揮しますね！
ちなみに曜日の計算にも使えるんですよ。
例えば、スタート地点を日曜日にしたときに100日後は何曜日になるか？
→ 要素が7で、100回読み取る
→ 100 % 7
→ 2（つまり、日曜日から2つ進めれば良い！）
→ 火曜日
解法（実装）
package main
import "fmt"
func circulate(nums []int, k int) {
// 前回のコード
// for i := 0; i < k; i++ {
// fmt.Printf("k=%d のとき nums[%d] = %d\n", i+1, i, nums[i])
// }
for i := 0; i < k; i++ {
// iを(要素数)で割った余りをi_convertへ
i_convert := i % len(nums) // i_convert を循環させる
fmt.Printf("k=%d のとき nums[%d] = %d\n", i+1, i_convert, nums[i_convert])
}
}
func main() {
// 例 1
nums1 := []int{19, 5, 77}
k1 := 3
fmt.Println("=== 例1 ===")
circulate(nums1, k1)
// 例 2
nums2 := []int{19, 5, 77}
k2 := 7
fmt.Println("=== 例2 ===")
circulate(nums2, k2)
}
main.go 実行結果
=== 例1 ===
k=1 のとき nums[0] = 19
k=2 のとき nums[1] = 5
k=3 のとき nums[2] = 77
=== 例2 ===
k=1 のとき nums[0] = 19
k=2 のとき nums[1] = 5
k=3 のとき nums[2] = 77
k=4 のとき nums[0] = 19
k=5 のとき nums[1] = 5
k=6 のとき nums[2] = 77
k=7 のとき nums[0] = 19
Discussion