[leetcode/lintcode 题解] 算法面试真题详解:程序检查-阿里云开发者社区

开发者社区> 算法编程> 正文
登录阅读全文

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

简介: [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

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
算法编程
使用钉钉扫一扫加入圈子
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
链接