【2024年华为OD机试】 (B卷,100分)- 字符串摘要（JavaScriptJava PythonC/C++）

一、问题描述

题目描述

给定一个字符串的摘要算法，请输出给定字符串的摘要值。具体步骤如下：

1. 去除字符串中非字母的符号：只保留字母字符。
2. 处理连续字符：如果出现连续字符（不区分大小写），则输出该字符（小写）加上连续出现的次数。
3. 处理非连续字符：如果是非连续字符（不区分大小写），则输出该字符（小写）加上该字母之后字符串中出现的该字符的次数。
4. 排序：对按照以上方式表示后的字符串进行排序。字母和紧随的数字作为一组进行排序，数字大的在前，数字相同的则按字母进行排序，字母小的在前。

输入描述

一行字符串，长度为[1,200]。

输出描述

摘要字符串。

用例

用例1

输入
aabbcc

输出
a2b2c2

说明
字符串中的字符都是连续的，因此直接输出每个字符及其连续出现的次数。

用例2

输入
bAaAcBb

输出
a3b2b2c0

说明

• 第一个b是非连续字母，该字母之后字符串中还出现了2次（最后的两个Bb），所以输出b2。
• a连续出现3次，输出a3。
• c非连续，该字母之后字符串再没有出现过c，输出c0。
• Bb连续2次，输出b2。
• 对b2a3c0b2进行排序，最终输出a3b2b2c0。

题目解析

主要难点

1. 非连续字符的处理：对于非连续字符，需要统计该字符在当前位置之后出现的次数。为了避免重复扫描，可以预先统计每个字符的总出现次数，并在遍历时动态更新剩余次数。
2. 排序规则：排序时，字母和紧随的数字作为一组进行排序。数字大的在前，数字相同的则按字母进行排序，字母小的在前。

解题思路

1. 预处理字符串：去除字符串中非字母的符号，并将所有字符转换为小写。
2. 统计字符出现次数：预先统计每个字符在字符串中的总出现次数。
3. 遍历字符串：
   • 对于连续字符，统计连续出现的次数，并输出字符及其次数。
   • 对于非连续字符，输出字符及其在后续字符串中出现的次数。
4. 排序：根据排序规则对输出结果进行排序，最终得到摘要字符串。

注意事项

• 在处理连续字符时，需要注意大小写不敏感。
• 在统计非连续字符的后续出现次数时，需要动态更新剩余次数。
• 排序时需要将字母和数字作为一组进行排序，确保排序规则正确。

通过以上步骤，可以有效地解决该问题，并生成符合要求的摘要字符串。

二、JavaScript算法源码

以下是代码的详细解析和实现思路：

---

代码解析

1. 输入处理

• 使用 readline 模块从控制台读取输入。
• 将输入字符串转换为小写，以便不区分大小写。

2. 统计字母出现次数

• 使用一个对象 count 来统计每个字母在字符串中出现的总次数。
• 过滤掉非字母字符，并将字母存入数组 letters 中。

3. 处理连续和非连续字符

• 遍历字符串，记录当前字符 cur 和上一个字符 pre。
• 如果当前字符与上一个字符相同，则增加连续次数 repeat。
• 如果当前字符与上一个字符不同，则根据连续次数判断：
  • 如果 repeat > 1，说明是连续字符，输出 pre + repeat。
  • 否则，说明是非连续字符，输出 pre + count[pre]（即后续该字符的出现次数）。
• 更新 pre 和 repeat，继续遍历。

4. 排序和输出

• 将结果数组 ans 按照规则排序：
  • 数字大的在前。
  • 数字相同的，字母小的在前。
• 将排序后的结果拼接成字符串并返回。

---

代码实现

