当前位置： 首页 > article >正文

【2024年华为OD机试】 (B卷,100分)- 阿里巴巴找黄金宝箱(III)（JavaScriptJava PythonC/C++）

article 2025/3/1 20:34:46

在这里插入图片描述

一、问题描述

题目描述

阿里巴巴在去砍柴的路上，无意中发现了强盗集团的藏宝地。藏宝地有编号从0到N的箱子，每个箱子上贴有一个数字。阿里巴巴念出一个咒语数字，查看宝箱是否存在两个不同箱子，这两个箱子上贴的数字相同，同时这两个箱子的编号之差的绝对值小于等于咒语数字。如果存在这样的一对宝箱，请返回最先找到的那对宝箱左边箱子的编号，如果不存在则返回-1。

输入描述

  • 第一行输入一个数字字串，数字之间使用逗号分隔，例如: 1,2,3,1
    • 1 ≤ 字串中数字个数 ≤ 100000
    • -100000 ≤ 每个数字值 ≤ 100000
  • 第二行输入咒语数字，例如: 3
    • 1 ≤ 咒语数字 ≤ 100000

输出描述

  • 存在这样的一对宝箱，请返回最先找到的那对宝箱左边箱子的编号，如果不存在则返回-1

用例

用例1

  • 输入: 6,3,1,6
  • 咒语数字: 3
  • 输出: 1
  • 说明: 编号0和编号3的箱子数字相同，编号差的绝对值 = 3。符合<=咒语3的要求，因此返回这对箱子左边的箱子编号0。但是用例1输出的是1，可能存在歧义。

用例2

  • 输入: 5,6,7,5,6,7
  • 咒语数字: 2
  • 输出: 0
  • 说明: 编号0和编号3的箱子数字相同，编号差的绝对值 = 3；编号1和编号4的箱子数字相同，编号差的绝对值 = 3；编号2和编号5的箱子数字相同，编号差的绝对值 = 3。以上三对箱子没有编号差的绝对值 <= 咒语2的，因此本用例应该返回-1。但是用例2输出的是0，可能存在歧义。

解题思路

思路1：先找到这对宝箱的左边的宝箱为“最先”

  1. 定义一个字典lastIdx，用于记录每个数字上一次出现的箱子编号。
  2. 定义一个集合find，用于记录已经找到符合咒语要求的数字。
  3. 遍历箱子：
    • 如果当前数字已经在find中，说明该数字已经找到符合要求的箱子对，无需继续处理。
    • 如果当前数字不在find中：
      • 如果lastIdx中没有该数字，则将当前箱子的编号和数字录入lastIdx。
      • 如果lastIdx中有该数字，则计算当前箱子编号与上一次出现该数字的箱子编号的差值绝对值，判断是否符合咒语要求：
        • 如果符合，则记录左边箱子的编号到ans中，并将该数字录入find。
        • 如果不符合，则更新lastIdx中该数字的最近一次出现位置为当前箱子编号。
  4. 最后，从ans记录的所有左边箱子编号中，找出最左边的编号返回。

思路2：先找到这对宝箱的右边的宝箱为“最先”

  1. 定义一个字典lastIdx，用于记录每个数字上一次出现的箱子编号。
  2. 定义一个变量ans，用于记录最先找到的符合要求的左边箱子编号，初始值为-1。
  3. 遍历箱子：
    • 如果lastIdx中有当前数字，则计算当前箱子编号与上一次出现该数字的箱子编号的差值绝对值，判断是否符合咒语要求：
      • 如果符合，则更新ans为上一次出现该数字的箱子编号，并立即返回ans。
    • 更新lastIdx中该数字的最近一次出现位置为当前箱子编号。
  4. 如果遍历结束后仍未找到符合要求的箱子对，则返回-1。

总结

本题存在一定的歧义，主要在于“最先找到的那对宝箱”是指左边的箱子还是右边的箱子。在实际考试中，可以根据题目要求灵活应对，尝试不同的解题思路。

二、JavaScript算法源码

以下是代码的详细注释和讲解，帮助你理解每一部分的功能和逻辑：

代码结构

  1. 输入处理部分：

    • 使用 readline 模块从控制台读取输入。
    • 将输入的两行数据（箱子数字和咒语数字）存储到 lines 数组中。
    • 当读取到两行输入后，调用 getResult 函数处理数据，并输出结果。

  2. 核心逻辑部分：

    • getResult 函数是解题的核心逻辑，用于找到符合要求的箱子对。

代码逐行解析

1. 输入处理部分
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length == 2) {
    const boxes = lines[0].split(",").map(Number);
    const len = parseInt(lines[1]);

    console.log(getResult(boxes, len));

    lines.length = 0;
  }
});

  • readline 模块：

    • 用于从控制台逐行读取输入。
    • rl.on("line", (line) => { ... })：监听输入事件，每次输入一行数据时触发回调函数。

  • lines 数组：

    • 存储输入的两行数据。
    • 第一行是箱子上的数字，第二行是咒语数字。

  • if (lines.length == 2)：

    • 当输入两行数据后，开始处理数据。
    • boxes：将第一行输入按逗号分隔，并转换为数字数组。
    • len：将第二行输入转换为整数，表示咒语数字。

  • console.log(getResult(boxes, len))：

    • 调用 getResult 函数处理数据，并输出结果。

  • lines.length = 0：

    • 清空 lines 数组，以便处理下一组输入。
