前端程式員學好演算法系列（六）佇列

利用佇列我們可以解決很多問題，js陣列也可以實作佇列，佇列的思想為先近先出，js可以用 push和 shift() 很容易的實作一個佇列

給你一個二叉樹，請你回傳其按 層序遍歷 得到的節點值， （即逐層地，從左到右訪問所有節點），

示例：

二叉樹：[3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7

回傳其層次遍歷結果：

[
[3],
[9,20],
[15,7]
]

解題：

1.root為空師回傳 []
2.定義佇列為queue，默認在queue中傳入root節點
3.我們記錄一下當前節點的層級i，每次從佇列頭部取出一個節點，如果該節點有左右節點值就把左右節點都重新放入佇列

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. 完全平方數
給定正整數 n，找到若干個完全平方數（比如 1, 4, 9, 16, ...）使得它們的和等于 n，你需要讓組成和的完全平方數的個數最少，

示例 1:

輸入: n = 12
輸出: 3 
解釋: 12 = 4 + 4 + 4.

示例 2:

輸入: n = 13
輸出: 2
解釋: 13 = 4 + 9.

解題：

1.創建佇列queue 默認傳入num = n step為0；
2.創建visited 物件記錄 num - i*i 的值是否訪問過，訪問過時無需重復訪問；
3.操作佇列彈出隊首節點，操作彈出的節點 —— 根據業務生成子節點，判斷這些節點 —— 符合業務條件，則return，不符合業務條件，且不在已訪問集合，則追加到隊尾，并加入已訪問集合

/**
 * @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 個高頻元素
給定一個非空的整數陣列，回傳其中出現頻率前 k 高的元素，

示例 1:

輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2]

示例 2:

輸入: nums = [1], k = 1
輸出: [1]

解題：
1.遍歷一遍陣列統計每個元素的數量
2.定義priority_queue 保存 [元素的頻率，元素的值]
3.排序陣列（這里應該用最小堆進行排序）
4.建立res 獲取到需要的值

/**
 * @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

};

標籤：JavaScript

上一篇：JS腳本獲取URL資訊的方法

下一篇：整數反轉