一、216.组合总和III
题目链接：
学习前：
思路：
- 返回类型和参数：
void fun(int n, int k, int start)
- 终止条件：
int len = list.size();
if(len==k){
if(n==0 ){
List<Integer> temp = new ArrayList<>();
for (int i = 0; i < len; i++) temp.add(list.get(i));
res.add(temp);
}
return;
}
- 单次遍历内容
for (int i = start; i <= 9; i++) {
list.add(i);
n-=i;
fun(n,k,i+1);
n+=i;
list.remove(len);
}
进一步优化：
首先修改单次遍历中i的范围：
for (int i = start; i <= 10-k+len; i++) {
if(n-i<0) return;
if(n-i>0 && len==k-1) continue;
list.add(i);
n-=i;
fun(n,k,i+1);
n+=i;
list.remove(len);
}
故而终止条件修改为：
int len = list.size();
if(len==k){
List<Integer> temp = new ArrayList<>();
for (int i = 0; i < len; i++) temp.add(list.get(i));
res.add(temp);
return;
}
学习后：
加深理解
二、17.电话号码的字母组合
题目链接：
学习前：
思路：
- 定义成员变量：res存放结果集，list存放单个结果
private List<String> res;
private List<Character> list;
- 返回类型和参数：
void fun(String digits, int index)
- 终止条件：当输入字符串遍历完成后结束
int len = list.size();
if (index == digits.length()) {
StringBuffer sb = new StringBuffer();
for (char c : list) sb.append(c);
res.add(sb.toString());
return;
}
- 单次遍历内容：start表示当前数字对应的第一个字符，len表示当前数字对应的字符的个数
int cur = digits.charAt(index)-'0';
int start=(cur-2)*3;
int len=3;
if(cur==8 || cur==9) start++;
if(cur==7 || cur==9) len++;
for (int i = 97+start; i <97+start+len; i++) {
list.add((char)i);
fun(digits,index+1);
list.remove(list.size()-1);
}
学习后：
进一步优化：
首先用数组存放数字对应的字符集合
String[] numLetters={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
定义的成员变量：res存放结果集，per存放单个字符串
private List<String> res;
private StringBuffer per;
故而终止条件修改为：
if (index == digits.length()) {
res.add(per.toString());
return;
}
单次遍历内容修改为：
String s= numLetters[digits.charAt(index)-'0'];
for (int i = 0; i <s.length(); i++) {
per.append(s.charAt(i));
fun(digits,index+1,numLetters);
per.deleteCharAt(per.length()-1);
}
三、学习总结
- 时间：2h
- 继续了解回溯