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);
    }
全部评论

相关推荐

05-16 11:16
已编辑
东华理工大学 Java
牛客73769814...:盲猜几十人小公司,庙小妖风大,咋不叫她去4️⃣呢😁
牛客创作赏金赛
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务