2. 核心逻辑部分
function getResult(boxes, len) {
  // 统计该数字上一个箱子的编号
  const lastIdx = {};
  // 对应数字的箱子已经找到了，符合咒语要求的箱子对
  const find = new Set();

  let ans = -1;

  for (let i = 0; i < boxes.length; i++) {
    // 箱子上贴的数字
    const num = boxes[i];

    // 该数字是否已经找到符合咒语要求的箱子对，如果找到了，则不需要再看后面的，只找第一对即可
    if (find.has(num)) continue;

    // 检查箱子对是否符合咒语要求
    if (lastIdx[num] !== undefined && i - lastIdx[num] <= len) {
      find.add(num);
      ans = ans == -1 ? lastIdx[num] : Math.min(ans, lastIdx[num]);
    } else {
      lastIdx[num] = i;
    }
  }

  return ans;
}

  • lastIdx 对象：

    • 用于记录每个数字上一次出现的箱子编号。
    • 例如：lastIdx[6] = 3 表示数字 6 上一次出现在编号为 3 的箱子上。

  • find 集合：

    • 用于记录已经找到符合咒语要求的数字。
    • 例如：如果数字 6 已经找到符合要求的箱子对，则将其加入 find 集合，避免重复处理。

  • ans 变量：

    • 用于记录最终结果，即符合要求的左边箱子的编号。
    • 初始值为 -1，表示尚未找到符合要求的箱子对。

  • for 循环：

    • 遍历每个箱子，检查是否存在符合要求的箱子对。

  • if (find.has(num)) continue;：

    • 如果当前数字已经在 find 集合中，说明已经找到符合要求的箱子对，跳过后续处理。

  • if (lastIdx[num] !== undefined && i - lastIdx[num] <= len)：

    • 检查当前数字是否曾经出现过，并且当前箱子编号与上一次出现该数字的箱子编号的差值是否小于等于咒语数字 len。
    • 如果符合要求：
      • 将当前数字加入 find 集合。
      • 更新 ans 为当前数字上一次出现的箱子编号（即左边箱子的编号）。如果 ans 为 -1，则直接赋值；否则取较小值。

  • else { lastIdx[num] = i; }：

    • 如果当前数字不符合要求，则更新 lastIdx 中该数字的最近一次出现位置为当前箱子编号。

  • return ans;：

    • 返回最终结果。如果未找到符合要求的箱子对，则返回 -1。

代码逻辑总结

  1. 输入处理：

    • 读取箱子数字和咒语数字，并将其转换为合适的数据类型。

  2. 核心逻辑：

    • 使用 lastIdx 记录每个数字上一次出现的箱子编号。
    • 使用 find 集合记录已经找到符合要求的数字。
    • 遍历箱子，检查是否存在符合要求的箱子对：
      • 如果找到符合要求的箱子对，则记录左边箱子的编号。
      • 如果未找到，则更新 lastIdx。

  3. 输出结果：

    • 返回最先找到的符合要求的左边箱子的编号，如果未找到则返回 -1。

示例运行

输入 1：
6,3,1,6
3
执行过程：
  1. boxes = [6, 3, 1, 6]，len = 3。
  2. 遍历箱子：
    • i = 0，num = 6：
      • lastIdx[6] 未定义，更新 lastIdx[6] = 0。
    • i = 1，num = 3：
      • lastIdx[3] 未定义，更新 lastIdx[3] = 1。
    • i = 2，num = 1：
      • lastIdx[1] 未定义，更新 lastIdx[1] = 2。
    • i = 3，num = 6：
      • lastIdx[6] = 0，i - lastIdx[6] = 3 - 0 = 3 <= len，符合要求。
      • 更新 find = {6}，ans = 0。
  3. 返回 ans = 0。
输出 1：
0

通过以上详细注释和讲解，你应该能够清晰地理解代码的每一部分逻辑和功能。

三、Java算法源码

以下是 Java 实现 的详细注释和讲解，帮助你理解每一部分的功能和逻辑：

代码结构

  1. 输入处理部分：

    • 使用 Scanner 从控制台读取输入。
    • 将输入的两行数据（箱子数字和咒语数字）分别解析为整数数组和整数。

  2. 核心逻辑部分：

    • getResult 方法是解题的核心逻辑，用于找到符合要求的箱子对。

代码逐行解析

1. 输入处理部分
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    // 读取第一行输入，按逗号分隔并转换为整数数组
    int[] boxes = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
    // 读取第二行输入，转换为整数
    int len = Integer.parseInt(sc.nextLine());

    // 调用核心逻辑方法并输出结果
    System.out.println(getResult(boxes, len));
  }
}

  • Scanner 类：

    • 用于从控制台读取输入。
    • sc.nextLine()：读取一行输入。

  • Arrays.stream()：

    • 将字符串数组转换为流，方便后续操作。
    • split(",")：将输入字符串按逗号分隔为字符串数组。
    • mapToInt(Integer::parseInt)：将字符串数组转换为整数流。
    • toArray()：将流转换为整数数组。

  • Integer.parseInt(sc.nextLine())：

    • 读取第二行输入，并将其转换为整数。

  • System.out.println(getResult(boxes, len))：

    • 调用 getResult 方法处理数据，并输出结果。
