ETH官方钱包

前往
大廳
主題

LeetCode - 2682. Find the Losers of the Circular Game 解題心得

Not In My Back Yard | 2024-07-19 12:00:15 | 巴幣 2 | 人氣 100

題目連結:


題目意譯:
現在有 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 位朋友第二次拿到球,所以遊戲結束。


解題思維:
模擬即可,並在過程中用一個布林陣列來紀錄每一個人有沒有碰過球。

最後在遊戲結束後掃過一次布林陣列看哪些人沒碰過球即是所求。




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

創作回應

相關創作

更多創作