您现在的位置是：首页 >技术交流 >【2024年华为OD机试】 (E卷,100分)-查找充电设备组合（JavaScript&Java & Python&C/C++）网站首页技术交流

【2024年华为OD机试】 (E卷,100分)-查找充电设备组合（JavaScript&Java & Python&C/C++）

妄北y 2025-12-08 12:01:03
简介【2024年华为OD机试】 (E卷,100分)-查找充电设备组合（JavaScript&Java & Python&C/C++）

在这里插入图片描述

一、问题描述

题目解析

题目描述

某个充电站提供 n 个充电设备，每个充电设备有对应的输出功率。任意个充电设备组合的输出功率总和，构成一个功率集合 P。功率集合 P 的最优元素是指最接近充电站最大输出功率 p_max 的元素，且最优元素必须小于或等于 p_max。

输入描述

输入为 3 行：

  1. 第 1 行为充电设备个数 n。
  2. 第 2 行为每个充电设备的输出功率。
  3. 第 3 行为充电站最大输出功率 p_max。

备注：

  • 充电设备个数 n > 0。
  • 最优元素必须小于或等于充电站最大输出功率 p_max。
输出描述

输出功率集合 P 的最优元素。

示例

示例 1：

  • 输入：
    4
50 20 20 60
90
  • 输出：
    90
  • 说明：
    • 当选择功率为 50、20、20 的设备组合时，总功率为 90，最接近充电站最大输出功率 90，因此最优元素为 90。

示例 2：

  • 输入：
    2
50 40
30
  • 输出：
    0
  • 说明：
    • 所有充电设备的输出功率组合均大于充电站最大输出功率 30，此时最优元素为 0。

示例 3：

  • 输入：
    3
2 3 10
9
  • 输出：
    5
  • 说明：
    • 选择功率为 2 和 3 的设备组合，总功率为 5，最接近最大功率 9。不能选择设备 10，因为已经超过了最大功率 9。

解题思路

问题转化

题目要求从 n 个充电设备中选择任意组合，使得其总功率最接近且不超过 p_max。这可以转化为一个经典的 01 背包问题：

  • 背包容量：充电站最大输出功率 p_max。
  • 物品重量和价值：每个充电设备的输出功率（重量 = 价值）。

目标是找到在不超过背包容量 p_max 的情况下，能够装入的最大价值（即最大功率）。

动态规划解法

  1. 定义状态：

    • 设 dp[i][j] 表示前 i 个充电设备中，总功率不超过 j 时的最大功率。
    • 其中，i 表示前 i 个充电设备，j 表示总功率不超过 j。

  2. 状态转移方程：

    • 对于每个充电设备，可以选择选或不选：
      • 如果当前充电设备的功率 power[i-1] 大于当前总功率 j，则不能选，此时 dp[i][j] = dp[i-1][j]。
      • 如果当前充电设备的功率 power[i-1] 小于等于当前总功率 j，则可以选择选或不选：
        • 选：dp[i][j] = dp[i-1][j-power[i-1]] + power[i-1]。
        • 不选：dp[i][j] = dp[i-1][j]。
        • 取两者中的最大值。
    • 状态转移方程为：
      dp[i][j] = max(dp[i-1][j], dp[i-1][j-power[i-1]] + power[i-1])

  3. 初始条件：

    • dp[0][j] = 0：没有充电设备时，最大功率为 0。
    • dp[i][0] = 0：总功率不超过 0 时，最大功率为 0。

  4. 最终结果：

    • dp[n][p_max] 即为功率集合 P 的最优元素。
优化空间复杂度

由于 dp[i][j] 只依赖于 dp[i-1][j] 和 dp[i-1][j-power[i-1]]，可以使用一维数组 dp[j] 来优化空间复杂度：

  • 从后向前更新 dp[j]，避免覆盖未使用的状态。
复杂度分析

  1. 时间复杂度：

    • 动态规划的状态数为 n * p_max，每个状态的计算时间为 O(1)。
    • 总体时间复杂度为 O(n * p_max)。

  2. 空间复杂度：

    • 使用二维数组时，空间复杂度为 O(n * p_max)。
    • 使用一维数组优化后，空间复杂度为 O(p_max)。

总结

本题通过将问题转化为 01 背包问题，利用动态规划求解最接近且不超过 p_max 的功率组合。动态规划的状态转移方程和优化方法是解决此类问题的核心思路。

二、JavaScript算法源码

这段代码是一个使用 Node.js 的 readline 模块从标准输入读取数据的脚本，并通过动态规划算法解决了一个关于充电设备功率选择的问题。下面是对这段代码的详细解释：

