279. 完全平方数

一、题目描述

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

示例 1:

输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4.

示例 2:

输入: n = 13
输出: 2
解释: 13 = 4 + 9.

二、题解

一、解题思路

对问题建模：
  整个问题转化为一个图论问题。
  从n到0，每个数字表示一个节点；
  如果两个数字x到y相差一个完全平方数，则连接一条边。
  我们得到了一个无权图。
  原问题转化成，求这个无权图从n到0的最短路径。

二、代码

    public int numSquares(int n) {
        Queue<Pair<Integer, Integer>> queue = new ArrayDeque<>();
        queue.add(new Pair<>(n, 0));
        //访问标志的数组 进行路径优化
        // 提前已经访问的节点即可证明之前路径比此路径短
        boolean[] visited = new boolean[n + 1];
        visited[n] = true;
        while (!queue.isEmpty()) {
            int num = queue.peek().getKey();
            int step = queue.peek().getValue();
            queue.poll();
            for (int i = 1; ; i++) {
                int temp = num - i * i;
                if (temp < 0) break;
                if (temp == 0) return step + 1;
                if (!visited[temp]) {
                    //该数之前已访问 通过此线的路径 绝不是最短路径
                    // 则可以不用将后续的节点入队列
                    queue.add(new Pair<>(temp, step + 1));
                    visited[temp] = true;
                }
            }
        }
        return -1;
    }