「算法」13个人手拉手围成一个圈，依次报数
题目：
13个人手拉手围成一个圈，假设从1号开始报数1，他的下一位2号报数2，再下一位3号报数3，当报数是3的人（即3号）退出圈，他的前后两人（即2号和4号）重新拉上手，然后从4号开始重复上述过程，这样经过若干次后这个圈会最终剩下一个人，那么请问最后这个人是谁，请写出程序找到这个人。
下面是我的解法：
第一种： 重新排队
12345 排队 => 删除3并且1、2到队伍后面 => 4512 排队=> 删除1 并且45到队伍后面 => ...
大家看运行结果就能看出来我的思路：
点击查看单链表LinkedList
复制代码function getNum (num1, num2) {
// 初始化化链表
var list = new LinkedList();
for (let i = 0; i< num1; i++) {
list.append(i+1);
}
reallyFunc(list, num1, num2)
function reallyFunc(list, num1, num2) {
let j = 0; // 监测循环次数
while(list.length > 1){
var h = list.head;
var i = 1;
while(h.next && i <= num2) {
j++
// 将第num2个移除掉
if(i == num2) {
console.log('抛弃元素: ', h.data);
list.head = h.next
list.length -= num2
} else {
list.append(h.data);
}
h = h.next;
i++;
}
}
console.log('data: ', list.head.data);
console.log('循环次数: ', j);
return list.head.data
}
}
getNum(13, 3)
// data: 13
复制代码// 单链表
function LinkedList() {
// 内部的类：节点类
function Node(data) {
this.data = data;
this.next = null;
}
// 属性
this.head = null;
this.length = 0; // 存储节点个数
// 向链表尾部添加一个新的项
LinkedList.prototype.append = function (data) {
var newNode = new Node(data);
if (this.length == 0) {
// 第一个节点为头节点
this.head = newNode;
} else {
var current = this.head;
while(current.next){
current = current.next
}
current.next = newNode; // 找到最后一个
}
this.length += 1;
}
}
复制代码从上述代码可知，该算法时间复杂度为O(n²),空间复杂度O(1)， 这样的时间复杂度对于算法而言勉强是刚到及格线，所以面试官一定会让你优化的
第二种： 手拉手成圈
再次分析题，灵光乍现，最好的解法不就是创建一个循环单连表么，这样就模拟了图上的圈了，删除第3个的时候就是讲上一个元素的next指向3的下个元素，这样就是踢出了第3个元素，这样只需桉循序往下走，然后当前数的值等于当前数的next的时候就是最后的数了，按照这种推理，时间复杂度也就是元素个数减去1, 就是O(n)，按照这个来实现一一下
简单的说 是用代码实现了一个圈，next 就是人的手，怎么删除每次报数的第三个人呢， 就是将上一个人的手（next）和 （next.next）下下个人的手牵起来。这样 代码就和现实世界的情况一样了，真数字孪生。
- 将单链表头尾相连（改动不大）
- 更改嵌套循环算法
function getNum (num1, num2) {
// 初始化化链表
var list = new LinkedList();
for (let i = 0; i< num1; i++) {
list.append(i+1);
}
console.log('list: ', list);
reallyFunc(list, num1, num2)
function reallyFunc(list, num1, num2) {
let j = 0; // 监测循环次数
let i = 1;
let h = list.head
while(h.next.data !== h.next.next.data) {
j++
// 将第num2移除掉
if(i == num2 -1) {
h.next = h.next.next // 核心
i = 1
} else {
i++;
}
h = h.next;
}
console.log('data: ', h.data);
console.log('循环次数: ', j);
}
}
复制代码// 双链表
function LinkedList() {
// 内部的类：节点类
function Node(data) {
this.data = data;
this.next = null;
}
// 属性
this.head = null;
this.length = 0; // 存储节点个数
/* 向链表尾部添加一个新的项 */
LinkedList.prototype.append = function (data) {
var newNode = new Node(data);
if (this.length == 0) {
this.head = newNode;
newNode.next = this.head; // 新增，头尾相连
} else {
var current = this.head;
while(current.next !== this.head){
current = current.next
}
current.next = newNode;
newNode.next = this.head; // 新增，头尾相连
}
this.length += 1;
}
}
复制代码如上时间复杂度为O(n)，空间复杂度O(1)，我满意了，面试官也估计满意了。
这样不仅时间复杂度少了，而且代码看着更易懂了。重要的是代码逻辑就是现实中的处理模式 good~。
测试用例
最后，按照标准答案find函数进行测试用例对比如下：
find(5,4) // 1
getNum(5,4) // 1
find(13,3) // 13
getNum(13, 3) // 13
find(133, 13) // 32
getNum(133, 13) // 32
复制代码通过测试结果，说明应该是可以的，但更要精简代码。
我的这种做法大家有没懂得可以评论留言哦~
本文系转载，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文系转载，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
