LeetCode:Combination Sum II

发布时间:2016-12-9 0:14:56 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"LeetCode:Combination Sum II",主要涉及到LeetCode:Combination Sum II方面的内容,对于LeetCode:Combination Sum II感兴趣的同学可以参考一下。

这题跟Combination Sum差不多,区别是: 数组中的数字可以重复 每个出现在数组中数字在一个答案中只能使用一次。 我把给的数组对重复的数字进行了合并,并把数字可使用次数设置为重复次数,此题就转化成了Combination Sum。 我看了LeetCode上的讨论,这种类型的题目有个专有词:Combination Sum。使用递归实现代码非常简洁,有时间我重写一下。 package leetcode; import java.io.IOException; import java.util.ArrayList; import java.util.Arrays; public class CombinationSumII { public static void main(String[] args) throws IOException { int[] c = new int[7]; c[0] = 10; c[1] = 1; c[2] = 2; c[3] = 7; c[4] = 6; c[5] = 1; c[6] = 5; CombinationSumII s = new CombinationSumII(); ArrayList<ArrayList<Integer>> t = s.combinationSum2(c, 8); System.out.println(t); } private int[] candidates; private int[] maxPos; public ArrayList<ArrayList<Integer>> combinationSum2(int[] c, int target) { ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); if (c.length == 0) { return result; } this.buildCandidates(c); Arrays.sort(this.candidates); int[] pos = new int[this.candidates.length + 1]; Arrays.fill(pos, -1); int[] sum = new int[this.candidates.length + 2]; Arrays.fill(sum, 0); int index = 0; while (index >= 0) { pos[index]++; int p = pos[index]; if (index == 1) { //System.out.println(pos[0] + "-" + pos[1]); } if (p > this.maxPos[index]) { index--; } else { pos[index + 1] = -1; int a = this.candidates[index]; sum[index + 1] = sum[index] + p * a; if (sum[index + 1] == target) { ArrayList<Integer> list = new ArrayList<Integer>(); for (int i = 0; i <= index; i++) { if (pos[i] <= this.maxPos[i]) { for (int j = 0; j < pos[i]; j++) { list.add(this.candidates[i]); } } } result.add(list); } else if (sum[index + 1] > target) { index--; } else { if (index != this.candidates.length - 1) { index++; } } } } return result; } void buildCandidates(int[] c) { Arrays.sort(c); int distinctCount = 0; int pre = -1; for (int a : c) { if (a != pre) { distinctCount++; } pre = a; } this.candidates = new int[distinctCount]; this.maxPos = new int[distinctCount]; int index = 0; pre = -1; int count = 1; for (int a : c) { if (a != pre) { candidates[index] = a; if (index > 0) { maxPos[index - 1] = count; } count = 1; index++; } else { count++; } pre = a; } maxPos[distinctCount - 1] = count; //print(candidates); //print(maxPos); } void print(int[] a) { for (int c : a) { System.out.print(c + "-"); } System.out.println(); } }

上一篇:新浪微博,请让信息在关系链中流动
下一篇:Android系统启动过程简介(下)

相关文章

相关评论