文档章节

IT公司100题-18-圆圈中最后剩下的数字

关西大汉弹琵琶
 关西大汉弹琵琶
发布于 2015/12/20 15:55
字数 377
阅读 86
收藏 7

问题描述:

n个数字(下标为0, 1, …, n-1)形成一个圆圈,从数字0开始,每次从这个圆圈中删除第m个数字(当前数字从1开始计数)。当一个数字被删除后,从被删除数字的下一个数字开始计数,继续删除第m个数字。求这个圆圈中剩下的最后一个数字。

 

分析:

这是有名的约瑟夫环问题

最直接的方法:

使用链表来模拟整个删除过程。因为需要n个链表节点,所以空间复杂度为O(n)。每删除一个节点,都需要m次运算,所以时间复杂度为O(mn)。

实现代码如下所示:

package oschina.IT100;

import java.util.Scanner;

/**
 * @project: oschina
 * @filename: IT18.java
 * @version: 0.10
 * @author: JM Han
 * @date: 21:59 2015/12/19
 * @comment: josephus
 * @result:
 */

public class IT18 {
   private static class Node{
      public int no;
      public Node next;
      public Node(int no){
         this.no = no;
      }
   }

   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      System.out.println("Enter the whole number: ");
      int total = sc.nextInt();
      System.out.println("Enter the inter number: ");
      int count = sc.nextInt();
      Node header = new Node(1);
      Node current = header;
      for (int i = 2; i <= total; i++){
         current.next = new Node(i);
         current = current.next;
      }
      //cycle
      current.next = header;
      System.out.println("Below is the sequence of deletion: ");
      while(current.next != current){
         for (int i = 1; i < count; i++){
            current = current.next;
         }
         System.out.println("delete node: " + current.next.no);
         current.next = current.next.next;
      }
      System.out.println("The last node is: " + current.no);


   }
}

代码输出:

Enter the whole number: 
10
Enter the inter number: 
2
Below is the sequence of deletion: 
delete node: 2
delete node: 4
delete node: 6
delete node: 8
delete node: 10
delete node: 3
delete node: 7
delete node: 1
delete node: 9
The last node is: 5



© 著作权归作者所有

关西大汉弹琵琶
粉丝 8
博文 41
码字总数 14221
作品 0
浦东
程序员
私信 提问
剑指offer中的算法题(PHP版)

二维数组中的查找 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该...

Double段
09/29
0
0
【剑指offer纪念版】-- 面试题目录

2.实现Singleton模式 3.二维数组中的查找 4.替换空格 5.从尾到头打印链表 6.重建二叉树 7.用两个栈实现队列 8.旋转数组的最小数字 9.斐波那契数列 【剑指offer纪念版】--9 斐波那契数列 10.二...

细节探索者
01/19
55
0
互联网公司最常见的面试算法题有哪些?

所谓知己知彼,百战不殆,今天就和大家聊聊互联网公司那些最常见的面试算法题。 清点面试算法题之前我们先要明确面试官考察的目的,比如有一道经典考题是“怎么用3升和5升的桶量出4升的水?”...

慕课网官方_运营中心
2018/07/20
0
0
python剑指offer66题

二维数组的查找 替换空格 从头到尾打印链表 重建二叉树 用两个栈实现队列 选择数组中的最小数字 斐波那契数列 跳台阶 变态跳台阶 矩形覆盖 二进制中1的个数 数值的整数次方 调整数组顺序使奇...

lyy0905
2018/06/03
0
0
[CareerCup] 18.6 Smallest One Million Numbers 最小的一百万个数字

18.6 Describe an algorithm to find the smallest one million numbers in one billion numbers. Assume that the computer memory can hold all one billion numbers. 这道题让我们在十亿个......

机器的心脏
2017/12/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

golang-字符串-地址分析

demo package mainimport "fmt"func main() {str := "map.baidu.com"fmt.Println(&str, str)str = str[0:5]fmt.Println(&str, str)str = "abc"fmt.Println(&s......

李琼涛
今天
4
0
Spring Boot WebFlux 增删改查完整实战 demo

03:WebFlux Web CRUD 实践 前言 上一篇基于功能性端点去创建一个简单服务,实现了 Hello 。这一篇用 Spring Boot WebFlux 的注解控制层技术创建一个 CRUD WebFlux 应用,让开发更方便。这里...

泥瓦匠BYSocket
今天
6
0
从0开始学FreeRTOS-(列表与列表项)-3

FreeRTOS列表&列表项的源码解读 第一次看列表与列表项的时候,感觉很像是链表,虽然我自己的链表也不太会,但是就是感觉很像。 在FreeRTOS中,列表与列表项使用得非常多,是FreeRTOS的一个数...

杰杰1号
今天
8
0
Java反射

Java 反射 反射是框架设计的灵魂(使用的前提条件:必须先得到代表的字节码的 Class,Class 类 用于表示.class 文件(字节码)) 一、反射的概述 定义:JAVA 反射机制是在运行状态中,对于任...

zzz1122334
今天
5
0
聊聊nacos的LocalConfigInfoProcessor

序 本文主要研究一下nacos的LocalConfigInfoProcessor LocalConfigInfoProcessor nacos-1.1.3/client/src/main/java/com/alibaba/nacos/client/config/impl/LocalConfigInfoProcessor.java p......

go4it
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部