15

在一场“死亡游戏”中,如何活下来

 3 years ago
source link: https://studygolang.com/articles/30769
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

约瑟夫环-链表解法

之前遇到一个面试题,大意是:电梯里一拥而上一群人,导致电梯超重,于是大家约定,站成一圈,任选一人开始报数,数到3的那个人出电梯,圈内的下一个人重新从1开始报数,数到3的人再出电梯,一直这样,直到电梯不超重。

现给一串有序的数字,电梯超重需出去M个人,数到K的人出电梯,让列出出电梯的人的序号。

当时第一反应是约瑟夫环,然后用循环链表解决了。

什么是约瑟夫环?百度了一下,原来还有这么一个故事:

在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。问题是,给定了和,一开始要站在什么地方才能避免被处决?Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏

解决这类问题,最直接的方式,就是使用循环链表物理还原。

golang实现:

type Node struct {
    value int
    next  *Node
}

type Circle struct {
    tail  *Node
    lenth int
}

// 增加节点:
func (c *Circle) add(value int) {
    newNode := &Node{value, nil}
    if c.lenth == 0 { //空链表中添加节点
        c.tail = newNode
        c.tail.next = newNode
    } else {
        newNode.next = c.tail.next
        c.tail.next = newNode
        c.tail = newNode
    }
    c.lenth += 1
}

// 初始化 模拟所有人围成一圈
func (c *Circle) init(total int) {
    for i := 1; i <= total; i++ {
        c.add(i)
    }
    c.printCircle()
}

// 需要牺牲m个人,数到K的人kill
func (c *Circle) kill(m, k int) {
    if c.lenth < m || k<1{
        fmt.Println("脱离实际情况,玩不下去")
        return
    }
    pre := c.tail
    cur := c.tail.next //假设从头节点开始数
    j := 0             // 1~k 报数用的
    for died := 0; died < m; {
        j++
        if j == k {
            fmt.Print(cur.value, "号牺牲")
            if c.lenth > 1 {
                fmt.Println(" 下一轮从", cur.next.value, "开始")
            }
            died++ // 记录已经牺牲了的人数
            // 将节点从环形链表中删除
            if c.lenth == 1 { // 环中只剩一个节点的特殊情况
                c.tail = nil
            } else if cur == c.tail { // 要删除的节点是尾节点
                c.tail = pre
                pre.next = cur.next
            } else {
                pre.next = cur.next
            }

            c.lenth -= 1 // 更新链表长度
            j = 0        // 计数清零,下一轮回 又从1开始数
            fmt.Print("当前状态:")
            c.printCircle() // 打印链表
        }
        pre = cur
        cur = cur.next
    }
}

//打印节点:
func (c *Circle) printCircle() {
    if c.lenth == 0 {
        fmt.Println("空环")
        return
    }
    cur := c.tail.next
    for i := 0; i < c.lenth; i++ {
        fmt.Printf("%d ", cur.value)
        cur = cur.next
    }
    fmt.Println()
}

func main() {
    var circle *Circle = new(Circle)
    circle.init(41)
    circle.kill(39, 3)
    //circle.kill(41, 3)
    //circle.kill(41, 0)
}

python实现:

class Node:
    def __init__(self, value, next):
        self.value = value
        self.next = next

    def __str__(self):
        return str(self.value)


class Circle:
    def __init__(self, total):
        self.tail = None
        self.lenth = 0
        self.initialize(total)

    # 增加节点
    def add(self, v):
        new_node = Node(v, None)
        if self.lenth == 0:  # 空链表中添加节点
            self.tail = new_node
            self.tail.next = new_node
        else:
            new_node.next = self.tail.next
            self.tail.next = new_node
            self.tail = new_node
        self.lenth += 1

    def initialize(self, total):
        for i in range(1, total + 1):
            self.add(i)
        self.print_circle()

    # 需要牺牲m个人,数到K的人kill
    def kill(self, m, k):
        if self.lenth < m or k<1:
            print('脱离实际情况,玩不下去')
            return
        pre = self.tail
        cur = self.tail.next  # 假设从头节点开始数
        j = 0  # 1~k 报数用的
        died = 0  # 已经死亡的总人数
        while True:
            if died == m:
                break
            j += 1
            if j == k:
                print(cur.value, "号牺牲", end=' ')
                if self.lenth > 1:
                    print(" 下一轮从", cur.next.value, "开始")

                # 将节点从环形链表中删除
                if self.lenth == 1:  # 环中只剩一个节点的特殊情况
                    self.tail = Node
                elif cur == self.tail:  # 要删除的节点是尾节点
                    self.tail = pre
                    pre.next = cur.next
                else:
                    pre.next = cur.next

                died += 1  # 更新已死亡总人数
                self.lenth -= 1  # 更新链表长度
                j = 0  # 计数清零,下一轮回 又从1开始数
                print('当前状态:', end='')
                self.print_circle()
            pre = cur
            cur = cur.next

    # 打印链表
    def print_circle(self):
        if self.lenth == 0:
            print('空环')
            return
        cur = self.tail.next  # 头节点
        for i in range(self.lenth):
            print(cur, end=" ")
            cur = cur.next
        print()


if __name__ == '__main__':
    circle = Circle(41)
    circle.kill(39, 3)
    # circle.kill(41, 3)
    # circle.kill(41, 0)

运行结果,最终的状态确实是:16 31 ,整个队伍就剩下Josephus和他的朋友2人……

我不由感叹,这,太TM聪明了

另外说到面试题,我当时正得意输出结果和测试用例一样时,面试官给我输入了一个场景之外的奇葩数字,还好hold住了。所以,大家别忘了处理特殊情况,像 41,0这种

有疑问加站长微信联系

iiUfA3j.png!mobile

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK