[leetcode/lintcode 题解] 算法面试真题详解：程序检查

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

1. label ：声明一个标签，参数是一个字符串，且每个标签只声明一次。
2. goto ：跳转到一个标签，并从标签处开始按顺序执行程序。
3. halt：停机，程序终止。
4. print ：打印一个字符串，并执行下一个命令。
5. gotorand ：随机跳转到两个标签中的一个，并从标签处开始按顺序执行程序。
   当程序执行完最后一句，且没有跳转时，程序终止。
   设给定的程序的命令条数为 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;
  }
  }

更多题解参考：九章官网solution