const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});rl.on("line", (line) => {console.log(getResult(line));
});function getResult(s) {// 将字符串转换为小写s = s.toLowerCase();// 统计每个字母出现的次数const count = {};// 去除字符串中的非字母const letters = [];for (let c of s) {if (c >= "a" && c <= "z") {count[c] = (count[c] ?? 0) + 1;letters.push(c);}}// 在字符串末尾加一个空格，方便处理最后一个字符s = letters.join("") + " ";// 记录连续字母和非连续字母const ans = [];// 上一个位置的字母let pre = s[0];// 该字母连续次数记为1let repeat = 1;// 后续该字母还有 count[pre]-=1 个count[pre]--;for (let i = 1; i < s.length; i++) {// 当前位置的字母const cur = s[i];// 后续该字母还有 count[cur]-=1 个count[cur]--;if (cur == pre) {// 如果当前位置和上一个位置的字母相同，则产生连续// 连续次数 +1repeat++;} else {// 如果当前位置和上一个位置的字母不同，则连续打断// 如果 pre 字母连续次数 >1，则是真连续，输出 pre + repeat// 否则是假连续，输出 pre + count[pre]ans.push([pre, repeat > 1 ? repeat : count[pre]]);// 更新 pre 为 curpre = cur;// 更新 pre 连续次数为 1repeat = 1;}}// 字母和紧随的数字作为一组进行排序// 数字大的在前，数字相同的，则按字母进行排序，字母小的在前return ans.sort((a, b) =>a[1] != b[1] ? b[1] - a[1] : a[0].charCodeAt() - b[0].charCodeAt()).map(([letter, num]) => letter + num).join("");
}

---

示例运行

输入 1

aabbcc

输出 1

a2b2c2

输入 2

bAaAcBb

输出 2

a3b2b2c0

---

代码优化点

1. 末尾空格的处理：

   • 代码中在字符串末尾加了一个空格，目的是为了简化最后一个字符的处理逻辑。如果不加空格，需要在遍历结束后单独处理最后一个字符。
   • 可以通过其他方式优化，避免添加空格。

2. 性能优化：

   • 如果字符串长度较大（接近 200），可以考虑优化统计和遍历的逻辑，减少不必要的操作。

3. 代码可读性：

   • 可以提取部分逻辑为独立函数，提高代码的可读性和可维护性。

---

总结

该代码实现了题目要求的字符串摘要算法，通过统计字符出现次数、处理连续和非连续字符，并按照规则排序输出结果。代码逻辑清晰，能够正确处理各种边界情况。

三、Java算法源码

以下是 Java 代码的详细解析和实现思路：

---

代码解析

1. 数据结构

• 定义了一个内部类 Letter，用于存储字母及其对应的数字（连续次数或后续出现次数）。
• Letter 类包含两个属性：
  • letter：字母。
  • num：数字（连续次数或后续出现次数）。
• 重写了 toString 方法，方便输出格式化为 字母 + 数字。

2. 输入处理

• 使用 Scanner 从控制台读取输入字符串。
• 将字符串转换为小写，以便不区分大小写。

3. 统计字母出现次数

• 使用一个长度为 128 的数组 count 来统计每个字母的出现次数（ASCII 码范围）。
• 过滤掉非字母字符，并将字母存入 StringBuilder 中。

4. 处理连续和非连续字符

• 遍历字符串，记录当前字符 cur 和上一个字符 pre。
• 如果当前字符与上一个字符相同，则增加连续次数 repeat。
• 如果当前字符与上一个字符不同，则根据连续次数判断：
  • 如果 repeat > 1，说明是连续字符，输出 pre + repeat。
  • 否则，说明是非连续字符，输出 pre + count[pre]（即后续该字符的出现次数）。
• 更新 pre 和 repeat，继续遍历。

5. 排序和输出

• 将结果列表 ans 按照规则排序：
  • 数字大的在前。
  • 数字相同的，字母小的在前。
• 将排序后的结果拼接成字符串并返回。

---

代码实现

