【2024年华为OD机试】(C卷,100分)- 检查是否存在满足条件的数字组合 （Java JS PythonC/C++）

一、问题描述

题目描述

给定一个正整数数组，检查数组中是否存在满足规则的数字组合。

规则：A = B + 2C

输入描述

第一行输出数组的元素个数。

接下来一行输出所有数组元素，用空格隔开。

输出描述

如果存在满足要求的数，在同一行里依次输出规则里A/B/C的取值，用空格隔开。

如果不存在，输出0。

备注

数组长度在3-100之间。
数组成员为0-65535，数组成员可以重复，但每个成员只能在结果算式中使用一次。如：数组成员为[0, 0, 1, 5]，0出现2次是允许的，但结果0 = 0 + 2 * 0是不允许的，因为算式中使用了3个0。
用例保证每组数字里最多只有一组符合要求的解。

用例

输入

4
2 7 3 0

输出

7 3 2

说明
7 = 3 + 2 * 2

输入

3
1 1 1

输出

0

说明
找不到满足条件的组合

题目解析

本题数组长度不大，只有3~100，因此三重for暴力破解，也不会超时。

解题思路

1. 读取输入：

   • 读取第一行的整数N，表示数组的元素个数。
   • 读取第二行的整数序列，表示数组元素。

2. 排序：

   • 将数组元素进行降序排序，这样可以方便地选择最大的数作为A，较小的数作为B和C。

3. 三重循环：

   • 使用三重循环遍历数组，尝试找到满足A = B + 2C的组合。
   • 第一层循环选择A，第二层循环选择B，第三层循环选择C。
   • 确保A、B、C是不同的元素，即它们的索引不相同。

4. 检查条件：

   • 检查A是否等于B + 2C。
   • 如果找到满足条件的组合，输出A、B、C的值并结束程序。

5. 输出结果：

   • 如果没有找到满足条件的组合，输出0。

注意事项

• 数组成员使用限制：每个数组成员只能在结果算式中使用一次。
• 用例保证：每组数字里最多只有一组符合要求的解，因此一旦找到解就可以直接返回。

通过这种方法，我们可以有效地检查数组中是否存在满足规则的数字组合。时间复杂度为O(n^3)，其中n是数组的长度，因为我们使用了三重循环。

二、JavaScript算法源码

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

public class Main {
    public static void main(String[] args) {
        // 创建Scanner对象，用于读取输入
        Scanner sc = new Scanner(System.in);

        // 读取第一行输入，表示数组的元素个数
        int n = Integer.parseInt(sc.nextLine());

        // 读取第二行输入，将其分割为字符串数组，然后转换为Integer数组
        Integer[] arr = Arrays.stream(sc.nextLine().split(" ")).map(Integer::parseInt).toArray(Integer[]::new);

        // 调用getResult方法，传入数组长度和数组本身，获取结果并输出
        System.out.println(getResult(n, arr));
    }

    public static String getResult(int n, Integer[] arr) {
        // 对数组进行降序排序，这样可以方便地选择最大的数作为A，较小的数作为B和C
        Arrays.sort(arr, (a, b) -> b - a);

        // 使用三重循环遍历数组，尝试找到满足A = B + 2C的组合
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    // 检查A是否等于B + 2C
                    if (arr[i] == arr[j] + 2 * arr[k]) {
                        // 如果找到满足条件的组合，返回A、B、C的值
                        return arr[i] + " " + arr[j] + " " + arr[k];
                    }
                    // 检查A是否等于C + 2B
                    if (arr[i] == arr[k] + 2 * arr[j]) {
                        // 如果找到满足条件的组合，返回A、C、B的值
                        return arr[i] + " " + arr[k] + " " + arr[j];
                    }
                }
            }
        }

        // 如果没有找到满足条件的组合，返回0
        return "0";
    }
}

代码讲解

1. 读取输入：

   • 使用Scanner类读取输入。
   • 第一行输入表示数组的元素个数n。
   • 第二行输入是一个字符串，包含多个用空格分隔的整数，使用Arrays.stream将其转换为Integer数组。

2. 排序：

   • 使用Arrays.sort方法对数组进行降序排序。降序排序的目的是方便选择最大的数作为A，较小的数作为B和C。

3. 三重循环：

   • 使用三重循环遍历数组，尝试找到满足A = B + 2C或A = C + 2B的组合。
   • 第一层循环选择A，第二层循环选择B，第三层循环选择C。
   • 确保A、B、C是不同的元素，即它们的索引不相同。

4. 检查条件：

   • 在三重循环中，检查当前选择的A、B、C是否满足条件A = B + 2C或A = C + 2B。
   • 如果找到满足条件的组合，返回A、B、C的值并结束程序。

5. 输出结果：

   • 如果没有找到满足条件的组合，返回0。

