【2024年华为OD机试】 (C卷,200分)- 字符串拼接（JavaScriptJava PythonC/C++）

在这里插入图片描述

一、问题描述

问题描述

给定一个字符列表（字符范围为 a-z，且字符数量 M 满足 0 < M ≤ 30），从中选取字符（每个字符只能使用一次）拼接成长度为 N（0 < N ≤ 5）的字符串。要求拼接的字符串中，相同的字符不能相邻。计算给定的字符列表能够拼接出多少种满足条件的字符串。如果输入非法或无法拼接出满足条件的字符串，则返回 0。

输入输出

输入：给定的字符列表和结果字符串长度，中间使用空格(" ")拼接。
输出：满足条件的字符串个数。

示例

示例 1

输入: abc 1
输出: 3
说明: 给定的字符为 a, b, c，结果字符串长度为 1，可以拼接成 a, b, c，共 3 种。

示例 2

输入: dde 2
输出: 2
说明: 给定的字符为 d, d, e，结果字符串长度为 2，可以拼接成 de, ed，共 2 种。

解题思路

1. 排列问题

本题的核心是求解排列问题。排列是指从一组元素中按照一定的顺序选取元素，形成不同的序列。对于给定的字符列表，我们需要生成所有可能的长度为 N 的排列。

2. 不重复排列

由于字符列表中可能存在重复字符（如示例 2 中的 dde），我们需要考虑不重复的排列。即在生成排列时，避免生成相同的排列序列。

3. 相邻字符不相同

在生成排列的基础上，增加一个条件：排列中相邻的字符不能相同。这意味着在生成排列时，我们需要确保每一步选择的字符与前一个字符不相同。

4. 回溯算法

为了生成所有满足条件的排列，可以使用回溯算法。回溯算法通过递归的方式，逐步构建排列，并在每一步检查是否满足相邻字符不相同的条件。如果不满足条件，则回溯到上一步，尝试其他可能的字符。

5. 边界条件

如果字符列表为空或长度为 0，返回 0。
如果要求生成的字符串长度 N 大于字符列表的长度，返回 0。
如果字符列表中的所有字符都相同，且 N > 1，返回 0（因为无法满足相邻字符不相同的条件）。

总结

本题的核心是通过回溯算法生成所有满足条件的排列，并在生成过程中确保相邻字符不相同。通过合理的剪枝和条件判断，可以有效减少不必要的计算，提高算法的效率。

二、JavaScript算法源码

这段代码实现了一个基于回溯算法的解决方案，用于计算从给定的字符列表中拼接出长度为 N 且相邻字符不相同的字符串的个数。以下是对代码的详细解析：

代码结构

输入处理：
- 使用 readline 模块读取输入，并将输入拆分为字符列表 s 和目标长度 n。
- 将 n 转换为整数。
主函数 getResult：
- 检查输入是否合法：
  - 如果字符列表长度小于 n，直接返回 0。
  - 如果字符列表中有非法字符（非小写字母），直接返回 0。
- 对字符列表进行排序，方便后续去重。
- 调用 dfs 函数进行回溯求解。
回溯函数 dfs：
- 参数：
  - cArr：排序后的字符列表。
  - pre：上一个选择的字符在 cArr 中的索引。
  - level：当前排列的长度。
  - used：标记字符是否已被使用的数组。
  - count：当前满足条件的排列个数。
- 递归终止条件：
  - 当 level == n 时，表示找到一个满足条件的排列，count 加 1。
- 递归逻辑：
  - 遍历字符列表，尝试选择未被使用的字符。
  - 如果当前字符与前一个字符相同，跳过（避免相邻字符相同）。
  - 如果当前字符与前一个字符相同且前一个字符未被使用，跳过（树层去重）。
  - 标记当前字符为已使用，递归进入下一层。
  - 回溯时取消标记，继续尝试其他字符。
输出结果：
- 调用 getResult 函数并输出结果。

