🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

✨ 本系列打算持续跟新 春秋招笔试题

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

🍒 本专栏已收集 120+ 套笔试题，笔试真题 会在第一时间跟新

🍄 题面描述等均已改编，如果和你笔试题看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🌈 华为秋招(海外留学生版)笔试，来啦！！！

🍥 留学生的题目难度相对于国内来说总体来看会简单一丢丢，但整体题目风格，难度，几乎都是一样的哦～

tips 国内的有些题会复用留学生考过的题目哦，国内机考的朋友可以把留学生的题目也刷一刷

1️⃣ 推公式/枚举/二分，这题的做法很多，由于数据比较小，大家怎么做都可以哈

2️⃣ 模拟题，华子最喜欢的阅读理解+模拟，建议大家多练！！！

3️⃣ 力扣原题改编，今年秋招华为出了很多这种力扣的改编题，基本二三两题都是有出处的，大家平时没事可以多刷刷扣子，打打牛客/力扣的周赛。

💎 01.珠宝商的难题 评测链接🔗

问题描述

K小姐是一位著名的珠宝商，她最近收到了一批特殊的宝石。每颗宝石都有一个独特的"光泽值"，这个值是由宝石的十六进制编码中各位数字之和决定的（0-9代表0-9，A:10、B:11、C:12、D:13、E:14、F:15）。

K小姐想要将这些宝石按照特定的顺序排列，她需要知道每颗宝石右侧第一个光泽值更高的宝石的位置。如果一颗宝石右侧没有光泽值更高的宝石，则记为-1。

请你帮助K小姐设计一个程序，来解决这个排列问题。

输入格式

第一行包含一个正整数 ，表示宝石的数量。

第二行包含 个由空格分隔的非负整数，表示每颗宝石的编码。

输出格式

一行，包含 个整数，表示每颗宝石右侧第一个光泽值更高的宝石的位置（索引从0开始），如果不存在则输出-1。

样例输入1

3
12 3 24

样例输出1

-1 2 -1

样例输入2

5
15 8 23 42 7

样例输出2

-1 3 3 -1 -1

样例解释

数据范围

题解

单调栈

本质是找出数组中每个元素右侧第一个更大元素的位置，这个可以用单调栈来解决，但是需要先将原始的宝石编码转换为"光泽值"。

从右向左遍历数组，维护一个单调递减的栈，具体步骤如下：

1. 首先，将所有宝石编码转换为光泽值。
2. 从右向左遍历光泽值数组。
3. 对于每个元素，while循环比较栈顶元素：
   • 如果当前元素的光泽值大于栈顶元素的光泽值，就将栈顶元素弹出。
   • 重复这个过程，直到栈为空或者栈顶元素的光泽值大于当前元素。
4. 如果栈不为空，栈顶元素就是当前元素右侧第一个光泽值更大的元素。
5. 将当前元素的索引压入栈中。

这个算法的时间复杂度是 ，因为每个元素最多入栈和出栈一次。空间复杂度也是 ，用于存储结果数组和栈。

参考代码

• Python

def calculate_gloss(n):
    """计算宝石的光泽值"""
    gloss = 0
    while n > 0:
        gloss += n % 16
        n //= 16
    return gloss

def find_next_greater(gems):
    n = len(gems)
    gloss_values = [calculate_gloss(gem) for gem in gems]
    result = [-1] * n
    stack = []

    # 从右向左遍历
    for i in range(n - 1, -1, -1):
        # 当栈不为空且当前元素的光泽值大于栈顶元素的光泽值时
        while stack and gloss_values[i] >= gloss_values[stack[-1]]:
            stack.pop()
        
        # 如果栈不为空，栈顶元素就是右侧第一个光泽值更大的宝石
        if stack:
            result[i] = stack[-1]
        
        # 将当前索引入栈
        stack.append(i)

    return result

# 读取输入
n = int(input())
gems = list(map(int, input().split()))

# 计算结果并输出
result = find_next_greater(gems)
print(*result)

• Java

import java.util.*;

public class Main {
    // 计算宝石的光泽值
    private static int calculateGloss(long n) {
        int gloss = 0;
        while (n > 0) {
            gloss += (int)(n % 16);
            n /= 16;
        }
        return gloss;
    }

    // 找出每个宝石右侧第一个光泽值更高的宝石位置
    private static int[] findNextGreater(long[] gems) {
        int n = gems.length;
        int[] glossValues = new int[n];
        for (int i = 0; i < n; i++) {
            glossValues[i] = calculateGloss(gems[i]);
        }

        int[] result = new int[n];
        Arrays.fill(result, -1);
        Stack<Integer> stack = new Stack<>();

        // 从右向左遍历
        for (int i = n - 1; i >= 0; i--) {
            // 当栈不为空且当前元素的光泽值大于等于栈顶元素的光泽值时
            while (!stack.isEmpty() && glossValues[i] >= glossValues[stack.peek()]) {
                stack.pop();
            }

            // 如果栈不为空，栈顶元素就是右侧第一个光泽值更大的宝石
            if (!stack.isEmpty()) {
                result[i] = stack.peek();
            }

            // 将当前索引入栈
            stack.push(i);
        }

        return result;
    }

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

