【2024年华为OD机试】 (B卷,200分)- 最佳植树距离（Java & JS & Python&C/C++）

一、问题描述

题目解析

题目描述

小明需要在沙化严重的地区进行植树防沙工作，初步目标是种植一条直线的树带。由于有些区域目前不适合种植树木，所以只能在一些可以种植的点来种植树木。

在树苗有限的情况下，要达到最佳效果，就要尽量散开种植，不同树苗之间的最小间距要尽量大。给定一个适合种植树木的点坐标和一个树苗的数量，请帮小明选择一个最佳的最小种植间距。

输入描述

1. 第1行表示适合种树的坐标数量。
2. 第2行是适合种树的坐标位置。
3. 第3行是树苗的数量。

例如：

7
1 5 3 6 10 7 13
3

输出描述

最佳的最小种植间距。

例如：

6

备注

1. 位置范围为 1~10000000。
2. 种植树苗的数量范围 2~10000000。
3. 用例确保种植的树苗数量不会超过有效种植坐标数量。

用例

输入

7
1 5 3 6 10 7 13
3

输出

6

说明
3棵树苗分别种植在 1、7、13 位置时，树苗种植的最均匀，最小间距为 6。

---

题目解析

问题分析

1. 目标
   在给定的坐标点上种植一定数量的树苗，使得树苗之间的最小间距最大化。

2. 关键点

   • 适合种植的坐标点是离散的，需要在这些点中选择若干个点来种植树苗。
   • 树苗之间的最小间距要尽量大，以达到散开种植的目的。

3. 问题转化
   这是一个典型的最大化最小值问题，可以通过二分查找来解决。

---

解题思路

1. 排序坐标点
   首先将适合种植的坐标点按升序排序，方便后续计算间距。

2. 二分查找

   • 定义搜索范围：最小间距的可能范围是 [1, max_coordinate - min_coordinate]。
   • 使用二分查找在范围内寻找最大的最小间距。

3. 验证函数
   对于每一个候选的最小间距 mid，检查是否可以在坐标点中种植所有树苗，且树苗之间的间距不小于 mid。

4. 调整搜索范围

   • 如果当前 mid 满足条件，则尝试更大的间距（向右搜索）。
   • 如果当前 mid 不满足条件，则尝试更小的间距（向左搜索）。

5. 返回结果
   最终找到的最大最小间距即为答案。

---

示例分析

输入

7
1 5 3 6 10 7 13
3

步骤

1. 排序坐标点：[1, 3, 5, 6, 7, 10, 13]。
2. 定义搜索范围：[1, 13 - 1 = 12]。
3. 使用二分查找：
   • 初始范围：left = 1，right = 12。
   • 中间值 mid = 6，检查是否可以在坐标点中种植 3 棵树苗，且间距不小于 6。
     • 种植位置：1、7、13，间距分别为 6 和 6，满足条件。
   • 向右搜索更大的间距。
   • 最终确定最大最小间距为 6。

输出

6

---

复杂度分析

1. 时间复杂度

   • 排序坐标点：O(n log n)，其中 n 是坐标点的数量。
   • 二分查找：O(log(max_coordinate - min_coordinate))。
   • 验证函数：每次验证需要 O(n)。
   • 总时间复杂度：O(n log n + n log(max_coordinate - min_coordinate))。

2. 空间复杂度

   • 排序需要 O(n) 的额外空间。
   • 其他操作使用常数空间。
   • 总空间复杂度：O(n)。

---

总结

本题的核心是通过二分查找和贪心策略，找到树苗之间的最大最小间距。关键在于将问题转化为最大化最小值问题，并通过排序和二分查找高效地解决。

二、JavaScript算法源码

这段JavaScript代码是一个经典的二分查找问题，通常用于解决类似于“最大最小间距”的问题。在算法竞赛中，这种题目一般是关于在一定范围内放置项目以最大化最小间距。下面是对代码的详细解释和解析：

JavaScript代码解析