代码逻辑解析

输入合法性检查：
- 确保字符列表长度不小于 n，否则无法拼接出满足条件的字符串。
- 确保字符列表中的字符均为小写字母，否则输入非法。
排序与去重：
- 对字符列表进行排序，方便在回溯过程中进行树层去重，避免生成重复的排列。
回溯算法：
- 通过递归尝试所有可能的字符组合。
- 使用 used 数组标记字符是否已被使用，确保每个字符只能使用一次。
- 通过 pre 参数记录上一个选择的字符，确保相邻字符不相同。
- 通过树层去重（i > 0 && cArr[i] == cArr[i - 1] && !used[i - 1]）避免生成重复的排列。
递归终止条件：
- 当排列长度达到 n 时，表示找到一个满足条件的排列，count 加 1。

代码优化建议

提前剪枝：
- 如果字符列表中某个字符的数量过多，可能导致无法满足相邻字符不相同的条件。可以在回溯前进行统计，提前判断是否可能生成满足条件的排列。
性能优化：
- 对于较大的 n 和字符列表长度，回溯算法的性能可能较差。可以考虑使用动态规划或其他优化方法。
代码可读性：
- 可以增加注释，进一步解释树层去重和相邻字符不相同的逻辑。

示例运行

输入 1：

abc 1

字符列表：['a', 'b', 'c']，目标长度：1。
可能的排列：a, b, c。
输出：3。

输入 2：

dde 2

字符列表：['d', 'd', 'e']，目标长度：2。
可能的排列：de, ed。
输出：2。

输入 3：

aab 3

字符列表：['a', 'a', 'b']，目标长度：3。
可能的排列：aba, aab（不满足条件，因为有两个 a 相邻）。
输出：1（只有 aba 满足条件）。

总结

这段代码通过回溯算法高效地解决了问题，同时通过排序和树层去重避免了重复排列的生成。代码逻辑清晰，能够正确处理各种边界情况。

三、Java算法源码

这段 Java 代码实现了与之前 JavaScript 版本相同的功能，通过回溯算法计算从给定的字符列表中拼接出长度为 n 且相邻字符不相同的字符串的个数。以下是对代码的详细解析：

代码结构

输入处理：
- 使用 Scanner 读取输入，并将输入拆分为字符列表 s 和目标长度 n。
主函数 getResult：
- 检查输入是否合法：
  - 如果字符列表长度小于 n，直接返回 0。
  - 如果字符列表中有非法字符（非小写字母），直接返回 0。
- 对字符列表进行排序，方便后续去重。
- 调用 dfs 函数进行回溯求解。
回溯函数 dfs：
- 参数：
  - cArr：排序后的字符数组。
  - pre：上一个选择的字符在 cArr 中的索引。
  - level：当前排列的长度。
  - used：标记字符是否已被使用的布尔数组。
  - count：当前满足条件的排列个数。
- 递归终止条件：
  - 当 level == n 时，表示找到一个满足条件的排列，count 加 1。
- 递归逻辑：
  - 遍历字符数组，尝试选择未被使用的字符。
  - 如果当前字符与前一个字符相同，跳过（避免相邻字符相同）。
  - 如果当前字符与前一个字符相同且前一个字符未被使用，跳过（树层去重）。
  - 标记当前字符为已使用，递归进入下一层。
  - 回溯时取消标记，继续尝试其他字符。
输出结果：
- 调用 getResult 函数并输出结果。

代码逻辑解析

输入合法性检查：
- 确保字符列表长度不小于 n，否则无法拼接出满足条件的字符串。
- 确保字符列表中的字符均为小写字母，否则输入非法。
排序与去重：
- 对字符列表进行排序，方便在回溯过程中进行树层去重，避免生成重复的排列。
回溯算法：
- 通过递归尝试所有可能的字符组合。
- 使用 used 数组标记字符是否已被使用，确保每个字符只能使用一次。
- 通过 pre 参数记录上一个选择的字符，确保相邻字符不相同。
- 通过树层去重（i > 0 && cArr[i] == cArr[i - 1] && !used[i - 1]）避免生成重复的排列。
递归终止条件：
- 当排列长度达到 n 时，表示找到一个满足条件的排列，count 加 1。

