有没有免费开网站的,电子商务网站建设讨论,建站快车管理,营销型企业网站的建设方案216. 组合总和 III
中等 找出所有相加之和为 n 的 k 个数的组合#xff0c;且满足下列条件#xff1a;
只使用数字1到9 每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次#xff0c;组合可以以任何顺序返回。
class Solution {List且满足下列条件
只使用数字1到9 每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次组合可以以任何顺序返回。
class Solution {ListListInteger res new ArrayList();ListInteger path new ArrayList();int sum 0;public ListListInteger combinationSum3(int k, int n) {traversal(k, n, 1);return res;}public void traversal(int k, int n, int start) {if (path.size() k sum n) {res.add(new ArrayList(path));return;}if (sum n || path.size() k) return;for (int i start; i 9 - (k - path.size()) 1; i) {path.add(i);sum i;traversal(k, n, i 1);path.removeLast();sum - i;}}
}下面这个我没懂为何可以改为 if (path.size() k) return;
// 上面剪枝 i 9 - (k - path.size()) 1; 如果还是不清楚
// 也可以改为 if (path.size() k) return; 执行效率上是一样的
class Solution {LinkedListInteger path new LinkedList();ListListInteger ans new ArrayList();public ListListInteger combinationSum3(int k, int n) {build(k, n, 1, 0);return ans;}private void build(int k, int n, int startIndex, int sum) {if (sum n) return;if (path.size() k) return;if (sum n path.size() k) {ans.add(new ArrayList(path));return;}for(int i startIndex; i 9; i) {path.add(i);sum i;build(k, n, i 1, sum);sum - i;path.removeLast();}}
}17. 电话号码的字母组合
中等 给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。
难点我觉得这个题思路不难就是具体的语法操作不会
难点每个for循环都是一个在某个集合里挑选的过程这一类问题。其实。关键的点是在确定每一次循环的时候要挑选的元素的集合然后依次从这样一个集合里面挑出来进行排列或者组合 class Solution {// 每个数字到字母的映射String[] mapping new String[] {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};ListString res new ArrayList(); //设置全局列表存储最后的结果StringBuilder sb new StringBuilder(); //每次迭代获取一个字符串所以会设计大量的字符串拼接所以这里选择更为高效的 StringBuildpublic ListString letterCombinations(String digits) {// 数字字符串为空直接返回空结果if (digits null || digits.length() 0) return res;backTrack(digits, 0);return res;}public void backTrack(String digits, int digitIndex) { //digitIndex代表在字符串digits中的第几个数用来确定在哪个集合中挑选元素if (digitIndex digits.length()) { // 这里不是digits.length()-1res.add(sb.toString());return;}int num digits.charAt(digitIndex) - 0; // 得到这个数字String str mapping[num]; // 得到这个数字与字母的映射集合for (int i 0; i str.length(); i) {sb.append(str.charAt(i)); // 添加backTrack(digits, digitIndex 1);sb.deleteCharAt(sb.length() - 1); // 删掉刚添加的}}
}
