【年前最后一波装逼】记一次阿里面试,我是如何用一行代码解决约瑟夫环问题的
2020/1/24 13:22:34
本文主要是介绍【年前最后一波装逼】记一次阿里面试,我是如何用一行代码解决约瑟夫环问题的,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
约瑟夫环问题算是很经典的题了,估计大家都听说过,然后我就在一次阿里的笔试中也遇到了,下面我就用 3 种方法来详细讲解一下这道题,最后一种方法学了之后保证让你可以让你装逼。
问题描述:编号为 1-N 的 N 个士兵围坐在一起形成一个圆圈,从编号为 1 的士兵开始依次报数(1,2,3...这样依次报),数到 m 的 士兵会被杀死出列,之后的士兵再从 1 开始报数。直到最后剩下一士兵,求这个士兵的编号。(注意,编号不是从0开始的哈)
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、然后一边遍历链表一遍删除,直到链表只剩下一个节点,我这里就不全部演示了
代码如下:
// 定义链表节点 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),牛逼!那如果你想跟别人说,我想一行代码解决约瑟夫问题呢?答是没问题的,如下:
int f(int n, int m){ return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1; } 复制代码
卧槽,以后面试官让你手写约瑟夫问题,你就扔这一行代码给它。
总结
不过那次笔试时,并没有用递归的方法做,而是用链表的方式做,,,,,那时,不知道原来还能用一行代码搞定的,,,,欢迎各位大佬提供半行代码搞定的方法!
老铁,要不点个赞再走可好?么么哒
1、给俺点个赞呗,可以让更多的人看到这篇文章,顺便激励下我,嘻嘻。
2、老铁们,关注我的原创微信公众号「帅地玩编程」,专注于写算法 + 计算机基础知识(计算机网络+ 操作系统+数据库+Linux)。
保存让你看完有所收获,不信你打我。后台回复『电子书』送你一份精选电子书大礼包,包含各类技能的优质电子书。
作者简洁
作者:大家好,我是帅地,从大学、校招一路走来,深知算法,计算机基础知识的重要性,所以申请了一个微星公众号『帅地玩编程』,专业于写这些底层知识,提升我们的内功,帅地期待你的关注,和我一起学习。 转载说明:未获得授权,禁止转载
这篇关于【年前最后一波装逼】记一次阿里面试,我是如何用一行代码解决约瑟夫环问题的的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-22项目:远程温湿度检测系统
- 2024-12-21《鸿蒙HarmonyOS应用开发从入门到精通(第2版)》简介
- 2024-12-21后台管理系统开发教程:新手入门全指南
- 2024-12-21后台开发教程:新手入门及实战指南
- 2024-12-21后台综合解决方案教程:新手入门指南
- 2024-12-21接口模块封装教程:新手必备指南
- 2024-12-21请求动作封装教程:新手必看指南
- 2024-12-21RBAC的权限教程:从入门到实践
- 2024-12-21登录鉴权实战:新手入门教程
- 2024-12-21动态权限实战入门指南