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;
};