Skip to content

Commit a32ad5d

Browse files
unrealworkunrealwork
committed
leetcode: MyQueue: passed
leetcode: SumOfLeftLeaves: passed leetcode: ZeroOneMatrix: passed leetcode: PopulatingRightPointer: passed
1 parent 54fe070 commit a32ad5d

File tree

8 files changed

+257
-0
lines changed

8 files changed

+257
-0
lines changed

‎src/main/java/com/leetcode/array/ZeroOneMatrix.java

+72
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
package com.leetcode.array;
2+
3+
import java.util.ArrayDeque;
4+
import java.util.Arrays;
5+
import java.util.Deque;
6+
7+
public final class ZeroOneMatrix {
8+
private ZeroOneMatrix() {
9+
}
10+
11+
12+
public static int[][] updateMatrix(int[][] mat) {
13+
return new Solver(mat).solve();
14+
}
15+
16+
private static final class Solver {
17+
private static final int[][] SHIFTS = new int[][] {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
18+
private final int[][] mat;
19+
private final int m;
20+
private final int n;
21+
22+
Solver(int[][] mat) {
23+
this.mat = mat;
24+
this.m = mat.length;
25+
this.n = mat[0].length;
26+
}
27+
28+
private static int[][] initDist(int m, int n) {
29+
int[][] dist = new int[m][n];
30+
for (int[] ints : dist) {
31+
Arrays.fill(ints, Integer.MAX_VALUE);
32+
}
33+
return dist;
34+
}
35+
36+
int[][] solve() {
37+
int[][] dist = initDist(m, n);
38+
Deque<Integer> deque = new ArrayDeque<>();
39+
for (int i = 0; i < m; i++) {
40+
for (int j = 0; j < n; j++) {
41+
if (mat[i][j] == 0) {
42+
deque.addFirst(i);
43+
deque.addFirst(j);
44+
dist[i][j] = 0;
45+
}
46+
}
47+
}
48+
distBfs(dist, deque);
49+
return dist;
50+
}
51+
52+
private void distBfs(int[][] dist, Deque<Integer> deque) {
53+
while (!deque.isEmpty()) {
54+
int curI = deque.removeLast();
55+
int curJ = deque.removeLast();
56+
for (int[] shift : SHIFTS) {
57+
int adjI = curI + shift[0];
58+
int adjJ = curJ + shift[1];
59+
if (isValid(adjI, adjJ) && dist[adjI][adjJ] > dist[curI][curJ] + 1) {
60+
dist[adjI][adjJ] = dist[curI][curJ] + 1;
61+
deque.addFirst(adjI);
62+
deque.addFirst(adjJ);
63+
}
64+
}
65+
}
66+
}
67+
68+
private boolean isValid(int i, int j) {
69+
return i > -1 && i < m && j > -1 && j < n;
70+
}
71+
}
72+
}

‎src/main/java/com/leetcode/stack/MyQueue.java

+41
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
package com.leetcode.stack;
2+
3+
import java.util.ArrayDeque;
4+
import java.util.Deque;
5+
6+
class MyQueue {
7+
private Deque<Integer> popStack;
8+
private Deque<Integer> pushStack;
9+
10+
MyQueue() {
11+
this.popStack = new ArrayDeque<>();
12+
this.pushStack = new ArrayDeque<>();
13+
}
14+
15+
void push(int x) {
16+
if (popStack.isEmpty()) {
17+
popStack.addLast(x);
18+
} else {
19+
int size = popStack.size();
20+
while (!popStack.isEmpty()) {
21+
pushStack.addLast(popStack.removeLast());
22+
}
23+
popStack.addLast(x);
24+
for (int i = 0; i < size; i++) {
25+
popStack.addLast(pushStack.removeLast());
26+
}
27+
}
28+
}
29+
30+
int pop() {
31+
return popStack.removeLast();
32+
}
33+
34+
int peek() {
35+
return popStack.peekLast();
36+
}
37+
38+
boolean empty() {
39+
return popStack.isEmpty();
40+
}
41+
}

‎src/main/java/com/leetcode/tree/Node.java

+23
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
package com.leetcode.tree;
2+
3+
@SuppressWarnings("checkstyle:VisibilityModifier")
4+
class Node {
5+
int val;
6+
Node left;
7+
Node right;
8+
Node next;
9+
10+
Node() {
11+
}
12+
13+
Node(int v) {
14+
val = v;
15+
}
16+
17+
Node(int v, Node l, Node r, Node n) {
18+
val = v;
19+
left = l;
20+
right = r;
21+
next = n;
22+
}
23+
}

‎src/main/java/com/leetcode/tree/PopulatingRightPointer.java

+39
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
package com.leetcode.tree;
2+
3+
import util.ExcludeFromJacocoGeneratedReport;
4+
5+
@ExcludeFromJacocoGeneratedReport
6+
public final class PopulatingRightPointer {
7+
private PopulatingRightPointer() {
8+
9+
}
10+
11+
public Node connect(Node root) {
12+
Node it = root;
13+
Node head;
14+
Node tail;
15+
while (it != null) {
16+
head = null;
17+
tail = null;
18+
while (it != null) {
19+
if (it.left == null) {
20+
break;
21+
}
22+
if (head == null) {
23+
head = it.left;
24+
tail = head;
25+
} else {
26+
tail.next = it.left;
27+
tail = tail.next;
28+
}
29+
tail.next = it.right;
30+
tail = tail.next;
31+
it = it.next;
32+
}
33+
if (head != null) {
34+
it = head;
35+
}
36+
}
37+
return root;
38+
}
39+
}

‎src/main/java/com/leetcode/tree/SumOfLeftLeaves.java

+18
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
package com.leetcode.tree;
2+
3+
public final class SumOfLeftLeaves {
4+
private SumOfLeftLeaves() {
5+
}
6+
7+
public static int sumOfLeftLeaves(TreeNode root) {
8+
if (root == null) {
9+
return 0;
10+
} else {
11+
if (root.left != null && root.left.left == null && root.left.right == null) {
12+
return root.left.val + sumOfLeftLeaves(root.right);
13+
} else {
14+
return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
15+
}
16+
}
17+
}
18+
}

‎src/main/java/util/ExcludeFromJacocoGeneratedReport.java

+11
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
package util;
2+
3+
import java.lang.annotation.ElementType;
4+
import java.lang.annotation.Retention;
5+
import java.lang.annotation.RetentionPolicy;
6+
import java.lang.annotation.Target;
7+
8+
@Retention(RetentionPolicy.RUNTIME)
9+
@Target( {ElementType.METHOD, ElementType.TYPE})
10+
public @interface ExcludeFromJacocoGeneratedReport {
11+
}

‎src/test/java/com/leetcode/array/ZeroOneMatrixTest.java

+35
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package com.leetcode.array;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
import org.junit.jupiter.params.ParameterizedTest;
5+
import org.junit.jupiter.params.provider.Arguments;
6+
import org.junit.jupiter.params.provider.MethodSource;
7+
8+
import java.util.stream.Stream;
9+
10+
class ZeroOneMatrixTest {
11+
12+
static Stream<Arguments> testCases() {
13+
return Stream.of(
14+
Arguments.of(
15+
new int[][] {
16+
{0, 0, 0},
17+
{0, 1, 0},
18+
{1, 1, 1}
19+
},
20+
new int[][] {
21+
{0, 0, 0},
22+
{0, 1, 0},
23+
{1, 2, 1}
24+
}
25+
)
26+
);
27+
}
28+
29+
@ParameterizedTest
30+
@MethodSource("testCases")
31+
void testUpdateMatrix(final int[][] mat, final int[][] expected) {
32+
int[][] actual = ZeroOneMatrix.updateMatrix(mat);
33+
Assertions.assertArrayEquals(expected, actual);
34+
}
35+
}

‎src/test/java/com/leetcode/tree/SumOfLeftLeavesTest.java

+18
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
package com.leetcode.tree;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
import org.junit.jupiter.params.ParameterizedTest;
5+
import org.junit.jupiter.params.converter.ConvertWith;
6+
import org.junit.jupiter.params.provider.CsvSource;
7+
8+
class SumOfLeftLeavesTest {
9+
10+
@ParameterizedTest
11+
@CsvSource( {
12+
"'3,9,20,null,null,15,7',24"
13+
})
14+
void testSumOfLeftLeaves(@ConvertWith(TreeNodeConverter.class) TreeNode root, int expected) {
15+
int actual = SumOfLeftLeaves.sumOfLeftLeaves(root);
16+
Assertions.assertEquals(expected, actual);
17+
}
18+
}

0 commit comments

Comments
 (0)