前端算法題目解析（二）
- 2020 年 2 月 24 日
- 筆記
前言
雖然疫情還是嚴峻，但總會過去。在此居家辦公之際，應該趁這個時機好好提升下自我，多讀書多看報，少吃零食多運動哈哈。
最近看一些文章和題目有接觸一些算法題，我整理了一下收錄daily-question 的 algorithm 文件夾中，後續會繼續增加，本文分享我整理的十個算法題目。
11-計算矩陣中的島個數
問題描述：
一個矩陣中只有 0 和 1 兩種值，每個位置都可以和自己的上、下、左、右 四個位置相連，如果有一片 1 連在一起，這個部分叫做一個島，求一個矩陣中有多少個島？
舉例： 下面這個矩陣中有4個島。
let arrIsland = [ [0,0,1,0,1,0], [1,1,1,0,1,0], [1,0,0,1,0,0], [0,0,0,0,0,1] ] // 四個島分別是 【(0,2)(1,0)(1,1)(1,2)(2,0)】 【(0,5),(1,5)】 【(2,3)】【(3,5)】
思路：
- 用遞歸與雙循環實現，循環中遞歸找到一個島（即找出 1 及其上下左右的 1），將此島標記（我標記為2），然後重複依次找出剩下的島
- 注意邊界情況及不等於1的情況，此時應結束遞歸。
參考答案：
function islandCount(arr){ if (!arr || arr.length === 0) { return; }; let N = arr.length, M = arr[0].length, res = 0; for(let i = 0; i < N; i++){ for(let j = 0; j < M; j++){ if (arr[i][j] === 1) { ++res; infect(arr,i,j,N,M); } } } return res; } // 遞歸函數，傳入 數組arr, x坐標 i, y坐標j 數組長度N及數組內元素長度M function infect(arr,i,j,N,M){ // 處理邊界情況及不為1的情況，此時結束遞歸 if (i < 0 || j < 0 || i >= N || j >= M || arr[i][j] !== 1) { return; }; arr[i][j] = 2; // 將找到的島元素標記，避免重複 infect(arr,i,j-1,N,M); // 向左尋找 infect(arr,i+1,j,N,M); // 向右尋找 infect(arr,i,j+1,N,M); // 向下尋找 infect(arr,i-1,j,N,M); // 向上尋找 } let arrIsland = [ [0,0,1,0,1,0], [1,1,1,0,1,0], [1,0,0,1,0,0], [0,0,0,0,0,1] ]; console.log(islandCount(arrIsland)); // 4 複製代碼
12-漢諾塔問題
關於漢諾塔：
漢諾塔：漢諾塔（又稱河內塔）問題是源於印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞着64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。
思路：
- 遞歸解決：把問題轉化為規模縮小了的同類問題的子問題；
- 明確遞歸結束的條件(base case)：n == 1
- 其他過程：from：來源地；to：目的地；help：輔助。
參考答案：
function hanoiProcess(n,from,to,help){ if (n < 1) { return; } if (n == 1) { // 最後一個從from移到to console.log("Move 1 from " + from + " to " + to); } else{ hanoiProcess(n-1, from, help, to); // 前n-1個從from移到help上，可以藉助to console.log("Move "+ n +" from " + from + " to " + to); hanoiProcess(n-1, help, to, from); // 再把n-1個從help移到to，可以藉助from } } hanoiProcess(3, "左", "右", "中"); // Move 1 from 左 to 右 // Move 2 from 左 to 中 // Move 1 from 右 to 中 // Move 3 from 左 to 右 // Move 1 from 中 to 左 // Move 2 from 中 to 右 // Move 1 from 左 to 右 複製代碼
13-母牛生母牛
問題描述：
母牛每年生一隻母牛，新出生的母牛成長三年後也能每年生一隻母牛，假設不會死。求 N 年後，母牛的數量。
思路：
- 因為新生的母牛，只有等到第四年才能生小母牛。所以前 4 年，只有原來的一頭母牛每年生一頭。
- 第一年：原始牛 共 1 頭
- 第二年：原始牛生了 牛 A 共兩頭
- 第三年： 原始牛生了 牛 A , 牛 B 共三頭
- 第四年： 原始牛生了 牛 A , 牛 B, 牛 C ，共四頭
- 第五年： 原始牛生了 牛 A , 牛 B, 牛 C，牛 D 共五頭， 牛 A 生了牛 A1 共兩頭，其中牛 A 多算了一次。我們將牛 A 視為一頭新的原始牛抽離出去，則原來的原始牛生了 牛 B, 牛 C，牛 D 共四頭， 新原始牛生了牛 A1 共兩頭，從這裡你會發現，第五年剩的數量 = 第四年生的的數量 + 第二年生的數量
- 接着算第六年：原始牛生了 牛 A , 牛 B, 牛 C，牛 D，牛 F 共六頭，牛 A 生了牛 A1,牛 A2 共三頭, 牛 B 生了牛 B1 共兩頭
單獨把牛 A 拿出來做原始牛，你會發現剩下的
原始牛生了 牛B, 牛C，牛D，牛F， 牛B生了牛B1共兩頭與第五年的情況原始牛生了 牛A , 牛B, 牛C，牛D 共五頭， 牛A生了牛A1共兩頭及其相似，數量規則一致只是名字不一樣而已，那麼 第六年的數量 = 第五年的數量 + 第三年的數量，以此類推可以得出 f(n) = f(n-1) + f(n-3), 當 n <= 4 時， f(n) = n, 是不是有點斐波那契數列的感覺？？可以用遞歸實現！！
參考答案：
function cow(n) { if (n < 1) { return; } let count = 0; if (n > 4) { count = cow(n - 1) + cow(n - 3); } else { count = n; } return count; } let n = 7; console.log(n + ' 年後，牛的數量是： ' + cow(n)); // 7 年後，牛的數量是： 13 複製代碼
14-找出字符串中出現最多的字母
例如字符串： （ababccdeajxac）
- 最先想到的解法是用 map 紀錄每個字符的次數，然後找出最多的即可：
function getMaxNumberOfChar(str) { return (str + '').split('').reduce( function(pre, cur, index, arr) { cur in pre ? pre[cur]++ : (pre[cur] = 1); pre[cur] > pre.value && ((pre.char = cur), (pre.value = pre[cur])); return pre; }, { value: 0 } ); } getMaxNumberOfChar('ababccdeajxac'); // Object {value: 4, a: 4, char: "a", b: 2, c: 3…} 複製代碼
此外，可以考慮用正則來輔助處理：
function getMaxNumberOfChar(str) { return (str + '') .split('') .sort() .join('') .match(/(w)1*/g) // 1表示w匹配到的字母 1是匹配第一個分組匹配到的內容 .reduce( function(pre, cur) { return cur.length > pre.value ? { value: cur.length, char: cur[0] } : pre; }, { value: 0 } ); } getMaxNumberOfChar('ababccdeajxac'); // Object {value: 4, char: "a"} 複製代碼
這裡拓展一下 reduce 函數的用法
// reduce 函數 // array.reduce(function(accumulator, currentValue, currentIndex, arr), initialValue) // reducer回調函數本身接受幾個參數，第一個參數是 accumulator 累加器，第二個是數組中的 item，第三個參數是該項的索引，最後一個參數是原始數組的引用。 // initialValue 為reduce初始值，否則視數組第一個值為初始值，選填 const array1 = [1, 2, 3, 4]; // 1 + 2 + 3 + 4 console.log( array1.reduce((accumulator, currentValue) => { console.log(accumulator, currentValue); return accumulator + currentValue; }) ); 複製代碼
15-解析 URL 參數為對象
儘可能的全面正確的解析一個任意 url 的所有參數為 Object，注意邊界條件的處理
let url = 'http://www.suporka.com/?user=suporka&id=123&id=456&city=%E5%8C%97%E4%BA%AC&enabled'; parseParam(url); /* 結果 { user: 'suporka', id: [ 123, 456 ], // 重複出現的 key 要組裝成數組，能被轉成數字的就轉成數字類型 city: '北京', // 中文需解碼 enabled: true, // 未指定值得 key 約定為 true } */
解法
function parseParam(url) { const paramsStr = /.+?(.+)$/.exec(url)[1]; // 將 ? 後面的字符串取出來 const paramsArr = paramsStr.split('&'); // 將字符串以 & 分割後存到數組中 let paramsObj = {}; // 將 params 存到對象中 paramsArr.forEach(param => { if (/=/.test(param)) { // 處理有 value 的參數 let [key, val] = param.split('='); // 分割 key 和 value val = decodeURIComponent(val); // 解碼 val = /^d+$/.test(val) ? parseFloat(val) : val; // 判斷是否轉為數字 if (paramsObj.hasOwnProperty(key)) { // 如果對象有 key，則添加一個值 paramsObj[key] = [].concat(paramsObj[key], val); } else { // 如果對象沒有這個 key，創建 key 並設置值 paramsObj[key] = val; } } else { // 處理沒有 value 的參數 paramsObj[param] = true; } }); return paramsObj; } 複製代碼
16. 走樓梯的動態規劃
題目：
樓梯台階有 12 階，一步只能走 1 階或者 2 階，那麼，請問走完樓梯有多少走法？
這裡涉及到動態規劃，所謂動態規劃，意思就是說，大事化小，小事化了。術語的話，包含三個，最優子結構，邊界，狀態轉移公式
再來分析這道題目——
- 走到最後一個台階的前一個情況，只能有兩種，就是從第 11 台階走一步上來，或者從 10 台階走兩步上來，那麼不管有多少走法走到了 11 階假設是 X 種走法吧，假設是 Y 種走法走到了 10 階，那麼，走到 12 階的走法一定是 X+Y，這個是成立的吧。這就是最優子結構
- 那什麼是邊界呢？本例子中，走到第一個台階，就一種走法吧，沒有台階，那就 0 種走法吧，走到第二個台階，也就 2 種走法，其實這就是邊界了。
- 那麼狀態轉移公式就水到渠成了, F(n) = F(n-1) + F(n-2)，看起來是不是有點像斐波那契數列？？
代碼如下：
function fun(n) { if (n < 0) { return 0; } if (n === 1) { return 1; } if (n === 2) { return 2; } return fun(n - 1) + fun(n - 2); } console.log('12台階的走法 ：' + fun(12)); 複製代碼
我們之前在斐波那契數列裏面講過，這種遞歸有性能問題，根據斐波那契數列的優化，改寫代碼如下：
function fun(n) { if (n < 0) { return 0; } if (n === 1) { return 1; } if (n === 2) { return 2; } var a = 1; var b = 2; var temp = 0; for (var i = 3; i <= n; i++) { temp = a + b; a = b; b = temp; } return temp; } console.log('12台階的走法 ：' + fun(12)); 複製代碼
17-數組中找出和為 M 的 N 個數
先來道簡單的題目：
給定一個整數數組 nums 和一個目標值 target，請你在該數組中找出和為目標值的那 兩個 整數，並返回他們組成的數組。 你不能重複利用這個數組中同樣的元素。
比較容易想到的方法是用兩層循環，不斷遍歷找出和為目標值的兩個元素，然後存進數組。
var nums = [8, 9, 2, 15, 7, 1]; var target = 9; var twoSum = function(nums, target) { var result = []; for (var i = 0; i < nums.length; i++) { for (var j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] === target) { result.push([nums[i], nums[j]]); } } } return result; }; console.log(twoSum(nums, target)); //[ [ 8, 1 ], [ 2, 7 ] ] 複製代碼
如果要求我們使用遞歸，該如何實現呢？
這個和我上一個算法《走樓梯的動態規劃》有些相似，我們也來動態規划下：
假設數組和目標值如下
var nums = [8, 9, 2, 15, 7, 1]; var target = 9;
- 首先我們拿出第一個元素 8 ，再從後面剩下的
[9, 2, 15, 7 ,1]找9-8 (即1), 找到與目標值差值（這裡是 1）則返回這個組合，找不到返回空數組 - 然後再從剩下的
[9, 2, 15, 7 ,1]找出組合值等於目標值的數組，即重複 1 步驟 - 將 1，2 步驟合併就是我們所求的組合
- 狀態轉移公式為 f(n) = f(n 首項與目標值差值組合).concat(f(n – 1))
- 邊界。當數組長度小於取出元素個數時，返回空數組。當取出元素為 1 時，返回目標值數組。
// 以下是代碼 var nums = [8, 9, 2, 15, 7, 1]; var target = 10; function search(arr, m, n = 2) { if (arr.length < n) return []; if (n === 1) return arr.filter(i => i === m); return search(arr.slice(1), m - arr[0], 1) .map(item => [arr[0], item]) .concat(search(arr.slice(1), m)); } console.log(search(nums, target)); 複製代碼
升級版
從一個數組中找出 N 個數，其和為 M 的所有可能
從上面得知，如果使用循環，取出 2 個數就是兩層循環，3 個數就是三層循環，以此類推，n 越大循環越多，顯然不可取。所以選擇第二種方法，也就是遞歸。
上面已經為我們寫好了遞歸的雛形，現在對其進行改造
上面邊界 n === 1 其實還可以降為 0, 因為當 n === 0 && m === 0 時，上一步的 arr[0] 就是我們要找的最後一個數,而且在 map 函數中，我們已經將 arr[0] 置為首位，此時只要返回一個長度為 1 且首項為空的數組（[[]]），並且在 map 函數中將其 item([]) 展開即可
註：這裡要花點時間好好理解下，比較繞
// 代碼如下 function search(arr, m, n) { if (n === 0) return m === 0 ? [[]] : []; if (arr.length < n) return []; return search(arr.slice(1), m - arr[0], n - 1) .map(item => [arr[0], ...item]) .concat(search(arr.slice(1), m, n)); } // 測試一下 var nums = [8, 9, 2, 15, 7, 1]; var target = 10; console.log(search(nums, target, 3)); // [[2,7,1]] 複製代碼
18-數組中找出和為 M 的 N 個數(番外篇)
還是同樣的問題：
從一個數組中找出 N 個數，其和為 M 的所有可能
數組中選取不固定數值 N ，我們可以嘗試着使用標記的方式，我們把 1 表示成選取狀態， 把 0 表示成未選取狀態。
假設數組 const arr=[1,2,3,4] ，對應着每個元素都有標記 0 或者 1 。如果 N=4 ，也就是在這個數組中，需要選擇 4 個元素，那麼對應的標記就只有一種可能 1111 ，如果 N=3 ，那就有 4 種可能，分別是 1110 、 1101 、1011 以及 0111 (也就是 C4 取 3->4 ) 種可能。
標記中有幾個 1 就是代表選取了幾個數，然後再去遍歷這些 1 所有可能存在的排列方式，最後做一個判斷，這個判斷就是：每一種排列方式，都代表着數組中不同位置的被選中的數的組合，所以這裡就是將選中的這些數字，進行求和運算，然後判斷求出的和是不是等於 M 。
如何將數組和標記關聯
0101 明顯就是二進制嘛
對於 arr 來說，有 4 個元素，對應的選擇方式就是從 0000（ N = 0 ）到 1111( N = 4 )的所有可能。
而 1111 就是 15 的二進制，也就是說這所有的可能其實對應的就是 0 – 15 中所有數對應的二進制。
這裡的問題最終變成了如何從數組長度 4 推導出 0 – 15
這裡採用了位運算–左移運算， 1 << 4 的結果是 16 。 所以我們可以建立這樣一個迭代：
const arr = [1, 2, 3, 4]; let len = arr.length, bit = 1 << len; // 這裡忽略了 0 的情況(N = 0)，取值就是 1 - 15 for (let i = 1; i < bit; i++) { // ... }
如何從 1110 標記中取出 1 的個數
最簡單的方式：
const n = num => num.toString(2).replace(/0/g, '').length; 複製代碼
這其實也是一道算法常考題，因為位運算是不需要編譯的，肯定速度最快。
PS: 如果不理解位運算為何會提高性能的同學，可以自行搜索一下位運算。簡單點說就是：位運算直接用二進制進行表示，省去了中間過程的各種複雜轉換，提高了速度。
我們嘗試使用 & 運算來解決這個問題
首先我們肯定知道 1 & 1 = 1; 1 & 0 = 0 這些結論的。所以我們從 15 & 14 => 14 可以推導出 1111 & 1110 => 1110 ，為什麼可以這樣推導呢，因為 15 的二進制就是 1111 ，14 同理。
我們可以看到，通過上面的操作消掉了最後的 1。
所以我們可以建立一個迭代，通過統計消除的次數，就能確定最終有幾個 1 了。代碼如下：
const n = num => { let count = 0; while (num) { num &= num - 1; count++; } return count; }; 複製代碼
計算和等於 M
現在我們已經可以把所有的選取可能轉變為遍歷一個數組，然後通過迭代數組中的每個數對應的二進制，有幾個 1 來確定選取元素的個數。
那麼，現在需要的最後一層判斷就是選取的這些數字和必須等於 M
這裡其實就是建立一個映射：
1110 到 [1, 2, 3, 4] 的映射，就代表選取了 2, 3, 4，然後判斷 2 + 3 + 4 與 M 。
這裡可以這樣看：1110 中的左邊第一個 1 對應着數組 [1, 2, 3, 4] 中的 1 。
現在有一個問題，該如何建立這個映射關係呢？
我們知道前者 1110 其實就是對應的外層遍歷中的 i = 14 的情況。
再看看數組[1, 2, 3, 4] ，我們可以將元素及其位置分別映射為 1000 0100 0010 0001。
實現方式也是通過位運算–左位移來實現：
1 << inx ，inx 為數組的下標。
位掩碼介紹
對 位掩碼 不熟悉的童鞋會有點暈，這裡簡單科普下：
實質上，這裡的 1 << j ，是指使用 1 的移位來生成其中僅設置第 j 位的位掩碼。
比如：14 的二進制表示為 1110，其代表（從右往左）選取了第 2 , 3 , 4 位。
那麼(下面故意寫成上下對應的方式)：
// demo1 1110 & 0001 = 0000; // demo2 1110 & 0010 = 0010;
PS: 通過上面代碼，我們可以看到上下對應的 0 和 1 在進行 & 運算以後，得出的結果和在 js 中進行相同條件下 & 運算的結果相同。
所以：
1 << 0 // 1 -> 0001 1 << 1 // 2 -> 0010 1 << 2 // 4 -> 0100 1 << 3 // 8 -> 1000 // 說白了，就是把左邊的值變成二進制形式，然後左移或者右移，超出補 0 // 所以， 1110 對應着 第一位沒有選取，那麼 1110 & 0001(設置為第一位的位掩碼) = 0，如果 i & (1 << inx) !== 0 代表該位被選取了 for(let j = 0; j < arr.length; j++){ if((i & (1 << j) !== 0) { // 代表這個數被選取了，我們做累加求和就行 } }
複製代碼所以綜上所述，最終代碼實現如下：
// 參數依次為目標數組、選取元素數目、目標和 const search = (arr, count, sum) => { // 計算某選擇情況下有幾個 `1`，也就是選擇元素的個數 const n = num => { let count = 0; while (num) { num &= num - 1; count++; } return count; }; let len = arr.length, bit = 1 << len, res = []; // 遍歷所有的選擇情況 for (let i = 1; i < bit; i++) { // 滿足選擇的元素個數 === count if (n(i) === count) { let s = 0, temp = []; // 每一種滿足個數為 N 的選擇情況下，繼續判斷是否滿足 和為 M for (let j = 0; j < len; j++) { // 建立映射，找出選擇位上的元素 if ((i & (1 << j)) !== 0) { s += arr[j]; temp.push(arr[j]); } } // 如果這種選擇情況滿足和為 M if (s === sum) { res.push(temp); } } } return res; }; 複製代碼
總結
這裡位操作思路和代碼都很棒。但是 bit 位移有溢出問題。當數組長度大於 30 的時候，位操作已經溢出不精準。因此僅供參考其思想，不能作為其標準答案。
原文地址: 從一個數組中找出 N 個數，其和為 M 的所有可能–最 nice 的解法
19-TOP-k 問題
問題: 輸入 n 個整數，找出其中最大的 K 個數。例如輸入 4,5,1,6,2,7,3,8 這 8 個數字，則最大的 4 個數字是 8,7,6,5,。
比較簡單的是將這些數字組合成一個數組，然後進行從大到小進行排序，取前 K 個即可。
選擇算法
對整個數組進行排序有點浪費，我們只是取前 K 個，後面剩下的不進行排序也行。因此，對此數組使用選擇算法獲取前 K 個數即可。
function getLargeNumber(array, k) { if (array == null || k <= 0 || k > array.length) { return []; } let length = array.length, i, j, maxIndex, maxValue, temp; for (i = 0; i < k; i++) { maxIndex = i; maxValue = array[maxIndex]; for (j = i + 1; j < length; j++) { //通過循環選出最小的 if (array[j] > maxValue) { maxIndex = j; maxValue = array[maxIndex]; } } // 交換位置 temp = array[i]; array[i] = maxValue; array[maxIndex] = temp; } return array.slice(0, k); } // 測試一下 var nums = [8, 9, 2, 15, 7, 1]; console.log(getLargeNumber(nums, 3)); // [15,9,8] 複製代碼
快排算法
我們可以利用快排中 partion 函數的思想來做做題。
因為 partion 可以使得序列分為 2 部分：左邊的值都小於哨兵，右邊的值都大於哨兵。所以我們只要找到處於第 k 位置的哨兵即可，也就是說找到第 k 大的值所在的位置即可，那麼它的左邊的 k-1 值都小於等於第 k 大值。顯然，前 k 個值即為我們所求的最小 k 個數。在我們的劃分過程有 3 種情況：
- 哨兵的位置大於 k，說明第 k 大的數在左邊，繼續遞歸處理左部分即可。
- 哨兵的位置小於 k，說明第 K 大的數在右邊，繼續遞歸處理有部分即可。
- 哨兵的位置等於 k，說明該哨兵即為第 K 大的值，其左邊 k-1 個數都小於等於它，因此輸出前 k 個即為所求的結果。
var nums = [8, 9, 2, 15, 7, 1, 13, 35, 24]; function getLargeNumber(array, k) { if (array == null || k <= 0 || k > array.length) { return []; } partition(array, 0, array.length - 1, k - 1); return array.slice(0, k); } function partition(array, low, high, k) { if (low < high) { // 獲取 low 至 high 之間一個隨機數 let pivot = Math.floor(Math.random() * (high - low + 1)) + low; // 此隨機數對應的元素與最後一位暫時交換（後面會再交換一次），我們先找到有多少個數大於此隨機數，大的話從左到右排列 swap(array, pivot, high); let index = low; for (let i = low; i < high; i++) { if (array[i] > array[high]) { // 這裡便是一次選擇排序 swap(array, i, index); index++; } } // 交換數組第index個和剛才置於數組末尾的隨機數組元素，這樣array[index]左邊的數都比array[index]大 swap(array, index, high); // 如果index > k，說明我們剛才排的範圍過大，應該縮小範圍再次遞歸尋找 // 如果 index < k，說明我們剛才拍的範圍過小，應該擴大範圍再次遞歸尋找 if (index > k) { partition(array, low, index - 1, k); } else if (index < k) { partition(array, index + 1, high, k); } } } function swap(array, one, two) { [array[one], array[two]] = [array[two], array[one]]; } console.log(getLargeNumber(nums, 3)); // [35,24,15] 複製代碼
最小堆
我們知道，最小堆的頂部結點為該堆的最小值，因此我們創建一個具有 K 的節點的最小堆（可以先取該數組的前 K 個元素）調整為最小堆。
之後將第 K + 1 個元素與堆頂對比，如果大於堆頂元素，則說明堆頂元素不是第 K 大的值，因此將堆頂元素替換為第 K + 1 個元素，並調整此最小堆，以此類推至數組的最後一個元素，則最後整個最小堆即為所求答案。
// 建立堆 function buildHeap(nums) { // 注意這裡的頭節點是從0開始的，所以最後一個非葉子結點是 parseInt(nums.length/2)-1 let start = parseInt(nums.length / 2) - 1; let size = nums.length; // 從最後一個非葉子結點開始調整，直至堆頂。 for (let i = start; i >= 0; i--) { adjustHeap(nums, i, size); } return nums; } // 調整最小堆，使index的值小于于左右節點 function adjustHeap(nums, index, size) { // 交換後可能會破壞堆結構，需要循環使得每一個父節點都大於左右結點 while (true) { let min = index; let left = index * 2 + 1; // 左節點 let right = index * 2 + 2; // 右節點 if (left < size && nums[min] > nums[left]) min = left; if (right < size && nums[min] > nums[right]) min = right; // 如果左右結點大於當前的結點則交換，並再循環一遍判斷交換後的左右結點位置是否破壞了堆結構（比左右結點小了） if (index !== min) { [nums[index], nums[min]] = [nums[min], nums[index]]; index = min; } else { break; } } } // 獲取最大的前K個數 function getLargeNumber(nums, k) { // 創建一個具有 K 的節點的最小堆（可以先取該數組的前 K 個元素）調整為最小堆。 let minHeap = buildHeap(nums.slice(0, k)); for (let i = k; i < nums.length; i++) { // 將第 i 個元素與堆頂對比，如果大於堆頂元素，則說明堆頂元素不是第 K 大的值，因此將堆頂元素替換為第 i 個元素 if (minHeap[0] < nums[i]) { minHeap[0] = nums[i]; // 替換後調整此最小堆 adjustHeap(minHeap, 0, k); } } return minHeap; } var nums = [8, 9, 2, 15, 7, 1, 13, 35, 24]; console.log(getLargeNumber(nums, 4)); // [13,15,24,35] 複製代碼
20-判斷一個數是否為丑數
何為丑數？丑數就是只包含質因數 2, 3, 5 的正整數。
試着寫出一個函數，判斷傳入的是否為丑數？
function isUgly (num) { if (typeof +num !== 'number') return false if (num < 1) return false; // 從大往小除，先從5開始 while(num % 5 === 0) { num /= 5; } while(num % 3 === 0) { num /= 3; } while(num % 2 === 0) { num /= 2; } return num === 1; } // 測試一下 isUgly(18) // true isUgly(7) // false 複製代碼