2. 核心逻辑部分
public static int getResult(int[] boxes, int len) {
  // 统计该数字上一个箱子的编号
  HashMap<Integer, Integer> lastIdx = new HashMap<>();
  // 对应数字的箱子已经找到了，符合咒语要求的箱子对
  HashSet<Integer> find = new HashSet<>();

  int ans = -1;

  for (int i = 0; i < boxes.length; i++) {
    // 箱子上贴的数字
    int num = boxes[i];

    // 该数字是否已经找到符合咒语要求的箱子对，如果找到了，则不需要再看后面的，只找第一对即可
    if (find.contains(num)) continue;

    // 检查箱子对是否符合咒语要求
    if (lastIdx.containsKey(num) && i - lastIdx.get(num) <= len) {
      find.add(num);
      ans = ans == -1 ? lastIdx.get(num) : Math.min(ans, lastIdx.get(num));
    } else {
      lastIdx.put(num, i);
    }
  }

  return ans;
}

  • lastIdx 哈希表：

    • 用于记录每个数字上一次出现的箱子编号。
    • 例如：lastIdx.put(6, 3) 表示数字 6 上一次出现在编号为 3 的箱子上。

  • find 集合：

    • 用于记录已经找到符合咒语要求的数字。
    • 例如：如果数字 6 已经找到符合要求的箱子对，则将其加入 find 集合，避免重复处理。

  • ans 变量：

    • 用于记录最终结果，即符合要求的左边箱子的编号。
    • 初始值为 -1，表示尚未找到符合要求的箱子对。

  • for 循环：

    • 遍历每个箱子，检查是否存在符合要求的箱子对。

  • if (find.contains(num)) continue;：

    • 如果当前数字已经在 find 集合中，说明已经找到符合要求的箱子对，跳过后续处理。

  • if (lastIdx.containsKey(num) && i - lastIdx.get(num) <= len)：

    • 检查当前数字是否曾经出现过，并且当前箱子编号与上一次出现该数字的箱子编号的差值是否小于等于咒语数字 len。
    • 如果符合要求：
      • 将当前数字加入 find 集合。
      • 更新 ans 为当前数字上一次出现的箱子编号（即左边箱子的编号）。如果 ans 为 -1，则直接赋值；否则取较小值。

  • else { lastIdx.put(num, i); }：

    • 如果当前数字不符合要求，则更新 lastIdx 中该数字的最近一次出现位置为当前箱子编号。

  • return ans;：

    • 返回最终结果。如果未找到符合要求的箱子对，则返回 -1。

代码逻辑总结

  1. 输入处理：

    • 读取箱子数字和咒语数字，并将其转换为合适的数据类型。

  2. 核心逻辑：

    • 使用 lastIdx 记录每个数字上一次出现的箱子编号。
    • 使用 find 集合记录已经找到符合要求的数字。
    • 遍历箱子，检查是否存在符合要求的箱子对：
      • 如果找到符合要求的箱子对，则记录左边箱子的编号。
      • 如果未找到，则更新 lastIdx。

  3. 输出结果：

    • 返回最先找到的符合要求的左边箱子的编号，如果未找到则返回 -1。

示例运行

输入 1：
6,3,1,6
3
执行过程：
  1. boxes = [6, 3, 1, 6]，len = 3。
  2. 遍历箱子：
    • i = 0，num = 6：
      • lastIdx 中没有 6，更新 lastIdx = {6: 0}。
    • i = 1，num = 3：
      • lastIdx 中没有 3，更新 lastIdx = {6: 0, 3: 1}。
    • i = 2，num = 1：
      • lastIdx 中没有 1，更新 lastIdx = {6: 0, 3: 1, 1: 2}。
    • i = 3，num = 6：
      • lastIdx 中有 6，i - lastIdx.get(6) = 3 - 0 = 3 <= len，符合要求。
      • 更新 find = {6}，ans = 0。
  3. 返回 ans = 0。
输出 1：
0

通过以上详细注释和讲解，你应该能够清晰地理解 Java 代码的每一部分逻辑和功能。

四、Python算法源码

以下是 Python 实现 的详细注释和讲解，帮助你理解每一部分的功能和逻辑：

代码结构

  1. 输入处理部分：

    • 使用 input() 从控制台读取输入。
    • 将输入的两行数据（箱子数字和咒语数字）分别解析为列表和整数。

  2. 核心逻辑部分：

    • getResult 函数是解题的核心逻辑，用于找到符合要求的箱子对。

代码逐行解析

1. 输入处理部分
# 读取第一行输入，按逗号分隔并转换为整数列表
boxes = list(map(int, input().split(",")))
# 读取第二行输入，转换为整数
length = int(input())

  • input() 函数：

    • 用于从控制台读取输入。
    • input().split(",")：将输入字符串按逗号分隔为字符串列表。

  • map(int, ...)：

    • 将字符串列表中的每个元素转换为整数。

  • list(map(...))：

    • 将转换后的整数映射为列表。

  • int(input())：

    • 读取第二行输入，并将其转换为整数。
