Skip to content

Commit 89c632c

Browse files
SeanforfunSeanforfun
committed
[Function add]
1. Add leetcode questions with tag dfs.
1 parent 6199107 commit 89c632c

File tree

4 files changed

+157
-1
lines changed

4 files changed

+157
-1
lines changed

‎leetcode/22. Generate Parentheses.md

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -79,4 +79,31 @@ class Solution {
7979
if(right > 0 && right > left) backtrace(result, s + ")", left, right - 1);
8080
}
8181
}
82+
```
83+
84+
### Third time
85+
```Java
86+
class Solution {
87+
public List<String> generateParenthesis(int n) {
88+
List<String> result = new ArrayList<>();
89+
if(n == 0){
90+
result.add("");
91+
}else{
92+
dfs(n, n, "", result);
93+
}
94+
return result;
95+
}
96+
private void dfs(int left, int right, String s, List<String> result){
97+
if(left == 0 && right == 0){
98+
result.add(s);
99+
}else{
100+
if(left > 0){
101+
dfs(left - 1, right, s + '(', result);
102+
}
103+
if(left < right){
104+
dfs(left, right - 1, s + ')', result);
105+
}
106+
}
107+
}
108+
}
82109
```

‎leetcode/301. Remove Invalid Parentheses.md

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -76,5 +76,57 @@ class Solution {
7676
}
7777
```
7878

79+
### Second time
80+
* Method 1
81+
* Need to make full use of pruning.
82+
* Add index variable to remove the number of iteration.
83+
* merge removing ( and ) together.
84+
```Java
85+
class Solution {
86+
public List<String> removeInvalidParentheses(String s) {
87+
int left = 0, right = 0;
88+
char[] arr = s.toCharArray();
89+
for(int i = 0; i < arr.length; i++){
90+
if(arr[i] == '(' || arr[i] == ')'){
91+
if(arr[i] == '(') left ++;
92+
else{
93+
if(left > 0) left --;
94+
else if(left == 0) right++;
95+
}
96+
}
97+
}
98+
Set<String> set = new HashSet<>();
99+
dfs(s, set, left, right, 0);
100+
List<String> rr = new LinkedList<>();
101+
if(set.isEmpty()) rr.add("");
102+
else rr.addAll(set);
103+
return rr;
104+
}
105+
private void dfs(String s, Set<String> result, int left, int right, int index){
106+
char[] arr = s.toCharArray();
107+
if(left == 0 && right == 0 && valid(arr)){
108+
result.add(s);
109+
return;
110+
}
111+
for(int i = index; i < arr.length; i++){
112+
if(arr[i] != '(' && arr[i] != ')' || (i > 0 && arr[i - 1] == arr[i])) continue;
113+
if(right > 0 && arr[i] == ')') dfs(s.substring(0, i) + s.substring(i + 1), result, left, right - 1, i);
114+
else if(left > 0 && arr[i] == '(') dfs(s.substring(0, i) + s.substring(i + 1), result, left - 1, right, i);
115+
}
116+
}
117+
private boolean valid(char[] arr){
118+
int count = 0;
119+
for(int i = 0; i < arr.length; i++){
120+
if(arr[i] == '(' || arr[i] == ')'){
121+
if(arr[i] == '(') count++;
122+
else count --;
123+
if(count < 0) return false;
124+
}
125+
}
126+
return count == 0;
127+
}
128+
}
129+
```
130+
79131
### Reference
80132
1. [花花酱 LeetCode 301. Remove Invalid Parentheses - 刷题找工作 EP139](https://www.youtube.com/watch?v=2k_rS_u6EBk)

‎leetcode/37. Sudoku Solver.md

Lines changed: 37 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -82,4 +82,40 @@ class Solution {
8282
return true;
8383
}
8484
}
85-
```
85+
```
86+
87+
### Third time
88+
* Method 1: dfs
89+
* for each of the for-loop, its function is to find the next '.'.
90+
```Java
91+
class Solution {
92+
public void solveSudoku(char[][] board) {
93+
dfs(board, 0, 0);
94+
}
95+
private boolean dfs(char[][] board, int iStart, int jStart){
96+
for(int i = iStart; i < 9; i++, jStart = 0){
97+
for(int j = jStart; j < 9; j++){
98+
if(board[i][j] != '.') continue;
99+
for(char c = '1'; c <= '9'; c++){
100+
if(check(board, c, i, j)){
101+
board[i][j] = c;
102+
if(dfs(board, i, j + 1)) return true;
103+
else board[i][j] = '.';
104+
}
105+
}
106+
return false;
107+
}
108+
}
109+
return true;
110+
}
111+
private boolean check(char[][] board, char c, int row, int col){
112+
for(int i = 0; i < 9; i++){
113+
if(board[row][i] == c) return false;
114+
if(board[i][col] == c) return false;
115+
if(board[3 * (row / 3) + i / 3][ 3 * (col / 3) + i % 3] == c)
116+
return false;
117+
}
118+
return true;
119+
}
120+
}
121+
```

‎leetcode/51. N-Queens.md

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -123,4 +123,45 @@ class Solution {
123123
return true;
124124
}
125125
}
126+
```
127+
128+
### Third time
129+
* Method 1: Search + bfs 3ms
130+
```Java
131+
class Solution {
132+
public List<List<String>> solveNQueens(int n) {
133+
List<List<String>> result = new LinkedList<>();
134+
char[][] table = new char[n][n];
135+
for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) table[i][j] = '.';
136+
dfs(result, table, 0, n);
137+
return result;
138+
}
139+
public void dfs(List<List<String>> result, char[][] table, int row, int n){
140+
if(row == n){
141+
List<String> temp = new LinkedList<>();
142+
for(int i = 0; i < n; i++){
143+
temp.add(new String(table[i]));
144+
}
145+
result.add(temp);
146+
return;
147+
}
148+
for(int i = 0; i < n; i++){
149+
if(check(table, row, i, n)){
150+
table[row][i] = 'Q';
151+
dfs(result, table, row + 1, n);
152+
table[row][i] = '.';
153+
}
154+
}
155+
}
156+
private boolean check(char[][] table, int row, int col, int n){
157+
for(int i = 0; i < n; i++){
158+
if(table[row][i] == 'Q') return false;
159+
if(table[i][col] == 'Q') return false;
160+
}
161+
int tempRow = row, tempCol = col;
162+
while(tempRow >= 0 && tempCol >= 0) if(table[tempRow--][tempCol--] == 'Q') return false;
163+
while(row >= 0 && col < n) if(table[row--][col++] == 'Q') return false;
164+
return true;
165+
}
166+
}
126167
```

0 commit comments

Comments
 (0)