【2024年华为OD机试】 (C卷,100分)- 求字符串中所有整数的最小和（Java JS PythonC/C++）

一、问题描述

题目解析

题目描述

输入字符串 s，输出 s 中包含所有整数的最小和。

说明

1. 字符串 s 只包含 a-z、A-Z、+、-。
2. 合法的整数包括：
   • 正整数：一个或多个 0-9 组成，如 0、2、3、002、102。
   • 负整数：负号 - 开头，数字部分由一个或多个 0-9 组成，如 -0、-012、-23、-00023。

输入描述

包含数字的字符串。

输出描述

所有整数的最小和。

用例

输入

bb1234aa

输出

10

说明
无

---

输入

bb12-34aa

输出

-31

说明
1 + 2 + (-34) = -31

---

题目解析

问题分析

1. 目标
   从字符串中提取所有合法的整数（正整数和负整数），并计算它们的最小和。

2. 关键点

   • 正整数的每位数字应单独计算，以最小化和。
   • 负整数应整体计算，以最小化和。
   • 需要处理字符串中可能出现的连续符号（如 --）和不完整负数（如 -a）。

3. 问题转化
   通过遍历字符串，识别正负整数，并分别计算它们的贡献。

---

解题思路

1. 初始化变量

   • 使用一个变量 ans 存储当前的和。
   • 使用一个容器 negative 存储负数的数字字符。
   • 使用一个标志 isNegative 记录当前是否在处理负数。

2. 遍历字符串

   • 对于每个字符 c：
     • 如果 c 是 -：
       • 如果当前正在处理负数（isNegative == true），则将 negative 中的字符拼接成负数，加入 ans，并清空 negative。
       • 设置 isNegative = true，表示开始处理负数。
     • 如果 c 是数字：
       • 如果 isNegative == true，将 c 加入 negative。
       • 如果 isNegative == false，将 c 转换为数字并加入 ans。
     • 如果 c 是字母：
       • 如果 isNegative == true，将 negative 中的字符拼接成负数，加入 ans，并清空 negative。
       • 设置 isNegative = false。

3. 处理末尾的负数

   • 遍历结束后，如果 isNegative == true，将 negative 中的字符拼接成负数，加入 ans。

4. 返回结果

   • 返回 ans 作为最终的最小和。

---

示例分析

输入

bb12-34aa

步骤

1. 初始化 ans = 0，negative = []，isNegative = false。
2. 遍历字符串：
   • b：字母，忽略。
   • b：字母，忽略。
   • 1：数字，isNegative == false，ans += 1。
   • 2：数字，isNegative == false，ans += 2。
   • -：开始负数，isNegative = true。
   • 3：数字，isNegative == true，negative.push('3')。
   • 4：数字，isNegative == true，negative.push('4')。
   • a：字母，isNegative == true，将 negative 拼接为 -34，ans += -34，清空 negative，isNegative = false。
   • a：字母，忽略。
3. 返回 ans = 1 + 2 - 34 = -31。

---

复杂度分析

1. 时间复杂度

   • 遍历字符串一次，时间复杂度为 O(n)，其中 n 是字符串长度。

2. 空间复杂度

   • 使用 negative 存储负数字符，空间复杂度为 O(m)，其中 m 是负数的长度。
   • 总空间复杂度为 O(m)。

---

总结

本题的核心是通过遍历字符串，识别正负整数，并分别计算它们的贡献。关键在于：

1. 正整数的每位数字单独计算。
2. 负整数整体计算。
3. 处理不完整负数和连续符号的情况。
4. 时间复杂度优化为 O(n)，适合处理较长的字符串。

二、JavaScript算法源码

这段JavaScript代码使用Node.js的readline模块来处理控制台输入，采用ACM（ACM-ICPC，即国际大学生程序设计竞赛）模式来读取多行输入。这段代码的目标是从输入字符串中提取数字，并计算它们的总和，其中以负号开头的数字将被视为负数。以下是对这段代码的详细解析和讲解：

代码解析

输入处理

const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});rl.on("line", (line) => {console.log(getResult(line));
});

• 功能：创建一个readline接口，用于从标准输入读取数据。
• 逻辑解释：
  • readline.createInterface函数接受input和output流。
  • rl.on("line")事件监听器在每行输入时触发。
  • 每次读取一行，调用getResult函数进行处理，然后输出结果。

getResult函数