// 引入 Node.js 的 readline 模块，用于读取标准输入 
const readline = require('readline');
 
// 创建一个 readline 接口实例，用于读取标准输入和输出
const rl = readline.createInterface({ 
  input: process.stdin,  // 输入流设置为标准输入 
  output: process.stdout // 输出流设置为标准输出 
});
 
// 声明变量，用于存储充电设备个数、每个设备的功率和充电站的最大输出功率
let n, power, p_max;
let dp = []; // 声明动态规划数组，稍后进行初始化 
 
// 监听输入流中的每一行数据
rl.on('line', (line) => {
  // 去除行首尾的空白字符
  line = line.trim();
 
  // 如果 n 还未赋值，则将输入的第一行数据（充电设备个数）赋值给 n
  if (!n) { 
    n = parseInt(line);
  } 
  // 如果 power 还未赋值，则将输入的第二行数据（每个设备的功率）转化为数组赋值给 power
  else if (!power) {
    power = line.split(' ').map(Number); // 使用空格分割字符串，并将每个元素转换为数字
  } 
  // 如果 p_max 还未赋值，则将输入的第三行数据（充电站的最大输出功率）赋值给 p_max 
  // 并进行动态规划计算
  else if (!p_max) {
    p_max = parseInt(line);
 
    // 初始化动态规划数组 dp 
    // 创建一个 (n+1) x (p_max+1) 的二维数组，所有元素初始值为 0
    dp = new Array(n + 1).fill().map(() => new Array(p_max + 1).fill(0)); 
 
    // 进行动态规划计算 
    for (let i = 1; i <= n; i++) { 
      for (let j = 1; j <= p_max; j++) { 
        // 如果当前设备的功率大于当前考虑的总功率 j 
        if (power[i - 1] > j) { 
          // 则不能选择这个设备，dp[i][j] 等于不考虑当前设备时的最大输出功率 
          dp[i][j] = dp[i - 1][j];
        } else { 
          // 否则，计算选择当前设备和不选择当前设备两种情况下的最大输出功率
          // 并取较大值作为 dp[i][j] 的值
          dp[i][j] = Math.max(dp[i - 1][j], power[i - 1] + dp[i - 1][j - power[i - 1]]);
        } 
      } 
    } 
 
    // 输出计算结果：考虑所有设备，且总功率不超过 p_max 的情况下的最大输出功率 
    console.log(dp[n][p_max]);
 
    // 关闭 readline 接口实例，结束程序
    rl.close();
  } 
});

代码执行流程：

  1. 引入 readline 模块，并创建一个接口实例 rl，用于读取标准输入和输出。
  2. 声明变量 n、power、p_max 和 dp，分别用于存储充电设备个数、设备功率数组、充电站最大输出功率和动态规划数组。
  3. 使用 rl.on('line', ...) 监听输入流中的每一行数据。
  4. 根据输入数据的顺序，分别将第一行数据赋值给 n，第二行数据转换为数组赋值给 power，第三行数据赋值给 p_max。
  5. 在获取到 p_max 后，初始化动态规划数组 dp，并进行动态规划计算。
  6. 输出计算结果，即考虑所有设备且总功率不超过 p_max 的情况下的最大输出功率。
  7. 关闭 readline 接口实例，结束程序。

这段代码通过动态规划算法有效地解决了充电设备功率选择的问题，能够在给定的设备功率和充电站最大输出功率的约束下，找到最大的输出功率组合。

三、Java算法源码

import java.util.Scanner; // 引入Scanner类，用于读取输入 
 
