LeetCode279/127/126 - 用图建模
题目
给你一个整数 n
,返回 和为 n
的完全平方数的最少数量 。
完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1
、4
、9
和 16
都是完全平方数,而 3
和 11
不是。
示例 1:
输入:n = 12
输出:3
解释:12 = 4 + 4 + 4
坑 - 贪心算法
既然所求的是最少数量,很容易想到贪心算法:每次都找一个能取到的最大完全平方数,以此类推。
其实示例1恰恰就是一个反例。对于 n=12,最大的是 3<sup>2</sup>=9,然后只能连续取三个1,最后需要 4 个数,答案错误。
这也是贪心算法的典型缺陷——容易陷入局部最优解。
图论
这道题可以建模为图。
数字 [0, n] 每一个数是一个点。如果两点之差是一个完全平方数,则从大到小连接一条边,最终成为一个有向无权图。原问题转化为:求从节点 n 到 0 的最短路径长度。
简单起见,令 n=6,那么图如下所示:
不要真正建图
尽管我们按照图的模型来建模,但不意味着要先建出完整的图再来执行广度优先遍历,那样就本末倒置了。
BFS 核心的一步是,每遍历到一个节点,就把与之相连的节点全部加入到队列中。所谓「与之相连的节点」在本题的环境下,就是「与当前节点数值之差是完全平方数」,那么通过一个循环就能轻松解决了:
for (int i = 1; num - i * i >= 0; i++) {
q.add(num - i * i);
}
然后就是注意几个优化的地方:
- 设立
visited
数组,避免重复入栈。 - 在入栈时就判断是否为 0,不要等出栈再算。
num - i* i
避免多次计算。
java 代码
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 个字母的单词」,这就要遍历题目给出的列表,写一个函数来判断是否满足条件:
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),列表的最后一位是下次要访问的节点。
修改后的代码如下:
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 号题目不同,这题需要进行更多节点的扫描,同时寻找下一个节点的操作也比较复杂,所以「一边建图一边遍历」不再合适了。现在我们希望一次性建好图,后面算法直接在图的基础上进行。优化后代码如下:
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()));
});
}