代码编织梦想

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);
    }
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Gojavaee/article/details/128012052

leetcode hot 100 —— 23.合并k个升序链表_hdu-五七小卡的博客-爱代码爱编程

题目 给你一个链表数组,每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中,返回合并后的链表。 思路 在做本题之前,先考虑一下,如何合并两个有序链表,见 21.合并两个有序链表 最直接的思路就是,用一

剖分(树形差分)_wyw___的博客-爱代码爱编程

E-剖分_牛客小白月赛62 (nowcoder.com) 题目描述 牛牛有一颗包含n个结点的二叉树,这些结点编号为1 ...n。这颗树被定义为:1、以结点1为根。 2、编号为α结点的两个儿子编号分别为:2 xa和2×巴+ 1。3、每个结点的权重初始都为0。 牛牛接下来会对这颗树进行m次操作,操作的格式是以下四种之—: 1、op a(这里op = 1)代表

期末复习 c语言再学习_aniyaaaaa_的博客-爱代码爱编程

作者:@小萌新 专栏:@C语言复习 作者简介: 大二学生 希望能和大家一起进步! 本篇博客简介:回顾之前的分支循环以及一些题目博客 @[TOC](这里写目录标题 分支循环选择switch caseget

acwing245. 你能回答这些问题吗 线段树详解_kai_wei_的博客-爱代码爱编程

3.2线段树 例题分析 245. 你能回答这些问题吗 - AcWing题库 **题意:**给一条序列,如何动态维护区间的最大子段和,包括询问某区间的最大字段和和修改某个数。 分析:线段树struct保留什么信息。

约瑟夫环问题 —— 算法-爱代码爱编程

约瑟夫环问题 前言约瑟夫环问题一约瑟夫环问题二约瑟夫环问题三约瑟夫环问题四约瑟夫环问题五约瑟夫环问题六约瑟夫环问题七约瑟夫环问题解决一 —— 模拟队列约瑟夫环问题解决二 —— 环形链表约瑟夫环问题解决三 ——

leetcode栈和队列练习-爱代码爱编程

文章目录 前言1.力扣20. 有效的括号1.题目分析 2.代码示现2.力扣225. 用队列实现栈1.题目分析2.代码实现 3.力扣232. 用栈实现队列1.题目分析2.代码实现 4.力扣622

c++类与对象(一)-爱代码爱编程

目录 一、面向过程和面向对象认识 二、类的引入 三、类的定义 类的两种定义方式: 四、类的访问限定符及封装 4.1 访问限定符 4.2 封装 五、类的作用域 六、类的实例化 七、类对象模型 7.1 如何计算类对象的大小​​​​​ 7.2 类对象的存储方式 7.3 结构体内存对齐规则 八、this指针 8.1 this指针的引出