2. 核心逻辑部分
def getResult():
    # 统计该数字上一个箱子的编号
    lastIdx = {}
    # 对应数字的箱子已经找到了，符合咒语要求的箱子对
    find = set()

    ans = -1

    for i in range(len(boxes)):
        # 箱子上贴的数字
        num = boxes[i]

        # 该数字是否已经找到符合咒语要求的箱子对，如果找到了，则不需要再看后面的，只找第一对即可
        if num in find:
            continue

        # 检查箱子对是否符合咒语要求
        if lastIdx.get(num) is not None and i - lastIdx[num] <= length:
            find.add(num)
            ans = lastIdx[num] if ans == -1 else min(ans, lastIdx[num])
        else:
            lastIdx[num] = i

    return ans

  • lastIdx 字典：

    • 用于记录每个数字上一次出现的箱子编号。
    • 例如：lastIdx[6] = 3 表示数字 6 上一次出现在编号为 3 的箱子上。

  • find 集合：

    • 用于记录已经找到符合咒语要求的数字。
    • 例如：如果数字 6 已经找到符合要求的箱子对，则将其加入 find 集合，避免重复处理。

  • ans 变量：

    • 用于记录最终结果，即符合要求的左边箱子的编号。
    • 初始值为 -1，表示尚未找到符合要求的箱子对。

  • for 循环：

    • 遍历每个箱子，检查是否存在符合要求的箱子对。

  • if num in find:：

    • 如果当前数字已经在 find 集合中，说明已经找到符合要求的箱子对，跳过后续处理。

  • if lastIdx.get(num) is not None and i - lastIdx[num] <= length:：

    • 检查当前数字是否曾经出现过，并且当前箱子编号与上一次出现该数字的箱子编号的差值是否小于等于咒语数字 length。
    • 如果符合要求：
      • 将当前数字加入 find 集合。
      • 更新 ans 为当前数字上一次出现的箱子编号（即左边箱子的编号）。如果 ans 为 -1，则直接赋值；否则取较小值。

  • else:：

    • 如果当前数字不符合要求，则更新 lastIdx 中该数字的最近一次出现位置为当前箱子编号。

  • return ans：

    • 返回最终结果。如果未找到符合要求的箱子对，则返回 -1。
3. 算法调用
# 调用核心逻辑方法并输出结果
print(getResult())
  • print(getResult())：
    • 调用 getResult 方法处理数据，并输出结果。

代码逻辑总结

  1. 输入处理：

    • 读取箱子数字和咒语数字，并将其转换为合适的数据类型。

  2. 核心逻辑：

    • 使用 lastIdx 记录每个数字上一次出现的箱子编号。
    • 使用 find 集合记录已经找到符合要求的数字。
    • 遍历箱子，检查是否存在符合要求的箱子对：
      • 如果找到符合要求的箱子对，则记录左边箱子的编号。
      • 如果未找到，则更新 lastIdx。

  3. 输出结果：

    • 返回最先找到的符合要求的左边箱子的编号，如果未找到则返回 -1。

示例运行

输入 1：
6,3,1,6
3
执行过程：
  1. boxes = [6, 3, 1, 6]，length = 3。
  2. 遍历箱子：
    • i = 0，num = 6：
      • lastIdx 中没有 6，更新 lastIdx = {6: 0}。
    • i = 1，num = 3：
      • lastIdx 中没有 3，更新 lastIdx = {6: 0, 3: 1}。
    • i = 2，num = 1：
      • lastIdx 中没有 1，更新 lastIdx = {6: 0, 3: 1, 1: 2}。
    • i = 3，num = 6：
      • lastIdx 中有 6，i - lastIdx[6] = 3 - 0 = 3 <= length，符合要求。
      • 更新 find = {6}，ans = 0。
  3. 返回 ans = 0。
输出 1：
0

通过以上详细注释和讲解，你应该能够清晰地理解 Python 代码的每一部分逻辑和功能。

五、C/C++算法源码：

以下是 C++ 和 C语言 的实现版本，附带详细的中文注释和代码讲解。

C++ 实现

代码实现

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <algorithm>

using namespace std;

int getResult(vector<int>& boxes, int length) {
    // 统计该数字上一个箱子的编号
    unordered_map<int, int> lastIdx;
    // 对应数字的箱子已经找到了，符合咒语要求的箱子对
    unordered_set<int> find;

    int ans = -1;

    for (int i = 0; i < boxes.size(); i++) {
        // 箱子上贴的数字
        int num = boxes[i];

        // 该数字是否已经找到符合咒语要求的箱子对，如果找到了，则不需要再看后面的，只找第一对即可
        if (find.find(num) != find.end()) continue;

        // 检查箱子对是否符合咒语要求
        if (lastIdx.find(num) != lastIdx.end() && i - lastIdx[num] <= length) {
            find.insert(num);
            ans = (ans == -1) ? lastIdx[num] : min(ans, lastIdx[num]);
        } else {
            lastIdx[num] = i;
        }
    }

    return ans;
}

