利用队列我们可以解决很多问题,js数组也可以实现队列,队列的思想为先近先出,js可以用 push和 shift() 很容易的实现一个队列 给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。 示例: 二叉树:[3,9,20,null,null,15,7], 3 / 9 20 / 15 7 返回其层次遍历结果: [ [3], [9,20], [15,7] ] 解题:
4.res[res.length-1] 能帮我们取到当前操作的师哪层节点。 /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {number[][]} */ var levelOrder = function(root) { let res = [] if(root==null){ return [] } let queue = [root] while(queue.length){ let len = queue.length let i = 0 res.push([]) while(i++ < len){ let node = queue.shift() res[res.length-1].push(node.val) if(node.left){ queue.push(node.left) } if(node.right){ queue.push(node.right) } } } return res }; 279. 完全平方数 示例 1: 输入: n = 12 输出: 3 解释: 12 = 4 + 4 + 4. 示例 2: 输入: n = 13 输出: 2 解释: 13 = 4 + 9. 解题: 1.创建队列queue 默认传入num = n step为0;
/** * @param {number} n * @return {number} */ var numSquares = function(n) { // 创建一个队列默认传入数字num和step 为0 if(n<=1){ return n } let queue = [{'num':n,'step':0}] let visited = {} visited[n] =true while(queue.length){ const {num , step} = queue.shift() if(num==0){ return step } for(let i = 1; num - i*i >=0; i++){ if(!visited[num-i*i]){ queue.push({'num':num-i*i,"step":step +1}) visited[num-i*i] = true } } } }; 我们单独对上题中的 num - i*i 重复求解进行优化,同时当a==0 是我们无需继续走完循环直接返回当前步数 step + 1 for(let i = 1; ; i++){ let a = num - i*i if(a<0) break; if(a==0) return step +1; if(!visited[num-i*i]){ queue.push({'num':num-i*i,"step":step +1}) visited[num-i*i] = true } } 347. 前 K 个高频元素 示例 1: 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例 2: 输入: nums = [1], k = 1 输出: [1] 解题: /** * @param {number[]} nums * @param {number} k * @return {number[]} */ var topKFrequent = function(nums, k) { let obj = {} for(let i =0;i<nums.length;i++){ if(!obj[nums[i]]){ obj[nums[i]] = 1 } else { obj[nums[i]] = obj[nums[i]] + 1 } } // priority_queue 保存的内容为[元素的频率,元素值] let priority_queue = [] for(let i in obj){ // if(priority_queue.length==k){ priority_queue.push([obj[i],i]) // } } if(priority_queue.length==1){ return [priority_queue[0][1]] } priority_queue.sort((a,b)=>b[0]-a[0]) let res= [] for(let i =0;i<priority_queue.length;i++){ if(res.length<k){ res.push(priority_queue[i][1]) }else { return res } } return res };
|
|