华为秋季机试三道编程题（2021-09-08）

系统管理员 2022-09-11 08:28 210阅读 0赞

> 通知：**华为**、**阿里**最新的秋招笔试编程题题目、思路以及参考代码已经全部整理好放在微信公众号【TechGuide】了，私信公众号回复【华为】或者【阿里】即可获得最实时、最详细的笔试题解啦！

### 文章目录 ###

*  第一道：最优节点（100%）
 *   *  题目描述
     *  参考代码
 *  第二道： 梅花桩（100%）
 *   *  题目描述
     *  参考代码
     *   *  CPP版本
 *  第三道：最短编译时间（100%）
 *   *  题目描述
     *  参考代码

# 第一道：最优节点（100%） #

## 题目描述 ##

给出一颗二叉树，每个节点有一个编号和一个值，该值可能为负数，请你找出一个最优节点(除根节点外)，使得在该节点将树分成两棵树后(原来的树移除这个节点及其子节点，新的树以该节点为根节点)，分成的两棵树各节点的和之间的差绝对值最大。

请输出该节点编号，如有多个相同的差，输出编号最小的节点。

**输入描述**  
4  
4 9 -7 -8  
0 1  
0 3  
1 2  
第一行，四个节点，编号0-3，范围为1-10000  
第二行，节点0-3的权值  
第三行到第五行，表示二叉树各节点间的父子关系  
0 1 //节点0的左节点是1  
0 3 //节点0的右节点是3  
1 2 //节点1的左节点是2  
注意:左节点永远出现在右节点之前

4
    4 9 -7 -8
    0 1
    0 3
    1 2

**输出描述**

节点编号，示例中编号为3的节点是最优节点

## 参考代码 ##

暴力dfs, 求每一个结点以及其所有子结点的和就可以, 注意需要使用long long

// 关注TechGuide！ 大厂笔经面经闪电速递！

# 第二道： 梅花桩（100%） #

## 题目描述 ##

有一个 M\*N 的梅花桩阵，每个桩都有允许跳跃的最大步数，用户从0,0的位置开始跳跃，允许向右和向下两个方向跳跃，求最少要跳跃多少次能到达M-1，N-1的位置。无法到达目的地时返回-1。

M<=100，N<=100，每个桩上允许跳跃的最大步数均为小于10的正整数，0表示不允许跳跃到该位置

**输入描述：**  
1、第1行为M和N，用"，"号隔开;  
2、第2行为M\*N的梅花桩(格式参考样例)，数组位置为允许跳跃的最大步数，0表示该位置为空不能跳跃到该位置。

3,3
    3 2 2 0 1 0 1 1 1

**输出描述**  
最少跳跃的步数

## 参考代码 ##

暴力, 对每一个点更新其可以走到的所有点的最短步数即可

public class TechGuide{ 
        static class Node{ 
            int row;
            int col;
            public Node(int row, int col){ 
                this.row = row;
                this.col = col;
            }
    
            @Override
            public boolean equals(Object o) { 
                if (this == o) return true;
                if (o == null || getClass() != o.getClass()) return false;
                Node node = (Node) o;
                return row == node.row &&
                    col == node.col;
            }
    
            @Override
            public int hashCode() { 
                return Objects.hash(row, col);
            }
        }
    
        static int distance(Node node1, Node node2){ 
            return Math.abs(node2.row - node1.row) + Math.abs(node2.col - node1.col);
        }
    
        public static void main(String[] args) { 
            Scanner in = new Scanner(System.in);
            String line1 = in.nextLine();
            String line2 = in.nextLine();
            String[] line1s = line1.split(",");
            String[] line2s = line2.split(" ");
            int m = Integer.parseInt(line1s[0]);
            int n = Integer.parseInt(line1s[1]);
            int[][] nums = new int[m][n];
            for(int i = 0; i < m; i++){ 
                for(int j = 0; j < n; j++)
                    nums[i][j] = Integer.parseInt(line2s[i*m + j]);
            }
            Queue<Node> nodes = new ArrayDeque<>();
            int[][] dp = new int[m][n];
            for(int i =0; i < m; i++){ 
                Arrays.fill(dp[i], Integer.MAX_VALUE);
            }
            dp[0][0] = 0;
            nodes.add(new Node(0,0));
            while(!nodes.isEmpty()){ 
                Node node = nodes.poll();
                int step = nums[node.row][node.col];
                for(int i = step; i > 0; i--){ 
                    for(int row = node.row + i; row >= node.row; row--) { 
                        int col = i - (row - node.row) + node.col ;
                        if (row < m && col < n && nums[row][col] != 0) { 
                            dp[row][col] = Math.min(dp[row][col], dp[node.row][node.col] + 1);
                            Node temp = new Node(row, col);
                            if(!nodes.contains(temp))
                                nodes.add(new Node(row, col));
                            if(temp.row == m -1 && temp.col ==n - 1){ 
                                System.out.println(dp[m - 1][n - 1]);
                                System.exit(0);
                            }
    
                        }
                    }
                }
            }
            System.out.println(-1);
        }
    }
    // 关注TechGuide！ 大厂笔经面经闪电速递！