注意事项

• 数组成员使用限制：每个数组成员只能在结果算式中使用一次。
• 用例保证：每组数字里最多只有一组符合要求的解，因此一旦找到解就可以直接返回。

通过这种方法，我们可以有效地检查数组中是否存在满足规则的数字组合。时间复杂度为O(n^3)，其中n是数组的长度，因为我们使用了三重循环。

三、Java算法源码

/* 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) {
    let n = parseInt(lines[0]);
    let arr = lines[1].split(" ").map(Number);

    console.log(getResult(n, arr));

    lines.length = 0;
  }
});

/**
 * 检查数组中是否存在满足规则的数字组合
 * 规则：A = B + 2C
 * @param {number} n - 数组的元素个数
 * @param {number[]} arr - 数组元素
 * @returns {string} - 满足条件的A、B、C的值，或0
 */
function getResult(n, arr) {
  // 对数组进行降序排序，这样可以方便地选择最大的数作为A，较小的数作为B和C
  arr.sort((a, b) => b - a);

  // 使用三重循环遍历数组，尝试找到满足A = B + 2C的组合
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      for (let k = j + 1; k < n; k++) {
        // 检查A是否等于B + 2C
        if (arr[i] == arr[j] + 2 * arr[k]) {
          // 如果找到满足条件的组合，返回A、B、C的值
          return `${arr[i]} ${arr[j]} ${arr[k]}`;
        }
        // 检查A是否等于C + 2B
        if (arr[i] == arr[k] + 2 * arr[j]) {
          // 如果找到满足条件的组合，返回A、C、B的值
          return `${arr[i]} ${arr[k]} ${arr[j]}`;
        }
      }
    }
  }

  // 如果没有找到满足条件的组合，返回0
  return "0";
}

代码讲解

1. 读取输入：

   • 使用readline模块读取控制台输入。
   • 创建一个readline.Interface实例rl，用于监听line事件。
   • 使用lines数组存储读取的每一行输入。

2. 处理输入：

   • 当读取到两行输入时，解析第一行的整数n，表示数组的元素个数。
   • 解析第二行的字符串，将其分割为字符串数组，然后转换为Number数组arr。

3. 排序：

   • 使用Array.prototype.sort方法对数组进行降序排序。降序排序的目的是方便选择最大的数作为A，较小的数作为B和C。

4. 三重循环：

   • 使用三重循环遍历数组，尝试找到满足A = B + 2C或A = C + 2B的组合。
   • 第一层循环选择A，第二层循环选择B，第三层循环选择C。
   • 确保A、B、C是不同的元素，即它们的索引不相同。

5. 检查条件：

   • 在三重循环中，检查当前选择的A、B、C是否满足条件A = B + 2C或A = C + 2B。
   • 如果找到满足条件的组合，返回A、B、C的值并结束程序。

6. 输出结果：

   • 如果没有找到满足条件的组合，返回0。

注意事项

• 数组成员使用限制：每个数组成员只能在结果算式中使用一次。
• 用例保证：每组数字里最多只有一组符合要求的解，因此一旦找到解就可以直接返回。

通过这种方法，我们可以有效地检查数组中是否存在满足规则的数字组合。时间复杂度为O(n^3)，其中n是数组的长度，因为我们使用了三重循环。

四、Python算法源码

# 输入获取
n = int(input())
arr = list(map(int, input().split()))

# 算法入口
def getResult():
    # 对数组进行降序排序，这样可以方便地选择最大的数作为A，较小的数作为B和C
    arr.sort(reverse=True)

    # 使用三重循环遍历数组，尝试找到满足A = B + 2C的组合
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                # 检查A是否等于B + 2C
                if arr[i] == arr[j] + 2 * arr[k]:
                    # 如果找到满足条件的组合，返回A、B、C的值
                    return f"{arr[i]} {arr[j]} {arr[k]}"

                # 检查A是否等于C + 2B
                if arr[i] == arr[k] + 2 * arr[j]:
                    # 如果找到满足条件的组合，返回A、C、B的值
                    return f"{arr[i]} {arr[k]} {arr[j]}"

    # 如果没有找到满足条件的组合，返回0
    return "0"

# 算法调用
print(getResult())

代码讲解

1. 输入获取：

   • 使用input函数读取第一行输入，表示数组的元素个数n。
   • 使用input函数读取第二行输入，将其分割为字符串列表，然后使用map函数转换为整数列表arr。

2. 排序：

   • 使用arr.sort(reverse=True)对数组进行降序排序。降序排序的目的是方便选择最大的数作为A，较小的数作为B和C。

3. 三重循环：

   • 使用三重循环遍历数组，尝试找到满足A = B + 2C或A = C + 2B的组合。
   • 第一层循环选择A，第二层循环选择B，第三层循环选择C。
   • 确保A、B、C是不同的元素，即它们的索引不相同。

