前言
❤️笔芯❤️~
队列
队列数据结构,队列是遵循FIFO,先进先出,也有叫先来先服务,原则的一组有序的项。很像现实中的排队(最常见的队列的例子),排在第一位的人会先接受到服务。
创建队列:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| // 声明类 function Queue() { // 这里是属性和方法 }
// 一个用于存储队列中元素的数据结构:数组 let items = [];
// 向队列尾部添加一个或多个新的项 enqueue(element(s))
// 移除队列的第一项,并返回被移除的元素 dequeue()
// 返回队列中第一个元素,最先被添加,也将是最先被移除的元素,队列不做任何变动 front()
// 如果队列中不包含任何元素,返回true,不然返回false isEmpty()
// 返回队列包含的元素个数,与数组的length属性类似 size()
|
向队列添加元素,新的项只能添加到队列末尾
实现的是enqueue
方法
1 2 3
| this.enqueue = function(element) { items.push(element); };
|
从队列移除元素
实现dequeue
方法,使用shift
方法会从数组中移除存储在索引0(第一个位置)
的元素
1 2 3
| this.dequeue = function() { return items.shift(); }
|
查看队列头元素,使用front
方法,该方法返回队列最前面的项
1 2 3
| this.font = function() { return item[0]; };
|
检查队列是否为空,使用isEmpty
方法
1 2 3
| this.isEmpty = function() { return item.length == 0; };
|
1 2 3
| this.size = function() { return items.length; }
|
打印队列元素,使用print
方法
1 2 3
| this.print = function() { console.log(items.toSring()); };
|
队列和栈,唯一的区别是dequeue
方法和front
方法,这是由于先进先出和后进先出原则的不同所造成的
实例化:
1 2 3 4 5
| let queue = new Queue(); console.log(queue.isEmpty()); // 输出true
queue.enqueue("jeskson"); queue.enqueue("魔王哪吒");
|
使用ES6实现Queue类
使用WeakMap
来保存私有属性items
,并用外层函数(闭包)来封装Queue类。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| let Queue2 = (function () { const items = new WeakMap(); class Queue2 { constructor () { items.set(this, []); } enqueue(element) { let q = items.get(this); q.push(element); } dequeue() { let q = items.get(this); let r = q.shift(); return r; } //其他方法 } return Queue2; })();
|
实现一个优先队列:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
| function PriorityQueue() { let items = []; function QueueElement (element, priority){ // 要添加到队列的元素 // 在队列中的优先级 this.element = element; this.priority = priority; } this.enqueue = function(element, priority){ let queueElement = new QueueElement(element, priority); let added = false; for (let i=0; i<items.length; i++){ if (queueElement.priority < items[i].priority){ items.splice(i,0,queueElement); added = true; break; } } if (!added){ items.push(queueElement); } }; this.print = function(){ for (let i=0; i<items.length; i++){ console.log(`${items[i].element} - ${items[i].priority}`); } }; //其他方法和默认的Queue实现相同 }
|
循环队列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| function hotPotato (nameList, num){ // 实现的Queue类 let queue = new Queue(); for (let i=0; i<nameList.length; i++){ // 把里面的名字全都加入队列 queue.enqueue(nameList[i]); } // 给定一个数字,然后迭代队列 let eliminated = ''; while (queue.size() > 1){ // 从队列开头移除一项,再将其添加到队列末尾 for (let i=0; i<num; i++){ queue.enqueue(queue.dequeue()); } // 从队列中移除 eliminated = queue.dequeue(); } return queue.dequeue();// {5} }
|
当我们在浏览器中打开新标签时,就会创建一个任务队列,每个标签都是单线程处理所有任务,被称为事件循环。
浏览器负责多个任务,如渲染HTML,执行JavaScript代码,处理用户交互,执行和处理异步请求等。
66. 加一
一、题目描述
给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一。
最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外,这个整数不会以零开头。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| 示例 1:
输入:digits = [1,2,3] 输出:[1,2,4] 解释:输入数组表示数字 123。
示例 2:
输入:digits = [4,3,2,1] 输出:[4,3,2,2] 解释:输入数组表示数字 4321。
示例 3:
输入:digits = [0] 输出:[1]
|
二、思路分析
如果数组末位(个位)小于 9 ,直接个位加 1 返回即可
如果数组末位(个位)等于 9,将该位(个位)设置为 0 ,并且产生了进位,接下来观察前一位(十位)
如果前一位(十位)小于 9 ,直接十位加 1 返回即可
如果前一位(十位)等于 9,将该位(十位)设置为 0 ,并且产生了进位,接下来观察前一位(百位)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| // 最后一位计算得出新的sum sum = arr[arr.length - 1] + 1 // 判断sum是否>9 sum > 9 ? // >9 carry = 1 arr[i] = 0 // <9 arr[arr.length - 1] = sum return arr //倒数第二位重复进行上一步的操作
// 当我们完成以后,如果数组第一位时的sum大于0,那么我们就要给数组的首位增添一个1 result = new array with size of arr.length + 1 result[0] = 1 result[1] ...... result[result.length - 1] = 0
|
三、答案代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| /** * @param {number[]} digits * @return {number[]} */ var plusOne = function(digits) { //先遍历从右向左 for(let i = digits.length-1;i>=0;i--){ if(digits[i] !==9){ digits[i]++ return digits; }else{ // 是 9 digits[i] = 0 } }
let result = [1,...digits]; return result; };
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| var plusOne = function (digits) { var carry = 1; // 我们将初始的 +1 也当做是一个在个位的 carry for (var i = digits.length - 1; i > -1; i--) { if (carry) { var sum = carry + digits[i]; digits[i] = sum % 10; carry = sum > 9 ? 1 : 0; // 每次计算都会更新下一步需要用到的 carry } } if (carry === 1) { digits.unshift(1); // 如果carry最后停留在1,说明有需要额外的一个长度 所以我们就在首位增添一个 1 } return digits; };
|
四、总结
加一,队列题解
回看笔者往期高赞文章,也许能收获更多喔!
❤️关注+点赞+收藏+评论+转发❤️,原创不易,鼓励笔者创作更好的文章