import java.util.ArrayList;
import java.util.Scanner;public class Main {// 字母数字类static class Letter {char letter;int num;public Letter(char letter, int num) {this.letter = letter;this.num = num;}@Overridepublic String toString() {return this.letter + "" + this.num;}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println(getResult(sc.nextLine()));}public static String getResult(String s) {// 将字符串转换为小写s = s.toLowerCase();// 统计每个字母出现的次数int[] count = new int[128];// 去除字符串中的非字母StringBuilder sb = new StringBuilder();for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (c >= 'a' && c <= 'z') {count[c]++;sb.append(c);}}// 在字符串末尾加一个空格，方便处理最后一个字符s = sb + " ";// 记录连续字母和非连续字母ArrayList<Letter> ans = new ArrayList<>();// 上一个位置的字母char pre = s.charAt(0);// 该字母连续次数记为1int repeat = 1;// 后续该字母还有 count[pre]-=1 个count[pre]--;for (int i = 1; i < s.length(); i++) {// 当前位置的字母char cur = s.charAt(i);// 后续该字母还有 count[cur]-=1 个count[cur]--;if (cur == pre) {// 如果当前位置和上一个位置的字母相同，则产生连续// 连续次数 +1repeat++;} else {// 如果当前位置和上一个位置的字母不同，则连续打断// 如果 pre 字母连续次数 >1，则是真连续，输出 pre + repeat// 否则是假连续，输出 pre + count[pre]ans.add(new Letter(pre, repeat > 1 ? repeat : count[pre]));// 更新 pre 为 curpre = cur;// 更新 pre 连续次数为 1repeat = 1;}}// 字母和紧随的数字作为一组进行排序// 数字大的在前，数字相同的，则按字母进行排序，字母小的在前ans.sort((a, b) -> a.num != b.num ? b.num - a.num : a.letter - b.letter);StringBuilder res = new StringBuilder();for (Letter an : ans) {res.append(an.toString());}return res.toString();}
}

---

示例运行

输入 1

aabbcc

输出 1

a2b2c2

输入 2

bAaAcBb

输出 2

a3b2b2c0

---

代码优化点

1. 末尾空格的处理：

   • 代码中在字符串末尾加了一个空格，目的是为了简化最后一个字符的处理逻辑。如果不加空格，需要在遍历结束后单独处理最后一个字符。
   • 可以通过其他方式优化，避免添加空格。

2. 性能优化：

   • 如果字符串长度较大（接近 200），可以考虑优化统计和遍历的逻辑，减少不必要的操作。

3. 代码可读性：

   • 可以提取部分逻辑为独立方法，提高代码的可读性和可维护性。

---

总结

该 Java 代码实现了题目要求的字符串摘要算法，通过统计字符出现次数、处理连续和非连续字符，并按照规则排序输出结果。代码逻辑清晰，能够正确处理各种边界情况。

四、Python算法源码

以下是 Python 代码的详细解析和实现思路：

---

代码解析

1. 输入处理

• 使用 input() 获取输入字符串。
• 将字符串转换为小写，以便不区分大小写。

2. 统计字母出现次数

• 使用字典 count 统计每个字母的出现次数。
• 过滤掉非字母字符，并将字母存入列表 letters 中。

3. 处理连续和非连续字符

• 在字符串末尾加一个空格，方便处理最后一个字符。
• 遍历字符串，记录当前字符 cur 和上一个字符 pre。
• 如果当前字符与上一个字符相同，则增加连续次数 repeat。
• 如果当前字符与上一个字符不同，则根据连续次数判断：
  • 如果 repeat > 1，说明是连续字符，输出 pre + repeat。
  • 否则，说明是非连续字符，输出 pre + count[pre]（即后续该字符的出现次数）。
• 更新 pre 和 repeat，继续遍历。

4. 排序和输出

• 将结果列表 ans 按照规则排序：
  • 数字大的在前。
  • 数字相同的，字母小的在前。
• 将排序后的结果拼接成字符串并返回。

---

代码实现

