2022-05-04

[Zheaoli]

2022-05-04

[dreamhunter2333]

package main

/*
 * @lc app=leetcode.cn id=1823 lang=golang
 *
 * [1823] 找出游戏的获胜者
 */

// @lc code=start
func findTheWinner(n int, k int) int {
    data := make([]int, n)
    for i := range data {
        data[i] = i + 1
    }
    j := 0
    allSum := n
    for len(data) > 1 {
        j = (j+k%allSum)%allSum - 1
        if j == -1 {
            j = allSum - 1
        }
        data = append(data[:j], data[j+1:]...) // 删除中间1个元素
        allSum -= 1
    }
    return data[0]
}

// func main() {
//  fmt.Println(findTheWinner(5, 2))
// }
// @lc code=end

---

微信id: 而我撑伞 来自 vscode 插件

[SaraadKun]

1823. 找出游戏的获胜者

链表模拟

class Solution {
    class Node {
        int val;
        Node next;
        public Node(int val){
            this.val = val;
        }
    }

    public int findTheWinner(int n, int k) {
        //链表模拟
        Node pre = new Node(-1);
        Node cur = pre;
        for (int i = 1; i <= n; i++) {
            cur.next = new Node(i);
            cur = cur.next;
        }
        cur.next = pre.next;
        Node p = pre;
        int cnt = n;
        while(cnt > 1) {
            int step = (k - 1) % cnt + 1;
            for (int i = 1; i < step; i++) {
                p = p.next;
            }
            p.next = p.next.next;
            cnt--;
        }
        return p.next.val;
    }
}

递归

class Solution {
    public int findTheWinner(int n, int k) {
        if (n <= 1) {
            return n;
        }
        //当前轮次的坐标在下一轮中的相对坐标为 (cur + n - k) % n,即左移了k位（因为下轮游戏起始点右移了k位）
        //所以下一轮中的的坐标在当前轮的位置为 (next + k) % n,即右移k位
        int ans = (findTheWinner(n - 1, k) + k) % n;
        return ans == 0 ? n : ans;
    }
}

WeChat: Saraad