【2024-03-20】华为春招笔试三道编程题解

恭喜发现宝藏！搜索公众号【TechGuide】回复公司名，解锁更多新鲜好文和互联网大厂的笔经面经。
作者@TechGuide【全网同名】

订阅专栏： 【专享版】2024最新大厂笔试真题解析，错过必后悔的宝藏资源！

第一题：安排座位

题目描述

一列具有 m 个座位的火车，从起点到终点共停靠 n 个站点，站点编号从0到n-1。发车前有x名乘客预定了座位，因为预定数量可能超出座位数，为了保证效率最大化，请计算如何分配才能是座位利用率最大，并输出最大的座位利用数。

说明:

座位利用数定义为每个座位被使用的站数。例如有两个座位，第一个座位从第 0到 10 站有人坐(表示从0站上车，10站下车，第10站不占座，所以利用率是10-0=10)，第二个座位从第1到9站有人坐，则座位利用率为(10-0)+(9-1)=18。乘客在某站下车后，其他乘客从这一站就可以开始使用这个座位;无需考虑乘客需要更换座位的问题，保证任意时刻列车上乘客数量不超过 m 即可。

输入描述

第一行输入 m、n和x三个数字，分别表示列车座位数量、停靠站点数量和预定乘客数量

1 <= m <= 9

2 <= n <= 20

1 <= x <= 9

接下来x行输入，表示x条预定记录，每行有两个输入，分别表示此预定记录的上车站点和下车站点

输出描述

一个整数，表示最大的座位利用数。

样例

输入

2 11 4
0 1
1 9
0 10
3 8

输出

19

样例说明

选择前三位乘客可以使座位利用率最大:19=(1-0)+(9-1)+(10-0)。若选择后两位乘客，则利用率为15=(10-0)+(8-3)。若选择全部四位乘客，则第3到8站车上存在3名乘客，超出列车座位数。

思路

暴力穷举，循环枚举所有可能的乘客组合，计算每种组合下的座位利用数（某一站点上的乘客数量不超过座位数）。

代码

Java版本

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int seats, stations, bookings;
        seats = scanner.nextInt();
        stations = scanner.nextInt();
        bookings = scanner.nextInt();
        
        int[][] reservations = new int[bookings][2];
        for (int i = 0; i < bookings; i++) {
            reservations[i][0] = scanner.nextInt();
            reservations[i][1] = scanner.nextInt();
        }
        
        int maxUtilization = 0;
        for (int i = 0; i < (1 << bookings); i++) {
            int[] count = new int[stations];
            boolean valid = true;
            int result = 0;
            for (int j = 0; j < bookings; j++) {
                if ((i >> j & 1) == 1) {
                    for (int k = reservations[j][0]; k < reservations[j][1]; k++) {
                        count[k]++;
                    }
                    result += reservations[j][1] - reservations[j][0];
                }
            }
            for (int j = 0; j < stations; j++) {
                if (count[j] > seats) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                maxUtilization = Math.max(maxUtilization, result);
            }
        }
        System.out.println(maxUtilization);
    }
}
// vx公众号关注TechGuide，专业生产offer收割机，代码可能需要少量调试。

CPP版本

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int seats, stations, bookings;
    cin >> seats >> stations >> bookings;

    vector<pair<int, int>> reservations(bookings);
    for (int i = 0; i < bookings; i++) {
        cin >> reservations[i].first >> reservations[i].second;
    }

    int maxUtilization = 0;
    for (int i = 0; i < (1 << bookings); i++) {
        vector<int> count(stations, 0);
        bool valid = true;
        int result = 0;
        for (int j = 0; j < bookings; j++) {
            if ((i >> j) & 1) {
                for (int k = reservations[j].first; k < reservations[j].second; k++) {
                    count[k]++;
                }
                result += reservations[j].second - reservations[j].first;
            }
        }
        for (int j = 0; j < stations; j++) {
            if (count[j] > seats) {
                valid = false;
                break;
            }
        }
        if (valid) {
            maxUtilization = max(maxUtilization, result);
        }
    }
    cout << maxUtilization << endl;
    return 0;
}
// vx公众号关注TechGuide，专业生产offer收割机，代码可能需要少量调试。