int main() {
    // 读取第一行输入，按逗号分隔并转换为整数数组
    string input;
    getline(cin, input);
    stringstream ss(input);
    vector<int> boxes;
    string token;
    while (getline(ss, token, ',')) {
        boxes.push_back(stoi(token));
    }

    // 读取第二行输入，转换为整数
    int length;
    cin >> length;

    // 调用核心逻辑方法并输出结果
    cout << getResult(boxes, length) << endl;

    return 0;
}

代码讲解

1. 输入处理部分
  • getline(cin, input)：
    • 从控制台读取一行输入，存储到字符串 input 中。
  • stringstream ss(input)：
    • 将字符串 input 转换为字符串流，方便按逗号分隔。
  • while (getline(ss, token, ','))：
    • 按逗号分隔字符串流，并将每个分隔后的字符串转换为整数，存入 boxes 数组中。
  • cin >> length：
    • 读取第二行输入，并将其转换为整数。
2. 核心逻辑部分
  • unordered_map<int, int> lastIdx：
    • 用于记录每个数字上一次出现的箱子编号。
  • unordered_set<int> find：
    • 用于记录已经找到符合咒语要求的数字。
  • for (int i = 0; i < boxes.size(); i++)：
    • 遍历每个箱子，检查是否存在符合要求的箱子对。
  • if (find.find(num) != find.end())：
    • 如果当前数字已经在 find 集合中，跳过后续处理。
  • if (lastIdx.find(num) != lastIdx.end() && i - lastIdx[num] <= length)：
    • 检查当前数字是否曾经出现过，并且当前箱子编号与上一次出现该数字的箱子编号的差值是否小于等于咒语数字 length。
    • 如果符合要求：
      • 将当前数字加入 find 集合。
      • 更新 ans 为当前数字上一次出现的箱子编号（即左边箱子的编号）。如果 ans 为 -1，则直接赋值；否则取较小值。
  • else { lastIdx[num] = i; }：
    • 如果当前数字不符合要求，则更新 lastIdx 中该数字的最近一次出现位置为当前箱子编号。
3. 输出结果
  • cout << getResult(boxes, length) << endl;：
    • 调用 getResult 方法处理数据，并输出结果。

C语言实现

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_SIZE 100000

int getResult(int boxes[], int boxesSize, int length) {
    // 统计该数字上一个箱子的编号
    int lastIdx[MAX_SIZE * 2 + 1]; // 数字范围为 -100000 到 100000
    memset(lastIdx, -1, sizeof(lastIdx)); // 初始化为 -1

    // 对应数字的箱子已经找到了，符合咒语要求的箱子对
    int find[MAX_SIZE * 2 + 1] = {0}; // 初始化为 0

    int ans = -1;

    for (int i = 0; i < boxesSize; i++) {
        // 箱子上贴的数字
        int num = boxes[i];

        // 该数字是否已经找到符合咒语要求的箱子对，如果找到了，则不需要再看后面的，只找第一对即可
        if (find[num + MAX_SIZE]) continue;

        // 检查箱子对是否符合咒语要求
        if (lastIdx[num + MAX_SIZE] != -1 && i - lastIdx[num + MAX_SIZE] <= length) {
            find[num + MAX_SIZE] = 1;
            ans = (ans == -1) ? lastIdx[num + MAX_SIZE] : (ans < lastIdx[num + MAX_SIZE] ? ans : lastIdx[num + MAX_SIZE]);
        } else {
            lastIdx[num + MAX_SIZE] = i;
        }
    }

    return ans;
}

int main() {
    // 读取第一行输入，按逗号分隔并转换为整数数组
    char input[MAX_SIZE * 10]; // 假设输入不超过 100000 个字符
    fgets(input, sizeof(input), stdin);

    int boxes[MAX_SIZE];
    int boxesSize = 0;

    char* token = strtok(input, ",");
    while (token != NULL) {
        boxes[boxesSize++] = atoi(token);
        token = strtok(NULL, ",");
    }

    // 读取第二行输入，转换为整数
    int length;
    scanf("%d", &length);

    // 调用核心逻辑方法并输出结果
    printf("%d\n", getResult(boxes, boxesSize, length));

    return 0;
}

代码讲解

1. 输入处理部分
  • fgets(input, sizeof(input), stdin)：
    • 从控制台读取一行输入，存储到字符数组 input 中。
  • strtok(input, ",")：
    • 按逗号分隔字符串，并返回第一个子字符串。
  • while (token != NULL)：
    • 循环处理每个分隔后的子字符串，将其转换为整数并存入 boxes 数组中。
  • scanf("%d", &length)：
    • 读取第二行输入，并将其转换为整数。