function getResult(s) {let isNegative = false;const negative = [];// let ans = 0;let ans = BigInt(0);for (let c of s) {if (c >= "0" && c <= "9") {if (isNegative) {negative.push(c);} else {// ans += parseInt(c);ans += BigInt(c);}} else {if (isNegative && negative.length > 0) {// ans -= parseInt(negative.join(""));ans -= BigInt(negative.join(""));negative.length = 0;}isNegative = c == "-";}}if (negative.length > 0) {// ans -= parseInt(negative.join(""));ans -= BigInt(negative.join(""));}return ans.toString();
}

• 功能：解析输入字符串中的数字，并计算它们的总和。
• 逻辑解释：
  • isNegative用于指示当前数字是否为负。
  • negative数组用于存储当前负数的各个数字字符。
  • ans使用BigInt来存储结果，以处理可能出现的大数。
  • 遍历输入字符串，检查每个字符：
    • 如果是数字字符并且isNegative为true，将其添加到negative数组。
    • 如果是数字字符且不是负数，直接累加到ans。
    • 如果遇到非数字字符：
      • 如果存在负数，计算负数值并从ans中减去。
      • 更新isNegative状态。
  • 最后，如果negative数组中仍有数字，减去最后一个负数值。
  • 返回ans的字符串形式。

总结

• 核心思想：使用遍历和条件判断解析输入字符串中的数字，分别处理正数和负数。
• 使用场景：适用于需要从混合字符中提取并计算数字的场景。
• 代码优化：使用BigInt以处理大数字，确保计算结果的精度。

这段代码的设计良好，能够有效地处理输入并计算结果。如果您有其他问题或需要进一步解释，请随时询问！

三、Java算法源码

这段Java代码的功能是从输入的字符串中提取数字并计算它们的总和，其中以负号（-）开头的数字被视为负数。使用了BigInteger来处理可能出现的大数，确保计算的精度。下面是对这段代码的详细解析及讲解：

代码解析

主函数 main

public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println(getResult(sc.nextLine()));
}

• 功能：读取用户输入的字符串，并输出计算结果。
• 逻辑解释：
  • 使用Scanner对象sc从控制台读取输入。
  • 调用getResult方法，传入读取的字符串，并打印结果。

getResult函数

public static String getResult(String s) {boolean isNegative = false;StringBuilder negative = new StringBuilder();BigInteger ans = new BigInteger("0");for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (c >= '0' && c <= '9') {if (isNegative) {negative.append(c);} else {ans = ans.add(new BigInteger(c + ""));}} else {if (isNegative && negative.length() > 0) {ans = ans.subtract(new BigInteger(negative.toString()));negative = new StringBuilder();}isNegative = c == '-';}}if (negative.length() > 0) {ans = ans.subtract(new BigInteger(negative.toString()));}return ans.toString();
}

• 功能：从输入字符串s中解析数字，并计算结果。
• 逻辑解释：
  • isNegative：布尔变量，用于指示当前解析的数字是否为负数。
  • negative：使用StringBuilder存储当前负数的字符。
  • ans：使用BigInteger来累加结果，保证处理大数字的精度。
  • 遍历字符串s：
    • 如果是数字字符：
      • 根据isNegative状态决定是否将字符添加到负数字符串或直接累加到ans。
    • 如果遇到非数字字符：
      • 检查是否需要处理并减去负数。
      • 更新isNegative状态。
  • 最后，如果negative中仍有数字，减去这个负数。

总结

• 核心思想：通过遍历和条件判断解析输入字符串中的数字，识别并处理正负数。
• 使用场景：适用于需要从混合字符的字符串中提取并计算数字的场景。
• 代码特性：使用BigInteger以确保计算大数的精度，StringBuilder用于高效处理字符串连接。

这段代码结构清晰，功能明确，通过合理使用Java类库的功能实现了对输入字符串的数字解析和计算。如果您有任何问题或需要进一步的解释，请随时询问！

四、Python算法源码

这段Python代码从输入字符串中提取数字并计算它们的总和，其中以负号（-）开头的数字被视为负数。以下是对这段代码的详细解析和讲解：

代码解析

输入处理

s = input()

• 功能：读取一行输入。
• 逻辑解释：将输入的字符串存储在变量s中，供后续处理。

getResult函数

