题解 | #牛群的喂养顺序II#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numCows int整型
     * @param feedOrders int整型二维数组
     * @return int整型一维数组
     */
    public int[] findFeedOrderII(int numCows, int[][] feedOrders) {
        // write code here

        if(feedOrders.length==0){
            return new int[]{0};
        }
        Map<Integer, Integer> map = new TreeMap<Integer, Integer>();
        for (int[] feedOrder : feedOrders) {
            map.put(feedOrder[1], feedOrder[0]);
        }

        int start = 0;
        int end = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            start = entry.getKey();
            end = entry.getValue();
            break;
        }

        List<Integer> list = new LinkedList<>();
        list.add(start);
        list.add(end);
        while (start != end) {
            if (!map.containsKey(end)) {
                int[] arr = new int[list.size()];
                for(int i=0;i<list.size();i++){
                    arr[i] = list.get(i);
                }
                return arr;
            }
            end = map.get(end);
            list.add(end);
        }
        return new int[]{};
    }

}

本题考察的知识点是哈希表的应用，所用编程语言是java.

根据题目要求喂养顺序关系用一个数组 feedOrders 给出，其中 feedOrders[i] = [ai, bi]，表示如果要喂养牛 ai，则必须先喂养牛 bi。我们将[bi,ai]作为键值对存储在哈表中，然后观察是否成环。观察成环的方法是我们首先将其中一个键值对取出来，分别赋值给start,end,然后以end作为键值，观察是否对应值为start,如果不是更新end的值为以end为键值的对应值，因此类推，直到没有以end为键值的对应值或者对应值为start结束