### CPP版本 ###

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int mod = 1e9 + 7;
    const int inf = 0x3f3f3f3f; 
    const int ninf = 0xc0c0c0c0;
    const int maxn = 100 + 5;
    
    int f[maxn][maxn];
    int dp[maxn][maxn];
    
    int main() { 
        string s;
        cin >> s;
        int n, m;
        sscanf(s.c_str(), "%d,%d", &n, &m);
        for (int i = 0; i < n; ++i) { 
            for (int j = 0; j < m; ++j) { 
                scanf("%d", &f[i][j]);
            }
        }
        memset(dp, inf, sizeof dp);
        dp[0][0] = 0; 
        for (int i = 0; i < n; ++i) { 
            for (int j = 0; j < m; ++j) { 
                int x = f[i][j];
                for (int k = 0; k <= x; ++k) { 
                    if (i + k < n && f[i + k][j] != 0) { 
                        dp[i + k][j] = min(dp[i + k][j], dp[i][j] + 1);
                    }
                    if (j + k < m && f[i][j + k] != 0) { 
                        dp[i][j + k] = min(dp[i][j + k], dp[i][j] + 1);
                    }
                }
            }
        }
        if (dp[n - 1][m - 1] != inf) { 
            cout << dp[n - 1][m - 1];
        } else { 
            cout << -1;
        }
        return 0;
    }
    /* testcases: 3,3 3 2 2 0 1 0 1 1 1 */
    // 关注TechGuide！ 大厂笔经面经闪电速递！

# 第三道：最短编译时间（100%） #

## 题目描述 ##

A公司需要在项目中引入某开源工程，需要评估该开源工程中某模块的编译时间。

当前已知该项目中每个模块的编译时间以及其依赖的模块列表，在拥有无限数量的并行任务的情况下求某个指定模块的最短编译时间。

若模块间存在循环依赖或者依赖的模块不存在，则无法完成编译，返回-1。

**输入描述：**  
第一行输入为目标模块名，  
以后每行输入定义一个模块，包含模块的名字，编译时间，依赖模块列表，用逗号隔开，若依赖模块列表不存在，则表示可以独立编译，例如: module2,10,modulel module1,10  
模块名只包含字母和数字且至少包含1个字符模块数量不超过50000个

module3
    module1,10 
    module2,5
    module3,10,modulel,moduln2

**输出描述：**  
输出最短编译时间，若无法完成编译则输出-1

**解释:**  
module1编译需要10毫秒，module2编译需要5毫秒，module3编译依赖module1和module2同时自身编译也需要10毫秒，所以总编译时间为10+max(10，5)=20毫秒

## 参考代码 ##

拓扑排序, 没看见module后面可以是字母, 用数字写的

public class TechGUide{ 
        public static void main(String[] args) { 
            Scanner in = new Scanner(System.in);
            String name = in.nextLine();
            List<String> strings = new ArrayList<>();
            while(in.hasNextLine()){ 
                String string = in.nextLine();
                strings.add(string);
            }
            Set<String> set = new HashSet<>();
            //开始的标志
            set.add("start");
            //统计所有模块的名称，可以映射
            for(String s: strings){ 
                String[] temp = s.split(",");
                for(int i = 0; i < temp.length; i++){ 
                    if(i != 1){ 
                        set.add(temp[i]);
                    }
    
                }
            }
            //将字母映射成数字
            HashMap<String, Integer> mapping = new HashMap<>();
            int index = 0;
            for(String s : set){ 
                mapping.put(s, index);
                index++;
            }
            //保存节点的下一个节点位置
            HashMap<String, List<String>> relation = new HashMap<>();
            relation.put("start", new ArrayList<String>());
            int[][] weights = new int[set.size()][set.size()];
            for(String s: strings){ 
                String[] temp = s.split(",");
                //String end = temp[0];
                if(temp.length == 2){ 
                    List<String> start = relation.get("start");
                    start.add(temp[0]);
                    weights[mapping.get("start")][mapping.get(temp[0])] = Integer.parseInt(temp[1]);
                } else{ 
                    for(int i = 2; i < temp.length; i++){ 
                        weights[mapping.get(temp[i])][mapping.get(temp[0])] = Integer.parseInt(temp[1]);
                        if(relation.containsKey(temp[i])){ 
                            List<String> next = relation.get(temp[i]);
                            next.add(temp[0]);
                        } else{ 
                            List<String> next = new ArrayList<>();
                            next.add(temp[0]);
                            relation.put(temp[i], next);
    
                        }
                    }
                }
            }
    
            //检查是否有循环依赖
            for(int i = 0; i < set.size() - 1; i++){ 
                for(int j = i + 1; j < set.size(); j++){ 
                    if(weights[i][j] != 0 && weights[j][i] != 0){ 
                        System.out.println(-1);
                        System.exit(0);
                    }
                }
            }
    
            Queue<String> que = new ArrayDeque<>();
            que.add("start");
            //保存执行到该任务需要的最大时间
            int[] end = new int[set.size()];
            int max = 0;
            //从头开始遍历
            while(!que.isEmpty()){ 
                String node = que.poll();
                //执行到结束的模块
                List<String> nextNodes = relation.get(node);
                //缺少模块，提前终止
                if(!node.equals(name) && (nextNodes.size()==0 || nextNodes == null)){ 
                    System.out.println(-1);
                    break;
                }
                //到该任务了，数组到该任务的时候最大时间
                if(node.equals(name)){ 
                    System.out.println(end[mapping.get(node)]);
                    break;
                }
                for(String next : nextNodes){ 
                    que.add(next);
                    end[mapping.get(next)] = Math.max(end[mapping.get(next)], end[mapping.get(node)] + weights[mapping.get(node)][mapping.get(next)]);
                }
    
            }
        }
    }
    /* m2 m2,10,m1 m1,10,m2 */
    /* m2 m2,10,m1 */
    
    /* m3 m1,10 m2,5 m3,10,m1,m2 // 关注TechGuide！ 大厂笔经面经闪电速递！ */

> 恭喜发现宝藏！微信搜索公众号【TechGuide】关注更多新鲜好文和互联网大厂的笔经面经。