代码优化建议

提前剪枝：
- 如果字符列表中某个字符的数量过多，可能导致无法满足相邻字符不相同的条件。可以在回溯前进行统计，提前判断是否可能生成满足条件的排列。
性能优化：
- 对于较大的 n 和字符列表长度，回溯算法的性能可能较差。可以考虑使用动态规划或其他优化方法。
代码可读性：
- 可以增加注释，进一步解释树层去重和相邻字符不相同的逻辑。

示例运行

输入 1：

abc 1

字符列表：['a', 'b', 'c']，目标长度：1。
可能的排列：a, b, c。
输出：3。

输入 2：

dde 2

字符列表：['d', 'd', 'e']，目标长度：2。
可能的排列：de, ed。
输出：2。

输入 3：

aab 3

字符列表：['a', 'a', 'b']，目标长度：3。
可能的排列：aba, aab（不满足条件，因为有两个 a 相邻）。
输出：1（只有 aba 满足条件）。

总结

这段 Java 代码通过回溯算法高效地解决了问题，同时通过排序和树层去重避免了重复排列的生成。代码逻辑清晰，能够正确处理各种边界情况。

四、Python算法源码

通过回溯算法计算从给定的字符列表中拼接出长度为 n 且相邻字符不相同的字符串的个数。以下是对代码的详细解析：

代码结构

输入处理：
- 使用 input().split() 读取输入，并将输入拆分为字符列表 s 和目标长度 n。
- 将 n 转换为整数。
主函数 getResult：
- 检查输入是否合法：
  - 如果字符列表长度小于 n，直接返回 0。
  - 如果字符列表中有非法字符（非小写字母），直接返回 0。
- 对字符列表进行排序，方便后续去重。
- 调用 dfs 函数进行回溯求解。
回溯函数 dfs：
- 参数：
  - cArr：排序后的字符列表。
  - pre：上一个选择的字符在 cArr 中的索引。
  - level：当前排列的长度。
  - used：标记字符是否已被使用的布尔列表。
  - count：当前满足条件的排列个数。
- 递归终止条件：
  - 当 level == n 时，表示找到一个满足条件的排列，count 加 1。
- 递归逻辑：
  - 遍历字符列表，尝试选择未被使用的字符。
  - 如果当前字符与前一个字符相同，跳过（避免相邻字符相同）。
  - 如果当前字符与前一个字符相同且前一个字符未被使用，跳过（树层去重）。
  - 标记当前字符为已使用，递归进入下一层。
  - 回溯时取消标记，继续尝试其他字符。
输出结果：
- 调用 getResult 函数并输出结果。

代码逻辑解析

输入合法性检查：
- 确保字符列表长度不小于 n，否则无法拼接出满足条件的字符串。
- 确保字符列表中的字符均为小写字母，否则输入非法。
排序与去重：
- 对字符列表进行排序，方便在回溯过程中进行树层去重，避免生成重复的排列。
回溯算法：
- 通过递归尝试所有可能的字符组合。
- 使用 used 列表标记字符是否已被使用，确保每个字符只能使用一次。
- 通过 pre 参数记录上一个选择的字符，确保相邻字符不相同。
- 通过树层去重（i > 0 and cArr[i] == cArr[i - 1] and not used[i - 1]）避免生成重复的排列。
递归终止条件：
- 当排列长度达到 n 时，表示找到一个满足条件的排列，count 加 1。

代码优化建议

