8000 add 851 · githubniraj/Leetcode@4c4675c · GitHub
[go: up one dir, main page]
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
Appearance settings

Commit 4c4675c

Browse files
fishercoder1534fishercoder1534
committed
add 851
1 parent 5db9c76 commit 4c4675c

File tree

3 files changed

+105
-0
lines changed
  • paginated_contents/algorithms/1st_thousand
  • src
    • main/java/com/fishercoder/solutions/firstthousand
    • test/java/com/fishercoder/firstthousand

3 files changed

+105
-0
lines changed

‎paginated_contents/algorithms/1st_thousand/README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -78,6 +78,7 @@
7878
| 859 | [Buddy Strings](https://leetcode.com/problems/buddy-strings/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_859.java) | | Easy |
7979
| 856 | [Score of Parentheses](https://leetcode.com/problems/score-of-parentheses/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_856.java) | | Medium | Stack, String
8080
| 852 | [Peak Index in a Mountain Array](https://leetcode.com/problems/peak-index-in-a-mountain-array/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_852.java) | | Easy |
81+
| 851 | [Loud and Rich](https://leetcode.com/problems/loud-and-rich/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_851.java) | | Medium |Topological Sort
8182
| 849 | [Maximize Distance to Closest Person](https://leetcode.com/problems/maximize-distance-to-closest-person/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_849.java) | | Easy |
8283
| 848 | [Shifting Letters](https://leetcode.com/problems/shifting-letters/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_848.java) | | Medium | Array, String
8384
| 844 | [Backspace String Compare](https://leetcode.com/problems/backspace-string-compare/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_844.java) | | Easy |

‎src/main/java/com/fishercoder/solutions/firstthousand/_851.java

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
package com.fishercoder.solutions.firstthousand;
2+
3+
import java.util.ArrayList;
4+
import java.util.LinkedList;
5+
import java.util.List;
6+
import java.util.Queue;
7+
8+
public class _851 {
9+
public static class Solution1 {
10+
/**
11+
* My completely original solution. Practice does make perfect!
12+
* Topological sort template does work well for this:
13+
* 1. make variable names as descriptive as possible to help sort out your logic;
14+
* 2. initializing an array of size n for topological sort problems of n nodes is pretty handy;
15+
* 3. it's either indegree or outdegree, and each time, we process it, we decrement the degree by one, in this case, we also check the quietness;
16+
* 4. overwrite the value for quiet[v] each time it needs to be updated so that next time around, it's not going to use outdated quietness value
17+
*/
18+
public int[] loudAndRich(int[][] richer, int[] quiet) {
19+
List<Integer>[] adjList = new ArrayList[quiet.length];
20+
for (int i = 0; i < quiet.length; i++) {
21+
adjList[i] = new ArrayList<>();
22+
}
23+
int[] indegree = new int[quiet.length];
24+
if (richer.length != 0 && richer[0].length != 0) {
25+
for (int[] rich : richer) {
26+
indegree[rich[1]]++;
27+
adjList[rich[0]].add(rich[1]);
28+
}
29+
}
30+
Queue<Integer> q = new LinkedList<>();
31+
int[] result = new int[quiet.length];
32+
for (int i = 0; i < quiet.length; i++) {
33+
if (indegree[i] == 0) {
34+
q.offer(i);
35+
}
36+
result[i] = i;
37+
}
38+
while (!q.isEmpty()) {
39+
int curr = q.poll();
40+
for (int v : adjList[curr]) {
41+
int quietnessForLessRichPerson = quiet[v];
42+
int quietnessForRicherPerson = quiet[result[curr]];
43+
if (quietnessForRicherPerson < quietnessForLessRichPerson) {
44+
result[v] = result[curr];
45+
//remember to update the quietness value for this node as well
46+
quiet[v] = quiet[curr];
47+
}
48+
indegree[v]--;
49+
if (indegree[v] == 0) {
50+
q.offer(v);
51+
}
52+
}
53+
}
54+
return result;
55+
}
56+
}
57+
}

‎src/test/java/com/fishercoder/firstthousand/_851Test.java

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
package com.fishercoder.firstthousand;
2+
3+
import com.fishercoder.solutions.firstthousand._851;
4+
import org.junit.jupiter.api.BeforeEach;
5+
import org.junit.jupiter.api.Test;
6+
7+
import static org.junit.jupiter.api.Assertions.assertArrayEquals;
8+
9+
public class _851Test {
10+
private static _851.Solution1 solution1;
11+
12+
@BeforeEach
13+
public void setup() {
14+
solution1 = new _851.Solution1();
15+
}
16+
17+
@Test
18+
public void test1() {
19+
assertArrayEquals(new int[]{5, 5, 2, 5, 4, 5, 6, 7},
20+
solution1.loudAndRich(new int[][]{
21+
{1, 0}, {2, 1}, {3, 1}, {3, 7}, {4, 3}, {5, 3}, {6, 3}
22+
}, new int[]{3, 2, 5, 4, 6, 1, 7, 0}));
23+
}
24+
25+
@Test
26+
public void test2() {
27+
assertArrayEquals(new int[]{0}, solution1.loudAndRich(new int[][]{{}}, new int[]{0}));
28+
}
29+
30+
@Test
31+
public void test3() {
32+
assertArrayEquals(new int[]{0, 1}, solution1.loudAndRich(new int[][]{{}}, new int[]{0, 1}));
33+
}
34+
35+
@Test
36+
public void test4() {
37+
assertArrayEquals(new int[]{0, 1}, solution1.loudAndRich(new int[][]{{}}, new int[]{1, 0}));
38+
}
39+
40+
@Test
41+
public void test5() {
42+
assertArrayEquals(new int[]{0, 1, 0}, solution1.loudAndRich(new int[][]{
43+
{0, 2}, {1, 2}
44+
}, new int[]{0, 1, 2}));
45+
}
46+
47+
}

0 commit comments

Comments
 (0)
0