47.环形链表的约瑟夫问题

47.环形链表的约瑟夫问题

题目描述

编号为1到n的n个人围成一圈。从编号为1的人开始报数1,依次下去,报到m的人离开,问最后留下的一个人,编号是多少?

输入

5,2 

返回值

3 

分析

  1. 最终剩下一个人时的安全位置肯定为1,反推安全位置在人数为n时的编号
    人数为1: 0+1
    人数为2: (0+m) % 2+1
    人数为3: ((0+m) % 2 + m) % 3+1
    人数为4: (((0+m) % 2 + m) % 3 + m) % 4+1

代码实现

import java.util.*;               public class Solution {         /**          *           * @param n int整型           * @param m int整型           * @return int整型          */         public int ysf (int n, int m) {     	     if(n<1||m<1) {     	    	 return 0;     	     }     	     if(n==1) {     	    	 return 1;     	     }     	     else     	    	 return (ysf(n-1,m)+m-1)%n+1;     		      	    }     } 

版权声明:玥玥 发表于 2021-03-30 10:32:38。
转载请注明:47.环形链表的约瑟夫问题 | 女黑客导航