# 输入获取
s = input()# 算法入口
def getResult():global s# 不区分大小写s = s.lower()# 统计每个字母出现的次数count = {}# 去除字符串中的非字母letters = []for c in s:if 'z' >= c >= 'a':count[c] = count.get(c, 0) + 1letters.append(c)# 加空格是为了避免后续的收尾操作，如果有疑问可以移除下面加空格操作s = "".join(letters) + " "count[' '] = 1# 记录连续字母和非连续字母ans = []# 上一个位置的字母pre = s[0]# 该字母连续次数记为1repeat = 1# 后续该字母还有count[pre]-=1个count[pre] -= 1for i in range(1, len(s)):# 当前位置的字母cur = s[i]# 后续该字母还有count[cur]-=1个count[cur] -= 1if cur == pre:# 如果当前位置和上一个位置的字母相同，则产生连续# 连续次数+1repeat += 1else:# 如果当前位置和上一个位置的字母不同，则连续打断# 如果pre字母连续次数>1，则是真连续，那么就是pre+repeat,否则就是假连续,是pre+count[pre]ans.append([pre, repeat if repeat > 1 else count[pre]])# 更新pre为curpre = cur# 更新pre连续次数为1repeat = 1# 字母和紧随的数字作为一组进行排序，数字大的在前，数字相同的，则按字母进行排序，字母小的在前ans.sort(key=lambda x: (-x[1], x[0]))return "".join(map(lambda x: x[0] + str(x[1]), ans))# 算法调用
print(getResult())

---

示例运行

输入 1

aabbcc

输出 1

a2b2c2

输入 2

bAaAcBb

输出 2

a3b2b2c0

---

代码优化点

1. 末尾空格的处理：

   • 代码中在字符串末尾加了一个空格，目的是为了简化最后一个字符的处理逻辑。如果不加空格，需要在遍历结束后单独处理最后一个字符。
   • 可以通过其他方式优化，避免添加空格。

2. 性能优化：

   • 如果字符串长度较大（接近 200），可以考虑优化统计和遍历的逻辑，减少不必要的操作。

3. 代码可读性：

   • 可以提取部分逻辑为独立函数，提高代码的可读性和可维护性。

---

总结

该 Python 代码实现了题目要求的字符串摘要算法，通过统计字符出现次数、处理连续和非连续字符，并按照规则排序输出结果。代码逻辑清晰，能够正确处理各种边界情况。

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

---

C 语言代码解析

1. 输入处理

• 使用 gets 获取输入字符串（注意：gets 不安全，建议使用 fgets 替代）。
• 将字符串转换为小写，并过滤掉非字母字符。

2. 统计字母出现次数

• 使用数组 count 统计每个字母的出现次数（ASCII 码范围）。
• 过滤掉非字母字符，并将字母存入数组 ss 中。

3. 处理连续和非连续字符

• 遍历字符串，记录当前字符 cur 和上一个字符 pre。
• 如果当前字符与上一个字符相同，则增加连续次数 repeat。
• 如果当前字符与上一个字符不同，则根据连续次数判断：
  • 如果 repeat > 1，说明是连续字符，输出 pre + repeat。
  • 否则，说明是非连续字符，输出 pre + count[pre]（即后续该字符的出现次数）。
• 更新 pre 和 repeat，继续遍历。

4. 排序和输出

• 将结果数组 res 按照规则排序：
  • 数字大的在前。
  • 数字相同的，字母小的在前。
• 将排序后的结果拼接成字符串并输出。

---

C 语言代码实现

