约瑟夫环问题_嘎嘎乱敲怎么说的博客-爱代码爱编程
Description
约瑟夫问题是个有名的问题:N个人围成一圈,每个人都有自己对应的号数(号数从1到N),从1号开始报数(报数从数字1开始,轮到下一个人数字递增),当有人报数的数字为M将会被杀掉,下一个人接着从数字1开始报数,循环多次直到最后只剩下一个人,其余人都将被杀掉。返回剩下的那一个人的号数。
Input
输入两个正整数N,M
Output
一个整数表示剩下那个人的编号
Sample Input 1
6 5
Sample Output 1
1
Hint
0<=N&&M<=500
解题
思路一:本来想用环形链表解决,解题相对也简单
循环链表的向下枚举不需要考虑头尾问题,直接node=node.next向下
循环聊表的删除也不需要考虑头尾问题,直接node.next=node.next.next删除
当然也有一些需要注意的地方!
形成环形链表很简单,只需要将普通链表的最后一个节点的next指向第一个节点即可
循环链表中只有一个节点的时候停止返回,即node.next=node的时候
删除,需要找到待删除的前面节点,所以我们删除计数的时候要少即一位,利用前面的那个节点直接删除后面节点即可
但是如果M特别大的话消耗的时间会更多,比如现在环中只剩3个人,要杀第300个人,就要循环next 300次,浪费太多时间了,很难AC
思路二:ArrayList集合,压缩无效喊数
一百个人,杀喊103的兄弟,最左边的人开始喊从1喊道100无效定位了一轮,有用的其实就是又从头开始从101到103的情况;
通过这样的逻辑重新定位会快很多
屡一下逻辑:
用left记录喊1的人,index记录要杀的人(index = left + M )
先判断index是否超过集合长度,
如果超过:M先减掉left到最后一个人的人数,这时候left来到集合下标为0的人
剩下的步数对集合长度求余,压缩出现从头到尾喊但是没杀人的情况;
余数-1是最后一轮要杀的人的下标;
然后remove掉下标元素就可以
重复上步骤,直到list长度为1,结束;
上一手梵达芬奇高!需要灵魂感受的画。
如图所示,M为步长,先减掉6个人(arrayList.size()-left),在对8求余数,就等于2,表示杀集合中第2个,转换成下标2-1赋值给变量index,remove(index)。
没看懂看代码自己品一下,不难滴,就是下标修正
完整代码:
import java.util.ArrayList;
public class T_01 {
static int n = 6;
static int m = 12;
static int index = 12;
public static void main(String[] args) {
//初始化集合
ArrayList<Integer> arrayList = new ArrayList<>();
for (int j = 1; j <= 6; j++) {
arrayList.add(j);
}
System.out.println(arrayList);
//第一轮从第一个人开始喊,下标是0
remove(arrayList,0);
System.out.println("最后:"+arrayList);
}
static void remove(ArrayList<Integer> arrayList,int left){
//设置结束条件
if (arrayList.size() == 1){
return;
}
// 如果逻辑index大于N,表示从开始喊的人(不一定是集合的第一个人)到集合最后一个人是找不出杀谁的
// 需要从集合第一个开始继续数(这个阶段可以通过求余压缩)
if (index > n){
// 因为第一轮可能出现不是从集合第一个人开始数的情况
// 统一把特殊情况处理
// 先减掉从开始喊的人到集合最后一个人
index = (m-(arrayList.size()-left));
// 求余表示杀从头开始数第几个人
int q = index%n;
if (q == 0){
// 如果求余等于0就等于杀最后一个人,等于数组长度减一最后一个人的下标
index = n-1;
}else {
// 不等于0,余数-1等于下标
index = (q-1);
}
// 如果下标小于集合长度,代表一轮就能找到要杀的人
} else if (index <= n) {
index = index-1;
}
// 移除集合中下标为index的元素
arrayList.remove(index);
// 下一场游戏开始喊1的人
left = index;
n = arrayList.size();
// 如果你杀的是集合最后一个人,下一场游戏喊1的人在集合第一个,尾的下一个是头。
if (left > n-1){
left = 0;
}
// 逻辑上要杀的位置
index = left+m;
// 进入下一场,并告诉下一场开始喊1的人是谁
remove(arrayList,left);
}
}