public class Main { 
    public static void main(String[] args) {
        // 创建Scanner对象，用于从标准输入读取数据 
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入的整数n，表示有n个伤害值 
        int n = scanner.nextInt(); 
 
        // 创建一个长度为n的整型数组power，用于存储n个伤害值
        int[] power = new int[n]; 
        // 循环读取n个整数，存入power数组中
        // i从0开始，小于n，每次循环读取一个伤害值存入对应位置
        for (int i = 0; i < n; i++) { 
            power[i] = scanner.nextInt(); 
        } 
 
        // 读取输入的整数p_max，表示能够承受的最大伤害值
        int p_max = scanner.nextInt(); 
 
        // 创建一个二维整型数组dp，大小为(n+1)行×(p_max+1)列
        // dp[i][j]表示考虑前i个伤害值，在承受伤害不超过j的情况下，能够获得的最大能量值 
        int[][] dp = new int[n + 1][p_max + 1]; 
 
        // 使用两层循环计算dp数组的每个元素 
        // 外层循环遍历每个伤害值（从第一个到第n个）
        for (int i = 1; i <= n; i++) { 
            // 内层循环遍历每个可能的承受伤害值（从1到p_max）
            for (int j = 1; j <= p_max; j++) { 
                // 判断当前伤害值power[i-1]是否大于当前承受的伤害值j
                if (power[i - 1] > j) { 
                    // 如果大于，则当前伤害无法被承受，dp[i][j]等于不考虑当前伤害值时的最大能量值 
                    dp[i][j] = dp[i - 1][j]; 
                } else { 
                    // 如果不大于，则可以选择承受这个伤害值，获得相应的能量 
                    // dp[i][j]取不承受当前伤害值的最大能量值和承受当前伤害值后获得的能量值中的较大者
                    dp[i][j] = Math.max(dp[i - 1][j], power[i - 1] + dp[i - 1][j - power[i - 1]]); 
                } 
            } 
        } 
 
        // 输出结果：在承受伤害不超过p_max的情况下，能够获得的最大能量值 
        System.out.println(dp[n][p_max]);
    } 
}

讲解：

  1. 引入Scanner类：代码首先引入了java.util.Scanner类，这是Java标准库中的一个类，用于简化文本扫描操作，如从文件或标准输入读取值。

  2. 创建Scanner对象：通过new Scanner(System.in)创建了一个Scanner对象，用于从标准输入（通常是键盘）读取数据。

  3. 读取伤害值数量：使用scanner.nextInt()读取了一个整数n，表示接下来有n个伤害值需要读取。

  4. 存储伤害值：创建了一个长度为n的整型数组power，并通过循环读取了n个整数，存入该数组中。这些整数代表不同的伤害值。

  5. 读取最大承受伤害值：再次使用scanner.nextInt()读取了一个整数p_max，表示能够承受的最大伤害值。

  6. 初始化dp数组：创建了一个二维整型数组dp，大小为(n+1)行×(p_max+1)列。这个数组用于存储动态规划过程中的中间结果。dp[i][j]表示考虑前i个伤害值，在承受伤害不超过j的情况下，能够获得的最大能量值。

  7. 动态规划计算：使用两层嵌套循环来填充dp数组。外层循环遍历每个伤害值，内层循环遍历每个可能的承受伤害值。对于每个dp[i][j]，根据当前伤害值是否大于承受伤害值j，决定是忽略当前伤害值还是承受它并获取能量。

  8. 输出结果：最后，输出dp[n][p_max]的值，即在承受伤害不超过p_max的情况下，能够获得的最大能量值。

四、Python算法源码

这段代码是一个典型的动态规划问题解决方案，用于解决在给定的充电设备中，选择若干设备使得其总输出功率不超过充电站的最大输出功率，并使得这些设备的总输出功率最大化。下面是对这段代码的详细注释和讲解：

读取充电设备的个数 
n = int(input())  
 
读取每个充电设备的输出功率，并存储在一个列表中 
input().split() 会根据空格将输入的字符串分割成多个子字符串，map(int, ...) 将这些子字符串转换成整数 
power = list(map(int, input().split()))  
 
读取充电站的最大输出功率
p_max = int(input())  
 
初始化dp数组，大小为(n+1) x (p_max+1)，所有元素初始值为0
dp[i][j] 表示考虑前i个充电设备，且总输出功率不超过j的情况下，能够获得的最大输出功率
dp = [[0] * (p_max + 1) for _ in range(n + 1)]  
 
遍历每个充电设备 
for i in range(1, n + 1):  
    # 遍历每个可能的总输出功率（从1到p_max） 
    for j in range(1, p_max + 1):   
        # 判断当前充电设备的输出功率是否大于当前考虑的总输出功率j 
        if power[i - 1] > j:  
            # 如果大于，则不能选择这个充电设备，因此dp[i][j]等于不考虑当前设备时的最大输出功率 
            dp[i][j] = dp[i - 1][j]   
        else:   
            # 如果不大于，则有两种选择：选当前设备或不选当前设备 
            # 选当前设备时，总输出功率为当前设备的功率加上剩余功率（j-power[i-1]）下的最大输出功率
            # 不选当前设备时，总输出功率就是不考虑当前设备时的最大输出功率
            # 取这两种选择中的较大值作为dp[i][j]的值 
            dp[i][j] = max(dp[i - 1][j], power[i - 1] + dp[i - 1][j - power[i - 1]])   
 
输出考虑所有充电设备，且总输出功率不超过p_max的情况下的最大输出功率 
print(dp[n][p_max])

