剑指Offer-46.孩子们的游戏(圆圈中最后剩下的数)(C++/Java)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了剑指Offer-46.孩子们的游戏(圆圈中最后剩下的数)(C++/Java),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1877字,纯文字阅读大概需要3分钟。
内容图文
![剑指Offer-46.孩子们的游戏(圆圈中最后剩下的数)(C++/Java)](/upload/InfoBanner/zyjiaocheng/649/dea8b084cad745fa8fd975f6407a8ed5.jpg)
题目:
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢?(注:小朋友的编号是从0到n-1) ? 如果没有小朋友,请返回-1分析:
最先想到的就是利用队列,将小朋友序号添加进队列中,然后每由队首的开始报数,出队,再添加进队尾。当报数m-1时,队首的那个序号直接出队,不再进入队尾,继续执行直到队列中剩下一个序号,这个就是最后的答案。
看了下书,有一种利用推导求得答案的方法,就是删除的序号假如为k,实际上k=(m-1)%n,因为下一轮报数开始从k+1这个序号开始,将k+1...n-1,0,1,...k-1映射到0,1,2,...,n-2再利用k=(m-1)%n求得下一轮删除的序号,实际上也就是将最后剩下的那个序号当成0,反推回n个人时,为多少。
程序:
C++
//use queue class Solution { public: int LastRemaining_Solution(int n, int m) { if(n < 1 || m < 0) return -1; queue<int> q; for(int i = 0; i < n; i++) q.push(i); int num = 0; while(num < m){ if(q.size() == 1) return q.front(); if(num == m-1){ q.pop(); num = 0; } else{ auto temp = q.front(); q.pop(); q.push(temp); num++; } } } };
//f(n,m) =(f(n-1,m)+m) %n class Solution { public: int LastRemaining_Solution(int n, int m) { if(m < 0 || n < 1) return -1; if(n == 1) return 0; return (LastRemaining_Solution(n-1, m) + m) % n; } };
Java
//use ArrayList import java.util.*; public class Solution { public static int LastRemaining_Solution(int n, int m) { if(n < 1 || m < 0) return -1; ArrayList<Integer> list = new ArrayList<>(); for(int i = 0; i < n; i++) list.add(i); int index = 0; while(list.size() > 1) { index = (index + m - 1) % list.size(); list.remove(index); } return list.get(0); } }
内容总结
以上是互联网集市为您收集整理的剑指Offer-46.孩子们的游戏(圆圈中最后剩下的数)(C++/Java)全部内容,希望文章能够帮你解决剑指Offer-46.孩子们的游戏(圆圈中最后剩下的数)(C++/Java)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。