题目描述:许多人客人坐在圆桌上把花传递给旁边的人。某一时刻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数据结构与算法(第三版)》
#深信服笔试题##前端笔试##2023秋招#