LeetCode279/127/126 - 用图建模

题目

传送门

给你一个整数 n ,返回 和为 n 的完全平方数的最少数量

完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,14916 都是完全平方数,而 311 不是。

示例 1:

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

坑 - 贪心算法

既然所求的是最少数量,很容易想到贪心算法:每次都找一个能取到的最大完全平方数,以此类推。

其实示例1恰恰就是一个反例。对于 n=12,最大的是 32=9,然后只能连续取三个1,最后需要 4 个数,答案错误。

这也是贪心算法的典型缺陷——容易陷入局部最优解。

图论

这道题可以建模为图。

数字 [0, n] 每一个数是一个点。如果两点之差是一个完全平方数,则从大到小连接一条边,最终成为一个优向无权图。原问题转化为:求从节点 n 到 0 的最短路径长度。

简单起见,令 n=6,那么图如下所示:

不要真正建图

尽管我们按照图的模型来建模,但不意味着要先建出完整的图再来执行广度优先遍历,那样就本末倒置了。

BFS 核心的一步是,每遍历到一个节点,就把与之相连的节点全部加入到队列中。所谓「与之相连的节点」在本题的环境下,就是「与当前节点数值之差是完全平方数」,那么通过一个循环就能轻松解决了:

1
2
3
for (int i = 1; num - i * i >= 0; i++) {
  q.add(num - i * i);
}

然后就是注意几个优化的地方:

  • 设立 visited 数组,避免重复入栈。
  • 在入栈时就判断是否为 0,不要等出栈再算。
  • num - i* i 避免多次计算。

java 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int numSquares(int n) {
        Queue<Integer> q = new LinkedList<>();
        q.add(n);
        int step = 0;
        boolean[] visited = new boolean[n + 1];
        visited[n] = true;
        while (!q.isEmpty()) {
            int len = q.size();
            for (int j = 0; j < len; j++) {
                int num = q.poll();
                for (int i = 1; ; i++) {
                    int a = num - i * i;
                    if (a < 0)
                        break;
                    if (a == 0)
                        return step + 1;
                    if (!visited[a]) {
                        q.add(a);
                        visited[a] = true;
                    }
                }
            }
            step++;
        }
        throw new IllegalArgumentException();
    }
}

扩展

127. Word Ladder

利用相同的思想也可解决 LeetCode 127. Word Ladder 问题。在这个情境中,「与之相连的节点」相当于「与当前单词只差 1 个字母的单词」,这就要遍历题目给出的列表,写一个函数来判断是否满足条件:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
private boolean canTransform(String from, String to) {
    if (from.length() != to.length())
        return false;
    int n = 0;
    for (int i = 0; i < from.length(); i++)
        if (from.charAt(i) != to.charAt(i)) {
            n++;
            if (n > 1) return false;
        }
    return n == 1;
}

126. Word Ladder II

在 127 的基础上衍生出这道题(传送门),算是比较难的一个了。与前面不同的是,既要求出所有最短的路径,还要把它们保存下来。不难看出有两个关键点:

  • 求所有最短路径:BFS 找到一个结果后不能直接 return 了,而是要把这一层遍历完。
  • 保存下来:队列里不能仅存节点信息,而是要保存整个路径(List),列表的最后一位是下次要访问的节点。

修改后的代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
    List<List<String>> res = new LinkedList<>();
    Set<String> visited = new HashSet<>();
    Queue<LinkedList<String>> q = new LinkedList<>();
    q.add(new LinkedList<>(List.of(beginWord)));
    while (!q.isEmpty()) {
        boolean find = false; // 当前层是否找到了结果
        int len = q.size();
        for (int i = 0; i < len; i++) {
            LinkedList<String> path = q.poll();
            visited.add(path.getLast());
            for (String to : wordList) {
                if (!visited.contains(to) && canTransform(path.getLast(), to)) {
                    if (to.equals(endWord)) { // 找到了最近的 END 节点
                        find = true;
                        path.add(to);
                        res.add(path);
                        break;
                    }
                    LinkedList<String> newPath = new LinkedList<>(path);
                    newPath.add(to);
                    q.add(newPath);
                }
            }
        }
        if (find) break;
    }
    return res;
}

与一开始的 279 号题目不同,这题需要进行更多节点的扫描,同时寻找下一个节点的操作也比较复杂,所以「一边建图一边遍历」不再合适了。现在我们希望一次性建好图,后面算法直接在图的基础上进行。优化后代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
Map<String, List<String>> graph;

public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
    initGraph(wordList, beginWord);
    List<List<String>> res = new LinkedList<>();
    Set<String> visited = new HashSet<>();
    Queue<LinkedList<String>> q = new LinkedList<>();
    q.add(new LinkedList<>(List.of(beginWord)));
    while (!q.isEmpty()) {
        boolean find = false; // 当前层是否找到了结果
        int len = q.size();
        for (int i = 0; i < len; i++) {
            LinkedList<String> path = q.poll();
            visited.add(path.getLast());
            if (!graph.containsKey(path.getLast()))
                continue;
            for (String to : graph.get(path.getLast())) {
                if (visited.contains(to)) continue;
                if (to.equals(endWord)) { // 找到最近的 END 节点
                    find = true;
                    path.add(to);
                    res.add(path);
                    break;
                }
                LinkedList<String> newPath = new LinkedList<>(path);
                newPath.add(to);
                q.add(newPath);
            }
        }
        if (find) break;
    }
    return res;
}

private void initGraph(List<String> words, String begin) {
    graph = new HashMap<>();
    graph.put(begin, words.stream().filter(to -> canTransform(begin, to)).collect(Collectors.toList()));
    words.forEach(wd -> {
        graph.put(wd, words.stream().filter(to -> canTransform(wd, to)).collect(Collectors.toList()));
    });
}
禁止转载到私域(公众号,非自己托管的博客等),其他情况请注明原作者与可点击跳转的来源链接。