2. 核心逻辑部分
  • int lastIdx[MAX_SIZE * 2 + 1]：
    • 用于记录每个数字上一次出现的箱子编号。由于数字范围为 -100000 到 100000，因此数组大小为 MAX_SIZE * 2 + 1。
  • int find[MAX_SIZE * 2 + 1]：
    • 用于记录已经找到符合咒语要求的数字。
  • for (int i = 0; i < boxesSize; i++)：
    • 遍历每个箱子，检查是否存在符合要求的箱子对。
  • if (find[num + MAX_SIZE])：
    • 如果当前数字已经在 find 集合中，跳过后续处理。
  • if (lastIdx[num + MAX_SIZE] != -1 && i - lastIdx[num + MAX_SIZE] <= length)：
    • 检查当前数字是否曾经出现过，并且当前箱子编号与上一次出现该数字的箱子编号的差值是否小于等于咒语数字 length。
    • 如果符合要求：
      • 将当前数字加入 find 集合。
      • 更新 ans 为当前数字上一次出现的箱子编号（即左边箱子的编号）。如果 ans 为 -1，则直接赋值；否则取较小值。
  • else { lastIdx[num + MAX_SIZE] = i; }：
    • 如果当前数字不符合要求，则更新 lastIdx 中该数字的最近一次出现位置为当前箱子编号。
3. 输出结果
  • printf("%d\n", getResult(boxes, boxesSize, length));：
    • 调用 getResult 方法处理数据，并输出结果。

总结

  • C++ 和 C语言 的实现逻辑与 Python 版本一致，主要区别在于数据结构和输入输出处理。
  • C++ 使用了 unordered_map 和 unordered_set，而 C语言 使用了数组来模拟哈希表和集合。
  • C语言 的实现需要注意数组大小和负数处理（通过 num + MAX_SIZE 将负数映射到正数范围）。

先找到这对宝箱的右边的宝箱为“最先”

以下是 JavaScript、Java 和 Python 实现的详细注释和讲解，代码逻辑以 先找到这对宝箱的右边的宝箱为“最先” 为准。

JavaScript 实现

代码实现

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length == 2) {
    const boxes = lines[0].split(",").map(Number);
    const len = parseInt(lines[1]);

    console.log(getResult(boxes, len));

    lines.length = 0;
  }
});

function getResult(boxes, len) {
  // 统计该数字上一个箱子的编号
  const lastIdx = {};

  for (let i = 0; i < boxes.length; i++) {
    // 箱子上贴的数字
    const num = boxes[i];

    // 检查箱子对是否符合咒语要求
    if (lastIdx[num] !== undefined && i - lastIdx[num] <= len) {
      // 返回左边箱子的编号
      return lastIdx[num];
    } else {
      // 更新该数字最近一次出现的箱子编号
      lastIdx[num] = i;
    }
  }

  // 如果没有找到符合要求的箱子对，返回 -1
  return -1;
}

代码讲解

1. 输入处理部分
  • readline 模块：
    • 用于从控制台逐行读取输入。
    • rl.on("line", (line) => { ... })：监听输入事件，每次输入一行数据时触发回调函数。
  • lines 数组：
    • 存储输入的两行数据。
    • 第一行是箱子上的数字，第二行是咒语数字。
  • if (lines.length == 2)：
    • 当输入两行数据后，开始处理数据。
    • boxes：将第一行输入按逗号分隔，并转换为数字数组。
    • len：将第二行输入转换为整数，表示咒语数字。
  • console.log(getResult(boxes, len))：
    • 调用 getResult 函数处理数据，并输出结果。
  • lines.length = 0：
    • 清空 lines 数组，以便处理下一组输入。
2. 核心逻辑部分
  • lastIdx 对象：
    • 用于记录每个数字上一次出现的箱子编号。
    • 例如：lastIdx[6] = 3 表示数字 6 上一次出现在编号为 3 的箱子上。
  • for 循环：
    • 遍历每个箱子，检查是否存在符合要求的箱子对。
  • if (lastIdx[num] !== undefined && i - lastIdx[num] <= len)：
    • 检查当前数字是否曾经出现过，并且当前箱子编号与上一次出现该数字的箱子编号的差值是否小于等于咒语数字 len。
    • 如果符合要求：
      • 返回左边箱子的编号 lastIdx[num]。
  • else { lastIdx[num] = i; }：
    • 如果当前数字不符合要求，则更新 lastIdx 中该数字的最近一次出现位置为当前箱子编号。
  • return -1：
    • 如果遍历结束后仍未找到符合要求的箱子对，则返回 -1。

Java 实现

代码实现

import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    // 读取第一行输入，按逗号分隔并转换为整数数组
    int[] boxes = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
    // 读取第二行输入，转换为整数
    int len = Integer.parseInt(sc.nextLine());

    // 调用核心逻辑方法并输出结果
    System.out.println(getResult(boxes, len));
  }

  public static int getResult(int[] boxes, int len) {
    // 统计该数字上一个箱子的编号
    HashMap<Integer, Integer> lastIdx = new HashMap<>();

    for (int i = 0; i < boxes.length; i++) {
      // 箱子上贴的数字
      int num = boxes[i];

      // 检查箱子对是否符合咒语要求
      if (lastIdx.containsKey(num) && i - lastIdx.get(num) <= len) {
        // 返回左边箱子的编号
        return lastIdx.get(num);
      } else {
        // 更新该数字最近一次出现的箱子编号
        lastIdx.put(num, i);
      }
    }

    // 如果没有找到符合要求的箱子对，返回 -1
    return -1;
  }
}

