文章目录
一、题目🎃题目描述🎃输入输出🎃样例1🎃样例2
二、思路参考三、代码参考
作者:KJ.JK
🍂个人博客首页: KJ.JK 🍂专栏介绍: 华为OD机试真题汇总,定期更新华为OD各个时间阶段的机试真题,每日定时更新,本专栏将使用C语言进行更新解答,包含真题,思路分析,代码参考,欢迎大家订阅学习
一、题目
🎃题目描述
给定一个只包含大写英文字母的字符串S,要求你给出对S重新排列的所有不相同的排列数。 如:S为ABA,则不同的排列有ABA、AAB、BAA三种
🎃输入输出
输入 输入一个长度不超过10的字符串S,我们确保都是大写的 输出 输出S重新排列的所有不相同的排列数(包含自己本身)
🎃样例1
输入
ABA
输出
3
🎃样例2
输入
ABCDEFGHHA
输出
907200
二、思路参考
1、首先,我们需要计算字符串中每个字符的频率。可以使用一个大小为26的数组来记录每个字母的出现次数,数组下标对应字母的ASCII码减去65(即'A'的ASCII码)
2、接下来,我们需要计算总的排列数。根据给定字符串的长度,可以计算出总的排列数为n!,其中n为字符串的长度
3、然后,我们需要根据字符串中每个字符的频率来调整总的排列数。对于重复出现的字符,我们需要除以相应的阶乘值来消除重复的排列。具体做法是,对于每个字符的频率f,我们将总的排列数除以f!
4、最后,得到的结果即为所有不相同排列的数量
三、代码参考
#include
#define MAX_LEN 10
int factorial(int n) {
if (n 0}; // 记录每个字母的频率
int length = 0; // 字符串的长度
// 计算每个字母的频率和字符串的长度
for (int i = 0; str[i] != '\0'; i++) {
frequency[str[i] - 'A']++;
length++;
}
unsigned long long permutations = factorial(length); // 总的排列数
// 根据每个字符的频率调整总的排列数
for (int i = 0; i
permutations /= factorial(frequency[i]);
}
}
return permutations;
}
int main() {
char str[MAX_LEN + 1];
scanf("%s", str);
unsigned long long result = calculatePermutations(str);
printf("%llu\n", result);
return 0;
}
作者:KJ.JK
|