输入处理

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

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

  if (lines.length === 3) {
    const n = lines[0] - 0;
    const positions = lines[1].split(" ").map(Number);
    const m = lines[2] - 0;

    console.log(getResult(n, positions, m));

    lines.length = 0;
  }
});

• 功能：通过readline模块从标准输入读取数据，以ACM模式处理多行输入。
• 逻辑解释：
  • 每次输入一行，将其添加到lines数组中。
  • 当lines包含三行时，分别表示：
    • n：位置数量。
    • positions：位置数组。
    • m：需要放置的目标数量。
  • 读取完后调用getResult函数计算结果，并输出。

getResult 函数

function getResult(n, positions, m) {
  positions.sort((a, b) => a - b);

  let min = 1;
  let max = positions[n - 1] - positions[0];
  let ans = 0;

  while (min <= max) {
    const mid = (min + max) >> 1;
    if (check(positions, m, mid)) {
      ans = mid;
      min = mid + 1;
    } else {
      max = mid - 1;
    }
  }

  return ans;
}

• 功能：使用二分查找确定可以放置目标的最大最小间距。
• 逻辑解释：
  • 首先对positions数组进行排序。
  • 初始化搜索范围min和max，分别代表可能的最小和最大间距。
  • 在while循环中使用二分查找法：
    • 计算中间值mid。
    • 调用check函数判断是否可以以mid作为最小间距放置m个目标。
    • 如果可以，则更新ans为mid，并尝试增加间距（min = mid + 1）。
    • 如果不可以，则减小间距（max = mid - 1）。

check 函数

function check(positions, m, minDis) {
  let count = 1;
  let curPos = positions[0];

  for (let i = 1; i < positions.length; i++) {
    if (positions[i] - curPos >= minDis) {
      count++;
      curPos = positions[i];
    }
  }

  return count >= m;
}

• 功能：验证是否可以在给定最小间距minDis的情况下放置m个目标。
• 逻辑解释：
  • 从第一个位置开始，count记录已放置的目标数量。
  • 遍历positions数组，如果当前位置与上一个放置目标的位置间距不小于minDis，则放置一个新目标。
  • 如果count最终大于等于m，返回true，否则返回false。

总结

• 算法：通过二分查找和贪心算法，最大化最小间距。
• 时间复杂度：O(n log(max_distance))，其中max_distance是最大可能间距。
• 应用场景：适用于需要在一维空间中安排对象以最大化最小距离的问题，如Wi-Fi路由器布置、蜂窝基站设计等。

这段代码有效地解决了最大化最小间距的问题。如果有进一步的疑问或需要更多的解释，请随时告知！

三、Java算法源码

这段Java代码与之前的JavaScript代码实现了相同的算法，解决的问题是通过放置m个目标来最大化这些目标之间的最小间距。接下来，我将对这段Java代码进行详细的讲解。

Java代码解析

主程序 (main 方法)

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

    int n = sc.nextInt();

    int[] positions = new int[n];
    for (int i = 0; i < n; i++) {
        positions[i] = sc.nextInt();
    }

    int m = sc.nextInt();

    System.out.println(getResult(n, positions, m));
}

• 功能：从标准输入读取数据并调用getResult方法计算结果。
• 逻辑解释：
  • 使用Scanner从标准输入中读取变量；
  • n表示位置的数量；
  • positions是一个整数数组，存储不同位置的值；
  • m表示需要放置的目标数量；
  • 调用getResult方法并输出返回值。

getResult 方法

public static int getResult(int n, int[] positions, int m) {
    Arrays.sort(positions);

    int min = 1, max = positions[n - 1] - positions[0];
    int ans = 0;

    while (min <= max) {
        int mid = (min + max) >> 1;

        if (check(positions, m, mid)) {
            ans = mid;
            min = mid + 1;
        } else {
            max = mid - 1;
        }
    }

    return ans;
}

