# [1823. Find the Winner of the Circular Game](https://leetcode.com/problems/find-the-winner-of-the-circular-game/description/)

## 1. 題目說明
- **有 ==n 個人==在玩遊戲，按順序順時針編號從 ==1 ~ n==**
- **遊戲規則**
1. **從 ==第 1 個人== 開始遊戲**
2. **每次順時針方向 ==數 k 個人==(包括自己)**
3. **==最後被數到的人==輸掉並==離開遊戲==**
4. **下一次遊戲從順時針數的 ==第 1 個== 還在遊戲的人開始**
5. **重複 ==2 ~ 4 步驟==，直到剩下一個人**
6. **最後剩下的人贏得遊戲**
- **題目會給予 ==人數 n== 和 ==整數 k==，找出贏得遊戲的人對應的==編號==**
## 2. 解題思路1
1. **創建一個 ==Array==，用來記錄每位玩家的存活訊息**
- **若為 ==0==，代表存活**
- **若為 ==1==，代表離開遊戲**
2. **用一個指==針指==向要離開的玩家**
3. **直到剩下一個玩家，尋找該名玩家是第幾位玩家**

### ● 程式碼(index 指向)

int findTheWinner(int n, int k) {
    int* player = malloc(sizeof(int) * n); //紀錄玩家是否存活
    int size = n;                          //紀錄剩餘玩家數量
    int index = 0;                         //被指向的玩家

    for (int i = 0; i < n; i++)
        player[i] = 0;

    while (size > 1) { //循環遊戲回合，直到剩下1人
        for (int i = 0; i < k;) { //數k個人
            if (!player[index])
                i++;
            if (i < k){
                index++;
                index = index % n;
            }
        }
        player[index] = 1;
        size--;
    }
    while(player[index]){ //找出剩下的一個人
        index++;
        index = index % n;
    }
    return index + 1;
}

---
## 3. 解題思路2(Queue 版)

### ● 程式碼

struct queue {
    int* data;
    int head;
    int tail;
    int capacity;
    int size;
};
struct queue* createQueue(int size) {
    struct queue* obj = malloc(sizeof(struct queue));
    obj->data = malloc(sizeof(int) * size);
    obj->head = 0;
    obj->tail = 0;
    obj->capacity = 0;
    obj->size = size;
    return obj;
}
void enqueue(struct queue* obj, int data) {
    obj->capacity++;
    obj->data[obj->head] = data;
    obj->head++;
    obj->head %= obj->size;
}
int dequeue(struct queue* obj) {
    if (obj->capacity == 0)
        return 0;
    obj->capacity--;
    int reg = obj->data[obj->tail];
    obj->tail++;
    obj->tail %= obj->size;
    return reg;
}
int findTheWinner(int n, int k) {
    struct queue* obj = createQueue(n);
    for (int i = 0; i < n; i++)
        enqueue(obj, i + 1);
        
    while (obj->capacity > 1) {
        for (int i = 1; i < k; i++) {
            int reg = dequeue(obj);
            enqueue(obj, reg);
        }
        dequeue(obj);
    }
    return dequeue(obj);
}

## 4. 解題思路3(Ring Buffer)
1. **可以使用==Ring Buffer==完成該問題**
- **該 Ring Buffer 須滿足以下幾點：**
1. **==新增資料==從==末端==**
2. **==移除資料==從==當前指向的==**
3. **每一筆資料代表==玩家編號==**
2. **一樣持續執行遊戲，直到==剩下1人==**
3. **回傳最後一人的編號**

### ● 程式碼

//實作Ring Buffer
struct node {
    int data;
    struct node* next;
};
struct queue {
    struct node* head;
    struct node* tail;
};
struct queue* createQueue() {
    struct queue* obj = malloc(sizeof(struct queue));
    obj->head = NULL;
    obj->tail = NULL;
    return obj;
}
//插入資料行為
void enqueue(struct queue* obj, int data) {
    struct node* n = malloc(sizeof(struct node));
    n->data = data;
    n->next = NULL;
    if (!obj->head){
        obj->head = n;
        obj->tail = n;
    }
    else if (obj->head == obj->tail) {
        n->next = obj->head;
        obj->head->next = n;
        obj->tail = n;
    } else {
        n->next = obj->head;
        obj->tail->next = n;
        obj->tail = n;
    }
}
//移除資料從head開始
int dequeue(struct queue* obj) {
    struct node* reg = obj->head;
    obj->tail->next = obj->head->next;
    obj->head = obj->tail->next;
    int data = reg->data;
    free(reg);
    return data;
}
int findTheWinner(int n, int k) {
    //初始化queue
    struct queue* obj = createQueue();
    for (int i = 0; i < n; i++) {
        enqueue(obj, i + 1);
    }
    //dequeue直到剩下一位玩家
    while (obj->head != obj->tail) {
        for (int i = 1; i < k; i++) {
            obj->tail = obj->tail->next;
            obj->head = obj->head->next;
        }
        dequeue(obj);
    }
    return dequeue(obj);
}