华为笔试-通用软件开发工程师-0914复盘

听说华为面试可能会复盘笔试，这三道题属实有点难，一道题都没有AC，还是好好复盘一下，如果能进面试的话，可以留个好印象

编程题1-超级玛丽过吊桥

相当于青蛙跳台阶的改进版，走一个吊桥，吊桥的尽头是下水管道，其中随机的木板存在缺失，一旦踩到就会死亡，死亡后如果还有剩余的生命将在原地复活且不受模板缺失影响，但会消耗一次生命；如果跨过了管道，将坠入悬崖，通关失败。超级玛丽从起点S开始，可以走到下一个木板（计1），也可以跳着跨过一个块（计2）或两个木板（计3），最终必须刚好走到终点E，现在给定超级玛丽当前的生命数M，吊桥的长度N，缺失的木板数K，以及随机缺失的木板编号数组L，请帮忙计算一下，超级玛丽有多少种方法可以通过此关

解答要求

时间限制：C/C++ 1000ms，其他语言：2000ms

内存现在：C/C++ 256MB，其他语言：512MB

输入

超级玛丽当前生命数：$M(1\leq M \leq5)$ 整数

吊桥的长度：$N(1 \leq N \leq 32)$ 整数

缺失木板数：$K(1 \leq K \leq 32)$ 整数

缺失木板编号数组：$L$ （长度及编号的内容不大于 $N$ 的编号数组，$1 \leq L_i \leq N$，由空格分割的整数数组）

输入结构：

M N K
L

提示：

1. 输入总是合法，忽略参数校验
2. 必须从起点开始走
3. 必须离开吊桥走到终点

输出

输出通过此关的吊桥走法个数，如果不能通过此关，请输出0

样例1

输入

2 2 1
2

输出

4

解释：2个生命，2个木板，缺失1个木板，第二个木板有缺失，一共有四种走法：

1. 3
2. 1， 2
3. 2， 1
4. 1， 1（复活），1

样例2

输入

1 3 2
1 3

输出

1

题解

类似于这种跳台阶的，一般都可以考虑通过动态规划的方式来解决，和青蛙跳台阶的变化是需要考虑到生命的变化

定义一个二维矩阵dp[m][i]，表示走到当前i木板生命值为m的走法有多少，那么转移方程可以定义为：

• 如果i木板不缺失：$dp[m][i] = \sum_{k=1}^3 dp[m][i-k]$

• 如果i木板缺失：$dp[m-1][i] = \sum_{k=1}^3 dp[m][i-k]$

初始的起点也就是dp[M][0]=1，最后走到终点的方法为 $\sum_{m=1}^M dp[m][N + 1]$

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt(), n = scanner.nextInt(), k = scanner.nextInt();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < k; i++)
            set.add(scanner.nextInt());

        int[][] dp = new int[m + 1][n + 2];
        dp[m][0] = 1;
        for (int i = 1; i < n + 2; i++) {
            int lose = set.contains(i) ? -1 : 0;
            for (int x = i - 1; x >= Math.max(i - 3, 0); x--) {
                for (int j = 1; j < m + 1; j++) {
                    dp[j + lose][i] += dp[j][x];
                }
            }
        }

        int ans = 0;
        for (int i = 1; i < m + 1; i++)
            ans += dp[i][n + 1];
        System.out.println(ans);
    }
}

编程题2-最快传输

有一批数据包需要传输，每个数据包大小不一样，传输需要不同的时长，现在有N个传输通道，每个通道的大小也不一样，通道只能传输小于等于自己大小的数据包，不同通道可以同时传输数据包，同道中可以缓存多个数据包，当新任务来时，可以先进入缓存队列等待发送，问最短需要多长时间能够传输完成，通道会确保所有数据包都可以传输

解答要求

时间限制：C/C++ 1500ms，其他语言：3000ms

内存限制：C/C++ 256MS，其他语言：512MB

输入

第一行M N，M表示队列长度，N表示传输通道数

第二行有N个数，表示每个通道的大小P

第三行有M个数，表示每个数据包的大小Q

第四行有M个数，表示每个数据包的传输时长S

$1 \leq M, S, P, Q \leq 10000$

$1 \leq N \leq 1000$

输出

输出传输完所有数据包需要的最短时长

样例1

输入

5 2
5 3
1 4 5 2 3
1 6 10 3 4

输入

16

样例2

输入

3 2
6 13
2 11 5
3 25 14

输出

25

题解

这种贪心的题确实有点在我的知识点范围之外，按照牛客网上的大佬的说法是，需要考虑三个贪心条件：

1. 数据按照传输时间逆序排序，先处理传输时间最长的
2. 在满足传输条件的所有通道里，优先选取最早空闲的，也就是最早完成自己通道内传输任务的，这样可以最小限度地增加通道的处理时间
3. 如果最早空闲时间也相同，就选取传输能力最小的，将能力大的留给后面的任务

