combination-sum-ii（熟悉下Java排序）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了combination-sum-ii（熟悉下Java排序），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2645字，纯文字阅读大概需要4分钟。
内容图文
代码还是这一块代码，但是还是写的很慢。。
其中用到了Java对 List的排序。查了很久，发现使用 Collections.sort 很方便。
另外对结果的去重，使用了 Java的HashSet.
https://leetcode.com/problems/combination-sum-ii/
package
com.company;
import java.util.*;
class Solution {
Map<String, Set<List<Integer>>> mp;
int[] nums;
Set<List<Integer>> impl(int start, int target) {
String key = "" + start + "_" + target;
if (mp.containsKey(key)) {
return mp.get(key);
}
Set<List<Integer>> ret;
if (start < nums.length) {
ret = new HashSet<>();
ret.addAll(impl(start+1, target));
}
else {
ret = new HashSet<>();
}
if (start > 0) {
if (target == nums[start - 1]) {
List<Integer> item = new ArrayList<>();
item.add(nums[start - 1]);
//print(item, 1); ret.add(item);
}
elseif (start < nums.length && target > nums[start - 1]) {
Set<List<Integer>> tmpRet = impl(start + 1, target - nums[start - 1]);
Iterator<List<Integer>> iter = tmpRet.iterator();
while (iter.hasNext()) {
List<Integer> item = new ArrayList<>(iter.next());
//print(item, 2);
item.add(nums[start - 1]);
Collections.sort(item);
//print(item, 3);
//System.out.println("Start " + start + " target " + target); ret.add(item);
}
}
}
/*System.out.println("Begin ret:" + key);
Iterator<List<Integer>> iter = ret.iterator();
while (iter.hasNext()) {
print(iter.next(), 4);
}
System.out.println("End ret:" + key);*/
mp.put(key, ret);
return ret;
}
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
nums = candidates;
mp = new HashMap<>();
List<List<Integer>> ret = new ArrayList<>();
if (candidates.length == 0) {
return ret;
}
impl(0, target);
String key = "" + 0 + "_" + target;
ret = new ArrayList<>(mp.get(key));
return ret;
}
void print(List<Integer> item, int flag) {
System.out.printf("Here %d:", flag);
Iterator iter = item.iterator();
while (iter.hasNext()) {
System.out.printf("%d,", iter.next());
}
System.out.println();
}
}
publicclass Main {
publicstaticvoid main(String[] args) {
System.out.println("Hello!");
Solution solution = new Solution();
int[] cand = {10,1,2,7,6,1,5};
int target = 8;
List<List<Integer>> ret = solution.combinationSum2(cand, 8);
System.out.printf("Get ret: %s\n", ret.size());
Iterator<List<Integer>> iterator = ret.iterator();
while (iterator.hasNext()) {
Iterator iter = iterator.next().iterator();
while (iter.hasNext()) {
System.out.printf("%d,", iter.next());
}
System.out.println();
}
System.out.println();
}
}
原文：http://www.cnblogs.com/charlesblc/p/6001320.html
内容总结
以上是互联网集市为您收集整理的combination-sum-ii（熟悉下Java排序）全部内容，希望文章能够帮你解决combination-sum-ii（熟悉下Java排序）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。