华为OD机试107-跳格子游戏

原始题目链接可以参考如下链接 在阅读代码时，建议拷贝到idea或者eclipse里面看，为了便于理解代码，注释比较多， 在阅读代码时，可以先删掉注释 这个题目需要用到栈做广度优先搜索，解题主要有以下几个要点 1:要找到没有依赖关系的数字作为起始数字,从起始数字出发 像多米诺骨牌一样往后面的数字传递,依次解锁后面数字 2:使用Map<Integer, List<Integer>>数据结构来记录 数字之间的依赖关系,value依赖key 3:需要用到Stack，可以解锁的数字入栈,用出栈来模拟解锁过程

public class Demo107 {
    //测试代码
    public static void main(String[] args) {
        int n = 6;
        int[][] grids = {
         
  {0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}};
        boolean r = skipGrid(n, grids);
        System.out.println(r);
    }

    /*
     * n代表总共几个数字
     * grids存放每一行的两个数字
     * 举个例子,如果用户输入下面的数据
     * 2
     * 1 0
     * 0 1
     * 那么n = 2  grids = {
         
  {1,0},{0,1}}
     *
     */
    public static boolean skipGrid(int n, int[][] grids) {
        /*
         *  x数组的设计很有讲究,其索引代表需要解锁的数字,其值代表依赖数字
         *  如国值为null,说明当前数字无依赖数字,可以直接解锁,下面举2个例子
         *  便于理解
         *  如果用户输入
         *  2
         *  1 0
         *  0 1
         *  那么x=[1,0]
         *  观察上面的数据,可以看到 x[0] = 1; x[1] = 0
         *  以上是索引0依赖数字1,索引1依赖数字0
         *  再举个例子
         *  3
         *  0 1
         *  0 2
         *  则x=[null,0,0]
         *  观察上面的数据,可以看到 x[0] = null; x[1] = 0; x[2] = 0
         *  说明索引0没有依赖数字,可以直接解锁.而索引1,2都依赖0
         *
         */
        Integer[] x = new Integer[n];
        // key和value都存放的是数字,key可以解锁value
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < grids.length; i++) {
            int[] a = grids[i];
            List<Integer> list = map.getOrDefault(a[0], new ArrayList<>());
            list.add(a[1]);
            map.put(a[0], list);
            // 理解了上面的注释,这行代码就好理解,简单说,就是记录索引依赖的数字
            x[a[1]] = a[0];
        }
        Stack<Integer> stack = new Stack<>();
        //值为空的找出来,值为空说明没有依赖关系,可以直接解锁
        for (int i = 0; i < x.length; i++) {
            if (x[i] == null) {
                stack.add(i);
            }
        }
        //如果所有的数字都有依赖关系,说明没法解锁
        if (stack.isEmpty()) {
            return false;
        }
        while (!stack.isEmpty()) {
            // 一个个弹出,然后赋值为-1,代表已经解锁过了.后面不要重复访问解锁过的元素
            int index = stack.pop();
            x[index] = -1;
            // 获取以index为前提条件的数字,因为index解锁了,那么以index为前提条件的数字也可以解锁
            List<Integer> list = map.get(index);
            if (list == null) {
                continue;
            }
            list.forEach(item -> {
                // 等于 -1说明已经解锁过了,不需要重复解锁,避免死循环
                if (x[item] != -1) {
                    stack.add(item);
                }
            });
        }

        for (int i = 0; i < x.length; i++) {
            if (x[i] != -1) {
                return false;
            }
        }
        return true;
    }
}