华为OD算法复习5——栈与队列 Javascript

这些力扣题目来源：AI推荐+karshey博主

目录

232.用栈实现队列（通过）

225. 用队列实现栈（通过）

20. 有效的括号（通过）

1047. 删除字符串中的所有相邻重复项（通过）

150. 逆波兰表达式 求值（通过）

239. 滑动窗口最大值（通过）

347.前 K 个高频元素（通过）

232.用栈实现队列（通过）

232.用栈实现队列

var MyQueue = function() { this.stack=[]; }; /** * @param {number} x * @return {void} */ MyQueue.prototype.push = function(x) { this.stack.push(x); }; /** * @return {number} */ MyQueue.prototype.pop = function() { return this.stack.shift(); }; /** * @return {number} */ MyQueue.prototype.peek = function() { return this.stack[0]; }; /** * @return {boolean} */ MyQueue.prototype.empty = function() { if(this.stack.length==0) return true; else return false; }; var obj = new MyQueue() obj.push(3) console.log(obj); var param_2 = obj.pop() console.log(param_2); var param_3 = obj.peek() console.log(param_3); var param_4 = obj.empty() console.log(obj);

225. 用队列实现栈（通过）

225. 用队列实现栈

var MyStack = function() { this.stack = []; }; /** * @param {number} x * @return {void} */ MyStack.prototype.push = function(x) { this.stack.push(x) }; /** * @return {number} */ MyStack.prototype.pop = function() { let out = this.stack.pop(); return out; }; /** * @return {number} */ MyStack.prototype.top = function() { return this.stack[this.stack.length-1] }; /** * @return {boolean} */ MyStack.prototype.empty = function() { if(this.stack.length==0) return true; else return false; }; var obj = new MyStack() obj.push(3) console.log(obj); var param_2 = obj.pop() console.log(obj); console.log(param_2); var param_3 = obj.top() console.log(param_3); var param_4 = obj.empty() console.log(param_4);

20. 有效的括号（通过）

20. 有效的括号

使用栈来匹配。如果当前的字符串是“）”，“】”，“｝”，栈里面必须是对应的括号，否则直接返回false

如果是三个左括号，可以直接入栈

最后记得栈不为空代表匹配失败

/** * @param {string} s * @return {boolean} */ // let s = "()[]{}" // s = "()" // s = "(]" // s = "([])" s = "([)]" var isValid = function(s) { let stack=[]; let cur=-1; for(let i=0;i<s.length;i++){ if(s[i]=="("||s[i]=="["||s[i]=="{"){ stack.push(s[i]); cur++; continue; } if(cur==-1){ return false; } if (s[i]==")") { if(stack[cur]=="("){ stack.pop(); cur--; continue; } else { return false; } } if (s[i]=="]") { if(stack[cur]=="["){ stack.pop(); cur--; continue; } else { return false; } } if (s[i]=="}") { if(stack[cur]=="{"){ stack.pop(); cur--; continue; } else { return false; } } } if(cur==-1) return true; else return false; }; console.log(isValid(s))

1047. 删除字符串中的所有相邻重复项（通过）

1047. 删除字符串中的所有相邻重复项

/** * @param {string} s * @return {string} */ let s ="abbaca"; var removeDuplicates = function(s) { let arr =[]; arr.push(s[0]) let cur =0; for(let i=1;i<s.length;i++){ if(s[i]==arr[cur]) { cur--; arr.pop() } else { cur++; arr.push(s[i]) } } return arr.join("") }; console.log(removeDuplicates(s));

150. 逆波兰表达式 求值（通过）

150. 逆波兰表达式 求值

Math.trunc 专门可以向0截断，抛弃小数部分

注意顺序。先从栈里面pop出来是减数，而不是被减数

/** * @param {string[]} tokens * @return {number} */ // tokens = ["2","1","+","3","*"] // tokens = ["4","13","5","/","+"] tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] var evalRPN = function(tokens) { let numStack = []; for(let i=0;i<tokens.length;i++){ if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/"){ let num1 = numStack.pop(); let num2 = numStack.pop(); if(tokens[i]=="+") numStack.push(num2+num1); if(tokens[i]=="-") numStack.push(num2-num1); if(tokens[i]=="*") numStack.push(num2*num1); if(tokens[i]=="/") numStack.push(Math.trunc(num2/num1)) } else { numStack.push(parseInt(tokens[i])) } } return numStack.pop(); }; console.log(evalRPN(tokens));

239. 滑动窗口最大值（通过）

239. 滑动窗口最大值

建立一个栈存下标：只有在当前数字比站内数字小或者相等的情况下，才直接入栈，否则清空前面所有比当前数字小的下标。

这样可以保证栈里面的第一个数字永远是当前滑动窗口的最大值

每次滑动之后把最大值存起来

滑动之前还需要检查一下，当前存储的最大值下标是否不在滑动窗口的区间内

/** * @param {number[]} nums * @param {number} k * @return {number[]} */ // nums = [1,3,-1,-3,5,3,6,7], k = 3 // nums = [3,1,1,3], k=3; nums = [7,2,4], k=2; var maxSlidingWindow = function(nums, k) { let max=nums[0]; let myStack = []; let answer = [] for(let i=0;i<k;i++){ if(myStack.length==0 || nums[i]<=nums[myStack[myStack.length-1]] ){ myStack.push(i); } else { while(myStack.length!=0 && nums[myStack[myStack.length-1]]<nums[i]){ myStack.pop(); } myStack.push(i); } } answer.push(nums[myStack[0]]) for(let i=k;i<nums.length;i++){ if(myStack.length!=0 && myStack[0]<i-k+1){ myStack.shift(); } if(myStack.length==0 || nums[i]<=nums[myStack[myStack.length-1]] ){ myStack.push(i); } else { while(myStack.length!=0 && nums[myStack[myStack.length-1]]<nums[i]){ myStack.pop(); } myStack.push(i); } answer.push(nums[myStack[0]]); } return answer; }; console.log(maxSlidingWindow(nums,k));

347.前 K 个高频元素（通过）

347.前 K 个高频元素

先用对象存储每个数字的出现频率，然后利用sort（）自定义排序，最后用slice切割前k个高频数字

/** * @param {number[]} nums * @param {number} k * @return {number[]} */ nums = [1,1,1,2,2,3], k = 2 var topKFrequent = function(nums, k) { let stat = {}; for(let i=0;i<nums.length;i++){ if(stat[nums[i]]==undefined) stat[nums[i]]=1; else stat[nums[i]]+=1; } let ans = (Object.entries(stat).sort((a,b)=>b[1]-a[1])).map(item=>parseInt(item[0])).slice(0,k); return ans; }; console.log(topKFrequent(nums,k))