约瑟夫环-链表解法
之前遇到一个面试题，大意是：电梯里一拥而上一群人，导致电梯超重，于是大家约定，站成一圈，任选一人开始报数，数到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这种
有疑问加站长微信联系（非本文作者）
