Leetcode-279. 完全平方数，BFS建模深度分析

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

解题思路
BFS解法，干净利落。
起初我想不通为什么用BFS,这题与BFS又有什么关系，相信很多刷题量不是很多的朋友也会有同样的困惑。
我们可以先刻意的把这题往BFS上靠，然后等越靠越近的时候，你就慢慢有感觉了，就会明白与BFS的微妙关系了，具体又该怎么靠呢？
还记得我们初次接触BFS，是在层序遍历树的时候，遍历树的时候，首先会不会得从根节点出发，层层遍历，没见过从最底层节点开始层序遍历这种玩法把？

BFS建模
那么放在本题，既然要用BFS, 肯定得找一个根节点，这个根节点就是题目给的数字 n，然后我们的目标就是 [搜索]，将n 变成 0 的最短步数（可以理解每遍历一层就相当于走了一步）。到这里你可能脑海中还是没有树的形状，主要原因在于你现在脑海中的 n 是个比较小的数字，所以构建不出树的形状，比如 n=4，它本身就是完全平方数，自然就不能很好的扩散出树的形状，这时候我们可以把 n 取一个不大不小的数字 12.

641036134c746b8bba3be26299a9cbd8493950dba92edcf50408031903c4f37c.jpg

class Solution { 
    public int numSquares(int n) { 
          Queue<int[]> queue = new LinkedList<>(); 
          boolean[] vis = new boolean[n+1]; //int数组的第一个数字表示的是当前的数字，第二个数字表示，需要走几步才能到达数字n 
         //因为是从根节点 n 开始遍历的，所以我一上来就能访问到 n，即可直接到达n, 走0步即可。 
          queue.add(new int[]{n,0}); 
          vis[n] = true; 
          while(!queue.isEmpty()) { 
         int size = queue.size(); 
        for(int i = 0; i < size; i++) { 
             int[] cur = queue.poll(); 
            if(cur[0] == 0) return cur[1]; 
          //这个循环是精华所在，作用就是将13 依次分割成12 9 4 
         for(int j = 1; ; j++) { 
            int a = cur[0] - j*j; if(a < 0) break; 
            if(a == 0) 
              return cur[1] + 1; 
           if(!vis[a]) { 
           //为什么步数+1 ？因为我当前数字a,比如是9，我可以由 13-4分割而来，并且4是一个完全平方数，这个-4就说明走了一步， 所以+1 
        queue.add(new int[]{a, cur[1] + 1}); vis[a] = true; } } } } return -1; } }