组合总和III
link：216. 组合总和 III - 力扣（LeetCode）
思路分析
既然是要比对，那自然需要和目标值比对的sum，同时要记录path.
这么一想其实和我们之前分析的组合问题就非常相似了.
注意一下题目中给定的判定逻辑限制（数字1-9且不能重复）很完美的组合问题.
天生的回溯搭子.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution {
List<Integer> path = new LinkedList<>();
List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
backtracking(n,k,1,0);
return result;
}
public void backtracking(int targetSum, int k, int startIndex, int sum)
{
if(sum>targetSum)
{
return;
}
if(path.size() == k)
{
if(targetSum == sum)
{
result.add(new ArrayList(path));
return;
}
}
for(int i = startIndex;i<=9-(k-path.size())+1;i++)
{
path.add(i);
sum+=i;
backtracking(targetSum,k,i+1,sum);
path.remove(path.size()-1);
sum-=i;
}
}
}
|
电话号码数字组合
link：17. 电话号码的字母组合 - 力扣（LeetCode）
思路分析
首先明确，当对字符串进行修改的时候需要使用StringBuffer和StringBuilder类.
和String类不同的是上述两者的对象能够多次被修改且不产生新的对象.
StringBuilder 相较于 StringBuffer 有速度优势，所以多数情况下建议使用 StringBuilder 类.（虽然StringBuilder线程不安全）
题目给的是电话号码，数字和字母要对应上，那么自然想到使用Map进行映射存储.
特殊的0和1（好奇妙的二进制原来电话也是有设计的！bushi 发上癫了）我们置为空即可.
那么此时关键点已经变成了如何在此题中找到我们之前使用的”n”和”k”.
按上图分析我们需要的深度就是传入参数的长度，广度就是固定好的字符个数（也就是3）这俩必要参数确定好之后再来一个记录当前遍历位置的指针即可.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
List<String> res = new ArrayList<>();
public List<String> letterCombinations(String digits) {
if(digits == null || digits.length() == 0) {
return res;
}
String[] numStr = {"","","abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
backtracking(digits,numStr,0);
return res;
}
StringBuilder tmp = new StringBuilder();
public void backtracking(String digits,String[] numStr,int num) {
if(num == digits.length()) {
res.add(tmp.toString());
return;
}
String str = numStr[digits.charAt(num) - '0'];
for(int i = 0; i < str.length(); i++) {
tmp.append(str.charAt(i));
backtracking(digits, numStr, num + 1);
tmp.deleteCharAt(tmp.length() - 1);
}
}
}
|
Tips
- res.add(sb.toString());` 用于将当前构建的字母组合添加到结果列表中。
tmp.append(str.charAt(i)); 用于将当前字符添加到 tmp 中，以构建当前的字母组合。String str = numString[digits.charAt(num) - '0']; 用于将输入字符串中的字符转换为对应的数字，并获取该数字对应的字母字符串。
