（每日一练c++）CC186 字符串排列

谁借莪１个温暖的怀抱￠ 2023-10-04 18:04 50阅读 0赞

## 前言 ##

C++是一种计算机高级程序设计语言，由C语言扩展升级而产生 ，最早于1979年由本贾尼·斯特劳斯特卢普在AT&T贝尔工作室研发。  
C++既可以进行C语言的过程化程序设计，又可以进行以抽象数据类型为特点的基于对象的程序设计，还可以进行以继承和多态为特点的面向对象的程序设计。C++擅长面向对象程序设计的同时，还可以进行基于过程的程序设计。  
C++拥有计算机运行的实用性特征，同时还致力于提高大规模程序的编程质量与程序设计语言的问题描述能力。

Java是一门面向对象的编程语言，不仅吸收了C++语言的各种优点，还摒弃了C++里难以理解的多继承、指针等概念，因此Java语言具有功能强大和简单易用两个特征。Java语言作为静态面向对象编程语言的代表，极好地实现了面向对象理论，允许程序员以优雅的思维方式进行复杂的编程 。  
Java具有简单性、面向对象、分布式、健壮性、安全性、平台独立与可移植性、多线程、动态性等特点 。Java可以编写桌面应用程序、Web应用程序、分布式系统和嵌入式系统应用程序等 。

Python由荷兰数学和计算机科学研究学会的吉多·范罗苏姆 于1990 年代初设计，作为一门叫做ABC语言的替代品。Python提供了高效的高级数据结构，还能简单有效地面向对象编程。Python语法和动态类型，以及解释型语言的本质，使它成为多数平台上写脚本和快速开发应用的编程语言，随着版本的不断更新和语言新功能的添加，逐渐被用于独立的、大型项目的开发。  
Python解释器易于扩展，可以使用C语言或C++（或者其他可以通过C调用的语言）扩展新的功能和数据类型。Python 也可用于可定制化软件中的扩展程序语言。Python丰富的标准库，提供了适用于各个主要系统平台的源码或机器码。  
2021年10月，语言流行指数的编译器Tiobe将Python加冕为最受欢迎的编程语言，20年来首次将其置于Java、C和JavaScript之上。

### 描述 ###

给定一个字符串string **A**和其长度**n**，返回所有该字符串所包含字符的各种排列。要求输入字符串长度小于等于11且均为大写英文字符，排列中的字符串按字典序从大到小排序。(重复字符串不用合并)

测试样例：

"ABC"

返回：["CBA","CAB","BCA","BAC","ACB","ABC"]

public static ArrayList<String> getPermutation(String string) {
            // write code here
            ArrayList<String> list = new ArrayList<String>();
            deepSearch("", string.toCharArray(), list);
            //逆序排序字符串
            Collections.sort(list, new Comparator<String>() {
                @Override
                public int compare(String s1, String s2) {
                    // TODO Auto-generated method stub
                    return s2.compareTo(s1);
                }
            });
            return list;
        }
    
        private static void deepSearch(String string, char[] array,
            ArrayList<String> list) {
            // TODO Auto-generated method stub
            if (array.length == 1) {
                list.add(string.concat(String.valueOf(array[0])));
                return;
            }
            /*
             * 非去重的全排列
             */
            char ch = 0;
            for (int i = 0; i < array.length; i++) {
                ch = array[i];
                char[] levalArray = new char[array.length - 1];
                if (i - 1 >= 0) System.arraycopy(array, 0, levalArray, 0, i);
                if (i < array.length - 1) System.arraycopy(array, i + 1,
                    levalArray, i, levalArray.length - i);
                deepSearch(string.concat(String.valueOf(ch)), levalArray, list);
            }
    
            /*
            //如需要去除掉重复值的全排列，用下面代码段
            HashSet<Character> know = new HashSet<Character>();  
            char ch = 0;
            for (int i = 0; i < array.length; i++) {
                ch = array[i];
                  if (!know.contains(ch)) {
                    know.add(ch);
                char[] levalArray = new char[array.length - 1];
                if (i - 1 >= 0) System.arraycopy(array, 0, levalArray, 0, i);
                if (i < array.length - 1) System.arraycopy(array, i + 1,
                    levalArray, i, levalArray.length - i);
                deepSearch(string.concat(String.valueOf(ch)), levalArray, list);
                }
            }
            */
        }