导航菜单

一道阿里笔试题:我是如何用一行代码解决约瑟夫环问题的

约瑟夫环问题是一个非常经典的问题。据估计,每个人都听说过它。然后我在书面测试中遇到了它。下面我将使用三种方法详细解释这个问题。在最后一种方法之后,我会保证。让你强迫它。

问题描述:编号为1-N的N名士兵坐在一起形成一个圆圈,从编号为1的士兵开始(1,2,3 .轮流报告),编号为m的士兵将在死亡后被杀死,士兵们将从1再次开始计数。直到最后一名士兵离开,询问这名士兵的号码。

1,方法一:数组

当我在大学一年级第一次遇到这个问题时,我用阵列做了这个问题。我想大多数人都知道怎么做。方法是这样的:

使用数组来存储n个数字1,2,3 . n,如图所示(这里我们假设n=6,m=3)

60dca4e5492d4fccb43a33abe452900a

然后继续遍历数组,对于选定的数字,我们做一个标记,例如,选择数字arr [2]=3,然后我们可以做一个标记,例如,让arr [2]=-1,到指示存储在arr [2]中的数字已被删除。

2483f7a8f8f1463ba0dbff501abbb1ab

然后按照这个方法,继续遍历数组,并继续标记,直到数组中只有一个元素为非-1,这样剩下的元素就是我们要查找的元素。让我来证明一下:

a78db563df484c6193abb30942c0d380

这种方法简单吗?这个想法很简单,但编码并不那么简单。有许多关键条件。每次遍历到数组的最后一个元素时,必须将下标重置为0,并且必须在遍历时判断该元素是否为-1。对手写代码感兴趣,使用这种方法做的方法,感觉不是很简单,编码过程还是相当考验的。

该方法的时间复杂度为O(n * m),空间复杂度为O(n);

2.方法2:循环链接表

那些已经学习链表的人估计使用链表来处理约瑟夫环问题。使用链表来处理实际的想法与上面类似,但在处理链表时,所选的数字不再被标记,而是直接删除,因为从链表中删除元素的时间复杂度非常低,O(1)。当然,也可以去除上述阵列方法,但是阵列去除的时间复杂度是O(n)。所以链表的解决方案如下:

1.创建一个循环链表来存储元素:

171cc82452c34cddb420160d1a5657d4

2,然后遍历列表一次并删除它,直到列表中只剩下一个节点,我不会在这里全部演示

d5fc46062d0a49869f823aba60e4b72f

代码如下:

//定义链表节点

类节点{

国际日期;

节点接下来;

公共节点(int date){

This.date=date;

}

}

核心代码

Public static int solve(int n,int m){

如果(m==1 || n <2)

返回n;

//创建一个循环列表

节点头=createLinkedList(n);

//遍历删除

Int count=1;

节点cur=head;

节点pre=null; //前任节点

而(head.next!=head){

//删除节点

如果(count==m){

Count=1;

Pre.next=cur.next;

Cur=pre.next;

}否则{

计数++;

Pre=cur;

Cur=cur.next;

}

}

返回head.date;

}

静态节点createLinkedList(int n){

节点头=新节点(1);

节点next=head;

For(int i=2; i&lt;=n; i ++){

节点tmp=新节点(i);

Next.next=tmp;

下一个=next.next;

}

//头部和尾部连接

Next.next=head;

回头;

}

估计该方法是最有用的,时间复杂度为O(n * m),空间复杂度为O(n)。

有没有更好的办法?是的,请向下看

方法3:递归

实际上,这个问题也可以通过递归来解决。我们的想法是,每当我们删除一名士兵时,我们会对这些士兵重新编号,然后我们的难点是找到士兵在删除之前和之后的映射关系。

我们为递归函数f(n,m)定义的返回结果是幸存士兵的数量,显然当n=1时,f(n,m)=1.如果我们能找到f(n,m)之间的关系)和f(n-1,m),我们可以以递归的方式解决它。我们假设人数是n,而那些向m报告的人自杀。第一个数字是

.

1

.

m - 2

m - 1

m + 1

m + 2

.

.

删除后,删除编号为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是删除节点后的号码。新旧之间的关系是旧的=(new + m - 1)%n + 1。

注意:有些人可能想知道为什么它不老=(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){

如果(n==1)返回n;

返回(f(n - 1,m)+ m - 1)%n + 1;

}

我去,两行代码得到,时间复杂度是O(n),空间复杂度是O(n),牛逼!那么如果你想告诉别人,我想要一行代码来解决约瑟夫问题?答案没问题,如下:

Int f(int n,int m){

返回n==1? n:(f(n - 1,m)+ m - 1)%n + 1;

}

面对低谷,面试官会让你手写约瑟夫的问题,你会把这行代码扔给它。

总结

但是,当书面测试不是通过递归方法完成时,它是通过链表完成的。当时,我不知道我仍然可以使用一行代码来获取它,并且,欢迎您提供半行代码。代码得到它的方式!