---
# System prepended metadata

title: LeetCode 1823. Find the Winner of the Circular Game
tags: [python, LeetCode]

---

# LeetCode 1823. Find the Winner of the Circular Game

###### tags: `python`,`LeetCode`
>這邊使用Python解題

## 題目：
你有 𝑛 個數字，從 1 到 𝑛，每次前進 𝑘 個數字。如果 𝑘 前進時超過或等於 𝑛，則從 1 開始繼續，直到只剩下一個數字。


## 範例
### 範例 1:
![image](https://hackmd.io/_uploads/B1l6EWJtD0.png)
```
Input: n = 5, k = 2
Output: 3
Explanation: Here are the steps of the game:
1) Start at friend 1.
2) Count 2 friends clockwise, which are friends 1 and 2.
3) Friend 2 leaves the circle. Next start is friend 3.
4) Count 2 friends clockwise, which are friends 3 and 4.
5) Friend 4 leaves the circle. Next start is friend 5.
6) Count 2 friends clockwise, which are friends 5 and 1.
7) Friend 1 leaves the circle. Next start is friend 3.
8) Count 2 friends clockwise, which are friends 3 and 5.
9) Friend 5 leaves the circle. Only friend 3 is left, so they are the winner.
```

### 範例 2:
```
假設 𝑛=7，𝑘=3
k=3，程序的輸出過程如下：

初始列表: [1, 2, 3, 4, 5, 6, 7]
第一次移除: 移除位置 2，數字 3，列表變為 [1, 2, 4, 5, 6, 7]
第二次移除: 移除位置 4，數字 6，列表變為 [1, 2, 4, 5, 7]
第三次移除: 移除位置 1，數字 2，列表變為 [1, 4, 5, 7]
第四次移除: 移除位置 3，數字 7，列表變為 [1, 4, 5]
第五次移除: 移除位置 2，數字 5，列表變為 [1, 4]
第六次移除: 移除位置 1，數字 4，列表變為 [1]
最終剩下的數字是 1。
```


## 條件限制
* `1 <= k <= n <= 500`

## 我的解題思路：
1. 初始化數字列表：
我們用一個列表來表示這 **𝑛** 個數字。初始列表是 **[1, 2, 3, ..., n]**。

2. 追蹤當前位置：
用一個變數 **index** 來追蹤目前的位置。初始位置是 0（即列表的第一個元素）。

3. 計算下個要移除的數字的位置：
每次從當前位置開始，前進 𝑘−1 個位置（因為列表的索引是從 0 開始計算）。使用模運算來確保位置在範圍內，即 **(index + k - 1) % len(numbers)**。這個公式確保了即使前進的步數超過列表的長度，位置也能正確循環回列表的開頭。

4. 移除數字：
使用 **pop** 方法從列表中移除計算出的索引位置的數字，並更新 **index** 變數。

5. 迴圈直到只剩下一個數字：
重複步驟 3 和 4，直到列表中只剩下一個數字。

## 程式碼:
```python
def findTheWinner(self, n: int, k: int) -> int:
    n_list = [i for i in range(1, n+1)]
    index = 0

    while len(n_list) > 1:
       index = (index + k - 1) % len(n_list)
       n_list.pop(index)

    return n_list[0]
```

## 題外話
在第二行中有出現這樣的內容: `n_list = [i for i in range(1, n+1)]`，讀者老爺們即使沒用過應該也能很快知道這是幹嘛的，這是 Python 的 Comprehension，可以用在任何可迭代物件上，有興趣聊解的可以看這篇文章:【[一次了解 Python Comprehension 的用法](/c7myvEYVRWSXUKU1SJi3Hw)】。

###### Topic: `Array`、`Math`、`Recursion`、`Queue`、`Simulation`