前端程式員學好演算法系列(六)隊列

来源:https://www.cnblogs.com/kbnet/archive/2020/07/27/13385002.html
-Advertisement-
Play Games

利用隊列我們可以解決很多問題,js數組也可以實現隊列,隊列的思想為先近先出,js可以用 push和 shift() 很容易的實現一個隊列 給你一個二叉樹,請你返回其按 層序遍歷 得到的節點值。 (即逐層地,從左到右訪問所有節點)。 示例: 二叉樹:[3,9,20,null,null,15,7], 3 ...


利用隊列我們可以解決很多問題,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

};

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 作者:吉玉 智能化測試 在互動中經常需要維護大量的狀態,對這些狀態進行測試驗證成本較高,尤其是當有功能變動需要回歸測試的時候。為了降低開發測試的成本,在這方面使用強化學習模擬用戶行為,在兩個方面提效: mock介面:將學習過程中的狀態作為服務介面的測試數據; 回歸測試:根據mock介面數據回溯到特定 ...
  • 144. 二叉樹的前序遍歷給定一個二叉樹,返回它的 前序 遍歷。 示例: 輸入: [1,null,2,3] 1 \ 2 / 3 輸出: [1,2,3] 有兩種通用的遍歷樹的策略: 深度優先搜索(DFS) 在這個策略中,我們採用深度作為優先順序,以便從跟開始一直到達某個確定的葉子,然後再返回根到達另一個 ...
  • 當我們使用了websocket技術實現了實時的推送訪客來到消息,但是我們只能隨時看著頁面不離開才能知道有訪客來到 現在增加瀏覽器的通知消息,就可以只要打開著界面,不用一直盯著,乾別的事去就可以了,有新消息會從右下角彈出來 測試地址如下,當有訪客點擊咨詢按鈕時,客服後臺會彈出提示: https://g ...
  • 1.驗證ip地址 <input name="ip" class="mini-textbox" required emptyText="請輸入ip地址" onvalidation="isIpAddress" /> // ip地址驗證 function isIpAddress(e){ var reg = ...
  • 在日常佈局當中,肯定經常會遇到文本內容超過容器的情況。非常常見的一種解決方案是超出省略。 但是,有的時候,由於場景的限制,可能會出現在一些無法使用超出打點省略的方法的場景,譬如在導航欄中: 這種情況下,在容器定寬但是文本又溢出且不能換行的情況下,我們就需要尋求另外的解決方案。 hover 時彈出框提 ...
  • 在接觸 Web前端開發的一段時間,有時會去看Google或者百度的源代碼,有某些地方定義了 data-key ,這種語法 但是如果你直接去 Google data-key 或 data-item 可能又查不到這個屬性,到底這是哪個屬性呢? 通過查資料我發現,利用 HTML 5,可以為元素添加data ...
  • 1.js 前端將平級數據轉為樹形數據的方法 轉,實測成功 https://segmentfault.com/a/1190000022444269 // 將同級數據轉化為樹形結構 listToTree(dataSource) { // datasource是平級的數據來源 return dataSou ...
  • 給出一個 32 位的有符號整數,你需要將這個整數中每位上的數字進行反轉 示例 1: 輸入: 123 輸出: 321 示例 2: 輸入: -123 輸出: -321 示例 3: 輸入: 120 輸出: 21 /** * @param {number} x * @return {number} */ v ...
一周排行
    -Advertisement-
    Play Games
  • Github / Gitee QQ群(1群) : 813100564 / QQ群(2群) : 579033769 視頻教學 介紹 MiniWord .NET Word模板引擎,藉由Word模板和數據簡單、快速生成文件。 Getting Started 安裝 nuget link : https:// ...
  • Array.Sort Array類中相當實用的我認為是Sort方法,相比起冗長的冒泡排序,它的出現讓排序更加的簡化 結果如下: 還可以聲明一個靜態方法用來專門調用指定數組排序,從名為 array 的一維數組中 a 索引處開始,到 b 元素 從小到大排序。 註意: a + b 不能大於 array 的 ...
  • 前言 在上一篇文章CLR類型系統概述里提到,當運行時掛起時, 垃圾回收會執行堆棧遍歷器(stack walker)去拿到堆棧上值類型的大小和堆棧根。這裡我們來翻譯BotR里一篇專門介紹Stackwalking的文章,希望能加深理解。 順便說一句,StackWalker在中文里似乎還沒有統一的翻譯,J ...
  • 使用過 nginx 的小伙伴應該都知道,這個中間件是可以設置跨域的,作為今天的主角,同樣的 反向代理中間件的 YARP 毫無意外也支持了跨域請求設置。 有些小伙伴可能會問了,怎樣才算是跨域呢? 在 HTML 中,一些標簽,例如 img、a 等,還有我們非常熟悉的 Ajax,都是可以指向非本站的資源的 ...
  • 什麼是Git Git 是一個開源的分散式版本控制系統,用於敏捷高效地處理任何或小或大的項目。 Git 是 Linus Torvalds 為了幫助管理 Linux 內核開發而開發的一個開放源碼的版本控制軟體。 Git 與常用的版本控制工具 CVS, Subversion 等不同,它採用了分散式版本庫的 ...
  • 首先CR3是什麼,CR3是一個寄存器,該寄存器內保存有頁目錄表物理地址(PDBR地址),其實CR3內部存放的就是頁目錄表的記憶體基地址,運用CR3切換可實現對特定進程記憶體地址的強制讀寫操作,此類讀寫屬於有痕讀寫,多數驅動保護都會將這個地址改為無效,此時CR3讀寫就失效了,當然如果能找到CR3的正確地址... ...
  • 說明 onlyoffice為一款開源的office線上編輯組件,提供word/excel/ppt編輯保存操作 以下操作均基於centos8系統,officeonly鏡像版本7.1.2.23 鏡像下載地址:https://yunpan.360.cn/surl_y87CKKcPdY4 (提取碼:1f92 ...
  • 二叉樹查找指定的節點 前序查找的思路 1.先判斷當前節點的no是否等於要查找的 2.如果是相等,則返回當前節點 3.如果不等,則判斷當前節點的左子節點是否為空,如果不為空,則遞歸前序查找 4.如果左遞歸前序查找,找到節點,則返回,否繼續判斷,當前的節點的右子節點是否為空,如果不為空,則繼續向右遞歸前 ...
  • ##Invalid bound statement (not found)出現原因和解決方法 ###前言: 想必各位小伙伴在碼路上經常會碰到奇奇怪怪的事情,比如出現Invalid bound statement (not found),那今天我就來分析以下出現此問題的原因。 其實出現這個問題實質就是 ...
  • ###一、背景知識 爬蟲的本質就是一個socket客戶端與服務端的通信過程,如果我們有多個url待爬取,只用一個線程且採用串列的方式執行,那隻能等待爬取一個結束後才能繼續下一個,效率會非常低。 需要強調的是:對於單線程下串列N個任務,並不完全等同於低效,如果這N個任務都是純計算的任務,那麼該線程對c ...