def getResult():isNegative = Falsenegative = []ans = 0for c in s:if '0' <= c <= '9':if isNegative:negative.append(c)else:ans += int(c)else:if isNegative and len(negative) > 0:ans -= int("".join(negative))negative.clear()isNegative = c == '-'if len(negative) > 0:ans -= int("".join(negative))return ans

• 功能：从字符串s中解析数字并计算结果。
• 逻辑解释：
  • isNegative用于指示当前数字是否为负数。
  • negative列表用于存储当前负数的数字字符。
  • ans用于累加结果。
  • 遍历字符串s中的每个字符c：
    • 如果是数字字符：
      • 如果isNegative为True，将其添加到negative列表中。
      • 否则，直接将该数字累加到ans。
    • 如果是非数字字符：
      • 如果isNegative为True且negative列表不为空，将列表中的字符组合成一个数字，并从ans中减去该数字。
      • 重置negative列表，并更新isNegative状态为当前字符是否为-。
  • 在遍历结束后，如果negative列表仍不为空，再次组合并减去最后一个负数。
  • 返回累加的结果ans。

总结

• 核心思想：通过遍历和条件判断解析输入字符串，识别并处理正负数字。
• 使用场景：适用于从包含非数字字符的字符串中提取并计算数字的情况。
• 代码特性：使用简单的条件结构和列表操作，逻辑直观清晰。

这段代码结构清晰，功能明确，能够有效地实现解析和计算。如果您有其他问题或需要进一步的解释，请随时询问！

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

C++ 版本

#include <iostream>
#include <string>
#include <cstdlib> // 包含atoi函数using namespace std;int main() {string s;getline(cin, s); // 读取整行输入bool isNegative = false; // 标记当前数字是否为负数string negative; // 存储当前负数的字符long long ans = 0; // 用于累加结果for (char c : s) { // 遍历字符串中的每个字符if (c >= '0' && c <= '9') { // 如果是数字字符if (isNegative) {negative += c; // 将字符添加到负数字符串中} else {ans += c - '0'; // 直接将数字累加到结果中}} else {if (isNegative && !negative.empty()) {ans -= stoll(negative); // 将负数转换为整数并减去negative.clear(); // 清空负数字符串}isNegative = (c == '-'); // 更新负数标记状态}}if (!negative.empty()) {ans -= stoll(negative); // 处理最后一个负数}cout << ans << endl; // 输出结果return 0;
}

C 版本

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_SIZE 10000int main() {char s[MAX_SIZE];fgets(s, MAX_SIZE, stdin); // 读取整行输入int isNegative = 0; // 标记当前数字是否为负数char negative[MAX_SIZE]; // 存储当前负数的字符int negative_size = 0; // 负数字符计数long long ans = 0; // 用于累加结果int i = 0;while (s[i] != '\0' && s[i] != '\n') { // 遍历字符串中的每个字符，直到结束符char c = s[i];if (c >= '0' && c <= '9') { // 如果是数字字符if (isNegative) {negative[negative_size++] = c; // 将字符添加到负数数组中negative[negative_size] = '\0'; // 确保字符串以空字符结尾} else {ans += c - '0'; // 直接将数字累加到结果中}} else {if (isNegative && negative_size > 0) {ans -= atol(negative); // 将负数字符串转换为整数并减去memset(negative, '\0', MAX_SIZE); // 清空负数字符串negative_size = 0; // 重置负数字符计数}isNegative = (c == '-'); // 更新负数标记状态}i++;}if (negative_size > 0) {ans -= atol(negative); // 处理最后一个负数}printf("%lld\n", ans); // 输出结果return 0;
}

代码讲解

• 输入处理：

  • C++ 使用getline读取整行输入，而C使用fgets读取。

• 逻辑执行：

  • 利用isNegative变量判断当前解析的数字是否为负。
  • 遇到数字字符时判断是否在负数上下文中，并根据情况累加到ans或追加到negative中。
  • 遇到非数字字符时，检查是否为负号，并在需要时将negative中的字符转换为负数并减去。
  • 最后处理可能剩下的负数。

• 数字处理：

  • 使用字符和整数之间的ASCII码差进行简单的数字累加。
  • C++中使用stoll函数将字符串转换为长整数，C中使用atol。

通过这些步骤，代码能够有效地从输入字符串中提取并计算所有数字的总和，正确处理正负号。希望这些解释能够帮助您理解代码的工作原理！如有其他问题，请随时询问。

六、尾言

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

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