Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit95cba23

Browse files
committed
add: 022
1 parent134eb9b commit95cba23

File tree

3 files changed

+149
-0
lines changed

3 files changed

+149
-0
lines changed

‎README.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -79,6 +79,7 @@
7979
| 17|[Letter Combinations of a Phone Number][017]| String, Backtracking|
8080
| 18|[4Sum][018]| Array, Hash Table, Two Pointers|
8181
| 19|[Remove Nth Node From End of List][019]| Linked List, Two Pointers|
82+
| 22|[Generate Parentheses][022]| String, Backtracking|
8283
| 33|[Search in Rotated Sorted Array][033]| Arrays, Binary Search|
8384
| 43|[Multiply Strings][043]| Math, String|
8485
| 49|[Group Anagrams][049]| Hash Table, String|
@@ -152,6 +153,7 @@
152153
[017]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/017/README.md
153154
[018]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/018/README.md
154155
[019]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/019/README.md
156+
[022]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/022/README.md
155157
[033]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/033/README.md
156158
[043]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/043/README.md
157159
[049]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/049/README.md

‎note/022/README.md

Lines changed: 94 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,94 @@
1+
#[Generate Parentheses][title]
2+
3+
##Description
4+
5+
Given*n* pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
6+
7+
For example, given*n* = 3, a solution set is:
8+
9+
```
10+
[
11+
"((()))",
12+
"(()())",
13+
"(())()",
14+
"()(())",
15+
"()()()"
16+
]
17+
```
18+
19+
**Tags:** String, Backtracking
20+
21+
22+
##思路 0
23+
24+
题意是给你`n` 值，让你找到所有格式正确的圆括号匹配组，题目中已经给出了`n = 3` 的所有结果。遇到这种问题，第一直觉就是用到递归或者堆栈，我们选取递归来解决，也就是`helper` 函数的功能，从参数上来看肯定很好理解了，`leftRest` 代表还有几个左括号可以用，`rightNeed` 代表还需要几个右括号才能匹配，初始状态当然是`rightNeed = 0, leftRest = n`，递归的终止状态就是`rightNeed == 0 && leftRest == 0`，也就是左右括号都已匹配完毕，然后把`str` 加入到链表中即可。
25+
26+
```java
27+
classSolution {
28+
publicList<String>generateParenthesis(intn) {
29+
List<String> list=newArrayList<>();
30+
helper(list,"",0, n);
31+
return list;
32+
}
33+
34+
privatevoidhelper(List<String>list,Stringstr,intrightNeed,intleftRest) {
35+
if (rightNeed==0&& leftRest==0) {
36+
list.add(str);
37+
return;
38+
}
39+
if (rightNeed>0) helper(list, str+")", rightNeed-1, leftRest);
40+
if (leftRest>0) helper(list, str+"(", rightNeed+1, leftRest-1);
41+
}
42+
}
43+
```
44+
45+
46+
##思路 1
47+
48+
另一种实现方式就是迭代的思想了，我们来找寻其规律如下所示：
49+
50+
```
51+
f(0): “”
52+
53+
f(1): “(“f(0)”)”
54+
55+
f(2): "(“f(0)”)"f(1), “(“f(1)”)”
56+
57+
f(3): "(“f(0)”)"f(2), "(“f(1)”)"f(1), “(“f(2)”)”
58+
...
59+
```
60+
61+
可以递推出`f(n) = "(“f(0)”)"f(n-1) , "(“f(1)”)"f(n-2) "(“f(2)”)"f(n-3) … "(“f(i)”)“f(n-1-i) … “(f(n-1)”)”`
62+
63+
根据如上递推式写出如下代码应该不难了吧。
64+
65+
```java
66+
classSolution {
67+
publicList<String>generateParenthesis(intn) {
68+
HashMap<Integer,List<String>> hashMap=newHashMap<>();
69+
hashMap.put(0,Collections.singletonList(""));
70+
for (int i=1; i<= n; i++) {
71+
List<String> list=newArrayList<>();
72+
for (int j=0; j< i; j++) {
73+
for (String fj: hashMap.get(j)) {
74+
for (String fi_j_1: hashMap.get(i- j-1)) {
75+
list.add("("+ fj+")"+ fi_j_1);// calculate f(i)
76+
}
77+
}
78+
}
79+
hashMap.put(i, list);
80+
}
81+
return hashMap.get(n);
82+
}
83+
}
84+
```
85+
86+
87+
##结语
88+
89+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-java-leetcode][ajl]
90+
91+
92+
93+
[title]:https://leetcode.com/problems/generate-parentheses
94+
[ajl]:https://github.com/Blankj/awesome-java-leetcode
Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
packagecom.blankj.medium._022;
2+
3+
importjava.util.ArrayList;
4+
importjava.util.Collections;
5+
importjava.util.HashMap;
6+
importjava.util.List;
7+
8+
/**
9+
* <pre>
10+
* author: Blankj
11+
* blog : http://blankj.com
12+
* time : 2018/01/30
13+
* desc :
14+
* </pre>
15+
*/
16+
publicclassSolution {
17+
// public List<String> generateParenthesis(int n) {
18+
// List<String> list = new ArrayList<>();
19+
// helper(list, "", 0, n);
20+
// return list;
21+
// }
22+
//
23+
// private void helper(List<String> list, String str, int rightNeed, int leftRest) {
24+
// if (rightNeed == 0 && leftRest == 0) {
25+
// list.add(str);
26+
// return;
27+
// }
28+
// if (rightNeed > 0) helper(list, str + ")", rightNeed - 1, leftRest);
29+
// if (leftRest > 0) helper(list, str + "(", rightNeed + 1, leftRest - 1);
30+
// }
31+
32+
publicList<String>generateParenthesis(intn) {
33+
HashMap<Integer,List<String>>hashMap =newHashMap<>();
34+
hashMap.put(0,Collections.singletonList(""));
35+
for (inti =1;i <=n;i++) {
36+
List<String>list =newArrayList<>();
37+
for (intj =0;j <i;j++) {
38+
for (Stringfj :hashMap.get(j)) {
39+
for (Stringfi_j_1 :hashMap.get(i -j -1)) {
40+
list.add("(" +fj +")" +fi_j_1);// calculate f(i)
41+
}
42+
}
43+
}
44+
hashMap.put(i,list);
45+
}
46+
returnhashMap.get(n);
47+
}
48+
49+
publicstaticvoidmain(String[]args) {
50+
Solutionsolution =newSolution();
51+
System.out.println(solution.generateParenthesis(3));
52+
}
53+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp