- 浏览: 130818 次
文章分类
- 全部博客 (189)
- Tree (14)
- Dynamic Programming (34)
- Array (20)
- Search (1)
- Hash (12)
- Backtracking (22)
- Divide and Conque (8)
- Greedy (6)
- Stack (12)
- software (0)
- List (7)
- Math (22)
- Two pointers (16)
- String (20)
- Linux (1)
- Sliding Window (4)
- Finite State Machine (1)
- Breadth-first Search (7)
- Graph (4)
- DFS (6)
- BFS (3)
- Sort (9)
- 基础概念 (2)
- 沟通表达 (0)
- Heap (2)
- Binary Search (15)
- 小结 (1)
- Bit Manipulation (8)
- Union Find (4)
- Topological Sort (1)
- PriorityQueue (1)
- Design Pattern (1)
- Design (1)
- Iterator (1)
- Queue (1)
最新评论
-
likesky3:
看了数据结构书得知并不是迭代和递归的区别,yb君的写法的效果是 ...
Leetcode - Graph Valid Tree -
likesky3:
迭代和递归的区别吧~
Leetcode - Graph Valid Tree -
qb_2008:
还有一种find写法:int find(int p) { i ...
Leetcode - Graph Valid Tree -
qb_2008:
要看懂这些技巧的代码确实比较困难。我是这么看懂的:1. 明白这 ...
Leetcode - Single Num II -
qb_2008:
public int singleNumber2(int[] ...
Leetcode - Single Num II
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]
[分析] 每个元素可以使用任意多次,求解时就为每个元素枚举使用一次、两次直到其最大次数的情况,下面给出两者递归实现方式,recur1代码简洁些,而recur2效率稍高些,因为减少了递归调用次数,可手动模拟下[1,2],target=3的求解过程就能体会。此题最需注意的是for循环体前面的if判断,作用是避免重复结果,在我做时leetcode 是漏掉了这类test case,我有bug的code成了漏网之鱼~ 看到Code Ganker的解析后意识到了,考虑[1,1],1 这个case帮助理解。
The same repeated number may be chosen from C unlimited number of times.
Note:
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]
[分析] 每个元素可以使用任意多次,求解时就为每个元素枚举使用一次、两次直到其最大次数的情况,下面给出两者递归实现方式,recur1代码简洁些,而recur2效率稍高些,因为减少了递归调用次数,可手动模拟下[1,2],target=3的求解过程就能体会。此题最需注意的是for循环体前面的if判断,作用是避免重复结果,在我做时leetcode 是漏掉了这类test case,我有bug的code成了漏网之鱼~ 看到Code Ganker的解析后意识到了,考虑[1,1],1 这个case帮助理解。
public class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> result = new ArrayList<List<Integer>>(); if (candidates == null) return result; Arrays.sort(candidates); recur1(candidates, target, 0, new ArrayList<Integer>(), result); return result; } public void recur1(int[] candidates, int target, int start, ArrayList<Integer> oneAns, List<List<Integer>> result) { if (target <= 0) { if (target == 0) result.add((ArrayList<Integer>)oneAns.clone()); return; } for (int i = start; i < candidates.length && candidates[i] <= target; i++) { if (i > 0 && candidates[i] == candidates[i - 1]) continue; oneAns.add(candidates[i]); recur(candidates, target - candidates[i], i, oneAns, result); oneAns.remove(oneAns.size() - 1); } } public void recur2(int[] candidates, int target, int start, ArrayList<Integer> oneAns, List<List<Integer>> result) { if (target <= 0) { if (target == 0) result.add((ArrayList<Integer>)oneAns.clone()); return; } for (int i = start; i < candidates.length && candidates[i] <= target; i++) { if (i > 0 && candidates[i] == candidates[i - 1]) continue; int maxTimes = target / candidates[i]; for (int j = 1; j <= maxTimes; j++) { oneAns.add(candidates[i]); recur(candidates, target - j * candidates[i], i + 1, oneAns, result); } for (int j = 1; j <= maxTimes; j++) oneAns.remove(oneAns.size() - 1); } } }
发表评论
-
Leetcode - Palindrome Permutation II
2015-08-28 21:17 2187Given a string s, return all th ... -
Leetcode - Factor Combination
2015-08-28 09:53 824Numbers can be regarded as prod ... -
Leetcode - Generate Parentheses
2015-08-08 17:01 487[分析] 第一个思路(错误的~):假设递归函数返回 n - ... -
Leetcode - Word Search II
2015-08-03 21:25 940iven a 2D board and a list of w ... -
Leetcode - Word Search
2015-08-03 21:03 481Given a 2D board and a word, fi ... -
Leetcode - Subset
2015-08-02 12:06 918[分析] 三种思路 思路1:每层递归新加一个元素,第一层递归, ... -
Leetcode - Subset II
2015-08-02 12:13 924[分析] 延续Subset三种思路,关键是添加去重处理 思路 ... -
Leetcode - Gray Code
2015-08-01 17:26 548原题链接:https://leetcode.com/probl ... -
Leetcode - Permutation Sequence
2015-08-01 17:19 484原题链接:https://leetcode.com/probl ... -
Leetcode - Permutation II
2015-08-01 10:49 571原题链接:https://leetcode.com/probl ... -
Leetcode - Combination
2015-08-01 08:36 462[分析] 从 n 个数中取 k 个数,第一个数有 n 种取法… ... -
Leetcode - Combination Sum III
2015-07-31 22:04 501[分析] 思路就是枚举k个数所有可能的组合并判断是否符合条件。 ... -
Leetcode - Combination Sum II
2015-07-31 21:06 579[分析] 输入数组中的每个元素至多使用一次,相较于Combin ... -
Leetcode - Sudoku Solver
2015-07-31 09:14 436[分析] 做Valid Sudoku时表示3*3区块的下标想得 ... -
Leetcode - N Queues II
2015-07-30 20:52 379[分析] 做完N皇后第一题,这个就so easy~ pu ... -
Leetcode - N-Queens
2015-07-30 20:38 409[分析] N皇后摆放规则:两个皇后不能共存于同一行、同一列以及 ... -
Leetcode - Word Ladder II
2015-06-26 09:19 503Given two words (start and end) ... -
Leetcode - Combination Sum III
2015-06-10 10:09 513Find all possible combinati ... -
Leetcode - Palindrome Partition
2015-05-21 09:56 749Given a string s, partition s s ... -
Leetcode - WordBreak III
2015-04-16 08:30 426Given a string s and a dictio ...
相关推荐
combination sum: 39, 40, 216 - palindrome partitioning - regex - sudoku solver: 37 排序 - merge sort - quick sort - insertion sort - selection sort - counting sort 位操作 - find the only element which...
leetcode怎么销号 LeetCode-Solutions :green_heart:My own LeetCode solutions No. Problem LeetCode 力扣 Python Go Solution Difficulty Tag 0017 Letter Combinations of a Phone Number Medium 回溯、暴力 0034...
leetcode怎么计算空间复杂度是指 LeetCode-Solution my first solution of LeetCode 2015-5-7 Problem 95,98(80 already!) 我经常在递归的结束地方忘记return!!! 题型一:经典暴力递归:(里面涉及到重复不重复的...
第 296 章PY 和 GO 中的 Leetcode 我在 Python Golang ...Leetcode ...40:combination-sum-ii:传递最后选择的索引 41:先缺失正,交换 42:只是提醒:块 - 垃圾箱 43:多字符串,i+j,i+j+1 44:通配符
Leetcode\combination sum(39).swift Leetcode\count number of team(1395).swift Leetcode\counting bits(338).swift Leetcode \find 数组中的所有重复项(442).swift Leetcode\find peak element(162).swift ...
leetcode打不开Leetcode Note Tips Tip1: Two pointer for sorted array (#Array 1. Two Sum) Tip2: Sum[i:j] = Sum[0:j] - Sum[0:i] for continuous array (# Array 560. Subarray Sum Equals K) Tip3: Knapsack ...
Combination Sum Description 给一组candidates (list of int)和target (int),求使用candidates内数字组合,让总和等于target的所有组合。 candidates内的数字皆不同 candidates内的数字可以重复使用无限次 ...
leetcode题库 Little Algorithm 从 2020 年初开始,我在公众号《面向大象编程》上发表面试算法、LeetCode 题解相关文章,至今收获不少好评。此仓库是公众号内容的补充,包括公众号文章涉及到的题目的参考代码,以及 ...
leetcode 530 力码 全部的: 易(173/237+x) 中(144/437+x) 硬(4/x) 问题 1.Two Sum(dict) 7.(跳过)(数学) 9.(跳过)(串串技巧) 11.盛水最多的容器 12.(跳过)(问题不好) 13.(跳过)(蛮力) 14.(跳过)...
leetcode 2 和 c Leetcode_imp_C Leetcode 在 C 上的实现 大批: leetcode_0001_two_sum.c leetcode_0011_max_area.c leetcode_0015_three_sum.c ...leetcode_0039_combination_sum.c 40 leetcode_0041_first_miss
leetcode 2 Useful Links ...Sum], [17 Phone Num] [] BFS [] [] [] DP , [53 max subarray], , [96 DP | BST], , [] [] Binary Search , , [74 2D matrix] [] Slicing Window / Two Pointers [918 Ma
combinationSum ( self , candidates , target ): def backtrack ( tmp , start , end , target ): if target == 0 : ans . append ( tmp [:]) elif target > 0 : for i in range ( start , end ): tmp . append ( ...
leetcode Java 246 題目及解答 (英文) Contents 1 Rotate Array in Java 15 2 Reverse Words in a String II 19 3 Evaluate Reverse Polish Notation 21 4 Isomorphic Strings 25 5 Word Ladder 27 6 Word Ladder ...
CombinationSum 组合之和 完成 LinkedList 题目 说明 状态 AddTwoNumber 两数相加 完成 SwapPairs 两两交换链表中的节点 完成 String 题目 说明 状态 LongestSubstring 最长子串 完成 LongestPalindrome 最长回文...
Combination Sum III Generate Parentheses Sudoku Solver Word Search 总结 分治法 Pow(x,n) Sqrt(x) 贪心法 Jump Game Jump Game II Best Time to Buy and Sell Stock Best Time to Buy and Sell Stock II Longest...
def combinationSum(self, candidates, target): """ :type candidates: List[int] :type target: int :rtype: List[List[int]] """ result,temp = [],[] self.combinationSumRecu(sorted(candidates),...