约瑟夫环Java实现

约瑟夫环描述：编号为0到n-1的n个人围成一圈。从编号为0的人开始报数1，依次下去，报到m的人离开，问最后留下的一个人，编号是多少？

输出描述: 输出最后一个留下来的人的编号
思路一：写一个单向循环链表。每m个就删除一个节点。如果链表中只剩下来最后，那么答案就是它了。

1 构建一个单向循环链表，每一个节点的值是其报数的数字，从1开始。

2 构建一个虚拟头节点，从头结点开始，每m个开始删除。

具体的删除逻辑是使用pre指针来删除。

3 当链表只剩下最后一个，就可以返回该值了

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    public int ysf (int n, int m) {
        // write code here
    
        Node head = new Node(-1);  // 虚拟头节点
        Node cur = head;
        for (int i = 1; i <= n; i++){  // 把所有报数都放进链表中
            Node node = new Node(i);
            cur.next = node;
            cur = cur.next;
        }
        cur.next = head.next;  // 单向循环链表
        
        cur = head;  // cur指针重新回来头部
        Node pre = null;
        
        while (cur.next != null){
            int count = m;  // 注意这里每一次都需要更新为m
            while (count-- > 0){
                pre = cur;
                cur = cur.next;
            }
            // 删除这个节点
            pre.next = cur.next;
            cur.next = null;
            cur = pre;
        }
        return cur.val;
        
    }
}

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

思路二：使用数组的方法解决

1 将所有的报数都放在一个容器中

2 每一个使用取出下标来删除 (cur + m - 1) 表示要取出来的元素， % len 是为了防止数组溢出（这个 % len是解这道题的关键）

3 返回最后一个数。

public class Solution {
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    public int ysf (int n, int m) {
        // write code here
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= n; i++){
            list.add(i);
        }
        int cur = 0;
        while (list.size() > 1){  // 删到只剩下一个元素
            int len = list.size();
            cur  = (cur + m - 1) % len;
            list.remove(cur);
        }
        return list.get(0);
    }
}

#Java##学习路径#