題目連結:
題目意譯:
現在有 n 位朋友正在玩一個遊戲。這群朋友坐下圍成一個圈並按順時針編號為 1 到 n。更正式地說,從第 i 位朋友往順時針方向移動將會帶你到第 i + 1 位朋友那邊(1 ≦ i < n),而從第 n 位朋友往順時針方向移動將會把你帶到第 1 位朋友那邊。
遊戲的規則如下:
第 1 位朋友拿到了球。
之後,第 1 位朋友會把球往順時針方向距離他 k 步遠的人傳過去。
接下來,得到球的該朋友會把球往順時針方向距離他 2 × k 步遠的人傳過去。
再之後,得到球的該朋友會把球往順時針方向距離他 3 × k 步遠的人傳過去,以此類推。
換句話說,在第 i 回合時,拿著球的朋友將會把球往順時針方向距離他 i × k 步遠的人傳過去。
遊戲結束於有朋友第二次得到球為止。
該遊戲的輸家們將會是那些整個遊戲中沒拿過球的人。
給定朋友數 n 以及一整數 k,回傳陣列 answer,其包含著以升序排序的遊戲輸家編號。
限制:
1 ≦ k ≦ n ≦ 50
範例測資:
範例 1:
輸入: n = 5, k = 2
輸出: [4,5]
解釋: 遊戲流程如下:
1) 開始於第 1 位朋友並傳到 2 步遠的朋友,即第 3 位朋友。
2) 第 3 位朋友傳球給 4 步遠的朋友,即第 2 位朋友。
3) 第 2 位朋友傳球給 6 步遠的朋友,即第 3 位朋友。
4) 因為第 3 位朋友第二次拿到球,所以遊戲結束。
範例 2:
輸入: n = 4, k = 4
輸出: [2,3,4]
解釋: The game goes as follows:
1) 開始於第 1 位朋友並傳到 4 步遠的朋友,即第 1 位朋友。
2) 因為第 1 位朋友第二次拿到球,所以遊戲結束。
解題思維:
模擬即可,並在過程中用一個布林陣列來紀錄每一個人有沒有碰過球。
最後在遊戲結束後掃過一次布林陣列看哪些人沒碰過球即是所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。