第二题：积木塔

题目描述

小盖在玩积木塔游戏。他有一系列的积木块，每块上标有一个正整数。他按照特定的规则堆积这些积木块：每次小盖添加一块新的积木时，如果这块积木上的数字与塔顶的积木数字相同，他会取下两块积木，将上面的数字相加后乘以二，然后放回一块新的积木。此外，如果塔顶的积木数字等于下面连续几块积木数字之和，他同样会取下这些积木，进行相同的操作。如果这两个条件都不符合，他就会简单地将新的积木放在塔顶。

现在，小盖按照一定顺序添加了一系列的积木，请你计算游戏结束后积木塔各块上的数字。

输入描述

第一行输入为一个由空格分隔的正整数序列，表示小盖按顺序添加到积木塔中的积木块上的数字。

输出描述

输出为一个由空格分隔的正整数序列，从左到右依次表示游戏结束后从塔顶到塔底的积木块上的数字。

样例

输入

55 66 121 5 5

输出

10 242

思路

模拟。看到积木塔>>先进后出>>栈模拟，根据游戏规则遍历操作，两种情况，如果当前积木的数字与塔顶的数字相同或等于下面连续几块积木的数字之和，则取下对应积木块，再乘以二，重新入栈。

代码

Java版本

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] inputs = scanner.nextLine().split(" ");
        List<Integer> tower = new ArrayList<>();

        for (String input : inputs) {
            int block = Integer.parseInt(input);
            boolean flag = true;
            while (flag && sum(tower) >= block) {
                int sum = 0;
                int count = 0;
                for (int i = tower.size() - 1; i >= 0; i--) {
                    sum += tower.get(i);
                    count++;
                    if (sum == block) {
                        for (int j = 0; j < count; j++) {
                            block += tower.remove(tower.size() - 1);
                        }
                        break;
                    } else if (sum > block) {
                        flag = false;
                        break;
                    }
                }
            }
            tower.add(block);
        }
        
        Collections.reverse(tower);
        for (int block : tower) {
            System.out.print(block + " ");
        }
    }

    private static int sum(List<Integer> list) {
        int total = 0;
        for (int num : list) {
            total += num;
        }
        return total;
    }
}
// vx公众号关注TechGuide，专业生产offer收割机，代码可能需要少量调试。

CPP版本

#include <iostream>
#include <vector>
#include <sstream>
using namespace std;

int main() {
    string line;
    getline(cin, line);
    istringstream iss(line);
    vector<int> tower;
    string num;
    while (iss >> num) {
        int block = stoi(num);
        bool flag = true;
        while (flag && accumulate(tower.begin(), tower.end(), 0) >= block) {
            int sum = 0;
            int count = 0;
            for (int i = tower.size() - 1; i >= 0; i--) {
                sum += tower[i];
                count++;
                if (sum == block) {
                    for (int j = 0; j < count; j++) {
                        block += tower.back();
                        tower.pop_back();
                    }
                    break;
                } else if (sum > block) {
                    flag = false;
                    break;
                }
            }
        }
        tower.push_back(block);
    }

    reverse(tower.begin(), tower.end());
    for (int block : tower) {
        cout << block << " ";
    }
    return 0;
}
// vx公众号关注TechGuide，专业生产offer收割机，代码可能需要少量调试。

第三题：循环依赖

题目描述

给定一组元素，及其依赖关系，一个元素可以依赖于多个元素(不包括自己，被依赖元素不会重复)一个元素也可被多个元素依赖。假定总是存在唯一的循环依赖，请输出该循环依赖。

输入描述

第一行一个正整数N，表示依赖关系的个数。

接下来每一行表示一个依赖关系，是由空格分割的多个正整数，第一个数n表示后面有n个元素，第二个数为元素编号a，后面多个数为a依赖的元素编号。

输出描述

一串数字，代表这个循环依赖，从最小元素编号开始，按照依赖关系依次输出，以最小元素结束。

