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

来源: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
  • C#.Net的BCL提供了豐富的類型,最基礎的是值類型、引用類型,而他們的共同(隱私)祖先是 System.Object(萬物之源),所以任何類型都可以轉換為Object。 ...
  • 最近有群友咨詢C#如何調用Python?小編嘗試Python.NET過程中遭遇的版本相容性和環境配置難題,小編決定尋找一個更為簡單、穩定且對初學者友好的解決方案。小編搜索一番,除了Python.NET之外,還有其他途徑能夠幫助我們輕鬆地在C#項目調用Python腳本,那就是通過命令行調用,使用 Sy ...
  • .NET中特性+反射 實現數據校驗 在.NET中,我們可以使用特性+反射來實現數據校驗。特性是一種用於為程式中的代碼添加元數據的機制。元數據是與程式中的代碼相關聯的數據,但不直接成為代碼的一部分。通過特性,我們可以為類、方法、屬性等添加額外的信息,這些信息可以在運行時通過反射獲取和使用。 對反射不太 ...
  • Biwen.Settings 是一個簡易的配置項管理模塊,主要的作用就是可以校驗並持久化配置項,比如將自己的配置存儲到資料庫中,JSON文件中等 使用上也是很簡單,只需要在服務中註入配置, 比如我們有一個GithubSetting的配置項,我們只需要定義好對象然後註入到Service中即可: [De ...
  • EDP是一套集組織架構,許可權框架【功能許可權,操作許可權,數據訪問許可權,WebApi許可權】,自動化日誌,動態Interface,WebApi管理等基礎功能於一體的,基於.net的企業應用開發框架。通過友好的編碼方式實現數據行、列許可權的管控。 ...
  • 前言 VB.NET,全名Visual Basic .NET,是Microsoft .NET框架的一部分,是一種面向對象的編程語言。它繼承了Visual Basic的易用性,同時增加了對面向對象編程的支持。VB.NET提供了大量的內置函數,使得開發者可以更容易地處理字元串、數學計算、文件和目錄訪問等任 ...
  • 自定義可移動點二維坐標軸控制項 目錄 路由參數 坐標軸控制項定義 Demo 路由參數 X_YResultCollection為當前X軸對應Y軸值存儲字典 public class ResultCollectionChangedEventArgs(RoutedEvent routedEvent, obje ...
  • 自定義分頁控制項 tip: 該控制項的樣式用的是materialDesign庫,需要下載Nuget包 Code Xaml <UserControl x:Class="TestTool.CustomControls.PagingControl" xmlns="http://schemas.microsof ...
  • 最近群里有個小伙伴把Dapper遷移SqlSugar幾個不能解決的問題進行一個彙總,我正好寫一篇文章來講解一下 一、sql where in傳參問題: SELECT * FROM users where id IN @ids 答: SqlSugar中應該是 var sql="SELECT * FRO ...
  • 安裝nuget包 Wesky.Net.OpenTools 1.0.8或以上版本。支持.net framework 4.6以上版本,以及所有.net core以及以上版本引用。 開發一個簡單的Winform界面,用來測試使用。如需該winform的demo,可以在公眾號【Dotnet Dancer】後 ...