代码随想录算法训练营Day22|77、组合216、组合综合17、电话号码的字母组合
77、组合回溯三部曲：1、确定函数头 2、确定停止条件 3、确定单层逻辑（for循环横向遍历，遍历的时候把递归看成一个黑盒）
for循环控制的是当前层的逐个元素遍历，递归层的i+1控制的是下一层从这个元素的下一个开始取，如果可以取重复元素的话，下一层依旧从i开始就可以。但是一定不能再取到i-1或更前面的元素了，由于在取i-1的时候就已经把含有i-1的所有环境（包括可以重复和不可以重复的环境）都取过了。
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new LinkedList<>();
public List<List<Integer>> combine(int n, int k) {
backingTrace(n,k,1);
return res;
}
public void backingTrace(int n, int k, int startIndex){
if(path.size() == k){
res.add(new ArrayList<>(path));
return;
}
for(int i = startIndex; i <=n; i++){
path.add(i);
backingTrace(n, k, i + 1);
path.removeLast();
}
}
} 216、组合总和
思绪和上一题差不多，注意sum如果已经大于目标值，没须要再组合下去了，我们组合出来的和都是递增的。
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
backingTrace(k,n,1, 0);
return res;
}
private void backingTrace(int k, int n, int startIndex,int sum){
if(sum > n){
return;
}
if(path.size() == k){
if(sum == n){
res.add(new ArrayList<>(path));
}
return;
}
for(int i = startIndex; i <=9 ; i++){
path.add(i);
backingTrace(k,n,i + 1,sum +i);
path.removeLast();
}
}
} 17、电话号码的字母组合
积累下StringBuilder的几个方法，添加元素append，删除元素deleteCharAt（index）
class Solution {
String[] numbers = {
"",
"",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz"
};
List<String> res = new ArrayList<>();
StringBuilder sb = new StringBuilder();
public List<String> letterCombinations(String digits) {
if(digits == null || digits.length() == 0) return res;
int[] digitsArr = new int;
for(int i = 0; i < digitsArr.length; i++){
int temp = digits.charAt(i) - '0';
digitsArr = temp;
System.out.println(temp);
}
backingTrace(digitsArr,0);
return res;
}
private void backingTrace(int[] digits,int index){
if(index == digits.length){
res.add(sb.toString());
return;
}
//电话号码的第index位
int inNum = digits;
for(int i = 0; i < numbers.length(); i++)
{
charcur = numbers.charAt(i);
sb.append(cur);
backingTrace(digits,index + 1);
sb.deleteCharAt(sb.length() - 1);
}
}
}
//二刷
class Solution {
String[] numbers = {
"",
"",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz"
};
List<String> res = new ArrayList<>();
StringBuilder sb = new StringBuilder();
public List<String> letterCombinations(String digits) {
int n = digits.length();
if(n == 0) return res;
int[] nums = new int;
for(int i = 0; i < digits.length();i++){
nums = (int)(digits.charAt(i) -'0');
System.out.println(nums);
}
backingTrace(n,nums);
return res;
}
private void backingTrace(int n, int[] nums){
if(sb.length() == n){
res.add(new String(sb));
return;
}
//当前遍历到电话号码的位置索引
int location = sb.length();
//当前遍历到的电话号码数字
int locationNum = nums;
//遍历数字按键对应的3-4个字母
for(int i = 0; i < numbers.length(); i++){
//添加字母
sb.append(numbers.charAt(i));
backingTrace(n,nums);
sb.deleteCharAt(sb.length() - 1);
}
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]