菊厂笔试2

HW（菊厂） 题目2

   由于疫情影响，动物园进行人流管控，减少人员接触，因此从入口处进入之后，只能选择某一条路单向进行，比如：老虎园的编码为1，狮子园的编码为2，猴子园的编码为3，天鹅园的编号为4，而从一个地方到另一个地方有一定的距离，则用以下结构表示：老虎园到狮子园，[1，2，15]，狮子园到猴子园，[2，3，7]，猴子园到天鹅园，[3，4，9]，现在随机给定一个景点（S）作为出发点，判断是否有可能逛完所有景点（N个）。若不能逛完返回-1，若可以逛完，则返回最长距离。

测试用例：
1.
输入：
[1,2,15]
[1,3,7]
[3,4,9]
4
1
输出：
16
2.
输入：
[1,2,15]
[1,3,7]
[3,4,9]
4
3
输出：
-1

思路：
考虑深度优先遍历，从给定的出发点出发，计算经过的每个节点，增加长度并访问数量加一，递归调用最后的得到长度最长的一个距离，并判断访问数量是否等于总的数量，相等则输出最长长度，不等则输出-1。

邻接矩阵方法：

package com.cgq.thread;

import java.util.Scanner;

public class huawei2 {
    static int count = 0;
    static int ans = 0;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
            String input = scanner.nextLine();
            int[][] G = new int[200][200];
            while(input.charAt(0) == '['){
                String[] edges = input.substring(1,input.length() - 1).split(",");
                G[Integer.parseInt(edges[0]) - 1][Integer.parseInt(edges[1]) - 1] = Integer.parseInt(edges[2]);
                input = scanner.nextLine();
            }
            int num = Integer.parseInt(input);
            input = scanner.nextLine();
            int start = Integer.parseInt(input);
//            System.out.println(num + " " + start);
            count = 0;
            ans = 0;
            dfs(G, start - 1, num, 0);
//            System.out.println(count);
//            System.out.println(ans);
            if(count == num){
                System.out.println(ans);
            }
            else {
                System.out.println(-1);
            }
        }
    }

    public static void dfs(int[][] G, int index, int num, int path){
        count++;
        if(path > ans){
            ans = path;
        }
        for (int i = 0; i < num; i++) {
            if(G[index][i] != 0){
                dfs(G, i, num, path + G[index][i]);
            }
        }
    }
}

空间复杂度高，对于稀疏图不够优化

邻接表法：

package com.cgq.thread;

import java.util.HashMap;
import java.util.Scanner;

public class huawei2v2 {
    static int count = 0;
    static int ans = 0;
    static class Edge{
        int end;
        int weight;
        Edge next;

        public Edge() {
        }

        public Edge(int end, int weight) {
            this.end = end;
            this.weight = weight;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()) {
            String input = scanner.nextLine();
            HashMap<Integer, Edge> vexes = new HashMap<>();
            while (input.charAt(0) == '[') {
                String[] edges = input.substring(1, input.length() - 1).split(",");
//                G[Integer.parseInt(edges[0]) - 1][Integer.parseInt(edges[1]) - 1] = Integer.parseInt(edges[2]);
                int begin = Integer.parseInt(edges[0]);
                int end = Integer.parseInt(edges[1]);
                int weight = Integer.parseInt(edges[2]);
                if (vexes.containsKey(begin)){
                    Edge firstEdge = vexes.get(begin);
                    Edge newEdge = new Edge(end, weight);
                    newEdge.next = firstEdge;
                    vexes.put(begin, newEdge);
                }
                else{
                    Edge newEdge = new Edge(end, weight);
                    vexes.put(begin, newEdge);
                }
                input = scanner.nextLine();
            }
            int num = Integer.parseInt(input);
            input = scanner.nextLine();
            int start = Integer.parseInt(input);
//            System.out.println(num + " " + start);
            count = 0;
            ans = 0;
            dfs(vexes, start, num, 0);
            if (count == num){
                System.out.println(ans);
            }
            else{
                System.out.println(-1);
            }
        }
    }

    public static void dfs(HashMap<Integer, Edge> vexes, int index, int num, int path){
        count++;
        if(path > ans){
            ans = path;
        }
        Edge edge = vexes.getOrDefault(index, null);
        while(edge != null){
            dfs(vexes, edge.end, num, path + edge.weight);
            edge = edge.next;
        }
    }
}

代码更复杂，但是空间利用率高，使用了HashMap存储节点信息，也可以用数组。
python版本邻接表

import collections
dict_ = collections.defaultdict(list)
count = 0
ans = 0
def track(dict_, start, path, ans, list_reach):
    if start not in dict_.keys():
        ans = max(path, ans)
        return ans
    for (key,value) in dict_[start]:
        list_reach[key-1] = 1
        ans = track(dict_, key, path+value, ans, list_reach)
    return ans

while True:
    try:
        str_ = input()
        if str_[0] == '[':
            list_ = list(map(int, str_[1:-1].split(',')))
            # 邻接表
            dict_[list_[0]].append(list_[1:])
        else:
            if not count:
                count += 1
                num = int(str_)
            else:
                start = int(str_)
    except:
        ans = 0
        list_reach = [0 for _ in range(num)]
        list_reach[start-1] = 1
        ans = track(dict_, start, 0, ans, list_reach)
        if sum(list_reach) < num:
            print(-1)
        else:
            print(ans)
        exit()