• 功能：通过二分查找找到可以放置m个目标的最大最小间距。
• 逻辑解释：
  • 首先对positions数组进行排序。
  • 初始化搜索范围min和max，分别表示可能的最小和最大间距。
  • 使用while循环进行二分查找：
    • 计算中间值mid。
    • 使用check方法验证是否可以以mid作为最小间距放置m个目标。
    • 如果可以，更新ans为mid，并增加最小间距（min = mid + 1）。
    • 如果不可以，减小最大间距（max = mid - 1）。

check 方法

public static boolean check(int[] positions, int m, int minDis) {
    int count = 1;

    int curPos = positions[0];
    for (int i = 1; i < positions.length; i++) {
        if (positions[i] - curPos >= minDis) {
            count++;
            curPos = positions[i];
        }
    }

    return count >= m;
}

• 功能：检查是否可以在给定的最小间距minDis下放置m个目标。
• 逻辑解释：
  • 从第一个位置开始，count记录已放置的目标数量。
  • 遍历positions数组，如果当前位置与上一个放置目标的位置间距不小于minDis，则放置一个新目标。
  • 如果count最终大于等于m，返回true，否则返回false。

总结

• 核心思想：通过二分查找和贪心策略来解决最大化最小间距的问题。
• 时间复杂度：O(n log(max_distance))，适合处理较大规模的数据。
• 应用场景：适用于一维空间中安排目标以最大化最小距离，例如放置Wi-Fi路由器、蜂窝基站等。

如果你对代码的某个部分有疑问或者想了解更多，请随时告知！

四、Python算法源码

这段Python代码实现了一个经典的二分查找算法，用于解决“最大化最小间距”问题。通过理解这段代码，你可以学会如何在一维空间中选择位置以最大化最小间距。以下是对这段代码的详细解析：

Python代码解析

输入处理

n = int(input())
positions = list(map(int, input().split()))
m = int(input())

• 功能：从标准输入读取数据。
• 逻辑解释：
  • n：整数，表示位置的数量。
  • positions：整数列表，表示不同的位置。
  • m：整数，表示需要放置的目标数量。

check 函数

def check(minDis):
    count = 1
    curPos = positions[0]

    for i in range(1, n):
        if positions[i] - curPos >= minDis:
            count += 1
            curPos = positions[i]

    return count >= m

• 功能：检查在给定的最小间距minDis下是否可以放置m个目标。
• 逻辑解释：
  • 从第一个位置开始，count记录已放置的目标数量。
  • 遍历positions列表，如果当前位置与上一个放置目标的间距不小于minDis，则放置一个新目标。
  • 如果最终放置的目标数量count大于或等于m，返回True，否则返回False。

getResult 函数

def getResult():
    positions.sort()

    low = 1
    high = positions[-1] - positions[0]
    ans = 0

    while low <= high:
        mid = (low + high) >> 1

        if check(mid):
            ans = mid
            low = mid + 1
        else:
            high = mid - 1

    return ans

• 功能：使用二分查找算法寻找可以放置m个目标的最大最小间距。
• 逻辑解释：
  • 首先对positions列表进行排序，以确保位置是按顺序排列的。
  • 初始化low和high为搜索范围的边界，分别表示可能的最小和最大间距。
  • 使用while循环进行二分查找：
    • 计算中间值mid。
    • 使用check函数判断是否可以以mid作为最小间距放置m个目标。
    • 如果可以，更新ans为mid，并尝试增加间距（low = mid + 1）。
    • 如果不可以，减小间距（high = mid - 1）。

算法调用

print(getResult())

• 功能：调用getResult函数并打印其返回值，即最大化的最小间距。

总结

• 核心思想：结合二分查找和贪心策略，最大化最小间距。
• 时间复杂度：O(n log(max_distance))，适合处理较大规模的数据。
• 应用场景：适用于在一维空间中安排对象以最大化最小距离的问题，如Wi-Fi路由器布置、蜂窝基站设计等。

这段代码结构清晰，逻辑明确。如果有任何疑问或需要进一步解释，请随时告诉我！

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

C++代码

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// getResult函数用于找到最大最小间距
int getResult(int n, vector<int>& positions, int m);

// 比较函数，用于排序
int cmp(const void* a, const void* b);