4. 检查条件：

   • 在三重循环中，检查当前选择的A、B、C是否满足条件A = B + 2C或A = C + 2B。
   • 如果找到满足条件的组合，返回A、B、C的值并结束程序。

5. 输出结果：

   • 如果没有找到满足条件的组合，返回0。

注意事项

• 数组成员使用限制：每个数组成员只能在结果算式中使用一次。
• 用例保证：每组数字里最多只有一组符合要求的解，因此一旦找到解就可以直接返回。

通过这种方法，我们可以有效地检查数组中是否存在满足规则的数字组合。时间复杂度为O(n^3)，其中n是数组的长度，因为我们使用了三重循环。

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

C++代码版本

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

// 定义比较函数，用于降序排序
bool cmp(int a, int b) {
    return a > b;
}

int main() {
    int n;
    std::cin >> n;

    std::vector<int> nums(n);
    for(int i = 0; i < n; i++) {
        std::cin >> nums[i];
    }

    // 使用自定义的比较函数进行降序排序
    std::sort(nums.begin(), nums.end(), cmp);

    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            for(int k = j + 1; k < n; k++) {
                if(nums[i] == nums[j] + 2 * nums[k]) {
                    std::cout << nums[i] << " " << nums[j] << " " << nums[k] << std::endl;
                    return 0;
                }

                if(nums[i] == nums[k] + 2 * nums[j]) {
                    std::cout << nums[i] << " " << nums[k] << " " << nums[j] << std::endl;
                    return 0;
                }
            }
        }
    }

    std::cout << "0" << std::endl;

    return 0;
}

代码讲解

1. 包含头文件：

   • #include <iostream>：用于输入输出流。
   • #include <algorithm>：包含排序算法。
   • #include <vector>：包含动态数组容器。

2. 定义比较函数：

   • bool cmp(int a, int b)：返回true如果a大于b，用于降序排序。

3. 主函数：

   • 读取输入的数组长度n。
   • 创建一个std::vector<int>来存储输入的数字。
   • 使用std::cin读取每个数字到vector中。
   • 使用std::sort和自定义的cmp函数对vector进行降序排序。

4. 三重循环查找符合条件的组合：

   • 外层循环变量i遍历数组，选择最大的数A。
   • 中层循环变量j从i+1开始，选择次大的数B。
   • 内层循环变量k从j+1开始，选择最小的数C。
   • 检查是否满足A = B + 2C或A = C + 2B，如果满足则输出这三个数并返回0。

5. 输出结果：

   • 如果没有找到满足条件的组合，输出0。

C语言代码版本

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

// 定义比较函数，用于降序排序
int cmp(const void* a, const void* b) {
    return (*(int*)b) - (*(int*)a);
}

int main() {
    int n;
    scanf("%d", &n);

    int nums[n];
    for(int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }

    // 使用qsort和自定义的比较函数进行降序排序
    qsort(nums, n, sizeof(int), cmp);

    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            for(int k = j + 1; k < n; k++) {
                if(nums[i] == nums[j] + 2 * nums[k]) {
                    printf("%d %d %d\n", nums[i], nums[j], nums[k]);
                    return 0;
                }

                if(nums[i] == nums[k] + 2 * nums[j]) {
                    printf("%d %d %d\n", nums[i], nums[k], nums[j]);
                    return 0;
                }
            }
        }
    }

    puts("0");

    return 0;
}

代码讲解

1. 包含头文件：

   • #include <stdio.h>：用于输入输出函数。
   • #include <stdlib.h>：包含qsort函数。

2. 定义比较函数：

   • int cmp(const void* a, const void* b)：返回b - a，用于降序排序。

3. 主函数：

   • 读取输入的数组长度n。
   • 创建一个整数数组nums来存储输入的数字。
   • 使用scanf读取每个数字到数组中。
   • 使用qsort和自定义的cmp函数对数组进行降序排序。

4. 三重循环查找符合条件的组合：

   • 外层循环变量i遍历数组，选择最大的数A。
   • 中层循环变量j从i+1开始，选择次大的数B。
   • 内层循环变量k从j+1开始，选择最小的数C。
   • 检查是否满足A = B + 2C或A = C + 2B，如果满足则输出这三个数并返回0。

5. 输出结果：

   • 如果没有找到满足条件的组合，输出0。

注意事项

• 数组成员使用限制：每个数组成员只能在结果算式中使用一次。
• 用例保证：每组数字里最多只有一组符合要求的解，因此一旦找到解就可以直接返回。

通过这种方法，我们可以有效地检查数组中是否存在满足规则的数字组合。时间复杂度为O(n^3)，其中n是数组的长度，因为我们使用了三重循环。

六、尾言

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

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