最近复习到了数据结构中的普通队列部分,来实现一个击鼓传花游戏的应用。
循环队列的一个例子就是击鼓传花(hot potato),在这个游戏中,孩子们围成一个圆圈,把花尽快地传递给旁边的人。某一时刻传话停止,这个时候花在谁手里,谁就退出圆圈、结束游戏。重复这个过程,直到只剩一个孩子(胜者)
首先我们需要实现队列这个数据结构。class Queue {
constructor() {
// count属性控制队列的大小
this.count = 0;
// 追踪第一个元素
this.lowestCount = 0;
// 首先我们需要一个用于存储队列中元素的数据结构,我们可以使用数组,就像Stack一样.
// 但是,为了写出一个在获取元素时更高效的数据结构,我们将使用一个对象来存储我们的元素
this.items = {};
}
enqueue(element) {
this.items[this.count] = element;
this.count++;
}
dequeue() {
if(this.isEmpty()) {
return undefined;
}
const result = this.items[this.lowestCount];
delete this.items[this.lowestCount];
this.lowestCount++;
return result;
}
isEmpty() {
return this.count - this.lowestCount === 0;
}
peek() {
if(this.isEmpty()) {
return undefined;
}
return this.items[this.lowestCount];
}
size() {
return this.count - this.lowestCount;
}
clear() {
this.items = {};
this.count = 0;
this.lowestCount = 0;
}
toString() {
if(this.isEmpty()) {
return '';
}
let objString = `${this.items[this.lowestCount]}`;
for(let i = this.lowestCount + 1; i < this.count; i++) {
objString = `${objString},${this.items[i]}`;
}
return objString;
}
} 然后说一下通过队列实现这个游戏的思路,先把所有人添加到队列中,然后循环遍历队列,从队列头部移除一项,再将其添加到队列末尾,模拟击鼓传花的过程,一旦达到给定的传递次数,拿着花的那个人就被淘汰。function hotPotato(elementList,num) {
const queue = new Queue();
const elimitatedList = [];
// 把名单的名字全都加入队列中
for(let i = 0; i < elementList.length; i++) {
queue.enqueue(elementList[i]);
}
while(queue.size() > 1) {
for(let i = 0; i < num; i++) {
// 从队列开头移除一项,再将其添加到队列末尾,模拟击鼓传花
// (如果你把花传给了旁边的人,你被淘汰的威胁就立即解除了)。
// 一旦达到给定的传递次数,拿着花的那个人就被淘汰了
queue.enqueue(queue.dequeue());
}
// 被淘汰,从队列中移除
elimitatedList.push(queue.dequeue());
}
return {
elimitatedList:elimitatedList,
winner:queue.dequeue()
};
}
const names = ['John','Jack','Camila','Ingrid','Carl'];
const result = hotPotato(names,7);
result.elimitatedList.forEach(item => {
console.log(`${item}在击鼓传花游戏中被淘汰。`);
})
console.log(`胜利者:${result.winner}`);
通过测试用例可以看到结果是正确的。
有任何问题都可以加我联系方式沟通交流。
QQ:505417246
微信:18331092918
微信公众号:Code程序人生
个人博客:https://Creator12333.github.io(详细总结一些面试题,以及前端进阶的内容,CSDN写偏基础的内容)
|