剑指46-孩子们的游戏
2023-02-18 16:41:12 时间
数组、取余
题目描述
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢?(注:小朋友的编号是从0到n-1)
如果没有小朋友,请返回-1
题目很复杂,大概意思就是一个循环链表,每次取第m个删除,然后从下一位继续取第m个删除,直到只剩最后一个元素
解法
这个题很像循环链表,但是我觉得用循环链表做未免太麻烦了点,我直接用数组计算
#include<vector>
using namespace std;
class Solution {
public:
int LastRemaining_Solution(int n, int m)
{
if (n <= 0 || m <= 0) return -1;
vector<int> res(n);
int i = 0;
for (int i = 0; i < n; i++)
res[i] = i;
int index;
while (res.size() != 1)
{
int len = res.size();
index = (index + m - 1) % len; //关键计算点
res.erase(res.begin() + index);
}
return res[0];
}
};
相关文章
- JAVA只要掌握内部类,多继承和单继承都不是问题
- 今儿直白的用盖房子为例,给你讲讲Java建造者模式
- 用实例带你深入理解Java内存模型
- 你知道,java项目中是如何获取文件地址的吗?
- 【架构师(第十五篇)】脚手架之创建项目模板开发
- 【架构师(第十六篇)】脚手架之创建项目模板的下载与更新
- 【架构师(第十八篇)】脚手架之项目模板的安装
- 【架构师(第十九篇)】脚手架之组件库模板开发
- 【架构师(第二十篇)】脚手架之自定义模板及第一阶段总结
- 【架构师(第二十一篇)】编辑器开发之需求分析和架构设计
- 【架构师(第二十二篇)】编辑器开发之项目整体搭建
- 【架构师(第二十三篇)】编辑器开发之画布区域组件的渲染
- 【架构师(第二十四篇)】编辑器开发之添加模版到画布
- Java异常处理:如何写出“正确”但被编译器认为有语法错误的程序
- 我以订披萨为例,给女朋友详细讲了Java设计模式的3种工厂模式
- 【架构师(第二十五篇)】编辑器开发之属性编辑区域表单渲染
- 【架构师(第二十六篇)】编辑器开发之属性编辑同步渲染
- 2021年度“CCF-腾讯犀牛鸟基金”发布结题评优结果
- 【架构师(第二十七篇)】前端单元测试框架 Jest 基础知识入门
- 太空噗|重燃太空热潮!与噗噗星人一同探索星海浪漫