广度优先搜索

广度优先搜索具体操作是一层一层地进行遍历, 每层遍历都是以上一层遍历到的节点作为起点, 遍历其能访问到的所有节点. 需要注意的是, 遍历过的节点不能被再次遍历. 如下:

第一层: 0 -> {6, 2, 1, 5};

第二层: 6 -> {4}; 2 -> {}; 1 -> {}; 5 -> {3}

第三层: 4 -> {}; 3 -> {}

每一层遍历的节点到根节点的距离都相同. 假设 di 表示第 i 个节点与根节点的距离, 可以推导出一个结论: 对于先遍历的节点 i 与后遍历的节点 j, 有 di <= dj. 利用这个结论, 可以求解最短路径等 最优解 问题, 即第一次遍历到目标节点时, 所经过的路径为最短路径.

1. 完全平方

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

我们可以对问题进行抽象: 将 n 当做一个节点, 和其相连的节点是与其相差一个完全平方数的数, 如下所示, 我们就可以得到一个无权图(可能更像一个多叉树), 这样原问题就转化为: 求这个无权图中从 n 到 0 的最短路径, 使用广度优先搜索.

                                n = 7
                              6       3
                           5    2     2
                          4 1   1     1
                          0 0   0     0

下面使用代码实现 BFS , 需要额外考虑的是:

• 使用队列: 存储遍历到的节点.

• 使用布尔数组: 标记遍历过的节点, 防止重复遍历.

public int numSquares(int n) {
    if (n == 0) return 0;
    Queue<Integer> queue = new ArrayDeque<>();
    boolean[] visited = new boolean[n + 1]; // 标记当前节点是否访问过
    // 从n点出发寻找最短路径, 当前步数为0
    queue.add(n);
    visited[n] = true;
    int depth = 0;
    while (!queue.isEmpty()) {
        depth++; // 步数加一
        int size = queue.size(); // 上一层的节点数
        // 以上一层遍历到的节点作为起点
        while (size-- > 0) {
            int cur = queue.poll();
            // 遍历其能访问到的所有节点
            for (int i = 1; i * i <= cur; i++) {
                int next = cur - i * i;
                // 走到节点0找到最短路径, 返回步数
                if (next == 0) return depth;
                // 若当前节点之前访问过, 则跳过(若再走, 步数一定大于之前访问的步数)
                if (visited[next]) continue;
                visited[next] = true;
                queue.add(next);
            }
        }
    }

    // n的组成除1外无其他完全平方数
    return n;
}

Note: 上述解法是标准的bfs模板, 利用queue.size()得到每一层的节点数并进行遍历, 同时也方便记录当前节点所在层数. 当遍历到目标节点时, 层数即为最短路径.

2. 参考

• Cyc2018-LeetCode题解