8000 add 802 · githubniraj/Leetcode@5db9c76 · 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 5db9c76

Browse files
fishercoder1534fishercoder1534
committed
add 802
1 parent 341819c commit 5db9c76

File tree

3 files changed

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

3 files changed

+97
-2
lines changed

‎paginated_contents/algorithms/1st_thousand/README.md

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -101,6 +101,7 @@
101101
| 807 | [Max Increase to Keep City Skyline](https://leetcode.com/problems/max-increase-to-keep-city-skyline/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_807.java) | | Medium |
102102
| 806 | [Number of Lines To Write String](https://leetcode.com/problems/number-of-lines-to-write-string/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_806.java) | | Easy |
103103
| 804 | [Unique Morse Code Words](https://leetcode.com/problems/unique-morse-code-words/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_804.java) | | Easy |
104+
| 802 | [Find Eventual Safe States](https://leetcode.com/problems/find-eventual-safe-states/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_802.java) | | Medium | Topological Sort
104105
| 800 | [Similar RGB Color](https://leetcode.com/problems/similar-rgb-color/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_800.java) | | Easy |
105106
| 799 | [Champagne Tower](https://leetcode.com/problems/champagne-tower/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_799.java) | | Medium |
106107
| 796 | [Rotate String](https://leetcode.com/problems/rotate-string/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_796.java) | | Easy |
@@ -159,7 +160,7 @@
159160
| 717 | [1-bit and 2-bit Characters](https://leetcode.com/problems/1-bit-and-2-bit-characters/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_717.java) | | Easy |
160161
| 716 | [Max Stack](https://leetcode.com/problems/max-stack/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_716.java) | | Hard | Design
161162
| 714 | [Best Time to Buy and Sell Stock with Transaction Fee](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/) | [Solution](https 8000 ://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_714.java) | | Medium | DP
162-
| 713 | [Subarray Product Less Than K](https://leetcode.com/problems/subarray-product-less-than-k/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_713.java) || Medium | Sliding Window, Two Pointers
163+
| 713 | [Subarray Product Less Than K](https://leetcode.com/problems/subarray-product-less-than-k/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_713.java) || Medium | Sliding Window, Two Pointers
163164
| 712 | [Minimum ASCII Delete Sum for Two Strings](https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_712.java) | | Medium | DP
164165
| 709 | [To Lower Case](https://leetcode.com/problems/to-lower-case/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_709.java) | | Easy | String
165166
| 708 | [Insert into a Sorted Circular Linked List](https://leetcode.com/problems/insert-into-a-sorted-circular-linked-list/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_708.java) | | Medium | Linked List
@@ -443,7 +444,7 @@
443444
| 384 | [Shuffle an Array](https://leetcode.com/problems/shuffle-an-array/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_384.java) | | Medium |
444445
| 383 | [Ransom Note](https://leetcode.com/problems/ransom-note/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_383.java) | | Easy | String
445446
| 382 | [Linked List Random Node](https://leetcode.com/problems/linked-list-random-node/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_382.java) | | Medium | Reservoir Sampling
446-
| 381 | [Insert Delete GetRandom O(1) - Duplicates allowed](https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_381.java) || Hard | Design, Randomized, HashTable
447+
| 381 | [Insert Delete GetRandom O(1) - Duplicates allowed](https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_381.java) || Hard | Design, Randomized, HashTable
447448
| 380 | [Insert Delete GetRandom O(1)](https://leetcode.com/problems/insert-delete-getrandom-o1/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_380.java) | | Medium | Design, HashMap
448449
| 379 | [Design Phone Directory](https://leetcode.com/problems/design-phone-directory/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_379.java) | | Medium |
449450
| 378 | [Kth Smallest Element in a Sorted Matrix](https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_378.java) | | Medium | Binary Search

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

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
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 _802 {
9+
public static class Solution1 {
10+
/**
11+
* This is a variation of the templated topological sort in that it doesn't use indegree array, instead, it uses an outdegree array.
12+
* <p>
13+
* For topological sort, it usually makes sense to just keep an array of elements since it's a graph of n nodes,
14+
* we always need to take care each and every one of the nodes, no skipping any, so using an array could let you access each node by its index/name directly.
15+
*/
16+
public List<Integer> eventualSafeNodes(int[][] graph) {
17+
int n = graph.length;
18+
List<Integer>[] adjList = new ArrayList[n];
19+
for (int i = 0; i < n; i++) {
20+
adjList[i] = new ArrayList<>();
21+
}
22+
int[] outdegree = new int[n];
23+
for (int i = 0; i < n; i++) {
24+
for (int g : graph[i]) {
25+
adjList[g].add(i);
26+
outdegree[i]++;
27+
}
28+
}
29+
Queue<Integer> q = new LinkedList<>();
30+
for (int i = 0; i < n; i++) {
31+
if (outdegree[i] == 0) {
32+
q.offer(i);
33+
}
34+
}
35+
boolean[] safe = new boolean[n];
36+
while (!q.isEmpty()) {
37+
Integer curr = q.poll();
38+
safe[curr] = true;
39+
for (int v : adjList[curr]) {
40+
outdegree[v]--;
41+
if (outdegree[v] == 0) {
42+
q.offer(v);
43+
}
44+
}
45+
}
46+
List<Integer> result = new ArrayList<>();
47+
for (int i = 0; i < n; i++) {
48+
if (safe[i]) {
49+
result.add(i);
50+
}
51+
}
52+
return result;
53+
}
54+
}
55+
}

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

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

0 commit comments

Comments
 (0)
0