约瑟夫环问题的2种解法

不废话，直接上题目：

有2种解法（这里把他抽象出来，有n个人，报数到m就去除在外）

• 一种是模拟。 可用数组模拟，也可用循环链表模拟。
• 还有一种是 找规律。

找规律

先来看找规律的吧，模拟的后面直接贴代码了。

先来想一个问题，报数到m的人就去除，一直重复下去，这个算不算是一种规律😂。。。
如果有规律的话，我们通过和题目有关的 n、m2个数据，进行一些运算，就可以得出最后留下来的是哪个编号了。。。

目前确定的只有1种情况，就是如果只有一个人的话，不用报数，他直接留下来。

再来看看如果2个人的情况呢、3个人的情况呢、4个人、5个人、…… n-1个人、n个人的情况呢。（当然这后面都与要报的数是多少有关了，我们暂且先不管这个）
把这些情况都抽象出来，我们能不能找到 i 个人的情况 和 i-1 个人的情况，这时候留下来的编号是多少（这个结果肯定是带有m这个未知数的），找出他们这样相邻之间的关系？

用图解的方式说明吧：

主要难点就是在找规律，这个也是已经得到答案后，倒推出来的，想了大半天。。。
接下来就直接上代码吧。。。

/** * 找出规律，用递归解决 */
public class JosephusProblem {
   

    public static int getLive(int n, int m) {
   
        if (n == 1) {
   
            return 1;
        }
        return (getLive(n - 1, m) + (m - 1) % n) % n + 1;
    }

    public static void main(String[] args) {
   
        // 报1就去除，留下的总是最后一个。
        for (int i = 1; i <= 10; i++) {
   
            System.out.println(getLive(i, 1));
        }
        System.out.println("====================");

        // 报3去除
        for (int i = 1; i <= 10; i++) {
   
            System.out.println(i + "个人，留下来的是：" + getLive(i, 3));
        }
    }
}

数组模拟：

模拟的，（没什么好说的，思路都在代码里了。。。）

/** * 用数组模拟解决， 1表示该位置有人，0表示该位置没人。 */
public class JosephusProblemByArray {
   

    /** * 数组中，是不是 只剩下了 一个1元素，其他都是0元素。 */
    public static boolean isSoleOne(int[] people) {
   
        int oneNumber = people.length;
        for (int i = 0; i < people.length; i++) {
   
            if (people[i] == 0) {
   
                oneNumber--;
            }
        }
        return oneNumber == 1;
    }

    /** * 找到数组中 ， 第一个为 1 的下标。 */
    public static int firstOne(int[] people) {
   
        for (int i = 0; i < people.length; i++) {
   
            if (people[i] == 1) {
   
                return i;
            }
        }

        // 不可能进到这种情况，随便写了个数字
        return -1;
    }

    /** * 当前下标为 index， 这个位置是不是 数组中的最后一个为 1 的下标。（不循环来看的） */
    public static boolean isEndOne(int[] people, int index) {
   
        if (index == people.length - 1) {
   
            return true;
        }
        for (int i = index + 1; i < people.length; i++) {
   
            if (people[i] == 1) {
   
                return false;
            }
        }
        return true;
    }

    /** * 当前下标为 index，寻找数组中下一个为1的下标。 */
    public static int nextOne(int[] people, int index) {
   
        if (isEndOne(people, index)) {
   
            return firstOne(people);
        }

        for (int i = index + 1; i < people.length; i++) {
   
            if (people[i] == 1) {
   
                return i;
            }
        }

        // 不可能进到这种情况，随便写了个数字
        return -1;
    }

    /** * 用数组模拟所有人都情况：（初始时，所有元素都为 1） * 1：表示有人。 * 0：表示没人。 * * 返回 剩下一个人的序号。（从1开始计数的。） */
    public static int process(int[] people) {
   
        int number = 1;     // 报数的 数字。
        int index = 0;      // 数组中的下标 数字。

        // 只要不是剩最后一个1元素，就一直进行报数循环。
        while (!isSoleOne(people)) {
   
            if (number == 1) {
   
                number++;
            } else if (number == 2){
   
                number++;
            } else if (number == 3) {
   
                people[index] = 0;
                number = 1;
            }

            index = nextOne(people, index);

        }

        // 只剩下了最后一个1元素，找到他的下标。
        // 因为需要的是从1计数的，所以返回下标+1即可。
        for (int i = 0; i < people.length; i++) {
   
            if (people[i] == 1) {
   
                return i+1;
            }
        }

        // 不可能进到这种情况，随便写了个数字
        return -1;
    }

    public static void main(String[] args) {
   

        int[] people = new int[7];      // 7个人的最后结果是4
        Arrays.fill(people, 1);    // 对数组中的所有元素，初始时，都有人，填充为1.
        int resultIndex = process(people);
        System.out.println(resultIndex);        // 4

    }


}

链表模拟

/** * 用链表模拟解决。（是一个循环链表） */
public class JosephusProblemByList {
   
    // 内部类，节点的定义。
    private static class Node{
   
        int value;
        Node next;

        public Node(int value) {
   
            this.value = value;
            this.next = null;
        }

        // 一定不能重写 toString，否则会 栈溢出异常。
    }


    /** * @param head 循环链表的头节点 * @param m 报数到m就出局 * @return 最后留下来的节点。 */
    public static Node getLiveNode(Node head, int m) {
   
        // 传入的参数不符合实际，直接返回null。
        if (head == null || m < 1 || head.next == null) {
   
            return null;
        }

        // 找到 链表中的最后一个节点last
        Node last = head;
        while (last.next != head) {
   
            last = last.next;
        }

        // 模拟操作，需要用到 第一个、最后一个节点 来维护循环链表的结构。
        // 只剩下一个节点的时候就停止。
        int count = 0;      // 记录报数的变化
        while (last != head) {
   
            count++;
            if (count == m) {
         // 报数为m的节点，就去除掉了。
                last.next = head.next;
                head = last.next;
                count = 0;  // 重置记录报数的变量
            } else {
   
                // 其他的报数情况，平安的节点。
                // 只要把 last、head变量往下移动一位即可。维护链表。
                last = last.next;
                head = last.next;
            }
        }


        // 返回仅剩的最后一个节点。
        return head;
    }

    public static void main(String[] args) {
   
        // 测试用例1： 7个节点的循环链表，最后留下来的是 4节点。
        Node node = new Node(1);
        node.next = new Node(2);
        node.next.next = new Node(3);
        node.next.next.next = new Node(4);
        node.next.next.next.next = new Node(5);
        node.next.next.next.next.next = new Node(6);
        node.next.next.next.next.next.next = new Node(7);

        System.out.println(getLiveNode(node, 3).value);     // 4

    }
}