提前剪枝：
- 如果字符列表中某个字符的数量过多，可能导致无法满足相邻字符不相同的条件。可以在回溯前进行统计，提前判断是否可能生成满足条件的排列。
性能优化：
- 对于较大的 n 和字符列表长度，回溯算法的性能可能较差。可以考虑使用动态规划或其他优化方法。
代码可读性：
- 可以增加注释，进一步解释树层去重和相邻字符不相同的逻辑。

示例运行

输入 1：

abc 1

字符列表：['a', 'b', 'c']，目标长度：1。
可能的排列：a, b, c。
输出：3。

输入 2：

dde 2

字符列表：['d', 'd', 'e']，目标长度：2。
可能的排列：de, ed。
输出：2。

输入 3：

aab 3

字符列表：['a', 'a', 'b']，目标长度：3。
可能的排列：aba, aab（不满足条件，因为有两个 a 相邻）。
输出：1（只有 aba 满足条件）。

总结

这段 Python 代码通过回溯算法高效地解决了问题，同时通过排序和树层去重避免了重复排列的生成。代码逻辑清晰，能够正确处理各种边界情况。

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

以下是 C++ 和 C语言 版本的代码实现，并附带详细的中文注释和讲解。

C++ 版本

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int MAX_SIZE = 31; // 最大字符长度char s[MAX_SIZE]; // 存储输入的字符
int s_len;        // 字符数组的长度
int n;            // 目标字符串长度/*!* 全排列求解* @param pre 排列最后一个字符在s中的位置* @param level 当前排列的长度* @param used 标记字符是否已被使用的数组* @param count 当前满足条件的排列个数* @return count*/
int dfs(int pre, int level, bool used[], int count) {// 当排列长度到达n，则是一个符合要求的排列if (level == n) {// 符合要求的排列个数+1return ++count;}for (int i = 0; i < s_len; i++) {// 每个字符只能用一次if (used[i]) continue;// 相同的字符不能相邻，pre指向前面一个被选择的字符在s中的位置，i指向当前被选择的字符在s中的位置if (pre >= 0 && s[i] == s[pre]) continue;// 树层去重(去除重复排列)if (i > 0 && s[i] == s[i - 1] && !used[i - 1]) continue;used[i] = true; // 标记当前字符为已使用count = dfs(i, level + 1, used, count); // 递归进入下一层used[i] = false; // 回溯，取消标记}return count;
}/*!* 获取结果* @return 满足条件的排列个数*/
int getResult() {// 检查输入是否合法for (int i = 0; i < s_len; i++) {if (s[i] < 'a' || s[i] > 'z') {return 0; // 输入非法}}if (s_len < n) {return 0; // 无法拼接出满足条件的字符串}// 对字符数组进行排序，方便树层去重sort(s, s + s_len);bool used[MAX_SIZE] = {false}; // 初始化used数组return dfs(-1, 0, used, 0); // 调用dfs函数求解
}int main() {cin >> s >> n; // 输入字符数组和目标长度s_len = strlen(s); // 计算字符数组的长度cout << getResult() << endl; // 输出结果return 0;
}

C语言版本

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_SIZE 31 // 最大字符长度char s[MAX_SIZE]; // 存储输入的字符
int s_len;        // 字符数组的长度
int n;            // 目标字符串长度/*!* 全排列求解* @param pre 排列最后一个字符在s中的位置* @param level 当前排列的长度* @param used 标记字符是否已被使用的数组* @param count 当前满足条件的排列个数* @return count*/
int dfs(int pre, int level, int used[], int count) {// 当排列长度到达n，则是一个符合要求的排列if (level == n) {// 符合要求的排列个数+1return ++count;}for (int i = 0; i < s_len; i++) {// 每个字符只能用一次if (used[i]) continue;// 相同的字符不能相邻，pre指向前面一个被选择的字符在s中的位置，i指向当前被选择的字符在s中的位置if (pre >= 0 && s[i] == s[pre]) continue;// 树层去重(去除重复排列)if (i > 0 && s[i] == s[i - 1] && !used[i - 1]) continue;used[i] = 1; // 标记当前字符为已使用count = dfs(i, level + 1, used, count); // 递归进入下一层used[i] = 0; // 回溯，取消标记}return count;
}/*!* 比较函数，用于qsort排序*/
int cmp(const void *a, const void *b) {return *((char *) a) - *((char *) b);
}/*!* 获取结果* @return 满足条件的排列个数*/
int getResult() {// 检查输入是否合法for (int i = 0; i < s_len; i++) {if (s[i] < 'a' || s[i] > 'z') {return 0; // 输入非法}}if (s_len < n) {return 0; // 无法拼接出满足条件的字符串}// 对字符数组进行排序，方便树层去重qsort(s, s_len, sizeof(char), cmp);int used[MAX_SIZE] = {0}; // 初始化used数组return dfs(-1, 0, used, 0); // 调用dfs函数求解
}int main() {scanf("%s", s); // 输入字符数组scanf("%d", &n); // 输入目标长度s_len = strlen(s); // 计算字符数组的长度printf("%d\n", getResult()); // 输出结果return 0;
}

