当前位置：首页 > news >正文

华为OD机试 - 构成指定长度字符串的个数（Python/JS/C/C++ 2024 E卷 100分）

news 2024/11/13 11:55:48

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

给定 M 个字符( a-z ) ，从中取出任意字符(每个字符只能用一次)拼接成长度为 N 的字符串，要求相同的字符不能相邻。

计算出给定的字符列表能拼接出多少种满足条件的字符串，输入非法或者无法拼接出满足条件的字符串则返回 0 。

二、输入描述

给定长度为 M 的字符列表和结果字符串的长度 N ，中间使用空格(" ")拼接。

0 < M < 30
0 < N ≤ 5

三、输出描述

输出满足条件的字符串个数。

1、输入

dde 2

2、输出

3、说明

给定的字符为 dde ，果字符串长度为 2 ，可以拼接成 de、ed，共 2 种。

四、测试用例

1、输入

java 3

2、输出

3、说明

满足条件的字符串：

[jav, jva, ava, ajv, avj, aja, vja, vaj]

五、解题思路

使用深度优先搜索（DFS）的方法生成所有可能的满足条件的字符串。
递归遍历每个字符，判断当前字符是否与前一个字符相同，如果相同则跳过。
根据选择或跳过的情况继续向下递归，直到生成长度为 N 的字符串。
统计满足条件的字符串的数量，并输出结果。

五、Python算法源码

def dfs(arr, last_index, length, used, count):# 当字符串长度达到要求，符合条件，count + 1if length == N:return count + 1for i in range(len(arr)):# 用过了 || 相邻的两个字符不可以相同 || 过滤掉重复排列if used[i] or (last_index >= 0 and arr[i] == arr[last_index]) or (i > 0 and arr[i] == arr[i - 1] and not used[i - 1]):continueused[i] = Truecount = dfs(arr, i, length + 1, used, count)used[i] = Falsereturn countif __name__ == "__main__":str_input = input("请输入字符列表：")N = int(input("请输入字符串长度："))if len(str_input) < N:print(0)exit()arr = list(str_input)# 检查字符是否都是小写字母for c in arr:if c < 'a' or c > 'z':print(0)exit()# 对字符列表进行排序arr.sort()# 递归调用DFS进行全排列生成符合条件的字符串used = [False] * len(arr)print(dfs(arr, -1, 0, used, 0))

六、JavaScript算法源码

function dfs(arr, lastIndex, length, used, count) {// 当字符串长度达到要求，符合条件，count + 1if (length === N) {return count + 1;}for (let i = 0; i < arr.length; i++) {// 用过了 || 相邻的两个字符不可以相同 || 过滤掉重复排列if (used[i] || (lastIndex >= 0 && arr[i] === arr[lastIndex]) || (i > 0 && arr[i] === arr[i - 1] && !used[i - 1])) {continue;}used[i] = true;count = dfs(arr, i, length + 1, used, count);used[i] = false;}return count;
}function main() {const str = prompt("请输入字符列表：");N = parseInt(prompt("请输入字符串长度："));if (str.length < N) {console.log(0);return;}let arr = str.split('');// 检查字符是否都是小写字母for (let c of arr) {if (c < 'a' || c > 'z') {console.log(0);return;}}// 对字符列表进行排序arr.sort();// 递归调用DFS进行全排列生成符合条件的字符串let used = new Array(arr.length).fill(false);console.log(dfs(arr, -1, 0, used, 0));
}main();

七、C算法源码

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>int N;int dfs(char *arr, int lastIndex, int length, bool *used, int count) {// 当字符串长度达到要求，符合条件，count+1if (length == N) {return ++count;}for (int i = 0; i < strlen(arr); i++) {if (used[i] || (lastIndex >= 0 && arr[i] == arr[lastIndex]) || (i > 0 && arr[i] == arr[i - 1] && !used[i - 1])) {continue;}used[i] = true;count = dfs(arr, i, length + 1, used, count);used[i] = false;}return count;
}int main() {char str[100];printf("请输入字符列表：");scanf("%s", str);printf("请输入字符串长度：");scanf("%d", &N);if (strlen(str) < N) {printf("0\n");return 0;}// 检查字符是否都是小写字母for (int i = 0; i < strlen(str); i++) {if (str[i] < 'a' || str[i] > 'z') {printf("0\n");return 0;}}// 对字符列表进行排序qsort(str, strlen(str), sizeof(char), (int (*)(const void *, const void *))strcmp);bool used[strlen(str)];memset(used, false, sizeof(used));// 递归调用DFS进行全排列生成符合条件的字符串printf("%d\n", dfs(str, -1, 0, used, 0));return 0;
}

八、C++算法源码

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int N;int dfs(vector<char>& arr, int lastIndex, int length, vector<bool>& used, int count) {// 当字符串长度达到要求，符合条件，count + 1if (length == N) {return ++count;}for (int i = 0; i < arr.size(); i++) {if (used[i] || (lastIndex >= 0 && arr[i] == arr[lastIndex]) || (i > 0 && arr[i] == arr[i - 1] && !used[i - 1])) {continue;}used[i] = true;count = dfs(arr, i, length + 1, used, count);used[i] = false;}return count;
}int main() {string str;cout << "请输入字符列表：";cin >> str;cout << "请输入字符串长度：";cin >> N;if (str.length() < N) {cout << 0 << endl;return 0;}vector<char> arr(str.begin(), str.end());// 检查字符是否都是小写字母for (char c : arr) {if (c < 'a' || c > 'z') {cout << 0 << endl;return 0;}}// 对字符列表进行排序sort(arr.begin(), arr.end());// 递归调用DFS进行全排列生成符合条件的字符串vector<bool> used(arr.size(), false);cout << dfs(arr, -1, 0, used, 0) << endl;return 0;
}