专栏首页Java那些事每天一道剑指offer-孩子们的游戏(圆圈中最后剩下的数)

每天一道剑指offer-孩子们的游戏(圆圈中最后剩下的数)

考试结束,班级平均分只拿到了年级第二,班主任于是问道:大家都知道世界第一高峰珠穆朗玛峰,有人知道世界第二高峰是什么吗?正当班主任要继续发话,只听到角落默默响起来一个声音:”乔戈里峰

题目

每天一道剑指offer-孩子们的游戏(圆圈中最后剩下的数) https://www.nowcoder.com/practice/f78a359491e64a50bce2d89cff857eb6?tpId=13&tqId=11199&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目详述

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢?(注:小朋友的编号是从0到n-1)

题目详解

思路

Java实现的话,可以使用LinkedList,考虑删除节点的效率。模拟游戏过程即可:其实这是个约瑟夫环问题,但是绝对没必要去死记硬背数学公式,直接用链表模拟游戏过程即可。

代码

import java.util.*;
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        LinkedList<Integer> list = new LinkedList<>();
        for(int i=0;i<n;i++)
            list.add(i);
        int a = 0;
        while(list.size() > 1)
        {
            a = (a+m-1) % list.size();
            list.remove(a);//每次删除,直到留下最后的那一个!
        }
        if(list.size() == 1)
            return list.get(0);//数组只剩下最后的一个
        return -1;
    }
}

结束语

作者乔戈里亲历2019秋招,哈工大计算机本硕,百度java工程师,欢迎大家关注我的微信公众号:程序员乔戈里,公众号有3T编程资源,以及我和我朋友(百度C++工程师)在秋招期间整理的近200M的面试必考的java与C++面经,并有每天一道leetcode打卡群与技术交流群,欢迎关注。

本文分享自微信公众号 - 程序员乔戈里(CXYqiaogeli)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-01-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 每天一道leetcode-107-二叉树的层次遍历 II

    给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历) 例如: 给定二叉树 [3,9,20,null,nu...

    乔戈里
  • 漫话:如何给女朋友解释什么是负载均衡

    周末晚上,和女朋友去电影院,准备看晚上的DC的海底动作冒险电影——海王。在入口处,人很多,有几个引导人员时不时的指挥观众从不同的入口进入影院内。我们站在队伍的尾...

    乔戈里
  • 每天一道剑指offer-滑动窗口的最大值

    给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,...

    乔戈里
  • ZOJ 3620 Escape Time II

    题意:      从初始房间到达终止房间需要经过一系列的房间,没经过一个房间会得到一个价值,从一个房间到达另一个房间同时需要消耗一定的时间,在规定的时间内从初始...

    用户1624346
  • Asp.Net Web API 2第十一课——在Web API中使用Dependency Resolver

    阅读本文之前,您也可以到Asp.Net Web API 2 系列导航进行查看 http://www.cnblogs.com/aehyok/p/3446289.h...

    aehyok
  • 数据分析方法论-统计学内容学习

    最初学习数据分析只是出于兴趣,自学了Python。最近才生出转行数据分析的想法,目前已经辞职,准备全身心地投入到学习中。

    带萝卜
  • Eureka集群

    Eureka 作为注册中心,保存了系统服务的相关信息,如果注册中心挂掉,那么系统就瘫痪了。因此,对 Eureka 做集群实现高可用是必不可少的。

    崔笑颜
  • 如何优雅做系统错误提示?

    不知道你有没有过这样的感受,当你使用软件遇到异常的时候,有时候软件给出的错误提示让人摸不着头脑。唯一的办法就是复制到搜索引擎搜一下,看看有没有哪个不幸的人与我遇...

    Zachary_ZF
  • 给一台腾讯云服务器配上多个免费外网弹性IP

    https://cloud.tencent.com/document/product/213/15379#.E7.BD.91.E5.8D.A1.E7.9B.B8...

    Cong Min
  • python “目录服务不能在一个对象的RDN 属性上执行该请求的操作”

    今天使用Python的第三方库pyad在AD中修改部门(OU)的信息,通过ou.update更新部门属性,想要改部门的名字(Name),这是报错:“目录服务不能...

    BigYoung小站

扫码关注云+社区

领取腾讯云代金券