        int[] result = findNextGreater(gems);
        for (int i = 0; i < n; i++) {
            System.out.print(result[i] + (i == n - 1 ? "" : " "));
        }
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
#define int long long
// 计算宝石的光泽值
int calculateGloss(int n) {
    int gloss = 0;
    while (n > 0) {
        gloss += n % 16;
        n /= 16;
    }
    return gloss;
}

// 找出每个宝石右侧第一个光泽值更高的宝石位置
vector<int> findNextGreater(const vector<int>& gems) {
    int n = gems.size();
    vector<int> glossValues(n);
    for (int i = 0; i < n; i++) {
        glossValues[i] = calculateGloss(gems[i]);
    }

    vector<int> result(n, -1);
    stack<int> s;

    // 从右向左遍历
    for (int i = n - 1; i >= 0; i--) {
        // 当栈不为空且当前元素的光泽值大于等于栈顶元素的光泽值时
        while (!s.empty() && glossValues[i] >= glossValues[s.top()]) {
            s.pop();
        }

        // 如果栈不为空，栈顶元素就是右侧第一个光泽值更大的宝石
        if (!s.empty()) {
            result[i] = s.top();
        }

        // 将当前索引入栈
        s.push(i);
    }

    return result;
}

signed main() {
    int n;
    cin >> n;
    vector<int> gems(n);
    for (int i = 0; i < n; i++) {
        cin >> gems[i];
    }

    vector<int> result = findNextGreater(gems);
    for (int i = 0; i < n; i++) {
        cout << result[i] << (i == n - 1 ? "" : " ");
    }
    return 0;
}

🤖 02.智能仓库机器人 评测链接🔗

问题描述

在未来的智能仓库中，LYA公司开发了一款先进的机器人用于管理货架。仓库由一排排货架组成，每个货架有多层，每层可以放置一个货物。货物从底层开始摆放，每个货架的货物数量是随机的，但至少有一个。

这款机器人有两种检查模式：

1. 横向检查：可以同时检查多个货架的同一层，耗时1分钟。
2. 纵向检查：只能检查单个货架的所有层，耗时2分钟。

检查规则：

• 允许重复检查同一货物，但每次检查必须是连续的一段货架或货层。
• 单个货物的检查默认使用纵向检查，耗时2分钟。
• 检查时间与货物数量无关，只与检查模式有关。

请计算机器人检查完所有货物所需的最少时间。

输入格式

输入包含两行：

• 第一行是一个整数 ，表示货架的数量。
• 第二行包含 个整数 ，用空格分隔，表示每个货架的货物数量。

输出格式

输出一个整数，表示检查完所有货物所需的最少时间（以分钟为单位）。

样例输入1

3
5 5 5

样例输出1

1

样例输入2

5
2 2 1 2 1

样例输出2

4

样例输入3

5
7 4 3 3 5

样例输出3

6

样例解释

数据范围

• 
• ，其中

题解

DFS/记忆化搜索

本题暴力DFS应该也可以过，这里加一个记忆化数组来优化一下

关键思路是：对于任意一段连续的货架，我们有两种选择：

1. 使用横向检查，覆盖这段货架的最低层，然后递归处理剩余的上层货物。
2. 对每个货架单独使用纵向检查。

可以定义一个函数 dfs(left, right)，表示检查从 left 到 right 号货架所需的最少时间。那么对于任意一段货架，可以这样计算：

1. 找出这段货架中最矮的货架高度 minH。
2. 计算使用横向检查的成本：1分钟（横向检查最底层）+ 递归处理剩余上层货物的成本。
3. 计算使用纵向检查的成本：每个货架2分钟。
4. 取这两种方法中的最小值。

参考代码

• Python

import sys
sys.setrecursionlimit(10**7)
def dfs(left, right, shelf_heights, memo):
    """
    深度优先搜索函数，计算检查从left到right货架所需的最少时间
    
    参数:
    left (int): 左边界货架索引
    right (int): 右边界货架索引
    shelf_heights (list): 货架高度列表
    memo (dict): 记忆化搜索的缓存字典
    
    返回:
    int: 检查所需的最少时间
    """
    if left > right:
        return 0
    if left == right:
        return 2  # 单个货架默认使用纵向检查
    
    # 检查是否已经计算过这个区间
    if (left, right) in memo:
        return memo[(left, right)]
    
    min_height = min(shelf_heights[left:right+1])
    horizontal_cost = 1  # 横向检查的基础成本
    i = left
    while i <= right:
        if shelf_heights[i] > min_height:
            start = i
            while i <= right and shelf_heights[i] > min_height:
                i += 1
            horizontal_cost += dfs(start, i-1, shelf_heights, memo)
        else:
            i += 1
    
    vertical_cost = 2 * (right - left + 1)  # 纵向检查的总成本
    
    # 选择成本较低的检查方式
    result = min(horizontal_cost, vertical_cost)
    memo[(left, right)] = result
    return result

# 读取输入
n = int(input())
shelf_heights = list(map(int, input().split()))
memo = {}
# 计算并输出结果
result = dfs(0, n-1, shelf_heights, memo)
print(result)

• Java

import java.util.*;

public class Main {
    static int[] shelfHeights;
    static Map<String, Integer> memo = new HashMap<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        shelfHeights = new int[n];
        for (int i = 0; i < n; i++) {
            shelfHeights[i] = scanner.nextInt();
        }
        int result = dfs(0, n - 1);
        System.out.println(result);
    }

    /**
     * 深度优先搜索函数，计算检查从left到right货架所需的最少时间
     * 
     * @param left 左边界货架索引
     * @param right 右边界货架索引
     * @r