【华为OD机试真题 C语言】28、全排列

2023-06-14 00:28| 来源: 网络整理| 查看: 265

文章目录一、题目🎃题目描述🎃输入输出🎃样例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

【本文地址】

公司简介

联系我们