【华为OD题库-106】全排列-java

题目

给定一个只包含大写英文字母的字符串S，要求你给出对S重新排列的所有不相同的排列数。如:S为ABA，则不同的排列有ABA、AAB、BAA三种。
解答要求
时间限制:5000ms,内存限制:100MB
输入描述
输入一个长度不超过10的字符串S，确保都是大写的。
输出描述
输出S重新排列的所有不相同的排列数（包含自己本身)。
示例1:
输入
ABA
输出
3
示例2:
输入
ABCDEFGHHA
输出
907200

思路

求含重复元素的排列总数，两种方法（数学法效率远高于dfs）：

1. dfs列举所有排列，得到总数，只需要总数，不需要具体组合，具体思路详见：【JAVA-排列组合】一个套路速解排列组合题
2. 数学公式法

比如输入数据为：ABCDDDA
不考虑重复数据，总的排列数为：res=7!
统计重复元素出现次数：A出现2次，D出现3次，其他出现1次
所以最后结果为：res=7!/(2!*3!)=420

备注：数学法可以这样理解，不考虑重复，那么n个元素的排列方法为n！，再去重，比如某个元素有3个，在不去重时，它重复了3！次，去重时直接除掉它就可以了

题解

package hwod;import java.util.*;public class ArrangeInOrder {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String str = sc.nextLine();System.out.println(arrangeInOrder(str));System.out.println(arrangeInOrder2(str));}private static int res;private static int arrangeInOrder(String str) {final char[] chars = str.toCharArray();Arrays.sort(chars);int[] used = new int[chars.length];dfs(chars, used, 0);return res;}private static void dfs(char[] chars, int[] used, int len) {if (len == chars.length - 1) {//确定到倒数第二位即可res++;return;}for (int i = 0; i < chars.length; i++) {if (i > 0 && chars[i] == chars[i - 1] && used[i - 1] == 0) continue;if (used[i] == 1) continue;used[i] = 1;dfs(chars, used, len + 1);used[i] = 0;}}//方案二：数学法private static int arrangeInOrder2(String str) {Map<Character, Integer> map = statisticsCnt(str);int size = str.length();long res = getFactorialNum(size);int divide = 1;for (Character key : map.keySet()) {divide *= getFactorialNum(map.get(key));}return (int) (res / divide);}private static Map<Character, Integer> statisticsCnt(String string) {Map<Character, Integer> map = new HashMap<>();for (int i = 0; i < string.length(); i++) {map.put(string.charAt(i), map.getOrDefault(string.charAt(i), 0) + 1);}return map;}/*** @param n* @return 计算阶乘*/private static long getFactorialNum(long n) {if (n == 1) return 1;return n * getFactorialNum(n - 1);}
}

推荐

如果你对本系列的其他题目感兴趣，可以参考华为OD机试真题及题解（JAVA），查看当前专栏更新的所有题目。

说明

本专栏所有文章均为原创，欢迎转载，请注明文章出处：https://blog.csdn.net/qq_31076523/article/details/134176793。百度和各类采集站皆不可信，搜索请谨慎鉴别。技术类文章一般都有时效性，本人习惯不定期对自己的博文进行修正和更新，因此请访问出处以查看本文的最新版本。