- 使用 Spring Initializr 创建 Spring Boot 应用程序
- 在Spring Boot中配置Cassandra
- 在 Spring Boot 上配置 Tomcat 连接池
- 将Camel消息路由到嵌入WildFly的Artemis上
Josephu (约瑟夫,约瑟夫环) 问题,是一个计算机科学和数学中的问题,在计算机编程的算法中,类似问题又称为约瑟夫环,又称 “丢手绢问题”。
据说著名犹太历史学家Josephus有过以下的故事
在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。
问题是,给定了和,一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。
故事讲完了,在我们现实开发人员中如何使用单向环形链表解决这类问题呢?我们往下看!
假设编号为1,2,3,…n的n个犹太人围坐一圈,约定编号为k(1<=k<=n)的人从1开始报数,数到m的那个人出列,它的下一位又从1开始报数,数到m的那个人又出列,依此类推。直到所有人出列为止,由此产生出一个出队编号的序列。
出队列的顺序
首先从1开始报数,数两下2号出队列2号出队列后,这个环状节点就没有了。1号就会重新指向3号,由3号重新开始报数,3号数两下后4号出列。3号指向5号重新报数。5号报两下后1号出队列。1号出队列5号指向3号仍然是个环状。3号开始报数,报两下后5号出队列,5号走后场上就剩下3号,它自已指向自已依然是个环状,报数两下后也最终出了队列,最后得到的顺序为 2->4->1->5->3
。
构建一个单向的环形链表思路
遍历环形链表
创建一个Boy类,表示一个节点
class Boy{
//编号
private int no;
//指向下一个节点,默认null
private Boy next;
public Boy(int no){
this.no = no;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public Boy getNext() {
return next;
}
public void setNext(Boy next) {
this.next = next;
}
}
创建一个环形的单向链表并编写添加(add),遍历(show)方法
class CircleSingleLinkdList{
//创建一个first节点,当前没有编号
private Boy first =null;
//添加小孩节点,构建成一个环形的链表
public void addBoy(int nums){
//nums 做一个数据校验
if (nums < 1){
System.out.println("nums的值不正确!");
return; //直接结束
}
Boy curBoy = null; //辅助指针,帮助构建环形链表
//使用for来创建我们的环形链表
for (int i=1;i<=nums;i++){
//根据编号,创建小孩节点
Boy boy =new Boy(i);
//如果是第一个小孩
if (i == 1){
first = boy;
first.setNext(first); //构成环
curBoy = first; //让curBoy指向第一个小孩
}else {
curBoy.setNext(boy);
boy.setNext(first);
curBoy = boy;
}
}
}
//遍历当前的环形链表
public void showBoy(){
//判断链表是否为空
if (first == null){
System.out.println("没有任何小孩~");
return;
}
//因为first不能动,因此我们仍然使用一个辅助指针完成遍历
Boy curBoy = first;
while (true){
System.out.printf("小孩的编号 %d \n",curBoy.getNo());
if (curBoy.getNext() == first){ //说明已经遍历完毕
break;
}
curBoy = curBoy.getNext(); //curBoy后移
}
}
}
/**
* @author mengzhichao
* @create 2022-04-09-16:14
*/
public class Josephu {
public static void main(String[] args) {
CircleSingleLinkdList circleSingleLinkdList =new CircleSingleLinkdList();
circleSingleLinkdList.addBoy(5);//加入5个小孩节点
circleSingleLinkdList.showBoy();
}
}
出队思路
在CircleSingleLinkdList类中新增countBoy方法 根据用户的输入,计算小孩的出圈顺序。
/***
*
* @param startNo 表示从第几个小孩开始数数
* @param countNum 表示数几下
* @param nums 表示最初有多少个小孩在圈中
*/
public void countBoy(int startNo,int countNum,int nums){
//参数校验
if (first == null || startNo < 1 || startNo > nums){
System.out.println("参数输入有误!");
return;
}
//创建一个辅助指针,帮助完成小孩出圈
Boy helper = first;
//需要创建一个辅助指针(变量)helper,事先应该指向环形链表的最后这个节点。
while (true){
if (helper.getNext() == first){ //说明helper指向最后小孩节点
break;
}
helper = helper.getNext();
}
//小孩报数前,先让first和herlper移动k-1次
for (int j = 0;j <startNo - 1;j++){
first = first.getNext();
helper = helper.getNext();
}
//当小孩报数时,让first和helper指针同时的移动 m-1次,然后出圈。
//这里是一个循环操作,直到圈中只有一个节点。
while (true){
if (helper == first){ //说明圈中只有一个节点
break;
}
//让 first和 herlper指针同时的移动countNum-1
for (int j = 0;j<countNum - 1;j++){
first = first.getNext();
helper = helper.getNext();
}
//这时first指向的节点,就是要出圈的小孩节点
System.out.printf("小孩%d出圈\n",first.getNo());
//这时将first指向的小孩节点出圈
first = first.getNext();
helper.setNext(first);
}
System.out.printf("最后留在圈中的小孩编号%d \n",first.getNo());
}
//测试一把小孩出圈是否正确
circleSingleLinkdList.countBoy(1,2,5); //2>4>1>5>3
到此本文就结束了,如果在写的过程有什么问题导致异常可以参考下方的完整代码!
package com.company.linkedlist;
/**
* @author mengzhichao
* @create 2022-04-09-16:14
*/
public class Josephu {
public static void main(String[] args) {
CircleSingleLinkdList circleSingleLinkdList =new CircleSingleLinkdList();
circleSingleLinkdList.addBoy(5);//加入5个小孩节点
circleSingleLinkdList.showBoy();
//测试一把小孩出圈是否正确
circleSingleLinkdList.countBoy(1,2,5); //2>4>1>5>3
}
}
//创建一个环形的单向链表
class CircleSingleLinkdList{
//创建一个first节点,当前没有编号
private Boy first =null;
//添加小孩节点,构建成一个环形的链表
public void addBoy(int nums){
//nums 做一个数据校验
if (nums < 1){
System.out.println("nums的值不正确!");
return; //直接结束
}
Boy curBoy = null; //辅助指针,帮助构建环形链表
//使用for来创建我们的环形链表
for (int i=1;i<=nums;i++){
//根据编号,创建小孩节点
Boy boy =new Boy(i);
//如果是第一个小孩
if (i == 1){
first = boy;
first.setNext(first); //构成环
curBoy = first; //让curBoy指向第一个小孩
}else {
curBoy.setNext(boy);
boy.setNext(first);
curBoy = boy;
}
}
}
//遍历当前的环形链表
public void showBoy(){
//判断链表是否为空
if (first == null){
System.out.println("没有任何小孩~");
return;
}
//因为first不能动,因此我们仍然使用一个辅助指针完成遍历
Boy curBoy = first;
while (true){
System.out.printf("小孩的编号 %d \n",curBoy.getNo());
if (curBoy.getNext() == first){ //说明已经遍历完毕
break;
}
curBoy = curBoy.getNext(); //curBoy后移
}
}
//根据用户的输入,计算小孩的出圈顺序
/***
*
* @param startNo 表示从第几个小孩开始数数
* @param countNum 表示数几下
* @param nums 表示最初有多少个小孩在圈中
*/
public void countBoy(int startNo,int countNum,int nums){
//参数校验
if (first == null || startNo < 1 || startNo > nums){
System.out.println("参数输入有误!");
return;
}
//创建一个辅助指针,帮助完成小孩出圈
Boy helper = first;
//需要创建一个辅助指针(变量)helper,事先应该指向环形链表的最后这个节点。
while (true){
if (helper.getNext() == first){ //说明helper指向最后小孩节点
break;
}
helper = helper.getNext();
}
//小孩报数前,先让first和herlper移动k-1次
for (int j = 0;j <startNo - 1;j++){
first = first.getNext();
helper = helper.getNext();
}
//当小孩报数时,让first和helper指针同时的移动 m-1次,然后出圈。
//这里是一个循环操作,直到圈中只有一个节点。
while (true){
if (helper == first){ //说明圈中只有一个节点
break;
}
//让 first和 herlper指针同时的移动countNum-1
for (int j = 0;j<countNum - 1;j++){
first = first.getNext();
helper = helper.getNext();
}
//这时first指向的节点,就是要出圈的小孩节点
System.out.printf("小孩%d出圈\n",first.getNo());
//这时将first指向的小孩节点出圈
first = first.getNext();
helper.setNext(first);
}
System.out.printf("最后留在圈中的小孩编号%d \n",first.getNo());
}
}
//创建一个Boy类,表示一个节点
class Boy{
//编号
private int no;
//指向下一个节点,默认null
private Boy next;
public Boy(int no){
this.no = no;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public Boy getNext() {
return next;
}
public void setNext(Boy next) {
this.next = next;
}
}
@Cacheable在同一类中方法调用无效 上述图片中,同一个类中genLiveBullets()方法调用同类中的queryLiveByRoom()方法,这样即便标识了Cacheable标签,
目录 @Transaction注解导致动态切换更改数据库失效 使用场景 遇到问题 解决 @Transaction
@RequestBody不能class类型匹配 在首次第一次尝试使用@RequestBody注解 开始加载字符串使用post提交(貌似只能post),加Json数据格式传输的时候,
目录 @Autowired注入static接口问题 @Autowired自动注入普通service很方便 但是如果注入static修饰的serv
目录 @RequestBody部分属性丢失 问题描述 JavaBean实现 Controller实现
目录 解决@PathVariable参数接收不完整的问题 今天遇到的问题是: 解决办法: @PathVariable接受的参
这几天在项目里面发现我使用@Transactional注解事务之后,抛了异常居然不回滚。后来终于找到了原因。 如果你也出现了这种情况,可以从下面开始排查。 1、特性 先来了解一下@Trans
概述: ? 1
场景: 在处理定时任务时,由于这几个方法都是静态方法,在aop的切面中使用@Around注解,进行监控方法调用是否有异常。 发现aop没有生效。 代码如下:
最近做项目的时候 用户提出要上传大图片 一张图片有可能十几兆 本来用的第三方的上传控件 有限制图片上传大小的设置 以前设置的是2M&nb
我已经实现了这个SCIM reference code在我们的应用程序中。 我实现的代码确实通过了此postman link中存在的所有用户测试集合。 。我的 SCIM Api 也被 Azure 接受
我一直对“然后”不被等待的行为感到困扰,我明白其原因。然而,我仍然需要绕过它。这是我的用例。 doWork(family) { return doWork1(family)
我正在尝试查找 channel 中的消息是否仍然存在,但是,我不确定如何解决 promise ,查看其他答案和文档,我可以看到它可能是通过函数实现的,但我是不完全确定如何去做。我希望能在这方面获得一些
我有以下情况: 同一工作区中的 2 个 Eclipse 项目:Apa 和 Bepa(为简洁起见,使用化名)。 Apa 项目引用(包括)Bepa 项目。 我在 Bepa 有一个类 X,具有公共(publ
这个问题已经有答案了: Why am I getting a NoClassDefFoundError in Java? (31 个回答) 已关闭 6 年前。 我正在努力学习 spring。所以我输入
我正在写一个小游戏,屏幕上有许多圆圈在移动。 我在两个线程中管理圈子,如下所示: public void run() { int stepCount = 0; int dx;
我在使用 Sympy 求解方程时遇到问题。当我运行代码时,例如: 打印(校正(10)) 我希望它打印一个数字 f。相反,它给我错误:执行中止。 def correction(r): from
好吧,我制作的每个页面都有这个问题。我不确定我做错了什么,但我所有的页面都不适用于所有分辨率。可能是因为我使用的是宽屏?大声笑我不确定,但在小于宽屏分辨率的情况下,它永远不会看起来正确。它的某些部分你
我正在尝试像这样进行一个非常简单的文化 srting 检查 if(culture.ToUpper() == "ES-ES" || "IT-IT") { //do something } else
Closed. This question is off-topic. It is not currently accepting answers. Learn more。 想改进这个问题吗?Upda
我是一名优秀的程序员,十分优秀!