讲解：

  1. 输入处理：

    • 首先读取充电设备的个数n。
    • 然后读取每个充电设备的输出功率，存储在一个列表power中。
    • 最后读取充电站的最大输出功率p_max。

  2. 动态规划数组初始化：

    • 初始化一个二维数组dp，大小为(n+1) x (p_max+1)，所有元素都设为0。这个数组用于存储动态规划过程中的中间结果。

  3. 动态规划过程：

    • 使用两层嵌套循环来填充dp数组。外层循环遍历每个充电设备，内层循环遍历每个可能的总输出功率。
    • 对于每个充电设备和每个可能的总输出功率，根据当前充电设备的输出功率是否大于当前考虑的总输出功率，来决定是否选择这个充电设备。
    • 如果当前充电设备的输出功率大于当前考虑的总输出功率，则不能选择这个设备，dp[i][j]等于不考虑当前设备时的最大输出功率。
    • 否则，计算选择当前设备和不选择当前设备两种情况下的最大输出功率，并取较大值作为dp[i][j]的值。

  4. 输出结果：

    • 最后输出dp[n][p_max]的值，即考虑所有充电设备，且总输出功率不超过p_max的情况下的最大输出功率。

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

以下是C++和C语言版本的代码注释和讲解：

C++版本

#include <iostream>
using namespace std;
int main() {
    int n; // 充电设备个数
    cin >> n; // 输入充电设备的个数
    int power[n]; // 每个充电设备的输出功率
    for (int i = 0; i < n; i++) {
        cin >> power[i]; // 输入每个充电设备的输出功率
    }
    int p_max; // 充电站最大输出功率
    cin >> p_max; // 输入充电站的最大输出功率
    int dp[n + 1][p_max + 1] = {}; // 初始化动态规划数组dp，大小为(n+1) x (p_max+1)，初始值为0
    // 动态规划填表过程
    for (int i = 1; i <= n; i++) { // 遍历充电设备
        for (int j = 1; j <= p_max; j++) { // 遍历充电站最大输出功率
            if (power[i - 1] > j) { // 如果当前充电设备的功率大于当前总功率j，不能选择这个设备
                dp[i][j] = dp[i - 1][j]; // 不选择当前充电设备，最大功率为上一个状态的值
            } else {
                // 选择当前充电设备与不选择当前充电设备的最大值
                dp[i][j] = max(dp[i - 1][j], power[i - 1] + dp[i - 1][j - power[i - 1]]);
            }
        }
    }
    cout << dp[n][p_max] << endl; // 输出充电站可以达到的最大输出功率
    return 0;
}

C语言版本

#include <stdio.h>
#include <string.h> // 用于memset函数
int max(int a, int b) {
    return (a > b) ? a : b; // 返回两个整数中的较大值
}
int main() {
    int n; // 充电设备个数
    scanf("%d", &n); // 输入充电设备的个数
    int power[n]; // 每个充电设备的输出功率
    for (int i = 0; i < n; i++) {
        scanf("%d", &power[i]); // 输入每个充电设备的输出功率
    }
    int p_max; // 充电站最大输出功率
    scanf("%d", &p_max); // 输入充电站的最大输出功率
    int dp[n + 1][p_max + 1]; // 定义一个二维数组dp，用于动态规划
    memset(dp, 0, sizeof(dp)); // 使用memset将数组dp初始化为0
    // 动态规划填表过程
    for (int i = 1; i <= n; i++) { // 遍历充电设备
        for (int j = 1; j <= p_max; j++) { // 遍历充电站最大输出功率
            if (power[i - 1] > j) { // 如果当前充电设备的功率大于当前总功率j，不能选择这个设备
                dp[i][j] = dp[i - 1][j]; // 不选择当前充电设备，最大功率为上一个状态的值
            } else {
                // 选择当前充电设备与不选择当前充电设备的最大值
                dp[i][j] = max(dp[i - 1][j], power[i - 1] + dp[i - 1][j - power[i - 1]]);
            }
        }
    }
    printf("%d
", dp[n][p_max]); // 输出充电站可以达到的最大输出功率
    return 0;
}

在这两个版本的代码中，我们使用动态规划的方法来解决一个背包问题，即如何在不超过充电站最大输出功率的情况下，选择充电设备使得总输出功率最大。dp[i][j]表示在前i个充电设备中选择，且总功率不超过j的情况下，能达到的最大输出功率。通过填表的方式，我们最终得到dp[n][p_max]，即为所求的最大输出功率。

六、尾言

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

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

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

站长推荐