编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。
下一个人继续从 1 开始报数。
n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？
数据范围： 
进阶：空间复杂度 )
，时间复杂度 )
[编程题]环形链表的约瑟夫问题
public int ysf (int n, int m) {
// write code here
ListNode p1=new ListNode(1) ,p2=p1;
for(int i=2;i<=n;i++){
p2.next=new ListNode(i);
p2=p2.next;
}
p2.next=p1;
while(p2.next!=p2){
for(int i=1;i<m;i++){
p2=p2.next;
}
p2.next=p2.next.next;
}
return p2.val;
}
编辑于 2024-03-09 16:36:49
回复(0)
使用数组莫名其妙抛出下表超限异常，干脆自己写了个双向链表，做个模拟，当然时间复杂度和空间爱你复杂度肯定是不满足进阶需求的：
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型
* @param m int整型
* @return int整型
*/
class AAAA {
int i;
int index;
AAAA next;
AAAA pri;
public AAAA(int i, int index) {
this.i = i;
this.index = index;
}
};
public int ysf (int n, int m) {
// write code here
AAAA head = new AAAA(1, 1);
AAAA quene = head;
for (int i = 2; i <= n; i++) {
AAAA p = new AAAA(i % m, i);
quene.next = p;
p.pri = quene;
quene = p;
System.out.println("i:" + i + " " + quene.index + " " + quene.i);
}
quene.next = head;
head.pri = quene;
quene = head;
while (true) {
if (quene.i == m) {
quene.pri.next = quene.next;
quene.next.pri = quene.pri;
quene = quene.next;
quene.i = 1;
} else {
quene = quene.next;
quene.i = quene.pri.i + 1;
}
if (quene.next.index == quene.index) {
break;
}
}
return quene.index;
}
}
发表于 2023-08-18 19:04:48
回复(0)
import java.util.*;
public class Solution {
/**
*
* @param n int整型
* @param m int整型
* @return int整型
*/
public int ysf (int n, int m) {
// write code here
//队列来模拟环
Queue<Integer> queue=new LinkedList<>();
//入队
for(int i=1;i<=n;i++){
queue.add(i);
}
//标记，用来出队
int flag=1;
while(queue.size()>1){
//报号到m则出队
if(flag==m){
queue.poll();
flag=0;
//否则添加到队尾模拟环
}else{
queue.add(queue.poll());
}
flag++;
}
//最后一个人出队
return queue.poll();
}
}
发表于 2023-05-14 16:11:26
回复(0)
public int ysf (int n, int m) {
// write code here
// 1. 永远考虑第一个数的人为1号位
// 2. 考虑f(n, m)和f(n-1, m)的转换关系
// 3. 假设第
int ans = 0;
for(int i = 2; i <= n; ++i) {
ans = (ans + m) % i;
}
return ans + 1;
} 1. 永远考虑第一个数的人为1号位
2. 考虑f(n, m)和f(n-1, m)的dp转换关系
3. 由于第一个出局的人是m号位，所以f(n-1, m)的1号位在f(n, m)中是m+1号位
4. 假设f(n-1, m)的安全位置是x，那么在f(n, m)中的安全位置是(x+m)%n号位
5. f(1, m)的安全位置永远是1号位
总结：
1. 递归关系：ysf(n, m) = n == 1 ? 1 : (ysf(n-1, m) + m) %n
2. 递推关系：ans = (ans + m) % n，n从2开始递推
发表于 2022-01-11 16:59:15
回复(0)
stack over
import java.util.*;
public class Solution {
/**
*
* @param n int整型
* @param m int整型
* @return int整型
*/
public int ysf (int n, int m) {
return lastRemaining(n,m)+1;
}
public int lastRemaining(int n, int m) {
if(n==1) return 0;
int x=lastRemaining(n-1,m);//0->x 移动了x个
int val=m%n;
return (x+val)%n;
}
}
发表于 2021-12-26 11:12:05
回复(0)
public class Solution {
/**
*
* @param n int整型
* @param m int整型
* @return int整型
*/
public int ysf (int n, int m) {
// write code here
// write code here
LinkedList<Integer> list = new LinkedList<>();
for(int i=1;i<=n;i++){
list.add(i);
}
Integer i=0,j= 0;
while(!list.isEmpty()){
i = list.removeFirst();
j++;
if(j%m==0){
j=0;
}else{
list.addLast(i);
}
}
return i;
}
}
发表于 2021-12-21 21:50:29
回复(0)
import java.util.*;
public class Solution {
/**
*
* @param n int整型
* @param m int整型
* @return int整型
*/
public int ysf (int n, int m) {
// write code here
if(n == 1 && m == 1){
return 1;
}
LinkedList<Integer> list = new LinkedList<>();
for( int i = 1; i <= n; i++){
list.add(i);
}
int start = 0;
int del = 0;
while(list.size() != 1){
// 找到要移除的位置
del = (start + m -1) % list.size();
start = del; //新的报数起点
list.remove(del);
}
return list.get(0);
}
}
发表于 2021-12-18 12:07:20
回复(0)
import java.util.*;
public class Solution {
/**
*
* @param n int整型
* @param m int整型
* @return int整型
*/
public int ysf (int n, int m) {
// 循环链表
if (n == 0) return 0;
// 虚拟头节点
ListNode head = new ListNode(-1);
ListNode pre = head;
for (int i = 1; i <= n; ++ i){
pre.next = new ListNode(i);
pre = pre.next;
}
pre.next = head.next;
int count = 0;
pre = head;
ListNode cur = pre.next;
while (cur != cur.next){
++ count;
if (count == m){
pre.next = cur.next;
count = 0;
} else {
pre = pre.next;
}
cur = pre.next;
}
return cur.val;
}
}
发表于 2021-12-16 15:10:41
回复(0)
import java.util.*;
public class Solution {
/**
*
* @param n int整型
* @param m int整型
* @return int整型
*/
public int ysf (int n, int m) {
// write code here
List<Integer> list = new ArrayList<>();
for (int i = 0; i <= n; i++) {
list.add(i);
}
int i = 0;
while (list.size() > 2){
i = (i + m) % (list.size()-1) == 0 ? (list.size() -1) : (i + m) % (list.size()-1);
list.remove(i--);
if(i == 0) i = list.size()-1;
}
return list.get(1);
}
}
发表于 2021-09-04 21:21:46
回复(0)
public class Solution {
/**
* @param n int整型
* @param m int整型
* @return int整型
*/
class ListNode{
int val;
ListNode next;
ListNode(int val){
this.val = val;
}
}
public int ysf (int n, int m) {
// write code here
ListNode head = new ListNode(1);
ListNode p = head;
for(int i = 2; i <= n; i++){
ListNode temp = new ListNode(i);
p.next = temp;
p = temp;
}
p.next = head;
p = head;
int cnt = 1;
while(p.next != p){
if(cnt == m){
ListNode rec = p.next;
ListNode q = p;
while(q.next != p){
q = q.next;
}
q.next = p.next;
p = rec;
cnt = 1;
}else{
p = p.next;
cnt++;
}
}
return p.val;
}
}
/**
* @param n int整型
* @param m int整型
* @return int整型
*/
class ListNode{
int val;
ListNode next;
ListNode(int val){
this.val = val;
}
}
public int ysf (int n, int m) {
// write code here
ListNode head = new ListNode(1);
ListNode p = head;
for(int i = 2; i <= n; i++){
ListNode temp = new ListNode(i);
p.next = temp;
p = temp;
}
p.next = head;
p = head;
int cnt = 1;
while(p.next != p){
if(cnt == m){
ListNode rec = p.next;
ListNode q = p;
while(q.next != p){
q = q.next;
}
q.next = p.next;
p = rec;
cnt = 1;
}else{
p = p.next;
cnt++;
}
}
return p.val;
}
}
发表于 2021-08-22 21:32:43
回复(0)
方法一：递归
public class Solution {
public int ysf (int n, int m) {
return joseph(n, m) + 1; // 结果加1，因为人的编号从 1 到 n。Caution!!!
}
// 套用人的编号从 0 到 (n - 1) 的代码
public int joseph(int n, int m) {
if (n == 1) return 0;
return (joseph(n - 1, m) + m) % n;
}
} 方法二：自建环形链表
public class Solution {
// 链表的节点
private static class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
public int ysf (int n, int m) {
// 建立环形链表
ListNode front = new ListNode(-1); // 头节点
ListNode rear = front; // 尾指针
for (int i = 1; i <= n; i++) {
ListNode node = new ListNode(i);
rear.next = node;
rear = node; // 尾插法建立链表
}
rear.next = front.next; // 建立环形链表
int size = n; // 环形链表节点的个数
ListNode prev = front;
ListNode curr = front.next;
while (size != 1) {
for (int i = 0; i < m - 1; i++) {
prev = prev.next;
curr = curr.next; // 走 (m - 1) 步
}
ListNode nextNode = curr.next;
prev.next = nextNode; // 删除curr指向的节点
curr = nextNode; // 更新curr
size--;
}
return curr.val; // 此时prev和curr都指向最后一个节点，所以返回prev.val也可以
}
}
发表于 2021-08-17 01:54:47
回复(0)
import java.util.*;
public class Solution {
/**
*
* @param n int整型
* @param m int整型
* @return int整型
*/
public int ysf (int n, int m) {
ListNode head = new ListNode(1);
ListNode p = head;
//创建一个循环链表
for(int i = 2; i <= n; i++){
ListNode node = new ListNode(i);
p.next = node;
node.next = head;
p = node;
}
ListNode pre = new ListNode(-1);
pre.next = head;
p = head;
int k = 0;
//按间隔删除节点
while(k < n-1){
for(int i = 1; i< m; i++){
pre = pre.next;
p = pre.next;
}
pre.next = p.next;
p.next = null;
k ++;
}
return pre.val;
}
}
class ListNode{
int val;
ListNode next;
public ListNode(){}
public ListNode(int val){
this.val = val;
}
}
发表于 2021-08-14 10:13:18
回复(0)
import java.util.*;
public class Solution {
/**
*
* @param n int整型
* @param m int整型
* @return int整型
*/
public int ysf (int n, int m) {
// write code here
ArrayList<Integer> arr = new ArrayList();
for(int i = 1;i<=n;i++){
arr.add(i);
}
//i为下标
int i = -1;
//j为计数器
int j = 0;
while(arr.size()!=1){
i++;
if(i>arr.size()-1){
i = 0;
}
j++;
if(j==m){
arr.remove(i);
j=0;
i = i-1;
}
}
return arr.get(0);
}
}
public class Solution {
/**
*
* @param n int整型
* @param m int整型
* @return int整型
*/
public int ysf (int n, int m) {
// write code here
ArrayList<Integer> arr = new ArrayList();
for(int i = 1;i<=n;i++){
arr.add(i);
}
//i为下标
int i = -1;
//j为计数器
int j = 0;
while(arr.size()!=1){
i++;
if(i>arr.size()-1){
i = 0;
}
j++;
if(j==m){
arr.remove(i);
j=0;
i = i-1;
}
}
return arr.get(0);
}
}
发表于 2021-08-11 21:53:57
回复(0)
同样的代码 python会超时 哭了
import java.util.*;
public class Solution {
public int ysf (int n, int m) {
// 一个人或者m为1时
if(n < 2 && m == 1){
return n;
}
// 组成环型链表
ListNode head = new ListNode(1);
ListNode tail = head;
for(int i=2; i<=n; i++){
tail.next = new ListNode(i);
tail = tail.next;
}
tail.next = head;
int count = 0;
while(tail != tail.next){
// 报数
count++;
// 幸运儿
if(count == m){
count = 0;
// 记录位置
head = tail;
// 删除目标结点
tail.next = tail.next.next;
// 返回位置
tail = head;
continue;
}
tail = tail.next;
}
return tail.val;
}
}
发表于 2021-08-02 14:09:53
回复(0)
import java.util.*;
// 暴力法
public class Solution {
public int ysf (int n, int m) {
List<Integer> list = new ArrayList<>();
for(int i=0; i<n; i++)
list.add(i+1);
int lastCurr = 0;
while(list.size()>1) {
n = list.size();
list.remove((lastCurr+m-1)%n);
lastCurr = (lastCurr+m-1)%n;
}
return list.get(0);
}
}
发表于 2021-07-29 17:26:28
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