样例

输入

3
3 1 2 5
3 2 3 4
2 3 1

输出

1 2 3 1

样例说明

元素1依赖于2，5
元素2依赖于3，4
元素3依赖于1

思路

dfs，深度优先搜索遍历节点，维护一个栈来记录遍历的路径，如果某个节点在本次遍历中已经被访问过，而且在栈中存在，那么说明存在环，直接输出环即可。注意递归的终止条件，以及节点反序，具体结合代码看。

代码

Java版本

import java.util.*;

public class Main {
    static final int MAX = 10000;
    static List<Integer>[] graph = new ArrayList[MAX];
    static int[] visited = new int[MAX];
    static int[] inStack = new int[MAX];
    static Stack<Integer> stack = new Stack<>();
    static List<Integer> result = new ArrayList<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for (int i = 0; i < MAX; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < n; i++) {
            int k = scanner.nextInt();
            int a = scanner.nextInt();
            for (int j = 0; j < k - 1; j++) {
                int b = scanner.nextInt();
                graph[a].add(b);
            }
        }

        for (int i = 1; i < MAX; i++) {
            if (visited[i] == 0) {
                if (dfs(i)) {
                    break;
                }
            }
        }

        if (!result.isEmpty()) {
            Collections.reverse(result);
            int minValue = Collections.min(result);
            int index = result.indexOf(minValue);
            List<Integer> finalResult = new ArrayList<>(result.subList(index, result.size()));
            finalResult.addAll(result.subList(0, index + 1));
            for (int node : finalResult) {
                System.out.print(node + " ");
            }
        }
    }

    static boolean dfs(int u) {
        if (visited[u] == 1) {
            if (!stack.isEmpty() && inStack[u] == 1) {
                while (!stack.isEmpty() && stack.peek() != u) {
                    result.add(stack.pop());
                }
                result.add(u);
                stack.pop();
                return true;
            } else {
                return false;
            }
        }

        visited[u] = 1;
        stack.push(u);
        inStack[u] = 1;
        for (int v : graph[u]) {
            if (dfs(v)) {
                return true;
            }
        }
        inStack[u] = 0;
        stack.pop();
        return false;
    }
}
// vx公众号关注TechGuide，专业生产offer收割机，代码可能需要少量调试。

CPP版本

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

const int MAX = 10000;
vector<int> graph[MAX];
int visited[MAX] = {0};
int inStack[MAX] = {0};
stack<int> stk;
vector<int> result;

bool dfs(int u) {
    if (visited[u] == 1) {
        if (!stk.empty() && inStack[u] == 1) {
            while (!stk.empty() && stk.top() != u) {
                result.push_back(stk.top());
                stk.pop();
            }
            result.push_back(u);
            stk.pop();
            return true;
        } else {
            return false;
        }
    }

    visited[u] = 1;
    stk.push(u);
    inStack[u] = 1;
    for (int v : graph[u]) {
        if (dfs(v)) {
            return true;
        }
    }
    inStack[u] = 0;
    stk.pop();
    return false;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < MAX; i++) {
        graph[i].clear();
    }

    for (int i = 0; i < n; i++) {
        int k;
        cin >> k;
        int a;
        cin >> a;
        for (int j = 0; j < k - 1; j++) {
            int b;
            cin >> b;
            graph[a].push_back(b);
        }
    }

    for (int i = 1; i < MAX; i++) {
        if (visited[i] == 0) {
            if (dfs(i)) {
                break;
            }
        }
    }

    if (!result.empty()) {
        reverse(result.begin(), result.end());
        int minValue = *min_element(result.begin(), result.end());
        int index = find(result.begin(), result.end(), minValue) - result.begin();
        vector<int> finalResult(result.begin() + index, result.end());
        finalResult.insert(finalResult.end(), result.begin(), result.begin() + index + 1);
        for (int node : finalResult) {
            cout << node << " ";
        }
    }

    return 0;
}

// vx公众号关注TechGuide，专业生产offer收割机，代码可能需要少量调试。