Leetcode279完全平方數（工商銀行面試題）：廣度優先搜尋.md

類似的題目參考： ES6廣度優先搜尋：最長回文字元串leetcode5.md

背景

今天做LeetCode的時候，偶爾翻看了一下題目所屬的企業，發現有工商銀行。作為一個在工商銀行軟體開發中心工作過10年以上的前員工，感慨，哇塞，看來技術人員招聘上與時俱進了。

這些題目總體上難度不算低，很好奇，于是就進去挨個做起來。

Leetcode279 完全平方數

答題語言

這道題目一年多前我用java做過，最近在搞前端和可視化，于是我拿出JavaScript（es6）做下。題外話，我覺得面試用js答題是不錯的選擇：

• 代碼量一般比java少是以顯得簡潔
• 數組的功能也很強大（比如這題答題中我js一個數組就行，java要分一個數組一個Set）

• 而且LeetCode裡面大部分題目都是不用多線程的

  總之，比較适合面試的場景。

題幹

https://leetcode-cn.com/problems/perfect-squares/

給定正整數 n，找到若幹個完全平方數（比如 1, 4, 9, 16, ...）使得它們的和等于 n。你需要讓組成和的完全平方數的個數最少。
           

思路

1. 廣度優先搜尋

   建立一個隊列，用于廣度優先搜尋，廣度優先搜尋是層層推進的，當到某層符合條件了，就break，傳回ans；注意，這裡不能用深度優先搜尋，大家思考下為什麼。

2. 四平方數定理

   這個問題本身是存在數值解的。大家可以搜尋下"四平方數定理"，所有我在循環設定了超過4層就退出的條件，提升算法效率

3. 候選數用數組緩存起來

代碼

var numSquares = function(n) {
        //4平方數定律，最大的傳回值不超過4，而且先把候選數用數組緩存起來
        let ans = 4;
        const squared = [10000,9801,9604,9409,9216,9025,8836,8649,8464,8281,8100,7921,7744,7569,7396,7225,7056,6889,6724,6561,6400,6241,6084,5929,5776,5625,5476,5329,5184,5041,4900,4761,4624,4489,4356,4225,4096,3969,3844,3721,3600,3481,3364,3249,3136,3025,2916,2809,2704,2601,2500,2401,2304,2209,2116,2025,1936,1849,1764,1681,1600,1521,1444,1369,1296,1225,1156,1089,1024,961,900,841,784,729,676,625,576,529,484,441,400,361,324,289,256,225,196,169,144,121,100,81,64,49,36,25,16,9,4,1];
        //建立一個隊列，用于廣度優先搜尋，廣度優先搜尋是層層推進的，當到某層符合條件了，就break，傳回ans
        const q = [];
        q.push(n);
        let level= 0;
        while (q.length > 0) {
            const size = q.length;
            level++;
            if (level >= 4) break;
            for (let i=0; i<size; i++) {
                const item = q.shift();
                //console.log('q=%o size=%o item=%o level=%o', q, size, item, level);
                if (squared.includes(item)) {
                    return level;
                } else {
                    for (let i=squared.length-1; i>=0; i--) {
                        if (squared[i] < item) q.push(item - squared[i]);
                        else break;
                    }
                }
            }
        }
        return ans;
};