深信服前端开发2022/9/29笔试编程题解题思路
题目描述：许多人客人坐在圆桌上把花传递给旁边的人。某一时刻K传花停止，这个时候花在谁手里，谁就离场。重复这个过程，直到只剩一个客人（胜利者）
解题思路：典型的击鼓传花游戏，用队列即可轻松解决
贴下代码
class Queue {
constructor() {
this.count = 0
this.lowestCount = 0
this.items = {}
}
enqueue(item) {
this.items[this.count] = item
this.count++
}
isEmpty() {
return this.count - this.lowestCount === 0
}
dequeue() {
if (this.isEmpty()) {
return undefined
}
const result = this.items[this.lowestCount]
delete this.items[this.lowestCount]
this.lowestCount++
return result
}
size() {
return this.count - this.lowestCount
}
}
//击鼓传花游戏
function hotPotato(elementsList, k) {
const queue = new Queue()
const elimitatedList = []
for (let i = 0; i < elementsList.length; i++) {
queue.enqueue(elementsList[i])
}
while (queue.size() > 1) {
for (let i = 0; i < k; i++) {
queue.enqueue(queue.dequeue())
}
elimitatedList.push(queue.dequeue())
}
return {
eliminated: elimitatedList,
winner: queue.dequeue()
}
} 来源：《学习JavaScript数据结构与算法(第三版)》
