描述
有一种编程语言，只有以下五种命令，每种命令最多有两个参数，请检查给定的程序是否
可能 无限循环。
这些命令分别是：
- label <string>：声明一个标签，参数是一个字符串，且每个标签只声明一次。
- goto <string>：跳转到一个标签，并从标签处开始按顺序执行程序。
- halt：停机，程序终止。
- print <string>：打印一个字符串，并执行下一个命令。
- gotorand <label1> <label2>：随机跳转到两个标签中的一个，并从标签处开始按顺序执行程序。
当程序执行完最后一句，且没有跳转时，程序终止。
设给定的程序的命令条数为 nn，1≤n≤1031≤n≤103。
所有标签中只含有英文字符，且长度 mm，1≤m≤51≤m≤5。
输出命令的字符串长度 ll，1≤l≤201≤l≤20。
在线评测地址：
领扣题库官网
样例1
输入：
label start
print "hello world!"
gotorand start end
print "good bye"
halt
label end
输出：
true
说明
样例中，每当程序执行到第三句 "gotorand start end" 后，都有可能回到第一句，从头执行，也可能跳到最后一句。第四，五句将不会被执行。
我们可以将每一行命令抽象成一个有向图，然后将命令间的跳转抽象成一个有向边，如果这个有向图中有环的话，就认为可能会死循环。
有向图判环的深度优先搜索算法：
如何判断一个有向图是否有环，在他的深度优先搜索树上如果有一个节点指回它的祖先节点，那么这个有向图是有环的。
- 在递归遍历图的过程中，实际上有一个栈在记录遍历时的路径，那么节点就有三种状态：
- 0代表节点未被访问过。
- 1代表节点在栈中，也就是在根节点到该节点的路径上，如果指回去的话，代表有环。
- 2代表节点已出栈，已经访问过。
- 所以在深度优先遍历图的基础上，如果遍历到某个节点而且这个节点的状态是1的话，代表有环
复杂度分析
时间复杂度
空间复杂度
public class Solution {
/**
* @param commands: the commands of this program.
* @return: return is the program may be in endless loop.
*/
public boolean check(List<String> commands) {
int n = commands.size();
// 标签对应的行数
Map<String, Integer> labelIdx = new HashMap<>();
// 每个节点的访问状态
Map<Integer, Integer> visitState = new HashMap<>();
for (int i = 0; i < n; i++) {
if (commands.get(i).charAt(0) == 'l') {
labelIdx.put(commands.get(i).substring(6), i);
}
}
return dfs(0, visitState, labelIdx, commands);
}
/**
* idx的状态
* 0 - 这个节点未被访问过
* 1 - 这个节点被访问过且在栈中
* 2 - 这个节点已被访问过且已出栈
*/
private boolean dfs(int idx,
Map<Integer, Integer> visitState,
Map<String, Integer> labelIdx,
List<String> commands) {
// 程序结束
if (idx == commands.size()) {
return false;
}
// 程序中有环，可能会死循环
if (visitState.containsKey(idx) && (int)visitState.get(idx) == 1) {
return true;
}
// visitState = 2, 代表之后都不会死循环
if (visitState.containsKey(idx) && (int)visitState.get(idx) == 2) {
return false;
}
// 将 idx 节点加入栈中
visitState.put(idx, 1);
boolean flag = false;
if (commands.get(idx).charAt(0) == 'h') {
visitState.put(idx, 2);
// 停机
return false;
}
if (commands.get(idx).charAt(0) == 'g') {
String[] parameters = commands.get(idx).split(" ");
if (parameters.length == 2) {
flag |= dfs(labelIdx.get(parameters[1]), visitState, labelIdx, commands);
}
else {
flag |= dfs(labelIdx.get(parameters[1]), visitState, labelIdx, commands);
flag |= dfs(labelIdx.get(parameters[2]), visitState, labelIdx, commands);
}
}
else {
flag |= dfs(idx + 1, visitState, labelIdx, commands);
}
visitState.put(idx, 2);
return flag;
}
}
更多题解参考：
九章solution