Skip to content

Commit cd9e8ca

Browse files
GeekUniversityGeekUniversity
authored
Merge pull request algorithm001#594 from AlenPark/master
[072-week3]
2 parents 0f3049f + d4ef56e commit cd9e8ca

8 files changed

Lines changed: 313 additions & 0 deletions

‎Week_03/id_72/LeetCode_104_72.java‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* public class TreeNode {
4+
* int val;
5+
* TreeNode left;
6+
* TreeNode right;
7+
* TreeNode(int x) { val = x; }
8+
* }
9+
*/
10+
class Solution {
11+
public int maxDepth(TreeNode root) {
12+
if (root == null) {
13+
return 0;
14+
}
15+
int maxLeft = maxDepth(root.left) + 1;
16+
int maxRight = maxDepth(root.right) + 1;
17+
return Math.max(maxLeft, maxRight);
18+
}
19+
}

‎Week_03/id_72/LeetCode_200_72.java‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
class Solution {
2+
public int numIslands(char[][] grid) {
3+
if (grid == null || grid.length == 0) {
4+
return 0;
5+
}
6+
int count = 0;
7+
for (int i = 0; i < grid.length; i++) {
8+
for (int j = 0; j < grid[0].length; j++) {
9+
if (grid[i][j] == '1') {
10+
search(grid, i, j);
11+
count++;
12+
}
13+
}
14+
}
15+
return count;
16+
}
17+
18+
private static void search(char[][] grid, int i, int j) {
19+
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') {
20+
return;
21+
}
22+
grid[i][j] = '0';
23+
search(grid, i - 1, j);
24+
search(grid, i + 1, j);
25+
search(grid, i, j - 1);
26+
search(grid, i, j + 1);
27+
}
28+
}

‎Week_03/id_72/LeetCode_210_72.java‎

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
class Solution {
2+
private class CourseVertex {
3+
int val;
4+
int inDegree;
5+
List<CourseVertex> adjacent;
6+
7+
private CourseVertex(int val) {
8+
this.val = val;
9+
this.inDegree = 0;
10+
this.adjacent = new LinkedList<>();
11+
}
12+
}
13+
public int[] findOrder(int numCourses, int[][] prerequisites) {
14+
int[] result = new int[numCourses];
15+
if (numCourses == 0 || prerequisites == null) {
16+
return result;
17+
}
18+
CourseVertex[] vertices = new CourseVertex[numCourses];
19+
for (int i = 0; i < numCourses; i++) {
20+
vertices[i] = new CourseVertex(i);
21+
}
22+
for (int[] depend : prerequisites) {
23+
int x = depend[0];
24+
int y = depend[1];
25+
vertices[y].adjacent.add(vertices[x]);
26+
vertices[x].inDegree++;
27+
}
28+
29+
int count = 0;
30+
Queue<CourseVertex> queue = new LinkedList<>();
31+
for (CourseVertex vertex : vertices) {
32+
if (vertex.inDegree == 0) {
33+
queue.offer(vertex);
34+
}
35+
}
36+
while (!queue.isEmpty()) {
37+
CourseVertex vertex = queue.poll();
38+
result[count] = vertex.val;
39+
count++;
40+
for (CourseVertex adj : vertex.adjacent) {
41+
if (--adj.inDegree == 0) {
42+
queue.offer(adj);
43+
}
44+
}
45+
}
46+
if (count != numCourses) {
47+
return new int[0];
48+
}
49+
return result;
50+
}
51+
}

‎Week_03/id_72/LeetCode_373_72.java‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
class Solution {
2+
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
3+
List<int[]> result = new LinkedList<>();
4+
if (nums1 == null || nums2 == null || k == 0) {
5+
return result;
6+
}
7+
PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
8+
@Override
9+
public int compare(int[] o1, int[] o2) {
10+
return o1[0] + o1[1] - o2[0] - o2[1];
11+
}
12+
});
13+
for (int i : nums1) {
14+
for (int j : nums2) {
15+
queue.add(new int[] {i, j});
16+
}
17+
}
18+
for (int i = 0; i < k && !queue.isEmpty(); i++) {
19+
result.add(queue.poll());
20+
}
21+
return result;
22+
}
23+
}

‎Week_03/id_72/LeetCode_429_72.java‎

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
/*
2+
// Definition for a Node.
3+
class Node {
4+
public int val;
5+
public List<Node> children;
6+
7+
public Node() {}
8+
9+
public Node(int _val,List<Node> _children) {
10+
val = _val;
11+
children = _children;
12+
}
13+
};
14+
*/
15+
class Solution {
16+
public List<List<Integer>> levelOrder(Node root) {
17+
List<List<Integer>> result = new LinkedList<>();
18+
if (root == null) {
19+
return result;
20+
}
21+
List<Node> rootList = new LinkedList<>();
22+
rootList.add(root);
23+
bfs(rootList, result);
24+
return result;
25+
}
26+
private void bfs(List<Node> nodes, List<List<Integer>> result) {
27+
if (nodes == null || nodes.isEmpty()) {
28+
return;
29+
}
30+
List<Node> children = new LinkedList<>();
31+
List<Integer> valueList = new LinkedList<>();
32+
result.add(valueList);
33+
for (Node node : nodes) {
34+
valueList.add(node.val);
35+
children.addAll(node.children);
36+
}
37+
bfs(children, result);
38+
}
39+
}

