题目描述
这一类题目包括了如下一堆题目：
1. 字符串、数组的全排列；（leetcode 46 给定一个 没有重复 数字的序列，返回其所有可能的全排列）
2. 字符串、数组的去重的/不去重的全组合；
3. 数组的最短子集，该子集所有元素之和为给定的K的倍数
4. 数组的最长子集，该子集所有元素之和为给定的K的倍数
上述题目都用到了回溯法
解法
1. 字符串、数组的全排列
看力扣上的题解，思路是：
数组长度为N，遍历每一位元素，将第i(0=<i<N)个元素固定到首位，剩下的N-1个元素递归调用该函数。跳出函数之后把第i个元素归位。
public class PermutationString {
public static void swap(StringBuilder str, int a, int b) {
char te = str.charAt(a);
str.setCharAt(a, str.charAt(b));
str.setCharAt(b, te);
}
/**
* 全排列
* @param str 用StringBuilder的好处是可以调换，因为全排列字符串的长度不变，所以用StringBuilder；长度变的话用ArrayList或者Hashset
* @return ArrayList 好处是可以调用Collections.sort()按照字典序排序
*/
public static ArrayList<String> Perm(StringBuilder str){
ArrayList<String> res = new ArrayList<String>();
int l = str.length();
if(l==1) res.add(str.toString());
else {
for(int i = 0; i<l; i++) {
//如果重复的字符就不交换了
if(i==0 || str.charAt(i) != str.charAt(0)) {
swap(str,i,0);
ArrayList<String> nres = Perm(new StringBuilder(str.substring(1)));
swap(str,i,0);
for(int m = 0; m<nres.size();m++) {
res.add(str.charAt(i)+nres.get(m));
}
}
}
}
return res;
}
public static ArrayList<String> PermMain(String str){
ArrayList<String> res = Perm(new StringBuilder(str));
Collections.sort(res);//输出字典序的话，直接调用Collections.sort()函数就能排序
return res;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String a = in.next();
ArrayList<String> res = PermMain(a);
//--------------------------打印测试-----------------------------
for(int i = 0; i<res.size();i++) {
System.out.print(res.get(i)+",");
}
}
}
2. 字符串、数组的全组合
- 全组合的长度是1~N，长度可变的。故函数的参数有3个：原数组、缓存的当前符合条件的子集、当前的步数。
/**
* 字符串全排列，不去重
* @param charArray 字符串转成char数组
* @param res 缓存当前子串
* @param begin 当前从哪个索引开始
*/
private static void allcombination(char[] charArray, StringBuilder res, int begin) {
if (begin == charArray.length && res.length()>0) {
System.out.println(res);
num++;
} else {
if (begin < charArray.length) {
/*添加第一个字符，从后面的字符中选择 iter-1个字符 */
res.append(charArray[begin]);
allcombination(charArray, res, begin + 1);
/*从剩下的n个中选择iter个*/
res.deleteCharAt(res.length() - 1);
allcombination(charArray, res, begin + 1);
}
}
}
- 如果要求去重，则在上述代码的基础上增加一些判断
/**
* 美团笔试，返回所有无重复字符的子字符串
* @param charArray
* @param res 用HashSet,因为HashSet.contains()可以查重
* @param begin
*/
private static void combination_Nosame(char[] charArray, HashSet<Character> res, int begin) {
if (begin == charArray.length && res.size()>0) {
//System.out.println("---################---");
System.out.println(res);
} else {
if (begin < charArray.length) {
/*用HashSet的contains()查重，如果当前的子集中已经有该元素了则跳过*/
if(!res.contains(charArray[begin])) {
res.add(charArray[begin]);
combination_Nosame(charArray, res, begin + 1);
res.remove(charArray[begin]);
combination_Nosame(charArray, res, begin + 1);
}
else combination_Nosame(charArray, res, begin + 1);
}
}
}
- 另外，字符串去重的方法如下
/**
* 字符串去重
* @param str
*/
public static String removeDuplicate(String str) {
StringBuilder res = new StringBuilder();
for(int i = 0; i<str.length(); i++) {
//用stringBuilder的indexOf()函数查重
if(res.indexOf(String.valueOf(str.charAt(i)))<0) res.append(String.valueOf(str.charAt(i)));
}
return res.toString();
}
3. 数组的最短子集，该子集所有元素之和为给定的K的倍数
找最短的子集的话，给原数组每个数字对K取余数，用长度为K的数组+K个ArrayList来存元素。
原数组的每个元素取余的值=它存的ArrayList的序号
如果不要求输出这个子集具体包括哪些元素，只输出该子集的长度的话，直接开辟一个长度为K的数组就行了，然后该数组第i个索引下的值为原数组中余数为i的元素的个数。如果余数为0的元素的个数大于0的话，最短子集长度为1
int[] dp = new int[K];
for(int i = 0; i<arr.length; i++) {
dp[arr[i]%K]++;
}
//如果余数为0的元素的个数大于0的话，最短子集长度为1
if (dp[0]>0) return 1;
找子集的过程还是回溯，先把第i个元素放进缓存的数组res里，一直遍历原数组，遍历完了判断res是否符合条件。然后再把第i个元素扔掉，继续递归。
//找最小值，故初始值设成很大的数
static int mintime = Integer.MAX_VALUE;
public static int smallsubK(int[] dp, ArrayList<Integer> res, int k, int begin) {
if(k==0) {
mintime = Math.min(mintime, res.size()) ;
return mintime;
}
if ((begin == dp.length && k!=0) || k<0) {
return -1;
} else {
if (begin < dp.length) {
/*添加第一个字符，从后面的字符中选择 iter-1个字符 */
if(dp[begin]>0) {
res.add(begin);
dp[begin]--;
smallsubK(dp, res,k-begin,begin + 1);
res.remove(res.size()-1);
dp[begin]++;
}
smallsubK(dp, res, k, begin + 1);
}
}
return mintime<Integer.MAX_VALUE? mintime:-1;
}
4. 数组的最长子集，该子集所有元素之和为给定的K的倍数
网易的笔试题，找子集，满足元素和为6的倍数，这个和的最大值
/*一个数组，找到数字和为6的倍数的最大和
4
6 8 4 3*/
static int maxsum = 6; //找最大值，故初始值设成比较小的数
public static int findsum(int[] arr, ArrayList<Integer> temp, int begin) {
//遍历结束的时候计算sum是否为6的倍数
if (begin == arr.length) {
int sum = 0;
//求和
for(int i = 0; i<temp.size(); i++) {
sum+= temp.get(i);
}
if(sum%6!=0) {
return -1;
}
else {
maxsum = Math.max(maxsum, sum);
return maxsum;
}
}
else {
//最普通的回溯法
if (begin < arr.length) {
temp.add(arr[begin]);
findsum(arr, temp, begin + 1);
temp.remove(temp.size()-1);
findsum(arr, temp, begin + 1);
}
}
return maxsum==0? -1:maxsum;
}
