原始題目鏈接可以參考如下鏈接?某廠機試算法刷題一覽_@_南先森的博客-CSDN博客
在閱讀代碼時，建議拷貝到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可以解鎖valueMap<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;} }

總結

以上是生活随笔為你收集整理的华为OD机试107-跳格子游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。