每天一道剑指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 条评论
登录 后参与评论

相关文章

来自专栏SDNLAB

kubernetes三种打开方式

kubernetes是容器管理编排引擎,是继openstack之后又一个优秀的云计算系统。kubernetes有着灵活,快速,健壮等特点,同时全面拥抱微服务架构...

22820
来自专栏Java架构

「BAT面试」搞懂并发编程,轻松应对80%的面试场景

作为一个合格的Java程序员,必须要对并发编程有一个深层次的了解,在很多互联网企业都会重点考察这一块。可能很多工作3年以上的Java程序员对于这一领域几乎没有太...

11120
来自专栏A周立SpringCloud

译:在 Spring Boot 中使用 Spring AOP 和 AspectJ 来测量方法的执行时间

原文链接:https://dzone.com/articles/logging-average-method-execution-times-via-aspec...

31810
来自专栏MixLab科技+设计实验室

像写作一样去写代码,如何把异步的形式改写成同步的形式

写代码的时候,碰到一大堆的缩进、花括号是不是特别头疼?为什么会有这么多的标点符号,还有各种技术概念?能不能像写作一样,自由得书写?从形式上,代码比文章多的是格式...

14310
来自专栏Java技术栈

Java 11 已发布,String 还能这样玩!

在文章《Java 11 正式发布,这 8 个逆天新特性教你写出更牛逼的代码》中,我有介绍到 Java 11 的八个新特性,其中关于 String 加强部分,我觉...

8820
来自专栏赵俊的Java专栏

LeetCode 299 Bulls and Cows

刚开始我的想法是依次获取公牛和奶牛的数量, 但奶牛的判断需要 O(n^2) 的时间复杂度, 后面想到, 用所有匹配的数量 - 公牛的数量就是奶牛的数量, 只需要...

16440
来自专栏计算机编程

ionic4 -- 修改tabs图标

官方命令为我们创建好了代码,这里不难发现,tabs分为两大部分: 第一大部分:ion-tab: 这里是路由器,存放页面跳转路由用,此部分的tab作为标签,对...

42020
来自专栏Java技术栈

Hashtable 为什么不叫 HashTable?

前几天在写《HashMap 和 Hashtable 的 6 个区别》这篇文章的时候,差点把 Hashtable 写成了 HashTable,后来看源码证实了是:...

10530
来自专栏JavaEE

Java8 新特性

北京时间2018年9月26日,Oracle官方发布Java 11。既然版本都更新到11了,现在才来学8是不是太晚了?其实不是的,目前应该大部分都还是使用的Jav...

1.5K30
来自专栏一枝花算不算浪漫

【转】Java并发的AQS原理详解

每一个 Java 的高级程序员在体验过多线程程序开发之后,都需要问自己一个问题,Java 内置的锁是如何实现的?最常用的最简单的锁要数 ReentrantL...

19610

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励