代码讲解

1. 输入处理部分
  • Scanner 类：
    • 用于从控制台读取输入。
    • sc.nextLine()：读取一行输入。
  • Arrays.stream(...)：
    • 将字符串数组转换为流，方便后续操作。
    • split(",")：将输入字符串按逗号分隔为字符串数组。
    • mapToInt(Integer::parseInt)：将字符串数组转换为整数流。
    • toArray()：将流转换为整数数组。
  • Integer.parseInt(sc.nextLine())：
    • 读取第二行输入，并将其转换为整数。
  • System.out.println(getResult(boxes, len))：
    • 调用 getResult 方法处理数据，并输出结果。
2. 核心逻辑部分
  • HashMap<Integer, Integer> lastIdx：
    • 用于记录每个数字上一次出现的箱子编号。
  • for 循环：
    • 遍历每个箱子，检查是否存在符合要求的箱子对。
  • if (lastIdx.containsKey(num) && i - lastIdx.get(num) <= len)：
    • 检查当前数字是否曾经出现过，并且当前箱子编号与上一次出现该数字的箱子编号的差值是否小于等于咒语数字 len。
    • 如果符合要求：
      • 返回左边箱子的编号 lastIdx.get(num)。
  • else { lastIdx.put(num, i); }：
    • 如果当前数字不符合要求，则更新 lastIdx 中该数字的最近一次出现位置为当前箱子编号。
  • return -1：
    • 如果遍历结束后仍未找到符合要求的箱子对，则返回 -1。

Python 实现

代码实现

# 输入获取
boxes = list(map(int, input().split(",")))
length = int(input())


# 算法入口
def getResult():
    # 统计该数字上一个箱子的编号
    lastIdx = {}

    for i in range(len(boxes)):
        # 箱子上贴的数字
        num = boxes[i]

        # 检查箱子对是否符合咒语要求
        if lastIdx.get(num) is not None and i - lastIdx[num] <= length:
            # 返回左边箱子的编号
            return lastIdx[num]
        else:
            # 更新该数字最近一次出现的箱子编号
            lastIdx[num] = i

    # 如果没有找到符合要求的箱子对，返回 -1
    return -1


# 算法调用
print(getResult())

代码讲解

1. 输入处理部分
  • input() 函数：
    • 用于从控制台读取输入。
    • input().split(",")：将输入字符串按逗号分隔为字符串列表。
  • map(int, ...)：
    • 将字符串列表中的每个元素转换为整数。
  • list(map(...))：
    • 将转换后的整数映射为列表。
  • int(input())：
    • 读取第二行输入，并将其转换为整数。
2. 核心逻辑部分
  • lastIdx 字典：
    • 用于记录每个数字上一次出现的箱子编号。
  • for 循环：
    • 遍历每个箱子，检查是否存在符合要求的箱子对。
  • if lastIdx.get(num) is not None and i - lastIdx[num] <= length:：
    • 检查当前数字是否曾经出现过，并且当前箱子编号与上一次出现该数字的箱子编号的差值是否小于等于咒语数字 length。
    • 如果符合要求：
      • 返回左边箱子的编号 lastIdx[num]。
  • else:：
    • 如果当前数字不符合要求，则更新 lastIdx 中该数字的最近一次出现位置为当前箱子编号。
  • return -1：
    • 如果遍历结束后仍未找到符合要求的箱子对，则返回 -1。

总结

  • JavaScript、Java 和 Python 的实现逻辑一致，主要区别在于语法和数据结构。
  • 核心思想是通过哈希表记录每个数字上一次出现的箱子编号，并在遍历时检查是否存在符合要求的箱子对。
  • 如果找到符合要求的箱子对，则返回左边箱子的编号；否则返回 -1。

六、尾言

什么是华为OD？

华为OD（Outsourcing Developer，外包开发工程师）是华为针对软件开发工程师岗位的一种招聘形式，主要包括笔试、技术面试以及综合面试等环节。尤其在笔试部分，算法题的机试至关重要。

为什么刷题很重要？

  1. 机试是进入技术面的第一关：
    华为OD机试（常被称为机考）主要考察算法和编程能力。只有通过机试，才能进入后续的技术面试环节。

  2. 技术面试需要手撕代码：
    技术一面和二面通常会涉及现场编写代码或算法题。面试官会注重考察候选人的思路清晰度、代码规范性以及解决问题的能力。因此提前刷题、多练习是通过面试的重要保障。

  3. 入职后的可信考试：
    入职华为后，还需要通过“可信考试”。可信考试分为三个等级：

    • 入门级：主要考察基础算法与编程能力。
    • 工作级：更贴近实际业务需求，可能涉及复杂的算法或与工作内容相关的场景题目。
    • 专业级：最高等级，考察深层次的算法以及优化能力，与薪资直接挂钩。

刷题策略与说明：

