面试题38：字符串的全排列和组合
2019-08-13 本文已影响0人
繁星追逐
题型1：排列
/**
- 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
*/
固定第一个字符，递归取得首位后面的各种字符串组合；
再把第一个字符与后面每一个字符交换，并同样递归获得首位后面的字符串组合；
递归的出口，就是只剩一个字符的时候，递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。
代码如下：
/**
* 固定第一个字符，递归取得首位后面的各种字符串组合；
* 再把第一个字符与后面每一个字符交换，并同样递归获得首位后面的字符串组合；
*递归的出口，就是只剩一个字符的时候，递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。
* @param str
* @return
*/
public ArrayList<String> Permutation(String str) {
ArrayList<String> list = new ArrayList<>();
if (str == null || str.length() <= 0){
return list;
}
permutate(str.toCharArray(),0,list);
Collections.sort(list);
return list;
}
private void permutate(char[] str, int begin, ArrayList<String> list) {
if (begin == str.length-1){
String s = String.valueOf(str);
//去除重复的字符串
if (!list.contains(s)){
list.add(s);
}
return;
}
//递归依次交换
for (int i=begin;i<str.length;i++){
swap(str,begin,i);
permutate(str,begin+1,list);
//回退出来后，尝试这种情况下的其他情况
swap(str,begin,i);
}
}
private void swap(char[] str, int begin, int i) {
char temp = str[begin];
str[begin] = str[i];
str[i] = temp;
}
public static void main(String[] args) {
Permutation a = new Permutation();
System.out.println(a.Permutation("aab"));
}
题型二：组合
- 求字符的所有组合,允许组合中有重复元素
如：其实就是求C(n, m) 其中n == str.length; m == num
思路：把问题分解为1，如果当前组合包括第一个元素，则需要再从剩下的n-1个元素中以同样的方式找出m-1个与第一个元素组成一个组合,2，如果当前组合不包括目前的第一个元素，则需要再从剩下的n-1个元素中找出m个元素凑成组合，以这样的方式递归寻找下去，直到找到m个元素为止。如果一直到字符串为空，仍然没有找齐元素则直接停止。
代码如下：
package jzOffer.chap4;
import java.util.ArrayList;
import java.util.List;
/**
* 求字符的所有组合,允许组合中有重复元素
*/
public class combination {
/**
* 其实就是求C(n, m) 其中n == str.length; m == num
*
* @param str 字符序列
* @param num 选几个字符进行组合
* @return C(n, m)的集合
*/
public List<String> combinationAccordingToNum(String str, int num) {
List<String> list = new ArrayList<>();
if (str == null || str.length() <= 0 || num > str.length()){
return list;
}
StringBuilder sb = new StringBuilder();
collect(str, num , sb , list);
return list;
}
/**
* 求所有组合
* @param str
* @return
*/
public List<String> combination(String str){
List<String> list = new ArrayList<>();
if (str == null || str.length() == 0){
return list;
}
StringBuilder sb = new StringBuilder();
//1到字符长度的所有单位
for (int i=1;i<=str.length();i++){
collect(str, i , sb, list);
}
return list;
}
private void collect(String str, int num, StringBuilder sb, List<String> list) {
//还剩下0位，到达最后一位，结束
// 两个if顺序不可交换，否则C(n, n)不会存入到list中：即collect("", sb, 0)时，要先判断num==0存入后，再判断str.length ==0决定不再递归
if (num == 0){
//字符已经去重
list.add(sb.toString());
return;
}
//// 当str为""时候直接返回，不然下一句charAt(0)就会越界
if (str.length() == 0){
return;
}
// 公式C(n, m) = C(n-1, m-1)+ C(n-1, m)
// 第一个字符是组合中的第一个字符，在剩下的n-1个字符中选m-1个字符
sb.append(str.charAt(0));
collect(str.substring(1), num-1, sb , list);
// 第一个字符不是组合中的第一个字符，在剩下的n-1个字符中选m个字符
sb.deleteCharAt(sb.length()-1); //取消选中的第一个字符
collect(str.substring(1), num, sb , list);
}
public static void main(String[] args) {
combination c = new combination();
System.out.println(c.combination("abcca"));
System.out.println(c.combination("abc"));
System.out.println(c.combinationAccordingToNum("aabbc", 2));
}
}
题型3：正方体数字和
- 输入一个含有八个数的数组，判断有没有可能把这8个数字分别加到正方形的八个定点上，使得正方体上三组相对面的四个顶点的和都相等
思路：全排列找出所有a数组的排列，判断是否满足正方体点的特性
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* 输入一个含有八个数的数组，判断有没有可能把这8个数字分别加到正方形的八个定点上，使得正方体上三组相对面的四个顶点的和都相等
*/
public class PermutationExt {
public List<int[]> possibilitiesOfCube(int[] array){
List<int[]> list = new ArrayList<>();
if (array == null && array.length <= 0){
return list;
}
//先得到所有的全排列组合
List<int[]> All = permution(array);
//检查对立面值是否相等
for (int[] one : All){
if (checkSum(one)){
list.add(one);
}
}
return list;
}
private boolean checkSum(int[] array) {
if ((array[0] + array[1] + array[2] + array[3] == array[4] + array[5] + array[6] + array[7]) &&
(array[0] + array[1] + array[4] + array[5] == array[2] + array[3] + array[6] + array[7])
&& (array[0] + array[2] + array[4] + array[6] == array[1] + array[3] + array[5] + array[7])){
return true;
}
return false;
}
public List<int[]> permution(int[] array) {
List<int[]> list = new ArrayList<>();
collect(array, 0 , list);
return list;
}
private void collect(int[] array, int index, List<int[]> list) {
if (index == array.length-1){
if (!has(list,array)){
// 必须使用副本，不能直接传入引用，否则list所有的int[]对象最后都一样
// !!!!
list.add(Arrays.copyOf(array,array.length));
}
}
//递归从传入的起始值开始
for (int i=index;i<array.length;i++){
swap(array, index, i);
collect(array, index+1, list);
swap(array, index, i);
}
}
private boolean has(List<int[]> list, int[] array) {
for (int[] one : list) {
if (equal(one,array)) {
return true;
}
}
return false;
}
private boolean equal(int[] a, int[] b){
for (int i=0;i<a.length;i++){
//如果遇到不相等的则可以提前返货
if (a[i] != b[i]){
return false;
}
}
return true;
}
private void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String[] args) {
PermutationExt p = new PermutationExt();
int[] a = {8, 3, 5, 4, 1, 2, 5, 6};
List<int[]> list = p.possibilitiesOfCube(a);
System.out.println("有" + list.size() + "种可能");
for (int[] arr : list) {
System.out.println(Arrays.toString(arr));
}
int[] b = Arrays.copyOfRange(a,1,a.length);
System.out.println(Arrays.toString(b));
}
}
题型四：八皇后
- 8X8的国际棋盘上，有8个皇后，使其不能相互攻击，即它们不能在同一行、同一列、且同一条对角。
- 1、保证不同行：使用一个数组表示不同行的皇后，八个皇后则int[] queens = new int[8]，其中queens[i]表示位于第i行的皇后，这保证了皇后不位于同一行
- 2、保证不同列：为queens[i]赋值各不相同的数值，queens[i] = j表示位于i行的皇后也位于j列，每个i赋予了不同的j值保证了不同行的皇后也不位于不同列
- 3、保证在同一条对角线：如果在同一条对角线，说明正方形的行数等于列数，即当j > i时:
- j - i == queens[j] -queens[i]（第j行的皇后在第i行的皇后右下方）；或者j - i == queens[i] -queensj
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* 8X8的国际棋盘上，有8个皇后，使其不能相互攻击，即它们不能在同一行、同一列、且同一条对角
*/
public class EightQueens {
/**
* 1、保证不同行：使用一个数组表示不同行的皇后，八个皇后则int[] queens = new int[8]，其中queens[i]表示位于第i行的皇后，这保证了皇后不位于同一行
* 2、保证不同列：为queens[i]赋值各不相同的数值，queens[i] = j表示位于i行的皇后也位于j列，每个i赋予了不同的j值保证了不同行的皇后也不位于不同列
* 3、保证在同一条对角线：如果在同一条对角线，说明正方形的行数等于列数，即当j > i时:
* j - i == queens[j] -queens[i]（第j行的皇后在第i行的皇后右下方）；或者j - i == queens[i] -queens[j](第j行的皇后在第i行的皇后左下方)
* <p>
* 这又是一个全排列的扩展问题，先求出所有的排列可能，从中排除不符合要求的摆放方法即可
*/
public List<int[]> possibilitiesOfQueensPlaced() {
List<int[]> list = new ArrayList<>();
// 大小为8的数组，且数值各不相同，任意排列都保证了不同行不同列
int[] array = {0,1,2,3,4,5,6,7};
//调用之前的全排列函数
PermutationExt permutationExt = new PermutationExt();
List<int[]> all = permutationExt.permution(array);
//去除满足对角线的情况
for (int[] one : all){
if (!isLocatedSameDiagonal(one)){
list.add(one);
}
}
return list;
}
//检查任意两个皇后是否在同一条对角线上
private boolean isLocatedSameDiagonal(int[] array) {
//双重循环按照每个依次与之后行元素位置的判断
for (int i=0;i<array.length;++i){
for (int j=i+1;j<array.length;++j){
if ((j - i == array[j] - array[i]) && (j - i == array[i] - array[j])){
// if ((Math.abs(j - i) == Math.abs(array[j] - array[i]))){
return true;
}
}
}
return false;
}
public static void main(String[] args) {
EightQueens queens = new EightQueens();
List<int[]> l = queens.possibilitiesOfQueensPlaced();
System.out.println("共有" + l.size() + "种放置方法");
for (int[] arr : l) {
System.out.println(Arrays.toString(arr));
}
}
}
