华为 9.14 笔试

分享一下我的代码,求大佬指点一下

三道题

1. 跳断桥,有生命值,每次可以跳1/2/3格,跳到断桥位置掉一滴血,求恰好能到达终点有几种走法

暴力递归过了70% 超时了

public class Main01 {

    private static int res = 0;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int m = scan.nextInt();
        int n = scan.nextInt();
        int k = scan.nextInt();
        HashSet<Integer> lose = new HashSet<>();
        for (int i = 0; i < k; i++) {
            lose.add(scan.nextInt());
        }
        process(n, lose, m, 0);
        System.out.println(res);
    }

    public static void process(int n, HashSet<Integer> lose, int curHP, int curP) {
        if (curP == n+1) {
            res++;
            return;
        }
        if (curP > n+1) {
            return;
        }
        if (lose.contains(curP)) {
            curHP--;
        }
        if (curHP < 1) {
            return;
        }

        for (int i = 1; i <= 3; i++) {
            process(n, lose, curHP, curP+i);
        }

    }
}

2. m个通道发n个文件,可以同时发送,通道有大小,文件有大小,耗时, 求发送完所有文件最小耗时

贪心 100%

先发耗时最大的文件,找一个最空闲的并且大于文件的通道发送

public class Main02 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        PriorityQueue<Road> heap = new PriorityQueue<>((x,y) -> {
            if (x.time == y.time) {
                return x.size-y.size;
            }
            return x.time-y.time;
        });
        for (int i = 0; i < n; i++) {
            heap.add(new Road(scanner.nextInt(), 0));
        }
        ArrayList<Package> packages = new ArrayList<>();
        int[] arr = new int[m];
        for (int i = 0; i < m; i++) {
            arr[i] = scanner.nextInt();
        }
        for (int i = 0; i < m; i++) {
            packages.add(new Package(arr[i], scanner.nextInt()));
        }

        packages.sort((x,y) -> y.time - x.time);

        for (Package p :packages){
            ArrayList<Road> temp = new ArrayList<>();
            while (!heap.isEmpty() && heap.peek().size < p.size) {
                temp.add(heap.poll());
            }
            Road r = heap.poll();
            r.time += p.time;
            heap.offer(r);
            for (Road road : temp) {
                heap.offer(road);
            }
        }

        int min = -1;
        for (Road road : heap) {
            min = Math.max(min, road.time);
        }
        System.out.println(min);
    }

    static class Road {
        int size;
        int time;
        public Road(int size, int time) {
            this.size = size;
            this.time = time;
        }
    }

    static class Package {
        int size;
        int time;
        public Package(int size, int time) {
            this.size = size;
            this.time = time;
        }
    }
}

3. ip寻址, 有ttl限制,求从发送路由到接收路由的最短路径

递归向邻居要信息,写的挺混乱 75% 超时了

public class Main03 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int start = scan.nextInt();
        int end = scan.nextInt();
        int ttl = scan.nextInt();
        Result[][] memo = new Result[501][501];
        for (int i = 0; i < n; i++) {
            int a = scan.nextInt();
            int b = scan.nextInt();
            int l = scan.nextInt();
            memo[a][b] = new Result(l,1);
            memo[b][a] = new Result(l,1);
        }
        boolean[] used = new boolean[501];

        Result res = findRoads(start, end, memo, used, ttl);
        if (res.ttl < 0) {
            System.out.println(-1);
            return;
        }
        System.out.println(res.len + " "+ res.ttl);
    }

    public static Result findRoads(int start, int end, Result[][] memo, boolean[] used, int ttl) {
        if (ttl < 0) {
            return new Result(-1, ttl);
        }
        if (memo[start][end] != null && memo[start][end].len > 0) {
            return new Result(memo[start][end].len, ttl-memo[start][end].ttl);
        }
        Result min = new Result(Integer.MAX_VALUE, Integer.MIN_VALUE);
        used[start] = true;
        for (int i = 1; i < 501; i++) {
            if (used[i]) {
                continue;
            }
            if (memo[start][i] == null) {
                continue;
            }
            if (memo[start][i].len > 0) {
                used[i] = true;
                Result result = findRoads(i, end, memo, used, ttl - memo[start][i].ttl);
                result.len += memo[start][i].len;
                if (result.len < min.len && result.ttl >= 0) {
                    min = result;
                }if (result.len == min.len) {
                    if (result.ttl > min.ttl) {
                        min = result;
                    }
                }
                used[i] = false;
            }
        }
        return min;
    }

    static class Result{
        int len;
        int ttl;
        public Result(int len, int ttl) {
            this.len = len;
            this.ttl = ttl;
        }
    }
}

#23届秋招笔面经#