#include <stdio.h>
#include <string.h>
#include <stdlib.h>#define MAX_SIZE 201typedef struct {char letter;int num;
} Letter;// 排序比较函数
int cmp(const void *a, const void *b) {Letter *A = (Letter *) a;Letter *B = (Letter *) b;return A->num != B->num ? B->num - A->num : A->letter - B->letter;
}int main() {char s[MAX_SIZE];fgets(s, MAX_SIZE, stdin); // 使用 fgets 替代 gets，避免缓冲区溢出unsigned long long len = strlen(s);// 记录转小写，去除非字母后的 s 字符串char ss[MAX_SIZE];int ss_size = 0;// 统计每个字母出现的次数int count[128] = {0};for (int i = 0; i < len; i++) {char c = s[i];if (c >= 'a' && c <= 'z') {count[c]++;ss[ss_size++] = c;} else if (c >= 'A' && c <= 'Z') {count[c + 32]++; // 转换为小写ss[ss_size++] = (char) (c + 32);}}// 记录连续字母和非连续字母Letter res[MAX_SIZE];int res_size = 0;// 上一个位置的字母char pre = ss[0];// 该字母连续次数记为 1int repeat = 1;// 后续该字母还有 count[pre]-=1 个count[pre]--;for (int i = 1; i <= ss_size; i++) {// 当前位置的字母char cur = ss[i];// 后续该字母还有 count[cur]-=1 个count[cur]--;if (cur == pre) {// 如果当前位置和上一个位置的字母相同，则产生连续// 连续次数 +1repeat++;} else {// 如果当前位置和上一个位置的字母不同，则连续打断// 如果 pre 字母连续次数 >1，则是真连续，那么就是 pre + repeat// 否则是假连续，是 pre + count[pre]res[res_size].num = repeat > 1 ? repeat : count[pre];res[res_size].letter = pre;res_size++;// 更新 pre 为 curpre = cur;// 更新 pre 连续次数为 1repeat = 1;}}// 字母和紧随的数字作为一组进行排序，数字大的在前，数字相同的，则按字母进行排序，字母小的在前qsort(res, res_size, sizeof(Letter), cmp);char ans[MAX_SIZE] = {'\0'};for (int i = 0; i < res_size; i++) {char letter[2];sprintf(letter, "%c", res[i].letter);char num[10];sprintf(num, "%d", res[i].num);strcat(ans, letter);strcat(ans, num);}puts(ans);return 0;
}

---

C++ 代码实现

以下是 C++ 版本的实现，使用了 STL 容器和算法：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cctype>
#include <cstring>using namespace std;struct Letter {char letter;int num;Letter(char l, int n) : letter(l), num(n) {}// 排序规则：数字大的在前，数字相同的字母小的在前bool operator<(const Letter &other) const {if (num != other.num) return num > other.num;return letter < other.letter;}
};int main() {string s;getline(cin, s);// 统计每个字母出现的次数int count[128] = {0};string ss;for (char c : s) {if (isalpha(c)) {char lower_c = tolower(c);count[lower_c]++;ss.push_back(lower_c);}}// 记录连续字母和非连续字母vector<Letter> res;char pre = ss[0];int repeat = 1;count[pre]--;for (size_t i = 1; i <= ss.size(); i++) {char cur = ss[i];count[cur]--;if (cur == pre) {repeat++;} else {res.emplace_back(pre, repeat > 1 ? repeat : count[pre]);pre = cur;repeat = 1;}}// 排序sort(res.begin(), res.end());// 输出结果for (const auto &item : res) {cout << item.letter << item.num;}cout << endl;return 0;
}

---

代码讲解

1. C 语言代码

• 使用结构体 Letter 存储字母及其对应的数字。
• 使用 qsort 对结果进行排序。
• 使用 sprintf 和 strcat 拼接结果字符串。

2. C++ 代码

• 使用 vector 存储结果，方便动态扩展。
• 使用 sort 对结果进行排序。
• 使用 emplace_back 高效地插入元素。
• 使用 isalpha 和 tolower 处理大小写转换。

---

示例运行

输入 1

aabbcc

输出 1

a2b2c2

输入 2

bAaAcBb

输出 2

a3b2b2c0

---

总结

• C 语言版本适合底层开发，代码较为冗长，但性能较高。
• C++ 版本利用 STL 简化了代码，提高了可读性和开发效率。
• 两种版本均实现了题目要求的功能，能够正确处理各种边界情况。

六、尾言

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

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