| Java解决约瑟夫环问题（通俗易懂版） | 您所在的位置：网站首页 › java使用队列解决问题答疑的方法是 › Java解决约瑟夫环问题（通俗易懂版） |
Java解决约瑟夫环问题（通俗易懂版）
|
约瑟夫环问题： 约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1，2，3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列;他的下一个人又从1开始报数，数到m的那个人又出列;依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后 结果+1即为原问题的解。 解法一：利用链表 我们可以把每一个人变成一个链表，然后不断地循环这个链表。每次删除一个结点，直到最终只剩下一个结点的时候就表示我们找到个！ //设计一个结点类 class Node{ int val; Node next; public Node(int val){ this.val = val; } } /** * 循环链表 * @param n 一共有n个人（每个人的编号从0开始到-1） * @param m 每次出去第m个人（每次报数也是从0开始到m-1） * @return */ public int LastRemaining_Solution3(int n, int m) { //这里表示没有人的情况 if(n == 0 || m == 0){ return -1; } //创建一个头结点（将第一个人设置为头） Node head = new Node(0); //把头结点保存一妇女进行循环~ Node temp = head; //然后我们从第二个人开始，不穿创建结点并和之前的节点进行连接 for(int i = 1 ; i //这里还是我们停在需要删除的节点的前一个 if(index == m-2){ //删除该节点 head.next = head.next.next; //同时我们的报数需要清0，重新开始报数 index = 0; } //如果不是要删除的节点那就正常报数 else{ index++; } //每次向后移动一个 head = head.next; } //最终返回剩下的那一个节点的值就好啦~ return head.val; }解法二：迭代 我们先举个例子~假设一共有5个人（n = 5），然后从0开始编号，从0开始报数，报到第2个出列（m = 3），我们来模拟一下这个过程。 0 1 2 3 4 （第一次出队的是2） 3 4 0 1 （第二次出队的是0） 1 3 4 （第三次出队的是4） 1 3 [ 1 3 ]（第四次出队的是1） 3（最终剩余的是3） 我们做这个题的时候只知道最后剩下的一定是一个数，他的下标是0，那我们可以从下往上看，根据下标找到最终的那个数。 所以我们需要看怎么从下面这一层的下标找到这个数在上一层的下标，我们发现当前下标加上m就是我们再上一层的下标，但是这个不一定是真实的下标，因为有可能我们当前的人数是小于m的，所以得到的下标就是一个将人数复制了之后的下标，那么想要得到真实的下标就是进行一个%操作就好，我们知道每次只出队1 个人，那么从后往前的人数分别是0，1，2…所以我们%一下这个人数就得到了真实的下标，然后再一样的办法，得到上一次循环该数的下标，直到到了最开始就知道我们这个最终剩下的人的下标，因为我们最开始的编号是从0开始的，所以回到最初的时候，下标就是编号，直接返回就好了！ 会比0开始的多一个步骤，但是思路完全一样~ |
我们看这个图，红色的是每次要删除的数据，蓝色的是我们的到的下标，绿色的是真实的下标。我们最开始只知道最后一个3的下标是0，然后不断往上一层找，拿到3的下标。 代码：【本文地址】