NC132环形链表的约瑟夫问题
环形链表的约瑟夫问题
http://www.nowcoder.com/questionTerminal/41c399fdb6004b31a6cbb047c641ed8a
题目描述
编号为1到n的n个人围成一圈。从编号为1的人开始报数1,依次下去,报到m的人离开,问最后留下的一个人,编号是多少?
示例1
输入 5,2
返回值 3
约瑟夫问题重在理解,一个是环形循环取出,一个是取出当前元素后,下一个元素从 1 开始报数;
这是唯一一个让我满意的代码,因为没有找到Java自带的单链表,自己写一个也没有必要,其实循环链表本就可以用数组和集合完成,只是数组取出数据不方便,故用集合;
public int ysf (int n, int m) { // write code here List<Integer> children = new ArrayList<>(); for (int i = 1; i <= n; i++) { children.add(i); } int index = 0; while (children.size() > 1) { //注意:此处异地更要让 index 取模,而且取模的对象不是 n,而是实际 list.size(); index = (index + m - 1)%children.size(); children.remove(index ); } return children.get(0); }