一气之下,我一行代码搞定了约瑟夫环问题,面试官懵了[通俗易懂]

一气之下,我一行代码搞定了约瑟夫环问题,面试官懵了[通俗易懂]大家好,我是帅地。对于约瑟夫环问题估计大家都听说过,除非你刚刚读大一,因为在大一大部分学校的课本都会降到这个算法题。为了以防万一你没听过,我还是给下问题的描述问题描述:编号为1-N的N个士兵围坐在一起形成一个圆圈,从编号为1的士兵开始依次报数(1,2,3…这样依次报),数到m的士兵会被杀死出列,之后的士兵再从1开始报数。直到最后剩下一士兵,求这个士兵的编号。记得有一次,貌似是阿里的面试,面试官给了我一到原汁原味的约瑟夫好,好家伙,看我不把你秀一把。不过,作为一个有着几十场面

大家好,又见面了,我是你们的朋友全栈君。

大家好,我是帅地。

对于约瑟夫环问题估计大家都听说过,除非你刚刚读大一,因为在大一大部分学校的课本都会降到这个算法题。为了以防万一你没听过,我还是给下问题的描述

问题描述:编号为 1-N 的 N 个士兵围坐在一起形成一个圆圈,从编号为 1 的士兵开始依次报数(1,2,3…这样依次报),数到 m 的 士兵会被杀死出列,之后的士兵再从 1 开始报数。直到最后剩下一士兵,求这个士兵的编号。

记得有一次,貌似是阿里的面试,面试官给了我一到原汁原味的约瑟夫好,好家伙,看我不把你秀一把。

不过,作为一个有着几十场面试经验的 xxx,我决定假装用最土的方法入手,等面试官问我还有没有其他方法时,我在一步步用更加牛逼的方法。

所以,第一种方法就是数组

1、方法一:数组

实不相瞒,在大一第一次遇到这个题的时候,我是用数组做的,我猜绝大多数人也都知道怎么做。方法是这样的:

用一个数组来存放 1,2,3 … n 这 n 个编号,如图(这里我们假设n = 6, m = 3)

一气之下,我一行代码搞定了约瑟夫环问题,面试官懵了[通俗易懂]
然后不停着遍历数组,对于被选中的编号,我们就做一个标记,例如编号 arr[2] = 3 被选中了,那么我们可以做一个标记,例如让 arr[2] = -1,来表示 arr[2] 存放的编号已经出局的了。

一气之下,我一行代码搞定了约瑟夫环问题,面试官懵了[通俗易懂]

然后就按照这种方法,不停着遍历数组,不停着做标记,直到数组中只有一个元素是非 -1 的,这样,剩下的那个元素就是我们要找的元素了。我演示一下吧:

一气之下,我一行代码搞定了约瑟夫环问题,面试官懵了[通俗易懂]

这种方法简单吗?思路简单,但是编码却没那么简单,临界条件特别多,每次遍历到数组最后一个元素的时候,还得重新设置下标为 0,并且遍历的时候还得判断该元素时候是否是 -1。

但是,这种方法也不是一无是处,怎么说也体现了咱们的思维严谨,毕竟临界条件这么多,我都能做对,嘿嘿。

感兴趣的可以动手写一下代码,用这种数组的方式做,千万不要觉得很简单,编码这个过程还是挺考验人的。

这种做法的时间复杂度是 O(n * m), 空间复杂度是 O(n);

面试官:还有其他方法吗?

当然,面试要是不问,咱们也要跟面试官说,我突然想到了更好的方法啊,,,,,

第二种方法,只能掏出我大一第二学期学到的链表了,下面用链表跟大家讲一讲。

2、方法二:环形链表

学过链表的人,估计都会用链表来处理约瑟夫环问题,用链表来处理其实和上面处理的思路差不多,只是用链表来处理的时候,对于被选中的编号,不再是做标记,而是直接移除,因为从链表移除一个元素的时间复杂度很低,为 O(1)。当然,上面数组的方法你也可以采用移除的方式,不过数组移除的时间复杂度为 O(n)。所以采用链表的解决方法如下:

1、先创建一个环形链表来存放元素(注意,是环形链表哦):

一气之下,我一行代码搞定了约瑟夫环问题,面试官懵了[通俗易懂]

2、然后一边遍历链表一遍删除,直到链表只剩下一个节点,我这里就不全部演示了

一气之下,我一行代码搞定了约瑟夫环问题,面试官懵了[通俗易懂]

代码我就用 Java 写了哈。

代码如下:

// 定义链表节点
class Node{ 
   
    int date;
    Node next;

    public Node(int date) { 
   
        this.date = date;
    }
}

核心代码

    public static int solve(int n, int m) { 
   
        if(m == 1 || n < 2)
            return n;
        // 创建环形链表
        Node head = createLinkedList(n);
        // 遍历删除
        int count = 1;
        Node cur = head;
        Node pre = null;//前驱节点
        while (head.next != head) { 
   
            // 删除节点
            if (count == m) { 
   
                count = 1;
                pre.next = cur.next;
                cur = pre.next;
            } else { 
   
                count++;
                pre = cur;
                cur = cur.next;
            }
        }
        return head.date;
    }

    static Node createLinkedList(int n) { 
   
        Node head = new Node(1);
        Node next = head;
        for (int i = 2; i <= n; i++) { 
   
            Node tmp = new Node(i);
            next.next = tmp;
            next = next.next;
        }
        // 头尾串联
        next.next = head;
        return head;
    }

