华为笔试华为留学生笔试 0920

笔试时间：2024年09月20日秋招

历史笔试传送门：2023秋招笔试合集

第一题

题目：十六进制权重数组分析

设计一个程序来处理特定的数组分析问题。给定一个非负整数数组arr，其中每个整数用其十六进制表示中的数字之和来表示其“权重”(权重计算是基于十六进制表示中每位数字的和， 0~9代表权重0~9，权重A：10、B:11、C:12、D:13、E:14、F:15)。您的任务是找出数组中每个元素右侧第一个具有更大“权重”的元素，并返回一个新的数组，该数组包含这些元素的索引。如果一个元素的右侧没有更大“权重”的元素，则对应位置返回-1。

输入描述

第一行:一个整数N，表示数组arr的大小；

第二行: N个由空格分隔的非负整数，表示数组 arr。

输出描述

一行:N个整数，表示每个元素右侧第一个权重更大的元素的索引，如果不存在则为-1。

样例输入一

3

12 3 24

样例输出一

-1 2 -1

说明：

十六进制表示分别为:[C, 3, 18]

对应的权重分别为:[12, 3, 1+8=9]

对于第一个元素 12(权重12)，其右侧没有更大权重的元素-1，因此返回-1

对于第二个元素3 (权重3)，其右侧第一个更大权重的元素是24(权重9)，位于索引2

对于第三个元素24 (权重9)，其不侧没有更大权重的元素，因此返回-1。

样例输入二

5

15 8 23 42 7

样例输出二

-1 3 3 -1 -1

说明：

十六进制表示分别为:[F，8，17，2A，7]

对应的权重分别为:[15，8，8，2+10=12，7]

对于第一个元素15 (权重15)，其右侧没有更大权重的元素，因此返回-1

对于第二个元素8(权重8)和第三个元素23 (权重8)，右侧第一个更大权重的元素是42(权重12)，位于索引3

对于第四个元素42(权重12)和第五个元素7(权重7)，其右侧没有更大权重的元素，因此对应位置返回-1。

参考题解

计算每个元素的“权重”（基于其十六进制表示中各位数字的和），然后找出每个元素右侧第一个具有更大“权重”的元素的索引。如果不存在，则返回 -1。我们可以使用单调栈来高效地解决这个问题。使用单调栈从右向左遍历数组，计算每个元素的权重并记录其右侧第一个更大权重元素的索引，不存在则为-1。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <bits/stdc++.h>
using namespace std;

