剑指 Offer 62. 圆圈中最后剩下的数字 + 约瑟夫环问题
2024-10-19 13:31:53
剑指 Offer 62. 圆圈中最后剩下的数字
Offer_62
题目描述
方法一:使用链表模拟
- 这种方法是暴力方法,时间复杂度为O(nm),在本题中数据量过大会超时。
方法二:递归方法
package com.walegarrett.offer;
/**
* @Author WaleGarrett
* @Date 2021/2/13 12:17
*/
/**
* 题目详情:0,1,···,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字(删除后从下一个数字开始计数)。
* 求出这个圆圈里剩下的最后一个数字。
* 例如,0、1、2、3、4这5个数字组成一个圆圈,从数字0开始每次删除第3个数字,则删除的前4个数字依次是2、0、4、1,因此最后剩下的数字是3。
*/
/**
* 方法一:递归求解
*/
public class Offer_62 {
public int lastRemaining(int n, int m) {
return dfs(n,m);
}
int dfs(int n, int m){
if(n==1)
return 0;
int x = dfs(n-1, m);
return (m+x)%n;
}
}
方法三:数学迭代方法
/**
* 方法二:使用迭代
*/
class Offer_62_2 {
public int lastRemaining(int n, int m) {
int f=0;
for(int i=2;i!=n+1;i++){
f=(m+f)%i;
}
return f;
}
}
最新文章
- redis键命令
- Mint Linux 安装 DotnetCore 遭遇无法修正错误,因为您要求某些软件包保持现状,就是它们破坏了软件包间的依赖关系
- 大数据组件原理总结-Hadoop、Hbase、Kafka、Zookeeper、Spark
- Visual Studio 中 UNICODE 宏的设置
- BZOJ 4551 树
- Java虚拟机学习 - 体系结构 内存模型
- Android Bitmap圆角
- MVC 视频笔记
- JAVA —— 数组
- 1642: [Usaco2007 Nov]Milking Time 挤奶时间
- linux修改root账户的用户名所得的教训
- trunk端口配置错误导致环路
- redis学习(四)——Hash数据类型
- db2 tablespaces table bufferpools reorgs
- ES6之字符串扩展
- 呼叫中心获取sip数据报文
- GUN WINDOW 工具
- ZTree id值太大,ZTree没有生成树,ZTree的id值过大
- ansible 删除路径下的多个文件[收集的参考]
- Python基本知识3----序列
热门文章
- cf-1230C Anadi and Domino
- POJ 3281 Dining(最大流板子)
- hdu5358 First One
- 主席树 【权值线段树】 &;&; 例题K-th Number POJ - 2104
- keras fit_generator 并行
- 数据库之ODPS中sql语句指南
- ubuntu 16.04 i386 安装 ruby + bundler + rails ; 搭建简单的网站bitbar
- python3 anaconda 安装pyhook3 pythoncom(pywin32)
- 图解算法——链表中倒数第k个节点
- RT-Thread学习笔记1-启动顺序与线程创建