栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

拓扑排序算法leetcode.剑指offer.114

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

拓扑排序算法leetcode.剑指offer.114

    boolean[] mark;//之前已经遍历的节点
    boolean[] on;//本此路径上的节点
    boolean flag;//是否有环
    String ans;//结果,模拟栈
    Deque[] adj;//邻接表
//添加v到w的边
 public void addEdge(int v,int w){
     if(adj[v]==null) adj[v]=new ArrayDeque<>();
     if(adj[w]==null) adj[w]=new ArrayDeque<>();
        if(!adj[v].contains(w))
            adj[v].offer(w);
        //当w包含v时形成闭环
        if(adj[w].contains(v))
            flag=true;
    }

    public String alienOrder(String[] words) {
        int n=words.length;
        if(n==1) return words[0];
        mark=new boolean[26];
        on=new boolean[26];
        flag=false;
        ans=new String();
        adj=new ArrayDeque[26];
        Set set=new HashSet<>();//存储出现的字母
        //取相邻的两个单词
        for(int i=1;iwords[i].length())
                    return "";
            char[] chs1=words[i-1].toCharArray();
            char[] chs2=words[i].toCharArray();
            boolean find=false;//是否找到能确定顺序的两个字母
            
            for(int j=0,k=0;j[] adj,int v){
        mark[v]=true;
        on[v]=true;
        if(adj[v]!=null){
            for (int w : adj[v]) {
                if(!mark[w]){
                    dfs(adj,w);
                } else if(on[w]){//已经标记的点,可能是之前遍历过的,也可能是本次路径上的
                    flag=true;
                    return;
                }
            }
        }
        on[v]=false;//回溯还原路径上点的状态
        ans=(char)(v+'a')+ans;//当该点没有指向,或已经遍历完后面的点,该点入栈
    }

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/959478.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号