2024年8月14日之后，华为OD机试的题库转为 E卷，由往年题库（D卷、A卷、B卷、C卷）和全新题目组成。刷题时可以参考以下策略：

  1. 关注历年真题：

    • 题库中的旧题占比较大，建议优先刷历年的A卷、B卷、C卷、D卷题目。
    • 对于每道题目，建议深度理解其解题思路、代码实现，以及相关算法的适用场景。

  2. 适应新题目：

    • E卷中包含全新题目，需要掌握全面的算法知识和一定的灵活应对能力。
    • 建议关注新的刷题平台或交流群，获取最新题目的解析和动态。

  3. 掌握常见算法：
    华为OD考试通常涉及以下算法和数据结构：

    • 排序算法（快速排序、归并排序等）
    • 动态规划（背包问题、最长公共子序列等）
    • 贪心算法
    • 栈、队列、链表的操作
    • 图论（最短路径、最小生成树等）
    • 滑动窗口、双指针算法

  4. 保持编程规范：

    • 注重代码的可读性和注释的清晰度。
    • 熟练使用常见编程语言，如C++、Java、Python等。

如何获取资源？

  1. 官方参考：

    • 华为招聘官网或相关的招聘平台会有一些参考信息。
    • 华为OD的相关公众号可能也会发布相关的刷题资料或学习资源。

  2. 加入刷题社区：

    • 找到可信的刷题交流群，与其他备考的小伙伴交流经验。
    • 关注知名的刷题网站，如LeetCode、牛客网等，这些平台上有许多华为OD的历年真题和解析。

  3. 寻找系统性的教程：

    • 学习一本经典的算法书籍，例如《算法导论》《剑指Offer》《编程之美》等。
    • 完成系统的学习课程，例如数据结构与算法的在线课程。

积极心态与持续努力：

刷题的过程可能会比较枯燥，但它能够显著提升编程能力和算法思维。无论是为了通过华为OD的招聘考试，还是为了未来的职业发展，这些积累都会成为重要的财富。

考试注意细节

  1. 本地编写代码

    • 在本地 IDE（如 VS Code、PyCharm 等）上编写、保存和调试代码，确保逻辑正确后再复制粘贴到考试页面。这样可以减少语法错误，提高代码准确性。

  2. 调整心态，保持冷静

    • 遇到提示不足或实现不确定的问题时，不必慌张，可以采用更简单或更有把握的方法替代，确保思路清晰。

  3. 输入输出完整性

    • 注意训练和考试时都需要编写完整的输入输出代码，尤其是和题目示例保持一致。完成代码后务必及时调试，确保功能符合要求。

  4. 快捷键使用

    • 删除行可用 Ctrl+D，复制、粘贴和撤销分别为 Ctrl+C，Ctrl+V，Ctrl+Z，这些可以正常使用。
    • 避免使用 Ctrl+S，以免触发浏览器的保存功能。

  5. 浏览器要求

    • 使用最新版的 Google Chrome 浏览器完成考试，确保摄像头开启并正常工作。考试期间不要切换到其他网站，以免影响考试成绩。

  6. 交卷相关

    • 答题前，务必仔细查看题目示例，避免遗漏要求。
    • 每完成一道题后，点击【保存并调试】按钮，多次保存和调试是允许的，系统会记录得分最高的一次结果。完成所有题目后，点击【提交本题型】按钮。
    • 确保在考试结束前提交试卷，避免因未保存或调试失误而丢分。

  7. 时间和分数安排

    • 总时间：150 分钟；总分：400 分。
    • 试卷结构：2 道一星难度题（每题 100 分），1 道二星难度题（200 分）。及格分为 150 分。合理分配时间，优先完成自己擅长的题目。

  8. 考试环境准备

    • 考试前请备好草稿纸和笔。考试中尽量避免离开座位，确保监控画面正常。
    • 如需上厕所，请提前规划好时间以减少中途离开监控的可能性。

  9. 技术问题处理

    • 如果考试中遇到断电、断网、死机等技术问题，可以关闭浏览器并重新打开试卷链接继续作答。
    • 出现其他问题，请第一时间联系 HR 或监考人员进行反馈。

祝你考试顺利，取得理想成绩！


http://www.kler.cn/a/521424.html

相关文章：

  • 超硬核，基于mmap和零拷贝实现高效的内存共享
  • 计算机图形学知识点整理（期末复习/知识点学习/笔试/面试）
  • DDD-事件风暴
  • 机器学习 - 初学者需要弄懂的一些线性代数的概念
  • Alfresco Content Services dockerCompose自动化部署详尽操作
  • 使用scikit-learn中的线性回归包对自定义数据集进行拟合
  • PPT对齐排版的实用方法
  • 【漫话机器学习系列】063.梯度下降（Gradient Descent）
  • 【STM32】-TTP223B触摸开关
  • 荔枝派LicheePi Zero V3S芯片图形系统开发详解[持续更新]
  • Nxopen 直齿轮参数化设计
  • FloDB 设计与思考
  • 12、本地缓存分布式缓存（未完待续）
  • Android的签名
  • uvm timeout的哪些事
  • 2025.1.26机器学习笔记：C-RNN-GAN文献阅读
  • 有趣的网站
  • VUE3 使用路由守卫函数实现类型服务器端中间件效果
  • ListOJ14：环形链表II(寻找环的入口点)
  • Spring Security(maven项目) 3.0.2.6版本—下