leetcode 269利用拓扑排序

傷城~ 2023-05-31 04:55 94阅读 0赞

package com.hnist.lzn;
    
    import javafx.scene.layout.Priority;
    
    import java.util.*;
    
    public class TopSort {
        
    
        public static String alienOrder(String[] words) {
        
    
            String res = "";
            if(words  == null || words.length == 0)return res;
    
            // 点集的入度
            Map<Character,Integer> degree = new HashMap<>();
            for(String word:words){
        
                for(char c:word.toCharArray()){
        
                    degree.put(c,0);
                }
            }
            // 边集
            Map<Character, Set<Character>> map = new HashMap<>();
            for(int i = 0;i<words.length-1;i++){
        
                String cur = words[i];
                String next = words[i+1];
                int len = Math.min(cur.length(),next.length());
                for(int j = 0;j<len;j++)
                {
        
                    char ch1 = cur.charAt(j);
                    char ch2 = next.charAt(j);
    
                    // 添加指向
                    if(ch1 != ch2){
        
                        Set<Character> set= new HashSet<>();
                        if(map.containsKey(ch1))
                            set = map.get(ch1);
                        if(!set.contains(ch2)){
        
                            set.add(ch2);
                            map.put(ch1,set);
                            degree.put(ch2,degree.get(ch2)+1);
                        }
                        break;
                    }
    
                }
            }
            Queue<Character> queue = new LinkedList<>();
            for(Map.Entry<Character,Integer> entry:degree.entrySet()){
        
                if(entry.getValue() == 0)queue.add(entry.getKey());
            }
    
            while(!queue.isEmpty()){
        
                // 拿一个非空的顶点
                char p = queue.poll();
                res += p;
                // map 中存在以p为起点的指向的度的节点
                if(map.containsKey(p)){
        
                    for(char c:map.get(p)){
        
                        degree.put(c,degree.get(c)-1);
                        if(degree.get(c) == 0)
                            queue.add(c);
                    }
                }
    
            }
    
            if(res.length() != degree.size())return "";
            return res;
        }
    
        public static void main(String[] args) {
        
    
         /*   String[] words = {"wrt","wrf","er","ett","rftt"};
            System.out.println(alienOrder(words));*/
            Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
        
                @Override
                public int compare(Integer o1, Integer o2) {
        
                    return o2-o1;
                }
            });
            queue.add(3);
            queue.add(5);
            System.out.println(queue.peek());
    
    
        }
    
    }