// check函数用于验证在给定的最小间距下能否放置m个目标
bool check(const vector<int>& positions, int n, int m, int minDis);

int main() {
    // 适合种树的坐标数量
    int n;
    cin >> n;

    // 适合种树的坐标位置
    vector<int> positions(n);
    for (int i = 0; i < n; i++) {
        cin >> positions[i];
    }

    // 树苗的数量
    int m;
    cin >> m;

    // 输出结果
    cout << getResult(n, positions, m) << endl;

    return 0;
}

int getResult(int n, vector<int>& positions, int m) {
    // 对位置进行排序
    sort(positions.begin(), positions.end());

    // 初始化二分查找的范围
    int min = 1;
    int max = positions[n - 1] - positions[0];

    int ans = 0;

    // 二分查找最大最小间距
    while (min <= max) {
        int mid = (min + max) >> 1;

        if (check(positions, n, m, mid)) {
            ans = mid;
            min = mid + 1;
        } else {
            max = mid - 1;
        }
    }

    return ans;
}

bool check(const vector<int>& positions, int n, int m, int minDis) {
    int count = 1;
    int curPos = positions[0];

    // 检查在minDis的间距下能否放置m个树苗
    for (int i = 1; i < n; i++) {
        if (positions[i] - curPos >= minDis) {
            count++;
            curPos = positions[i];
        }
    }

    return count >= m;
}

C++代码讲解

1. 输入处理：

   • 使用cin和vector读取输入数据。
   • n表示可种树的坐标数量，positions是保存坐标位置的数组。
   • m表示要种植的树苗数量。

2. getResult 函数：

   • 首先对positions进行排序。
   • 使用二分查找来确定可以种植m棵树的最大最小间距。
   • min和max初始化表示间距的搜索范围，ans记录最终结果。

3. check 函数：

   • 从第一个位置开始，利用贪心策略检查是否能满足当前间距minDis。
   • 若能放置m棵树，返回true，否则返回false。

C 代码

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

#define MAX_SIZE 100000

int getResult(int n, int* positions, int m);
int cmp(const void* a, const void* b);
int check(int* positions, int n, int m, int minDis);

int main() {
    // 适合种树的坐标数量
    int n;
    scanf("%d", &n);

    // 适合种树的坐标位置
    int positions[MAX_SIZE];
    for (int i = 0; i < n; i++) {
        scanf("%d", &positions[i]);
    }

    // 树苗的数量
    int m;
    scanf("%d", &m);

    // 输出结果
    printf("%d\n", getResult(n, positions, m));

    return 0;
}

int getResult(int n, int* positions, int m) {
    // 对位置进行排序
    qsort(positions, n, sizeof(int), cmp);

    // 初始化二分查找的范围
    int min = 1;
    int max = positions[n - 1] - positions[0];

    int ans = 0;

    // 二分查找最大最小间距
    while (min <= max) {
        int mid = (min + max) >> 1;

        if (check(positions, n, m, mid)) {
            ans = mid;
            min = mid + 1;
        } else {
            max = mid - 1;
        }
    }

    return ans;
}

int cmp(const void* a, const void* b) {
    return *((int*)a) - *((int*)b);
}

int check(int* positions, int n, int m, int minDis) {
    int count = 1;
    int curPos = positions[0];

    // 检查在minDis的间距下能否放置m个树苗
    for (int i = 1; i < n; i++) {
        if (positions[i] - curPos >= minDis) {
            count++;
            curPos = positions[i];
        }
    }

    return count >= m;
}

C 代码讲解

• 与C++代码结构相似，只是使用了标准C库函数qsort进行排序。
• cmp函数是qsort的比较函数，实现两个整数的比较。

这两种代码使用了相同的算法来解决最大化最小间距的问题，选择使用C还是C++依据具体需求和项目环境。希望这些解释对你理解代码有所帮助！如果有进一步的问题，请随时询问。

六、尾言

什么是华为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 或监考人员进行反馈。

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

原文地址：https://blog.csdn.net/m0_63168877/article/details/145208687

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！