回溯算法案例——网易面试题_网易面试算法题

题目

某游戏近期需推出全新玩法，有n个宝箱，宝箱按从0到n-1编号，玩家最初可直接开启0号宝箱，其余所有宝箱都被锁住。你的目标是打开所有宝箱。然而，你不能在没有获得钥匙的时候打开锁住的宝箱。
每打开一个宝箱，你可能会在里面找到一个或多个不同的钥匙,每把钥匙上都有对应的宝箱编号，即表示钥匙可以打开的宝箱。你可以拿上所有钥匙去解锁其它宝箱。

由于游戏策划希望这种玩法有充分的随机性，让不同的玩家以不同顺序打开宝箱，但是必须保证所有玩家都能开完所有宝箱获取到最终奖励。因此游戏开发设计了一套随机算法自动分配每个宝箱中的钥匙，现在需要由你来进一步验证每个生成出来的结果是否能让玩家打开每一个宝箱。给你一个数组 boxes 其中 boxes[]是你打开1号宝箱可以获得的钥匙集合。如果能打开所有的宝箱返回true,否则返回 false 。
输入描述:
第一行为JSON字符串,确保可用JSON解析成一个列表,例如:[[1,3],[3,0,1],[2],[0]]
输出描述:
如果能打开所有的宝箱返回 true，否则返回 false
示例:

输入
[[2],[3],[1],[]
输出
true

代码分析

	public static void main(String[] args) {
        // 解决json字符串转变为列表的问题，方式不是最优
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        Stack<Integer> stack=new Stack<>();
        List<List<Integer>> list=new ArrayList<>(); // 将json字符串转变为list数组
        int left=0;
        for (int i=1;i<s.length()-1;i++){
            if (s.charAt(i)=='[') {
                left=i+1;
                continue;
            }
            if (s.charAt(i)==']'){
                int i1=0;
                if (left<i)
                    i1=Integer.parseInt(s.substring(left,i));
                stack.push(i1);
                list.add(new ArrayList<>(stack));
                stack.clear();
            }
            if (s.charAt(i)==',') {
                if (s.charAt(i-1)==']') continue;
                int i1=0;
                if (left<i) {
                    String t = s.substring(left, i);
                    i1 = Integer.parseInt(t);
                }
                stack.push(i1);
                left=i+1;
            }
        }
        boolean[] box = new boolean[list.size()];  //box[i]为true表示该箱子打开
        if(list.size() <= 1) {
            System.out.println(true);   return;
        }
        int result = 1;
        box[0] = true;
        System.out.println(backtracking1(list,0,result,box));
    }
	
	 public static boolean backtracking1(List<List<Integer>> list,int num,int result,boolean[] box) {
        // 结束条件
        if(result==list.size()) return true;
        if(list.get(num)==null) return false; //为空的情况，代表该箱子里面没有钥匙
        for(int i=0;i<list.get(num).size();i++) {
            if(box[list.get(num).get(i)] == true) continue;// 递归
            result++;
            box[list.get(num).get(i)] = true;
            if(backtracking1(list,list.get(num).get(i),result,box)) return true;
            result--;  // 回溯
            box[list.get(num).get(i)] = false;
        }
        return false;
    }
    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55