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);
}