前端企业面试题：企业真实案例——28

Love The Way You Lie 2022-12-05 12:17 180阅读 0赞

> **请实现一个约瑟夫环**

首先，你必须先搞清楚什么是约瑟夫环。

> 相传，在罗马人占领敲他帕特之后，39个犹太人跟约瑟夫以及他的朋友躲到了一个山洞中，39个犹太人决定宁死也不要被敌人抓到，于是决定了一个自杀方式，41个人围成一个圈，由第1个人开始报数，每报数到第3人，该人就必须自杀。然后再由下一个重新报数，直到所有人都自杀身亡为止。然而约瑟夫和他的朋友并不想遵从。他将朋友和自己安排在了第16个和第31个位置，于是逃过了这场死亡游戏。请问他是如何做到的？

它可以衍生为一个通用问题，假设有M个元素

![49c68f9ffae7bcb0dc1dc351672cdf81.png][]

如果把每个人看做一个节点，他们形成了一个单向的循环链表

![ff340cbddcfd4d7c0dfa4d951b268c4a.png][]

我们现在假设K=3

![d94bab087a1a9eb8d33b50088daa36b8.png][]

![df1f6dacab57c7173fee14be5cfb0deb.png][]

当只剩下最后一个元素时

![33815c1e668e572883bdb6c24c969fda.png][]

于是我们的核心代码就可以写出来了

while(node.next != node){
        1 将指针移动K-1步
        2 重新建立连接删除当前节点
        3 修正指针位置到下一个
    }

我们先准备节点类

function Node(name){
        this.name = name;
        this.next;
    }

创建一个长度为10的单向循环链表

let head = temp = new Node(1);
    for(let i=2; i<=10; i++){
        temp.next = new Node(i);
        temp = temp.next;
    }
    temp.next = head;

创建出我们的指针类

function Pointer(node){
        this.current = node;
        this.move = function(){
            this.prev = this.current; //记录前一格
            this.current = this.current.next; //当前节点向前移动一格
        }
    }

接下来是完整代码

[49c68f9ffae7bcb0dc1dc351672cdf81.png]: /images/20221123/9744836dd67c42c981fff32c58ad18c7.png
[ff340cbddcfd4d7c0dfa4d951b268c4a.png]: /images/20221123/e37abbfd6c164bac96f4f2078f852194.png
[d94bab087a1a9eb8d33b50088daa36b8.png]: /images/20221123/a327ddd0aafe444ebf4944d58a35f061.png
[df1f6dacab57c7173fee14be5cfb0deb.png]: /images/20221123/417059b87054498fbb8355a51f321771.png
[33815c1e668e572883bdb6c24c969fda.png]: /images/20221123/fda97ea47b1643159170adfd945be5e7.png