// 函数用于计算整数 n 的十六进制表示中各位数字的和
int compute_weight(unsigned int n) {
    if (n == 0) return 0;
    int sum = 0;
    while (n > 0) {
        sum += (n & 0xF); // 获取最低四位
        n >>= 4;          // 右移四位
    }
    return sum;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N;
    cin >> N;
    vector<unsigned int> arr(N);
    for(int i=0; i<N; ++i){
        cin >> arr[i];
    }
    
    // 计算每个元素的权重
    vector<int> weights(N);
    for(int i=0; i<N; ++i){
        weights[i] = compute_weight(arr[i]);
    }
    
    // 初始化答案数组，默认所有位置为 -1
    vector<int> answer(N, -1);
    // 使用栈存储索引
    stack<int> st;
    
    // 从右到左遍历
    for(int i = N-1; i >=0; --i){
        // 弹出栈中所有权重小于或等于当前元素的索引
        while(!st.empty() && weights[st.top()] <= weights[i]){
            st.pop();
        }
        // 如果栈不为空，栈顶元素就是右侧第一个更大权重的元素
        if(!st.empty()){
            answer[i] = st.top();
        }
        // 将当前元素的索引压入栈中
        st.push(i);
    }
    
    // 输出结果
    for(int i=0; i<N; ++i){
        if(i > 0) cout << ' ';
        cout << answer[i];
    }
    cout << '\n';
    
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.io.*;
import java.util.*;

public class Main {
    // 函数用于计算整数 n 的十六进制表示中各位数字的和
    public static int computeWeight(long n){
        if(n == 0) return 0;
        int sum = 0;
        while(n > 0){
            sum += (n & 0xF);
            n >>=4;
        }
        return sum;
    }
    
    public static void main(String[] args) throws IOException {
        // 使用 BufferedReader 和 BufferedWriter 提高输入输出效率
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        // 读取第一个输入，数组的大小 N
        int N = Integer.parseInt(br.readLine());
        
        // 读取第二行的 N 个整数
        st = new StringTokenizer(br.readLine());
        long[] arr = new long[N];
        for(int i=0; i<N; i++){
            arr[i] = Long.parseUnsignedLong(st.nextToken());
        }
        
        // 计算每个元素的权重
        int[] weights = new int[N];
        for(int i=0; i<N; i++){
            weights[i] = computeWeight(arr[i]);
        }
        
        // 初始化答案数组，默认所有位置为 -1
        int[] answer = new int[N];
        Arrays.fill(answer, -1);
        
        // 使用栈存储索引
        Deque<Integer> stack = new ArrayDeque<>();
        
        // 从右到左遍历数组
        for(int i=N-1; i>=0; i--){
            // 弹出栈中所有权重小于或等于当前元素的索引
            while(!stack.isEmpty() && weights[stack.peek()] <= weights[i]){
                stack.pop();
            }
            // 如果栈不为空，栈顶元素就是右侧第一个更大权重的元素
            if(!stack.isEmpty()){
                answer[i] = stack.peek();
            }
            // 将当前元素的索引压入栈中
            stack.push(i);
        }
        
        // 构建输出结果
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<N; i++){
            sb.append(answer[i]);
            if(i != N-1){
                sb.append(' ');
            }
        }
        sb.append('\n');
        bw.write(sb.toString());
        bw.flush();
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

def compute_weight(n):
    """计算整数 n 的十六进制表示中各位数字的和"""
    if n == 0:
        return 0
    s = 0
    while n > 0:
        digit = n & 0xF  # 获取最低四位，即一个十六进制数字
        s += digit
        n >>= 4  # 右移四位，处理下一个十六进制数字
    return s

def main():
    import sys
    # 读取第一个输入，数组的大小 N
    N = int(input())
    
    # 读取第二行的 N 个整数
    arr = list(map(int, input().split()))
    
    # 确保读取的数组长度与 N 一致
    if len(arr) != N:
        print("输入的数组长度与指定的 N 不一致。")
        return
    
    # 计算每个元素的权重
    weights = [compute_weight(num) for num in arr]
    
    # 初始化答案数组，默认所有位置为 -1
    answer = [-1] * N
    
    stack = []  # 栈中存储的是元素的索引
    
    # 从右到左遍历数组
    for i in range(N-1, -1, -1):
        # 弹出栈中所有权重小于或等于当前元素权重的元素
        while stack and weights[stack[-1]] <= weights[i]:
            stack.pop()
        # 如果栈不为空，栈顶元素就是右侧第一个权重更大的元素
        if stack:
            answer[i] = stack[-1]
        else:
            answer[i] = -1
        # 将当前元素的索引压入栈中
        stack.append(i)
    
    # 输出结果，以空格分隔
    print(' '.join(map(str, answer)))

if __name__ == "__main__":
    main()

第二题

题目：服务器健康巡检

在一个未来的超级数据中心，有一排存放服务器的阵列，阵列由一列一列的机架组成，机架的每一行可以存放一个服务器，每列架子的服务器都是自底向上依次摆放，摆放的个数是随机且大于0的。现在有一个运维机器人用来检查服务器健康状态，机器人有行列2种检查模式：行检查支持多行服务器一起检查，检查时间为1秒。列检查仅支持单列服务器检查，检查时间为2秒。约束说明：允许在同一个服务器检查多次，但同一次行、列检查模式的服务器必须为连续的一段。单独的一个服务器检查，默认采用列检查方式，检查时间为2秒。行、列检查时间跟检查列的服务器数量无关，仅与检查模式相关。请问机器人最少要花费多少时间才能检查完整个数据中心的服务器。

解答要求：时间限制：C/C++ 5000ms，其他语言：10000ms内存限制：C/C++ 256MB，其他语言：512MB