‎Week_03/id_72/LeetCode_529_72.java‎

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
class Solution {
2+
public char[][] updateBoard(char[][] board, int[] click) {
3+
int x = click[0];
4+
int y = click[1];
5+
6+
bfs(board, x, y);
7+
return board;
8+
}
9+
10+
private void bfs(char[][] board, int x, int y) {
11+
if (!checkBound(board, x, y)) {
12+
return;
13+
}
14+
if (board[x][y] == 'M') {
15+
board[x][y] = 'X';
16+
return;
17+
}
18+
int count = countMine(board, x, y);
19+
if (board[x][y] == 'E') {
20+
if (count == 0) {
21+
board[x][y] = 'B';
22+
bfs(board, x - 1, y - 1);
23+
bfs(board, x, y - 1);
24+
bfs(board, x + 1, y - 1);
25+
bfs(board, x - 1, y);
26+
bfs(board, x, y);
27+
bfs(board, x + 1, y);
28+
bfs(board, x - 1, y + 1);
29+
bfs(board, x, y + 1);
30+
bfs(board, x + 1, y + 1);
31+
} else {
32+
board[x][y] = (char) (count + 48);
33+
}
34+
}
35+
}
36+
37+
private int countMine(char[][] board, int x, int y) {
38+
int count = 0;
39+
if (checkBound(board, x - 1, y - 1)) {
40+
if ('M' == board[x - 1][y - 1]) {
41+
count++;
42+
}
43+
}
44+
if (checkBound(board, x, y - 1)) {
45+
if ('M' == board[x][y - 1]) {
46+
count++;
47+
}
48+
}
49+
if (checkBound(board, x + 1, y - 1)) {
50+
if ('M' == board[x + 1][y - 1]) {
51+
count++;
52+
}
53+
}
54+
if (checkBound(board, x - 1, y)) {
55+
if ('M' == board[x - 1][y]) {
56+
count++;
57+
}
58+
}
59+
if (checkBound(board, x + 1, y)) {
60+
if ('M' == board[x + 1][y]) {
61+
count++;
62+
}
63+
}
64+
if (checkBound(board, x - 1, y + 1)) {
65+
if ('M' == board[x - 1][y + 1]) {
66+
count++;
67+
}
68+
}
69+
if (checkBound(board, x, y + 1)) {
70+
if ('M' == board[x][y + 1]) {
71+
count++;
72+
}
73+
}
74+
if (checkBound(board, x + 1, y + 1)) {
75+
if ('M' == board[x + 1][y + 1]) {
76+
count++;
77+
}
78+
}
79+
return count;
80+
}
81+
82+
private boolean checkBound(char[][] board, int x, int y) {
83+
return x >= 0 && y >= 0 && x < board.length && y < board[0].length;
84+
}
85+
}

‎Week_03/id_72/LeetCode_703_72.java‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
class KthLargest {
2+
3+
private PriorityQueue<Integer> queue;
4+
5+
private int k;
6+
7+
public KthLargest(int k, int[] nums) {
8+
queue = new PriorityQueue<>(k);
9+
this.k = k;
10+
for (int num : nums) {
11+
add(num);
12+
}
13+
}
14+
15+
public int add(int val) {
16+
if (queue.size() < k) {
17+
queue.add(val);
18+
return queue.peek();
19+
}
20+
if (queue.peek() < val) {
21+
queue.poll();
22+
queue.add(val);
23+
}
24+
return queue.peek();
25+
}
26+
}

‎Week_03/id_72/LeetCode_802_72.java‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
class Solution {
2+
public List<Integer> eventualSafeNodes(int[][] graph) {
3+
List<Integer> result = new LinkedList<>();
4+
if (graph == null || graph.length == 0) {
5+
return result;
6+
}
7+
boolean[] isSafeNode = new boolean[graph.length];
8+
boolean[] visited = new boolean[graph.length];
9+
for (int i = 0; i < graph.length; i++) {
10+
if (isSafeNode(graph, isSafeNode, i, visited)) {
11+
result.add(i);
12+
}
13+
}
14+
return result;
15+
}
16+
17+
private boolean isSafeNode(int[][] graph, boolean[] isSafeNode, int node, boolean[] visited) {
18+
if (isSafeNode[node]) {
19+
return true;
20+
}
21+
if (visited[node]) {
22+
return false;
23+
}
24+
visited[node] = true;
25+
int[] adjacent = graph[node];
26+
if (adjacent == null || adjacent.length == 0) {
27+
isSafeNode[node] = true;
28+
return true;
29+
}
30+
boolean isSafe = true;
31+
for (int adj : adjacent) {
32+
if (!isSafeNode(graph, isSafeNode, adj, visited)) {
33+
isSafe = false;
34+
break;
35+
}
36+
}
37+
if (isSafe) {
38+
isSafeNode[node] = true;
39+
}
40+
return isSafe;
41+
}
42+
}

0 commit comments

Comments
 (0)