这种方法估计是最多人用的,时间复杂度为 O(n * m), 空间复杂度是 O(n)。

和第一种方便相比,时间复杂度和空间复杂度都差不多,不过采用链表比较不容易出错。

面试官:还有更好的方法吗?

我:卧槽,链表这么好的方法还问我有没有更好的?好家伙,嫌弃代码太长没耐心看?

方法三:递归

帅地被迫只能拿出我的递归大法,递归是思路是每次我们删除了某一个士兵之后,我们就对这些士兵重新编号,然后我们的难点就是找出删除前和删除后士兵编号的映射关系

如果你对递归不大懂,可以看我之前的递归文章:连刷半年题,告别递归,谈谈我的一些经验

我们定义递归函数 f(n,m) 的返回结果是存活士兵的编号,显然当 n = 1 时,f(n, m) = 1。假如我们能够找出 f(n,m) 和 f(n-1,m) 之间的关系的话,我们就可以用递归的方式来解决了。我们假设人员数为 n, 报数到 m 的人就自杀。则刚开始的编号为


1

m – 2

m – 1

m

m + 1

m + 2

n

进行了一次删除之后,删除了编号为 m 的节点。删除之后,就只剩下 n – 1 个节点了,删除前和删除之后的编号转换关系为:

删除前 — 删除后

… — …

m – 2 — n – 2

m – 1 — n – 1

m —- 无(因为编号被删除了)

m + 1 — 1(因为下次就从这里报数了)

m + 2 —- 2

… —- …

新的环中只有 n – 1 个节点。且删除前编号为 m + 1, m + 2, m + 3 的节点成了删除后编号为 1, 2, 3 的节点。

假设 old 为删除之前的节点编号, new 为删除了一个节点之后的编号,则 old 与 new 之间的关系为 old = (new + m – 1) % n + 1。

有人可能看了会一脸懵逼?如果是这样,那么我建议你自己找几个例子模仿推导一下,估计就知道了

注:有些人可能会疑惑为什么不是 old = (new + m ) % n 呢?主要是因为编号是从 1 开始的,而不是从 0 开始的。如果 new + m == n的话,会导致最后的计算结果为 old = 0。所以 old = (new + m – 1) % n + 1.
这样,我们就得出 f(n, m) 与 f(n – 1, m)之间的关系了,而 f(1, m) = 1.所以我们可以采用递归的方式来做。代码如下:

int f(int n, int m){ 
   
    if(n == 1)   return n;
    return (f(n - 1, m) + m - 1) % n + 1;
}

我去,两行代码搞定,而且时间复杂度是 O(n),当然,空间复杂度还是 O(n),因为会递归会调用 n 次。

为了装逼,我必须用用一行代码来搞定,如下:

int f(int n, int m){ 
   
    return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1;
}

卧槽,以后面试官让你手写约瑟夫问题,你就扔这一行代码给它。这里需要注意的是,如果 n 的数值太大,那么就不适合用递归了,注意怕递归太深,爆栈了

无论是面试还是提升自己的内容,算法学习基本少不了,这里给大家推荐一份某 BAT 大佬总结的 Leetcode 刷题笔记,汇聚了上千道 leetcode 题解,并且代码都是 beat 100%::BAT 大佬分类总结的 Leetcode 刷题模版,助你搞定 90% 的面试

就算你现在不学算法,那么这份笔记也值得你收藏,万一有人问你 Leetcode 某道题解,或者有大神在讨论题解,咱打开这份笔记,不管三七二十一,直接把最优解扔给他,然后退出群聊

image-20210424144849752

链接:BAT 大佬分类总结的 Leetcode 刷题模版,助你搞定 90% 的面试

总结

不过那次笔试时,并没有用递归的方法做,而是用链表的方式做,,,,,那时,不知道原来还能用一行代码搞定的,,,,欢迎各位大佬提供半行代码搞定的方法!

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/136091.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 图解后缀表达式的计算过程

    为了解释后缀表达式的好处,我们先来看看,计算机如何应用后缀表达式计算出最终的结果20的。后缀表达式:9 3 1-3*+ 10 2/+规则:从左到右遍历表达式的每个数字和符号,遇到是数字就进栈,遇到是符号,就将处于栈顶两个数字出栈,进行运算,运算结果进栈,一直到最终获得结果。下面是详细的步骤:1. 初始化一个空栈。此桟用来对要运算的数字进出使用。

  • Python字符串中删除特定字符的方法

    Python字符串中删除特定字符的方法这篇文章主要介绍了Python字符串中删除特定字符的方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧分析在Python中,字符串是不可变的。所以无法直接删除字符串之间的特定字符。所以想对字符串中字符进行操作的时候,需要将字符串转变为列表,列表是可变的,这样就可以实现对字符串中特定字符的操作。1、删除特定字符特定字符…

  • python stdout

    python stdoutpythonstdout

  • VMware Workstation网络连接的三种方式原理详解 与 配置过程图解

    VMware Workstation网络连接的三种方式原理详解 与 配置过程图解

  • 测试集(2)-words

    测试集(2)-words aa.ma.mabandonabandonabattoirabilityabilityableableabnormalabnormalaboardaboardaboutaboutaboveaboveabracadabraabroadabroadabsenceabsenceabsentabsent

  • RowBounds实现分页[通俗易懂]

    RowBounds实现分页[通俗易懂]但使用RowBounds后,会将id>0的所有数据都加载到内存中,然后跳过offset=3条数据,截取10条数据出来,若id>0的数据有100万,则100w数据都会被加载到内存中,从而。

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号