public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> list = new ArrayList<>(); Arrays.sort(candidates); recursive(list, new ArrayList<>(), candidates, target, 0); return list; }
/** * * @param list * 总的输出 list * @param tempList * 存放的 list * @param nums * 数组 * @param remain * 剩余值 * @param index * 数组下标 */ private void recursive(List<List<Integer>> list, List<Integer> tempList, int[] nums, int remain, int index) {
if (remain < 0) // return 或者进行 add 操作后就开始执行弹出尾部元素 塞入下个元素 return; else if (remain == 0) list.add(new ArrayList<>(tempList)); // 这里需要注意不能直接 list.add(tempList),最终 tempList 所指向的对象是空的, // 所以需要 new 一个新对象，将值复制进去 else { for (int i = index; i < nums.length; i++) { tempList.add(nums[i]); // 挨个塞入 recursive(list, tempList, nums, remain - nums[i], i); // 由于元素可重复 所以是 i tempList.remove(tempList.size() - 1); // 挨个弹出 } } }
public List<List<Integer>> combinationSum2(int[] candidates, int target) { List<List<Integer>> list = new ArrayList<>(); Arrays.sort(candidates); recursive(list, new ArrayList<>(), candidates, target, 0); return list;
}
/** * DFS 添加每个满足条件的集合 * * @param list * 最终返回集合 * @param tempList * 每个满足条件的子集合 * @param candidates * 数组 * @param remain * 剩余值 * @param index * 数组下标 */ private void recursive(List<List<Integer>> list, List<Integer> tempList, int[] candidates, int remain, int index) { if (remain < 0) return; else if (remain == 0) list.add(new ArrayList<>(tempList)); else { for (int i = index; i < candidates.length; i++) { if (i > index && candidates[i] == candidates[i - 1]) // 说明两个值相等且之前一个值已经返回 continue; tempList.add(candidates[i]); recursive(list, tempList, candidates, remain - candidates[i], i + 1); // 规定数组中每个数字在每个组合中只能使用一次 tempList.remove(tempList.size() - 1); } } }
相比较上一题的代码，这次只是加了一个条件判断以及递归中元素下标加了一。
这里就要对数组先进行排序操作了，新增的条件判断也是为了优化代码执行速度。
Combination Sum III
再来看第三道变形，描述如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
总结一下：二分搜索只需要注意它的边界值，原先的数组下标范围是 [0..n-1]，当你用 lo = 0, hi = n-1 去运行时，对应条件满足情况下值的赋值应该是 lo = mid + 1, hi = mid - 1；而若是用 lo = -1, hi = n 去作为条件运行时，对应条件满足情况下值的赋值就应该为 lo = mid, hi = mid，因为它两个值都是作为边界值。[0, n]、[-1, n-1]也是如此。
public static String toString(int i, int radix) { if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX) radix = 10;
/* Use the faster version */ if (radix == 10) { return toString(i); } // int 32位 char buf[] = new char[33]; boolean negative = (i < 0); int charPos = 32;
if (!negative) { i = -i; } // 根据进制取余转换 while (i <= -radix) { buf[charPos--] = digits[-(i % radix)]; i = i / radix; } buf[charPos] = digits[-i];
if (negative) { buf[--charPos] = '-'; }
return new String(buf, charPos, (33 - charPos)); }
不过该方法需注意：If the first argument is negative, the first element of the result is the ASCII minus character '-' ('\u005Cu002D'). If the first argument is not negative, no sign character appears in the result. 例如：
public static Integer decode(String nm) throws NumberFormatException { int radix = 10; int index = 0; boolean negative = false; Integer result;
if (nm.length() == 0) throw new NumberFormatException("Zero length string"); char firstChar = nm.charAt(0); // Handle sign, if present if (firstChar == '-') { negative = true; index++; } else if (firstChar == '+') index++;
// Handle radix specifier, if present if (nm.startsWith("0x", index) || nm.startsWith("0X", index)) { index += 2; radix = 16; } else if (nm.startsWith("#", index)) { index ++; radix = 16; } else if (nm.startsWith("0", index) && nm.length() > 1 + index) { // 0 后面长度要大于 1 index ++; radix = 8; }
if (nm.startsWith("-", index) || nm.startsWith("+", index)) throw new NumberFormatException("Sign character in wrong position");
try { result = Integer.valueOf(nm.substring(index), radix); result = negative ? Integer.valueOf(-result.intValue()) : result; } catch (NumberFormatException e) { // If number is Integer.MIN_VALUE, we'll end up here. The next line // handles this case, and causes any genuine format error to be // rethrown. String constant = negative ? ("-" + nm.substring(index)) : nm.substring(index); result = Integer.valueOf(constant, radix); } return result; }
int n = 5;// 5件物品,物品编号为a,b,c,d,e（下面为多加一件物品，第一个物品为虚拟的物品） int weight[] = { 0, 4, 5, 6, 2, 2 };// 物品的重量 int value[] = { 0, 6, 4, 5, 3, 6 }; // 对应物品的价值 int c = 10; // 背包容量 int state[] = { 0, 0, 0, 0, 0, 0 };// 开始状态 char name[] = { ' ', 'a', 'b', 'c', 'd', 'e' }; int maxValue = getMaxValue(n, weight, value, state, c); System.out.println("最大价值为 = " + maxValue); System.out.print("放入的物品为 ："); for (int i = 1; i <= 5; i++) { if (state[i] == 1) { System.out.print(name[i] + " "); } }
// System.out.println(); }
/** * * @param n * 物品数量 * @param weight * 物品对应重量（数组下标从0开始，故第一个物品为虚拟物品） * @param value * 物品对应价值（数组下标从0开始，故第一个物品为虚拟物品） * @param state * 物品的开始状态 * @param c * 背包的容量 * @return */ public static int getMaxValue(int n, int weight[], int value[], int state[], int c) { // n 为物品的数量，数组时需要加 1，此时可以从 0,1,...n 个物品，共 n+1 个商品，其中第 0 个为虚构物品 // 对于物品的价值，可以写成 2 维数组 int m[][] = new int[n + 1][c + 1]; // n 为 0,1,2...(n-1),背包重量为 0,1,2...C int i, j;
for (i = 0; i <= n; i++) { m[i][0] = 0; } for (j = 0; j <= c; j++) { m[0][j] = 0; }
居住于 A 城的伯父，沉沦于二十年右派生涯，早妻离子散，平反后已垂垂暮老，多回忆早年英武及故友。我以他大学的一位女生名义去信慰藉，不想他立即复信，只好信来信往，谈当年的友情，谈数十年的思念，谈现在鳏寡人的处境，及至发展到黄昏恋。我半月一封，连续四年不断，且信中一再说要去见他，每次日期将至又以患病推延。伯父终老弱病倒，我去看他，临咽气说：“我等不及她来了。她来了，你把这个箱子交她。”又说一句：“我总没白活。”安详瞑目。掩埋了伯父，打开箱子，竟是我写给他的近百封信，得意为他在爱的幸福中度过晚年，不禁乐而开笑。