代码讲解

1. 输入处理

C++：使用 cin 读取输入，strlen 计算字符数组长度。
C语言：使用 scanf 读取输入，strlen 计算字符数组长度。

2. 输入合法性检查

检查字符是否均为小写字母（a 到 z）。
检查字符数组长度是否小于目标长度 n。

3. 排序

C++：使用 sort 函数对字符数组进行排序。
C语言：使用 qsort 函数对字符数组进行排序。

4. 回溯算法

dfs 函数：
- 参数：
  - pre：上一个选择的字符在数组中的索引。
  - level：当前排列的长度。
  - used：标记字符是否已被使用的数组。
  - count：当前满足条件的排列个数。
- 递归终止条件：当 level == n 时，表示找到一个满足条件的排列，count 加 1。
- 递归逻辑：
  - 遍历字符数组，尝试选择未被使用的字符。
  - 跳过相邻字符相同的情况。
  - 跳过树层重复的情况。
  - 标记字符为已使用，递归进入下一层。
  - 回溯时取消标记。

5. 输出结果

C++：使用 cout 输出结果。
C语言：使用 printf 输出结果。

示例运行

输入 1：

abc 1

字符列表：['a', 'b', 'c']，目标长度：1。
可能的排列：a, b, c。
输出：3。

输入 2：

dde 2

字符列表：['d', 'd', 'e']，目标长度：2。
可能的排列：de, ed。
输出：2。

输入 3：

aab 3

字符列表：['a', 'a', 'b']，目标长度：3。
可能的排列：aba, aab（不满足条件，因为有两个 a 相邻）。
输出：1（只有 aba 满足条件）。

总结

C++ 和 C语言 版本的代码逻辑一致，均通过回溯算法解决问题。
代码通过排序和树层去重避免了重复排列的生成。
代码结构清晰，注释详细，适合学习和参考。

六、尾言

什么是华为OD？

华为OD（Outsourcing Developer，外包开发工程师）是华为针对软件开发工程师岗位的一种招聘形式，主要包括笔试、技术面试以及综合面试等环节。尤其在笔试部分，算法题的机试至关重要。

为什么刷题很重要？

机试是进入技术面的第一关：
华为OD机试（常被称为机考）主要考察算法和编程能力。只有通过机试，才能进入后续的技术面试环节。
技术面试需要手撕代码：
技术一面和二面通常会涉及现场编写代码或算法题。面试官会注重考察候选人的思路清晰度、代码规范性以及解决问题的能力。因此提前刷题、多练习是通过面试的重要保障。
入职后的可信考试：
入职华为后，还需要通过“可信考试”。可信考试分为三个等级：
- 入门级：主要考察基础算法与编程能力。
- 工作级：更贴近实际业务需求，可能涉及复杂的算法或与工作内容相关的场景题目。
- 专业级：最高等级，考察深层次的算法以及优化能力，与薪资直接挂钩。

刷题策略与说明：

