标签：list sort 十分 i++ image info 字符串 rar ret
首先,我们上一篇说到了递归的二叉树套路,但是递归还有一种更常见的类型,就是题目我们要找到所有有可能的集合,这种类型我称之为"数组添加"。当然我现在这么说，可能你们看得也很懵，但是我举几个例子你们就懂了。我从leetcode里面找来了几道题目：
①给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
这一道题需要找的是所有能够组成目标数的数组的集合，因为组成target的数字数量是没有限定的，所以如果我们用循环语句去写的话，那代码会十分的臃肿和庞大。此时我们就用递归来解决这个问题。而这种类型的题目就是十分典型的“数组添加”类型。
我们解决这道题的思路就是，当我们选好candidates[index]当可能组成target的集合时，我们以这个数字为开头，去不断尝试candidates[index]的下一个下标当集合的第二个数字。递归就解决了臃肿的循环代码，因为题目给的不同集合时长度不同，循环的长度也不确定。（在这里我们优化一下代码，我们先把集合排好序，因为这个例子不太好画图，所以我把数据改了一下）
而当我们在第一个数字选择①时，我们的递归过程就是这样，而当我们选择第二个小标②时，又是一次递归过程，所以我们的递归里面有一个循环语句，而base case就是把我们已经收集到的集合list的sum== target，就将list加到整个大的List>，这就是几乎所有这种题目的套路，递归，base case就是把集合收集到，最后加到返回的list集合里面。
public List> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
List> resList = new ArrayList();
List list = new ArrayList();
process(candidates, target , 0, list, resList);
return resList;
}
public void process(int[] candidates, int target,int index ,List list,List> resList){
if(target == 0){
resList.add(list);
return;
}
if(index == candidates.length||target){
return;
}
//递归里面的循环语句
for(int i = index ; i ){
if(i>index && candidates[i]==candidates[i-1]){
continue;
}
List temp = new ArrayList(list);
temp.add(candidates[i]);
process(candidates,target-candidates[i],i+1,temp,resList);
}
}
②给定一个 没有重复 数字的序列，返回其所有可能的全排列。
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
这个题目跟上一题是差不多的,也是在递归体里面需要加循环语句,而全排列就是也是我们去选可能的集合,当我们选择集合的下标0的数字当第一个数字时,还有当我们选择集合的下标1的数字当第一个数字时.......这个就是递归里面的循环语句的意思.我们也不难发现,我们的base case也是把我们可能的集合添加的最后要返回的大集合List>。而这里的swap()也是当我们递归的时候的时候需要把它交换的数字给交换回来。
public List> permute(int[] nums) {
List> resList = new ArrayList();
List list = new ArrayList();
process(nums, resList, list, 0);
return resList;
}
public void process(int[] nums , List> resList ,
List list , int index) {
if (index == nums.length) {
resList.add(list);
}
for (int i = index; i tem = new ArrayList(list);
tem.add(nums[index]);
process(nums, resList, tem, index+1);
swap(nums, index, i);
}
}
public void swap(int[] nums, int i ,int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
③给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。就是手机上的九宫格输入法。
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
这道题也跟上面的类似，当时它递归里面的循环语句不一样，他不是用for语句，而是用到了switch语句。这里不多赘述了。
public static List letterCombinations(String digits){
List list = new ArrayList();
char[] ch = digits.toCharArray();
char[] path = new char[ch.length];
process(ch, path, 0, list);
return list;
}
public static void process(char[] ch, char[] path, int index, List list){
if (index == ch.length) {
list.add(new String(path));
return;
}
switch (ch[index]) {
case ‘2‘:
path[index] = ‘a‘;
process(ch, path,index+1, list);
path[index] = ‘b‘;
process(ch, path,index+1, list);
path[index] = ‘c‘;
process(ch, path,index+1, list);
break;
case ‘3‘:
path[index] = ‘d‘;
process(ch, path,index+1, list);
path[index] = ‘e‘;
process(ch, path,index+1, list);
path[index] = ‘f‘;
process(ch, path,index+1, list);
break;
case ‘4‘:
path[index] = ‘g‘;
process(ch, path,index+1, list);
path[index] = ‘h‘;
process(ch, path,index+1, list);
path[index] = ‘i‘;
process(ch, path,index+1, list);
break;
case ‘5‘:
path[index] = ‘j‘;
process(ch, path,index+1, list);
path[index] = ‘k‘;
process(ch, path,index+1, list);
path[index] = ‘l‘;
process(ch, path,index+1, list);
break;
case ‘6‘:
path[index] = ‘m‘;
process(ch, path,index+1, list);
path[index] = ‘n‘;
process(ch, path,index+1, list);
path[index] = ‘o‘;
process(ch, path,index+1, list);
break;
case ‘7‘:
path[index] = ‘p‘;
process(ch, path,index+1, list);
path[index] = ‘q‘;
process(ch, path,index+1, list);
path[index] = ‘r‘;
process(ch, path,index+1, list);
path[index] = ‘s‘;
process(ch, path,index+1, list);
break;
case ‘8‘:
path[index] = ‘t‘;
process(ch, path,index+1, list);
path[index] = ‘u‘;
process(ch, path,index+1, list);
path[index] = ‘v‘;
process(ch, path,index+1, list);
break;
case ‘9‘:
path[index] = ‘w‘;
process(ch, path,index+1, list);
path[index] = ‘x‘;
process(ch, path,index+1, list);
path[index] = ‘y‘;
process(ch, path,index+1, list);
path[index] = ‘z‘;
process(ch, path,index+1, list);
break;
default:
break;
}
}
浅谈递归--数组添加
标签：list sort 十分 i++ image info 字符串 rar ret
原文地址：https://www.cnblogs.com/carryup/p/13580285.html