递归 回溯
递归 回溯
总结：树的题目很多都可以需要通过递归来解决，而很多问题虽然直观上看不是一个树的问题，但是考虑一下其本质是一个树形问题，可以转化为一课树，然后通过递归解决，关键在于观察得到递归关系；回溯法是一种暴力解法的一个主要实现手段，通过剪枝可以让回溯法提升一些性能，当循环遍历不要暴力解决时，通过回溯法可以方便的暴力解决。
1. 17 电话号码的字母组合
- 字符串的合法性，1对应什么字母？空字符串如何处理？多个解时顺序问题？
- 递归函数的含义是：得到当前所有数字组合所能得到的所有字符串。将当前数字所有可能组合上除了当前数字剩余所有数字字符得到的所有字符串。
class Solution {
private String[][] hash = {
{},
{},
{"a", "b", "c"},
{"d", "e", "f"},
{"g", "h", "i"},
{"j", "k", "l"},
{"m", "n", "o"},
{"p", "q", "r", "s"},
{"t", "u", "v"},
{"w", "x", "y", "z"}
};
public List<String> letterCombinations(String digits) {
if(digits.length() == 0)
return new ArrayList<>();
if(digits.length() == 1){
ArrayList<String> result = new ArrayList<>();
int ch = digits.charAt(0) - '0';
String[] strs = hash[ch];
for(String str : strs)
result.add(str);
return result;
}
List<String> result = new ArrayList<>();
int ch = digits.charAt(0) - '0';
String[] strHash = hash[ch];
List<String> strs = letterCombinations(digits.substring(1, digits.length()));
for(int i = 0; i < strHash.length; i++){
for(String str : strs)
result.add(strHash[i] + str);
}
return result;
}
}
- 另外一种递归的形式，回溯的结果是搜索到的所有解，上面是通过返回值返回搜索到的所有解，还可以通过类的内部成员变量保存搜索到的解，不需要返回值。上面是在递归函数中不断进行深层递归，下面的方式是在递归函数的参数中不断传入深层递归的参数。一定要弄清楚递归函数的参数的含义以及对递归函数的影响。
class Solution {
private String[][] hash = {
{},
{},
{"a", "b", "c"},
{"d", "e", "f"},
{"g", "h", "i"},
{"j", "k", "l"},
{"m", "n", "o"},
{"p", "q", "r", "s"},
{"t", "u", "v"},
{"w", "x", "y", "z"}
};
private List<String> result = new ArrayList<>();
// digits是需要转为字母的数字字符串，index是当前处理的第几个digits，s是已经处理的digits中的数字得到的字符串
private void findLetters(String digits, int index, String s){
if(index == digits.length()){
result.add(s);
return;
}
int digit = digits.charAt(index) - '0';
String[] letters = hash[digit];
for(int i = 0; i < letters.length; i++){
findLetters(digits, index + 1, s + letters[i]);
}
}
public List<String> letterCombinations(String digits) {
if(digits.length() == 0)
return result;
findLetters(digits, 0, "");
return result;
}
}
2. 93 复原IP地址
- IP地址的数字范围是[0, 255]，注意连续的00 000 等不是合法的IP地址
- 方法：回溯法解决，递归函数的含义是对于当前传入的字符串参数，得到其所有可能的IP地址，
class Solution {
private List<String> result = new ArrayList<>();
// 参数含义，s为需要处理的字符串，index为当前要处理的s的第几个字符，temp为到index为止得到的IP地址（每一段以一个String类型存储在list temp中，temp中的每一个string都是IP地址中的一段）
private void findAllIPAddress(String s, int index, List<String> temp){
// 处理到字符串末尾且刚好4段才得到一个合法的IP地址，放入类私有变量result中
if(index == s.length()){
if(temp.size() == 4){
String strTemp = "";
for(int i = 0; i < temp.size() - 1; i++){
strTemp += temp.get(i) + ".";
}
strTemp += temp.get(temp.size() - 1);
result.add(strTemp);
}
}
for(int i = 1; index + i <= s.length() && i <= 3; i++){
String cur = s.substring(index, index + i);
if(Integer.valueOf(cur) > 255 || (cur.charAt(0) == '0' && cur.length() > 1))
break;
temp.add(cur);
String rightString = s.substring(index + i, s.length());
// 剪枝，当前已经有4段且后面还有剩余的字符串，则直接剪掉
if(rightString.length() != 0 && temp.size() == 4){
temp.remove(temp.size() - 1);
continue;
}
findAllIPAddress(s, index + i, temp);
temp.remove(temp.size() - 1);
}
}
public List<String> restoreIpAddresses(String s) {
findAllIPAddress(s, 0, new ArrayList<String>());
return result;
}
}
3. 131 分割回文串
- 方法：递归求解，下面的写法使用的传参比较少，内部代码逻辑就多一些，在写递归的时候，可以是下面的方式，也可以增加递归函数的参数，使得判断更方便。
class Solution {
// 递归函数的含义，对于当前的字符串s，得到所有使所有子串是回文串的分割
public List<List<String>> partition(String s) {
if(s.length() == 0 || s.length() == 1){
List<List<String>> result = new ArrayList<>();
List<String> temp = new ArrayList<>();
temp.add(s);
result.add(temp);
return result;
}
List<List<String>> result = new ArrayList<>();
for(int i = 1; i <= s.length(); i++){
String leftString = s.substring(0, i);
if(!isPalindrome(leftString))
continue;
String rightString = s.substring(i, s.length());
if(rightString.length() == 0){
List<String> temp = new ArrayList<>();
temp.add(leftString);
result.add(temp);
}else{
List<List<String>> rightResult = partition(rightString);
for(List<String> list : rightResult){
list.add(0, leftString);
result.add(list);
}
}
}
return result;
}
private boolean isPalindrome(String s){
if(s.length() == 0 || s.length() == 1)
return true;
int left = 0, right = s.length() - 1;
while(left < right){
if(s.charAt(left++) != s.charAt(right--))
return false;
}
return true;
}
}
- 多递归函数参数的写法
class Solution {
private List<List<String>> result = new ArrayList<>();
public List<List<String>> partition(String s) {
backTrack(s, 0, new ArrayList<String>());
return result;
}
// 递归函数的含义，s为需要处理的字符串，index为当前需要处理的s的第几个字符，当前搜索的路径保存在temp中
private void backTrack(String s, int index, ArrayList<String> temp){
if(index == s.length()){
result.add(new ArrayList<>(temp));
return;
}
for(int i = index; i < s.length(); i++){
if(isPalindrome(s, index, i)){
temp.add(s.substring(index, i + 1));
backTrack(s, i + 1, temp);
temp.remove(temp.size() - 1);
}
}
}
// 判断字符串是否回文
private boolean isPalindrome(String s, int left, int right){
while(left < right){
if(s.charAt(left) != s.charAt(right))
return false;
left++;
right--;
}
return true;
}
}
回溯处理排列问题
4. 46 全排列
- 方法：回溯，注意题目已经说明了给出的序列中没有重复的数字
class Solution {
private List<List<Integer>> result = new ArrayList<>();
private boolean[] used;
// nums是原始输入数组，index标记当前处理数组的第几个数字，p是当前已经处理前面的数字得到的排列
private void getPermute(int[] nums, int index, List<Integer> p){
if(index == nums.length){
result.add(new ArrayList<>(p));
return;
}
// for循环遍历数组获取能够取出的数字作为当前的排列数字（用过的不能再用了）
// 从这里可以直观的看出回溯和简单递归的区别，简单递归（或二叉树中）只有两种选择，通过if-else即可，这里回溯有多种选择，是一个多叉树，需要遍历尝试所有的可能
for(int i = 0; i < nums.length; i++){
if(!used[i]){
p.add(nums[i]);
used[i] = true;
getPermute(nums, index + 1, p);
p.remove(p.size() - 1);
used[i] = false;
}
}
}
public List<List<Integer>> permute(int[] nums) {
if(nums.length == 0)
return result;
used = new boolean[nums.length];
getPermute(nums, 0, new ArrayList<>());
return result;
}
}
5. 47 全排列II
- 方法：注意与上一题目的区别，这里的数字序列可能会有重复，而且要求返回的全排列中没有重复，还是基于上一题的思路解决，对去除重复的问题，考虑通过set去重。HashSet内部实现判断是否重复的规则是，首先计算hashcode是否一样，由于ArrayList重写了hashCode方法，其hashCode和内部值有关，因此内容一样的list hashCode一样，hashcode一样就会散列到数组的同一个位置，此时HashSet会再通过equals判断两个对象是否相等，而ArrayList重写了equals方法，内容相同的list会判断为相同的对象。因此可以通过HashSet去重。
class Solution {
private Set<List<Integer>> set = new HashSet<>();
private boolean[] isUsed;
private void findAllUniquePermute(int[] nums, int index, List<Integer> temp){
if(index == nums.length){
set.add(new ArrayList<Integer>(temp));
return;
}
for(int i = 0; i < nums.length; i++){
if(!isUsed[i]){
isUsed[i] = true;
temp.add(nums[i]);
findAllUniquePermute(nums, index + 1, temp);
temp.remove(temp.size() - 1);
isUsed[i] = false;
}
}
}
public List<List<Integer>> permuteUnique(int[] nums) {
if(nums.length == 0)
return new ArrayList<>();
isUsed = new boolean[nums.length];
List<List<Integer>> result = new ArrayList<>();
findAllUniquePermute(nums, 0, new ArrayList<>());
for(List x : set){
result.add(x);
}
return result;
}
}
- 方法二：不同过HashSet去重，毕竟这样效率太低，首先<mark>对数组排序</mark>，然后通过 boolean used数组判断，如果当前数字和前面的数字相等，则当前数字不能作为一个选择开辟树中一个分支因为会造成重复，通过这样去重。
class Solution {
private List<List<Integer>> result = new ArrayList<>();
private boolean[] used;
private void findAllUniquePermute(int[] nums, int index, List<Integer> temp){
if(index == nums.length){
result.add(new ArrayList<>(temp));
return;
}
for(int i = 0; i < nums.length; i++){
// 判断是否需要去重
if(used[i] || (i != 0 && used[i -1] && nums[i] == nums[i - 1]))
continue;
used[i] = true;
temp.add(nums[i]);
findAllUniquePermute(nums, index + 1, temp);
used[i] = false;
temp.remove(temp.size() - 1);
}
}
public List<List<Integer>> permuteUnique(int[] nums) {
if(nums.length == 0)
return result;
used = new boolean[nums.length];
Arrays.sort(nums);
findAllUniquePermute(nums, 0, new ArrayList<>());
return result;
}
}
回溯处理组合问题
6. 77 组合
- 方法： 回溯
class Solution {
// 私有变量保存结果
private List<List<Integer>> result = new ArrayList<>();
// 递归函数的参数n k 为目标范围和数字数量，start为当前树节点可以尝试的开始处（因为组合问题数字排列不同是认为同一种组合，去重复剪枝）
// temp为当前组合所得到的数字
private void findAllCombine(int n, int k, int start, List<Integer> temp){
if(temp.size() == k){
result.add(new ArrayList<>(temp));
return;
}
// 剪枝，当前temp中已有temp.size()个数，还需要k - temp.size()，当前最多能有[i, n] (n - i + 1)个数，则k - temp.size() < (n - i + 1)
// 即i <= n + 1 - (k - temp.size())，而不是i <= n，这样可以剪去一些尝试提升速度
for(int i = start; i <= n + 1 - (k - temp.size()); i++){
temp.add(i);
findAllCombine(n, k, i + 1, temp);
temp.remove(temp.size() - 1);
}
}
public List<List<Integer>> combine(int n, int k) {
if(n <= 0 || k == 0 || n < k)
return result;
findAllCombine(n, k, 1, new ArrayList<>());
return result;
}
}
7. 39 组合总和
- 方法：递归 回溯 剪枝
- 递归方法的含义：对于给定的数组candidates，寻找所有可能的和为target的组合，将其放入result中，curCombination参数为当前组合的所有数值，curSum为当前组合所有数值的和，start是当前组合的第一个数值在candidates中的位置
- 剪枝有两部分，由于给的数组中的值都是正整数，当前组合的和值已经大于target时，后面任意数组再加入当前组合都不会得到结果，因此直接return剪枝；设置start参数，从i开始的组合，会将其后的所有数值得所有可能组合都遍历到，因此从i+1开始的组合就不需要尝试i+1前面的数了。
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
allCombinationSum(candidates, target, new ArrayList<>(), 0, 0);
return result;
}
private List<List<Integer>> result = new ArrayList<>();
private void allCombinationSum(int[] candidates, int target, List<Integer> curCombination, int curSum, int start){
if(curSum > target){
return;
}
if(curSum == target){
result.add(new ArrayList<Integer>(curCombination));
return;
}
for(int i = start; i < candidates.length; i++){
curCombination.add(candidates[i]);
allCombinationSum(candidates, target, curCombination, curSum + candidates[i], i);
curCombination.remove(curCombination.size() - 1);
}
}
}
8. 40 组合总和II
- 方法：递归 回溯 剪枝，和上一道题目不同的是由于数组中有重复元素，且要求结果集中的组合不能有重复的，需要对组合进行去重，对数组排序，然后通过set去重
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
allCombinationSum2(candidates, target, new ArrayList<>(), 0, 0);
List<List<Integer>> result = new ArrayList<>();
for(List list : resultSet)
result.add(list);
return result;
}
private Set<List<Integer>> resultSet = new HashSet<>();
private void allCombinationSum2(int[] candidates, int target, List<Integer> curCombination, int curSum, int start){
if(curSum > target)
return;
if(curSum == target){
resultSet.add(new ArrayList<>(curCombination));
return;
}
for(int i = start; i < candidates.length; i++){
curCombination.add(candidates[i]);
allCombinationSum2(candidates, target, curCombination, curSum + candidates[i], i + 1);
curCombination.remove(curCombination.size() - 1);
}
}
}
9. 216 组合总和III
-
方法：递归 回溯 剪枝
class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
allCombinationSum3(k, n, new ArrayList<>(), 0, 0, 1);
return result;
}
List<List<Integer>> result = new ArrayList<>();
private void allCombinationSum3(int k, int n, List<Integer> curCombination, int curSum, int curNumbers, int start){
if(curSum > n)
return;
if(curNumbers == k){
if(curSum == n)
result.add(new ArrayList<>(curCombination));
return;
}
for(int i = start; i <= 9; i++){
curCombination.add(i);
allCombinationSum3(k, n, curCombination, curSum + i, curNumbers + 1, i + 1);
curCombination.remove(curCombination.size() - 1);
}
}
}
10. 78 子集
-
这其实就是一个组合问题，给了一个不包含重复数值的数组，得到其所有可能的组合
-
方法：递归 回溯，这是一个DFS的过程
class Solution {
public List<List<Integer>> subsets(int[] nums) {
result.add(new ArrayList<Integer>());
allSubsets(nums, 0, new ArrayList());
return result;
}
List<List<Integer>> result = new ArrayList<>();
private void allSubsets(int[] nums, int start, List<Integer> curSubsets){
if(start == nums.length)
return;
for(int i = start; i < nums.length; i++){
curSubsets.add(nums[i]);
result.add(new ArrayList<>(curSubsets));
allSubsets(nums, i + 1, curSubsets);
curSubsets.remove(curSubsets.size() - 1);
}
}
}
11. 90 子集II
- 方法：递归 回溯，相比较于上一题，数组中的元素可能是重复值，而且题目要求返回的子集不能有重复的，因此需要对得到的子集去重，比如 1 2 2 这个数组，1 可能和第一个2 组成 1 2，也可能和第二个2 组成 1 2，这样就是重复的，这里我们通过先对数组排序，然后通过set去重
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
allSubsets(nums, new ArrayList<>(), 0);
List<List<Integer>> result = new ArrayList<>();
result.add(new ArrayList<>());
for(List setResult : setResults)
result.add(setResult);
return result;
}
Set<List<Integer>> setResults = new HashSet<>();
private void allSubsets(int[] nums, List<Integer> curSubset, int start){
if(start == nums.length)
return;
for(int i = start; i < nums.length; i++){
curSubset.add(nums[i]);
setResults.add(new ArrayList<>(curSubset));
allSubsets(nums, curSubset, i + 1);
curSubset.remove(curSubset.size() - 1);
}
}
}
12. 401
- 方法：递归 回溯，这个题目虽然是一道简单的题目，但是题目的比较具象，需要对问题进行分析然后抽象成递归问题，找到隐藏的递归结构，是训练发现递归问题的一道不错的题目。
- 递归函数的含义：根据给定的参数，找出所有可能表示的时间，参数的含义是num表示还需要让几个灯亮，start表示当前需要点亮的灯从哪一个开始尝试，curTime记录当前点亮的灯所表示的时间。
- 不分开考虑小时和分钟灯的点亮，将其一块考虑，因为题目的意思本就是小时分钟共有num个灯亮，数组curTime长度为10表示小时分钟所有的灯，共有10个，数组从右到做分别为分钟的六个灯和小时的四个灯，从右到左，分钟和小时的灯分别为从低位到高位，具体可以表示为 8 4 2 1 32 16 8 4 2 1
class Solution {
public List<String> readBinaryWatch(int num) {
allPossibleTimes(num, 0, new int[10]);
return result;
}
private List<String> result = new ArrayList<>();
private void allPossibleTimes(int num, int start, int[] curTime){
if(num == 0){
int hour = curTime[0] * 8 + curTime[1] * 4 + curTime[2] * 2 + curTime[3] * 1;
int minimu = curTime[4] * 32 + curTime[5] * 16 + curTime[6] * 8 + curTime[7] * 4 + curTime[8] * 2 + curTime[9] * 1;
if(hour < 12 && minimu < 60){
StringBuilder sb = new StringBuilder();
sb.append(hour);
sb.append(":");
if(minimu < 10)
sb.append("0");
sb.append(minimu);
result.add(sb.toString());
}
return;
}
for(int i = start; i < 10; i++){
// 点亮当前位置的灯
curTime[i]++;
allPossibleTimes(num - 1, i + 1, curTime);
// 熄灭当前位置的灯进行回溯
curTime[i]--;
}
}
}
- 方法二：通过java中Integer.bitCount(num) 方法解决问题，该方***返回参数num二进制格式中为1的位数个数
class Solution {
public List<String> readBinaryWatch(int num) {
List<String> result = new ArrayList<>();
for(int i = 0; i < 12; i++){
for(int j = 0; j < 60; j++){
if(Integer.bitCount(i) + Integer.bitCount(j) == num){
StringBuilder sb = new StringBuilder();
sb.append(i);
sb.append(":");
if(j < 10)
sb.append("0");
sb.append(j);
result.add(sb.toString());
}
}
}
return result;
}
}
蚂蚁集团一面105人在聊
投递多益网络等公司10个岗位 >