2024年8月14日之后，华为OD机试的题库转为 E卷，由往年题库（D卷、A卷、B卷、C卷）和全新题目组成。刷题时可以参考以下策略：

关注历年真题：
- 题库中的旧题占比较大，建议优先刷历年的A卷、B卷、C卷、D卷题目。
- 对于每道题目，建议深度理解其解题思路、代码实现，以及相关算法的适用场景。
适应新题目：
- E卷中包含全新题目，需要掌握全面的算法知识和一定的灵活应对能力。
- 建议关注新的刷题平台或交流群，获取最新题目的解析和动态。
掌握常见算法：
华为OD考试通常涉及以下算法和数据结构：
- 排序算法（快速排序、归并排序等）
- 动态规划（背包问题、最长公共子序列等）
- 贪心算法
- 栈、队列、链表的操作
- 图论（最短路径、最小生成树等）
- 滑动窗口、双指针算法
保持编程规范：
- 注重代码的可读性和注释的清晰度。
- 熟练使用常见编程语言，如C++、Java、Python等。

如何获取资源？

官方参考：
- 华为招聘官网或相关的招聘平台会有一些参考信息。
- 华为OD的相关公众号可能也会发布相关的刷题资料或学习资源。
加入刷题社区：
- 找到可信的刷题交流群，与其他备考的小伙伴交流经验。
- 关注知名的刷题网站，如LeetCode、牛客网等，这些平台上有许多华为OD的历年真题和解析。
寻找系统性的教程：
- 学习一本经典的算法书籍，例如《算法导论》《剑指Offer》《编程之美》等。
- 完成系统的学习课程，例如数据结构与算法的在线课程。

积极心态与持续努力：

刷题的过程可能会比较枯燥，但它能够显著提升编程能力和算法思维。无论是为了通过华为OD的招聘考试，还是为了未来的职业发展，这些积累都会成为重要的财富。

考试注意细节

本地编写代码
- 在本地 IDE（如 VS Code、PyCharm 等）上编写、保存和调试代码，确保逻辑正确后再复制粘贴到考试页面。这样可以减少语法错误，提高代码准确性。
调整心态，保持冷静
- 遇到提示不足或实现不确定的问题时，不必慌张，可以采用更简单或更有把握的方法替代，确保思路清晰。
输入输出完整性
- 注意训练和考试时都需要编写完整的输入输出代码，尤其是和题目示例保持一致。完成代码后务必及时调试，确保功能符合要求。
快捷键使用
- 删除行可用 Ctrl+D，复制、粘贴和撤销分别为 Ctrl+C，Ctrl+V，Ctrl+Z，这些可以正常使用。
- 避免使用 Ctrl+S，以免触发浏览器的保存功能。
浏览器要求
- 使用最新版的 Google Chrome 浏览器完成考试，确保摄像头开启并正常工作。考试期间不要切换到其他网站，以免影响考试成绩。
交卷相关
- 答题前，务必仔细查看题目示例，避免遗漏要求。
- 每完成一道题后，点击【保存并调试】按钮，多次保存和调试是允许的，系统会记录得分最高的一次结果。完成所有题目后，点击【提交本题型】按钮。
- 确保在考试结束前提交试卷，避免因未保存或调试失误而丢分。
时间和分数安排
- 总时间：150 分钟；总分：400 分。
- 试卷结构：2 道一星难度题（每题 100 分），1 道二星难度题（200 分）。及格分为 150 分。合理分配时间，优先完成自己擅长的题目。
考试环境准备
- 考试前请备好草稿纸和笔。考试中尽量避免离开座位，确保监控画面正常。
- 如需上厕所，请提前规划好时间以减少中途离开监控的可能性。
技术问题处理
- 如果考试中遇到断电、断网、死机等技术问题，可以关闭浏览器并重新打开试卷链接继续作答。
- 出现其他问题，请第一时间联系 HR 或监考人员进行反馈。