public class Main2 {
 public static void main(String[] args) {
     Scanner scanner = new Scanner(System.in);
     int m = scanner.nextInt();
     // 通道数
     int n = scanner.nextInt();
     // [通道传输能力][空闲时间]
     int[][] channels = new int[n][2];
     for (int i = 0; i < n; i++) {
         channels[i][0] = scanner.nextInt();
     }
     int[][] data = new int[m][2];
     for (int i = 0; i < m; i++) {
         // 大小
         data[i][0] = scanner.nextInt();
     }
     for (int i = 0; i < m; i++) {
         // 传输时长
         data[i][1] = scanner.nextInt();
     }
     // 按传输时长逆序
     Arrays.sort(data, (a, b) -> {
         if (a[1] == b[1]) {
             return a[0] - b[0];
         }
         return b[1] - a[1];
     });
     // 贪心1
     for (int[] d : data) {
         int minIdleTime = Integer.MAX_VALUE;
         int ch = 0;
         // 遍历每个通道
         for (int i = 0; i < n; i++) {
             // 需要满足传输条件
             if (channels[i][0] >= d[0]) {
                 // 贪心2
                 if (channels[i][1] < minIdleTime) {
                     ch = i;
                     minIdleTime = channels[i][1];
                 } else if (channels[i][1] == minIdleTime && channels[i][0] < channels[ch][0]) {
                     // 贪心3
                     ch = i;
                 }
             }
         }
         channels[ch][1] += d[1];
     }
     int max = 0;
     for (int i = 0; i < n; i++) {
         max = Math.max(max, channels[i][1]);
     }
     System.out.println(max);
 }
}

编程题3-路由规划

H公司新结了一个订单，需要帮助客户给一个IP传输网络（该网络由M个路由器组成，每个路由器与其他多个路由器之间物理连接固定）规划路由，使IP报文从起点到终点，传输距离最小。IP报文在传输时，有如下限制：

1. IP报文头部有TTL字段表示生存周期。报文从起点经过中间多个路由器转发到终点，每经过一个路由器（包含起点）TTL减1。当TTL减到0时，该报文将不能转发，直接丢弃（若到达终点时TTL为0，则认为正常到达，不丢弃）
2. 起点的IP报文的TTL为固定值，由输入给定

a. 当IP报文的TTL=255时，最短路径为6（经过路由器1-5-6-7，TTL减3），当走该路径到达终点时的TTL为252

b. 当IP报文的TTL为2时，最短路径为11（经过路由器1-8-7，TTL减2），走该路径到达终点时的TTL为0

C、当IP报文的TTL=1时间，在生存周期内无法到达终点

解答要求

时间限制：C/C++ 400ms，其他语言：800ms

内存限制：C/C++ 256MB，其他语言：512MB

输入

第一行：4个整数，分别表示路由器连接边个数N，起点路由器ID，终点路由器ID，起点IP报文的TTL

第二行~第N+1行：路由器连接边信息，为3个正整数，分别为两个路由器ID和他们之间的距离L，比如1 5 2表示路由器1和路由器5物理连接在一起，它们之间的距离为2km；

用例保证输入：

1. 路由器连接边个数 $N \leq 500$；路由器ID为离散的正整数，其 $\leq 500$；路由器距离 $L \leq 1000$
2. 两个路由器之间连接边信息唯一，比如不会同时存在1 5 2和1 5 3这种输入
3. 起点IP报文的TTL $\leq 255$
4. 起点和终点的路由器ID一定不一样

输出

IP报文在生存周期内从起点到终点的最短距离和达到终点时的TTL。如果有多组数据，则输出达到终点时TTL最大的那组数据。如果无法到达终点，则输出-1

样例1

输入

10 1 7 2
1 2 3
1 5 2
1 8 5
2 3 3
2 5 3
3 4 3
4 7 3
5 6 2
6 7 2
8 7 6

输出

6 252

样例2

输入

10 1 7 1
1 2 3
1 5 2
1 8 5
2 3 3
2 5 3
3 4 3
4 7 3
5 6 2
6 7 2
8 7 6

输出

11 0

样例3

输入

10 1 7 255
1 2 3
1 8 4
2 8 4
2 3 6
2 5 3
3 8 4
3 4 4
4 5 3
4 7 3
3 7 4

输出

-1

样例4

输入

10 1 7 255
1 2 3
1 8 4
2 8 4
2 3 6
2 5 3
3 8 4
3 4 4
4 5 3
4 7 3
3 7 4

输出

12 252

题解

实在没想到好的办法，直接使用的dfs遍历，但是过了42%，后面提示超时，对于Java语言要求800ms，确实要求很严格，可能要换其他的方法

import java.util.*;

public class Main {

    static Long finalPath = Long.MAX_VALUE;
    static int finalTtl = 0;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(),
                start = scanner.nextInt(),
                end = scanner.nextInt(),
                ttl = scanner.nextInt();

        int[][] edges = new int[n + 1][n + 1];
        for (int i = 0; i < n; i++) {
            int id1 = scanner.nextInt(), id2 = scanner.nextInt(), distance = scanner.nextInt();
            edges[id1][id2] = distance;
            edges[id2][id1] = distance;
        }

        boolean[] visited = new boolean[n + 1];
        visited[start] = true;
        dfs(edges, start, end, 0L, ttl, visited);
        if (finalPath == Long.MAX_VALUE) {
            System.out.println(-1);
            return ;
        }
        System.out.println(finalPath + " " + finalTtl);

    }

    public static void dfs(int[][] edges, int cur, int end, long path, int ttl, boolean[] visited) {
        if (ttl < 0)
            return ;

        if (cur == end) {
            if ((finalPath > path) || (finalPath == path && finalTtl < ttl)) {
                finalPath = path;
                finalTtl = ttl;
            }
        }

        for (int i = 0; i < edges.length; i++) {
            if (edges[cur][i] != 0 && !visited[i]) {
                visited[i] = true;
                dfs(edges, i, end, path + edges[cur][i], ttl - 1, visited);
                visited[i] = false;
            }
        }
    }
}