- 浏览: 130121 次
文章分类
- 全部博客 (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
[分析]
第一个思路(错误的~):假设递归函数返回 n - 1对括号组成的所有合法字符串,将其看做整体A,则 所求 n 对括号组成的合法字符串是所有()A,A(),(A)。这个思路对于n<=3是可行的,一旦 n > 4,就会漏解,比如对于 n=4, 会漏掉(())(())
第二个思路:递归构造出合法字符串,初始时拥有 n 个左右括号,递归的每一层根据当前资源情况添加一个左括号或者右括号后继续递归,递归结束条件是 n 个左右括号正好使用完。
对于每次递归,仅当剩余左括号数 < 剩余右括号数时本次可添加右括号,否则已构成的字符串中没有左括号可与新加上右括号匹配。
这是一个经典的卡特兰数问题,可参考wikipedia:
https://zh.wikipedia.org/wiki/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0
第一个思路(错误的~):假设递归函数返回 n - 1对括号组成的所有合法字符串,将其看做整体A,则 所求 n 对括号组成的合法字符串是所有()A,A(),(A)。这个思路对于n<=3是可行的,一旦 n > 4,就会漏解,比如对于 n=4, 会漏掉(())(())
第二个思路:递归构造出合法字符串,初始时拥有 n 个左右括号,递归的每一层根据当前资源情况添加一个左括号或者右括号后继续递归,递归结束条件是 n 个左右括号正好使用完。
对于每次递归,仅当剩余左括号数 < 剩余右括号数时本次可添加右括号,否则已构成的字符串中没有左括号可与新加上右括号匹配。
这是一个经典的卡特兰数问题,可参考wikipedia:
https://zh.wikipedia.org/wiki/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0
public class Solution { // Method 2 List<String> result = new ArrayList<String>(); public List<String> generateParenthesis1(int n) { result.clear(); recur(n, n, new StringBuilder()); return result; } public void recur(int left, int right, StringBuilder item) { if (left == 0 && right == 0) { result.add(item.toString()); return; } if (left < right) { item.append(')'); recur(left, right - 1, item); item.deleteCharAt(item.length() - 1); } if (left > 0) { item.append('('); recur(left - 1, right, item); item.deleteCharAt(item.length() - 1); } } // Method 1: Fail @ n ==4, miss "(())(())" public Set<String> recur(int n) { Set<String> result = new HashSet<String>(); if (n == 1) { result.add("()"); return result; } Set<String> sub = recur(n - 1); for (String str : sub) { result.add("(" + str + ")"); result.add("()" + str); result.add(str + "()"); } return result; } }
发表评论
-
Leetcode - Palindrome Permutation II
2015-08-28 21:17 2183Given a string s, return all th ... -
Leetcode - Factor Combination
2015-08-28 09:53 818Numbers can be regarded as prod ... -
Leetcode - Word Search II
2015-08-03 21:25 933iven a 2D board and a list of w ... -
Leetcode - Word Search
2015-08-03 21:03 478Given a 2D board and a word, fi ... -
Leetcode - Subset
2015-08-02 12:06 912[分析] 三种思路 思路1:每层递归新加一个元素,第一层递归, ... -
Leetcode - Subset II
2015-08-02 12:13 919[分析] 延续Subset三种思路,关键是添加去重处理 思路 ... -
Leetcode - Gray Code
2015-08-01 17:26 544原题链接:https://leetcode.com/probl ... -
Leetcode - Permutation Sequence
2015-08-01 17:19 477原题链接:https://leetcode.com/probl ... -
Leetcode - Permutation II
2015-08-01 10:49 567原题链接:https://leetcode.com/probl ... -
Leetcode - Combination
2015-08-01 08:36 454[分析] 从 n 个数中取 k 个数,第一个数有 n 种取法… ... -
Leetcode - Combination Sum III
2015-07-31 22:04 496[分析] 思路就是枚举k个数所有可能的组合并判断是否符合条件。 ... -
Leetcode - Combination Sum II
2015-07-31 21:06 572[分析] 输入数组中的每个元素至多使用一次,相较于Combin ... -
Leetcode - Combination Sum
2015-07-31 20:21 553Given a set of candidate number ... -
Leetcode - Sudoku Solver
2015-07-31 09:14 432[分析] 做Valid Sudoku时表示3*3区块的下标想得 ... -
Leetcode - N Queues II
2015-07-30 20:52 373[分析] 做完N皇后第一题,这个就so easy~ pu ... -
Leetcode - N-Queens
2015-07-30 20:38 405[分析] N皇后摆放规则:两个皇后不能共存于同一行、同一列以及 ... -
Leetcode - Word Ladder II
2015-06-26 09:19 496Given two words (start and end) ... -
Leetcode - Combination Sum III
2015-06-10 10:09 508Find all possible combinati ... -
Leetcode - Palindrome Partition
2015-05-21 09:56 746Given a string s, partition s s ... -
Leetcode - WordBreak III
2015-04-16 08:30 421Given a string s and a dictio ...
相关推荐
leetcode 2 LeetCode-练习 我的 ...Generate Parentheses 运行时间:164 毫秒内存使用:22.5 MB 26. Remove Duplicates from Sorted Array 运行时间:100 毫秒内存使用:15.2 MB 27. Remove Element
leetcode 答案LeetCode 算法的复杂度分析。...因为是递回求解,所以很抽象不好懂,这里以leetcode的generate-parentheses一道题目为例,给定n,要找出n个括号的各种组合,例如n=2 ,答案会是[(()), ()()]
Parentheses | ImplementstrStr.java //28. Implement strStr() │ LongestIncreasingSubsequence.java 300.Longest Increasing Subsequence | LongestPalindromicSubstring.java 5. Longest Palindromic Substring...
generate-parentheses【】【中等】 这是一道递归题目,想法很重要,保证括号合法性是另一个要点 private List result; public List generateParenthesis(int n) { result = new ArrayList(); _generate(0, 0, n, "")...
leetcode 530 ** LeetCode 题目更新 ** 用来记录业余时间所做的算法题目,保持对于数据结构的熟悉。 ** Leetcode 题目列表 ...Parentheses ...Generate Parentheses 028 Implement strStr() 031 Next Permutat
题目来源:https://leetcode-cn.com/problems/generate-parentheses/submissions/ 题目 给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。 例如,给出 n = 3,生成结果为...
第四章 Leetcode 题解 1. Two Sum 2. Add Two Numbers 3. Longest Substring Without ...22. Generate Parentheses 23. Merge k Sorted Lists 24. Swap Nodes in Pairs 25. Reverse Nodes in k-Group 26. Remove Dupli
lru缓存leetcode leetcode 1. Two Sum 2. Add Two ...Generate Parentheses 25. Reverse Nodes in k-Group 26. Remove Duplicates from Sorted Array 27. Remove Element 28. Implement strStr() 3
022_Generate_Parentheses 023_Merge_k_Sorted_Lists 024_Swap_Nodes_in_Pairs 025_Reverse_Nodes_in_k-Group 026_Remove_Duplicates_from_Sorted_Array 027_Remove_Element 028_Implement_strStr() 029_...
Generate Parentheses 18 3 sum 扩展版, 外层多套一个循环即可。注意判断重复及细节优化 19 细节:nodelist前插入一个dummy node. 删除倒数第n 等于正数查到len - n 20 用stack 最后stack应该是空的 21 遍历直到二...
237 Generate Parentheses 575 238 Combination Sum 577 239 Combination Sum II 579 240 Combination Sum III 581 241 Combinations 583 242 Letter Combinations of a Phone Number 587 243 Restore IP Addresses ...
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 Substring Without ...