Skip to content

Commit 6154462

Browse files
h2plh2pl
committed
代码更新
1 parent 26cadec commit 6154462

6 files changed

Lines changed: 179 additions & 2 deletions

File tree

‎src/BackTracking/N皇后.java‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4,4 +4,8 @@
44
* Created by 周杰伦 on 2018/4/2.
55
*/
66
public class N皇后 {
7+
public static void main(String[] args) {
8+
StringBuilder sb = new StringBuilder();
9+
10+
}
711
}

‎src/BackTracking/数字键打出字母组合.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@
66
/**
77
* Created by 周杰伦 on 2018/4/1.
88
*/
9-
public class 数字键打出字母组合 {
9+
public class 数字键打出字母组合 {
1010
public List<String> letterCombinations(String digits) {
1111
if (digits == null || digits.equals(""))return new ArrayList<>();
1212
List<String> list = new ArrayList<>();

‎src/BackTracking/脑洞大开的矩阵查找单词.java‎

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
package BackTracking;
2+
3+
/**
4+
* Created by 周杰伦 on 2018/7/20.
5+
*/
6+
public class 脑洞大开的矩阵查找单词 {
7+
8+
static class StopMsgException extends RuntimeException {
9+
10+
}
11+
12+
static boolean flag;
13+
14+
public boolean exist(char[][] board, String word) {
15+
if (word.equals("")) {
16+
return true;
17+
}
18+
int[][] visit = new int[board.length][board[0].length];
19+
flag = false;
20+
try {
21+
for (int i = 0; i < board.length; i++) {
22+
for (int j = 0; j < board[0].length; j++) {
23+
if (word.charAt(0) == board[i][j]) {
24+
dfs(board, word, visit, i, j);
25+
}
26+
}
27+
}
28+
} catch (StopMsgException e) {
29+
System.out.println(e);
30+
}
31+
return flag;
32+
}
33+
34+
public void dfs(char[][] board, String word, int[][] visit, int i, int j) {
35+
if (word.equals("")) {
36+
flag = true;
37+
throw new StopMsgException();
38+
}
39+
if (i > board.length - 1 || i < 0 || j > board[0].length - 1 || j < 0) {
40+
return;
41+
}
42+
if (visit[i][j] == 1) {
43+
return;
44+
}
45+
46+
if (word.charAt(0) == board[i][j]) {
47+
visit[i][j] = 1;
48+
dfs(board, word.length() == 1 ? "" : word.substring(1, word.length()), visit, i + 1, j);
49+
dfs(board, word.length() == 1 ? "" : word.substring(1, word.length()), visit, i - 1, j);
50+
dfs(board, word.length() == 1 ? "" : word.substring(1, word.length()), visit, i, j - 1);
51+
dfs(board, word.length() == 1 ? "" : word.substring(1, word.length()), visit, i, j + 1);
52+
visit[i][j] = 0;
53+
}
54+
}
55+
56+
}

‎src/BinSearch/arrangeCoins.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,7 @@
33
/**
44
* Created by 周杰伦 on 2018/3/16.
55
*/
6-
public class arrangeCoins {
6+
public class arrangeCoins {
77
public int arrangeCoins(int n) {
88
if (n <= 1) {
99
return n;

‎src/DFS/朋友圈.java‎

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
package DFS;
2+
3+
/**
4+
* Created by 周杰伦 on 2018/7/19.
5+
*/
6+
public class 朋友圈 {
7+
public static void main(String[] args) {
8+
int [][]a = {{1,1,0}, {1,1,0}, {0,0,1}};
9+
System.out.println(findCircleNum(a));
10+
}
11+
private static int n;
12+
13+
public static int findCircleNum(int[][] M) {
14+
n = M.length;
15+
int circleNum = 0;
16+
boolean[] hasVisited = new boolean[n];
17+
for (int i = 0; i < n; i ++) {
18+
if (!hasVisited[i]) {
19+
dfs(M, i, hasVisited);
20+
circleNum++;
21+
}
22+
}
23+
return circleNum;
24+
}
25+
26+
private static void dfs(int[][] M, int i, boolean[] hasVisited) {
27+
hasVisited[i] = true;
28+
for (int k = 0; k < n; k++) {
29+
if (M[i][k] == 1 && !hasVisited[k]) {
30+
dfs(M, k, hasVisited);
31+
}
32+
}
33+
}
34+
// private static int n;
35+
// public static int findCircleNum(int[][] M) {
36+
// n = M.length;
37+
// int cnt = 0 ;
38+
// int []visit = new int[n];
39+
// for (int i = 0;i < M.length;i ++) {
40+
// if(visit[i] == 0) {
41+
// dfs(M, visit, i);
42+
// cnt ++;
43+
// }
44+
// }
45+
// return cnt;
46+
// }
47+
// public static void dfs(int[][]M, int[] visit, int i) {
48+
// visit[i] = 1;
49+
// for (int j = 0;j < M.length;j ++) {
50+
// if(visit[j] == 0 && M[i][j] == 1) {
51+
// dfs(M, visit, i);
52+
// }
53+
// }
54+
// }
55+
}

‎src/DFS/被围绕的区域.java‎

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
package DFS;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
6+
/**
7+
* Created by 周杰伦 on 2018/7/19.
8+
*/
9+
public class 被围绕的区域 {
10+
private int m, n;
11+
private int[][] matrix;
12+
private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
13+
14+
public List<int[]> pacificAtlantic(int[][] matrix) {
15+
List<int[]> ret = new ArrayList<>();
16+
if (matrix == null || matrix.length == 0) {
17+
return ret;
18+
}
19+
20+
m = matrix.length;
21+
n = matrix[0].length;
22+
this.matrix = matrix;
23+
boolean[][] canReachP = new boolean[m][n];
24+
boolean[][] canReachA = new boolean[m][n];
25+
26+
for (int i = 0; i < m; i++) {
27+
dfs(i, 0, canReachP);
28+
dfs(i, n - 1, canReachA);
29+
}
30+
for (int i = 0; i < n; i++) {
31+
dfs(0, i, canReachP);
32+
dfs(m - 1, i, canReachA);
33+
}
34+
35+
for (int i = 0; i < m; i++) {
36+
for (int j = 0; j < n; j++) {
37+
if (canReachP[i][j] && canReachA[i][j]) {
38+
ret.add(new int[]{i, j});
39+
}
40+
}
41+
}
42+
43+
return ret;
44+
}
45+
46+
private void dfs(int r, int c, boolean[][] canReach) {
47+
if (canReach[r][c]) {
48+
return;
49+
}
50+
canReach[r][c] = true;
51+
for (int[] d : direction) {
52+
int nextR = d[0] + r;
53+
int nextC = d[1] + c;
54+
if (nextR < 0 || nextR >= m || nextC < 0 || nextC >= n
55+
|| matrix[r][c] > matrix[nextR][nextC]) {
56+
57+
continue;
58+
}
59+
dfs(nextR, nextC, canReach);
60+
}
61+
}
62+
}

0 commit comments

Comments
 (0)