描述

有一种编程语言，只有以下五种命令，每种命令最多有两个参数，请检查给定的程序是否 可能 无限循环。 这些命令分别是：

1. label <string>：声明一个标签，参数是一个字符串，且每个标签只声明一次。
2. goto <string>：跳转到一个标签，并从标签处开始按顺序执行程序。
3. halt：停机，程序终止。
4. print <string>：打印一个字符串，并执行下一个命令。
5. 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 的话，代表有环

复杂度分析

• 设命令数为 N 。

时间复杂度

• 遍历图的时间复杂度为 O(N)。

空间复杂度

• 需要栈上 O(N)的开销来递归。

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;     } } 

更多题解参考

大佬有話說 (0)