Skip to content

Commit b231cfb

Browse files
fishercoder1534fishercoder1534
committed
add 2076
1 parent 989aa67 commit b231cfb

File tree

3 files changed

+136
-0
lines changed

3 files changed

+136
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,7 @@ _If you like this project, please leave me a star._ ★
88

99
| # | Title | Solutions | Video | Difficulty | Tag
1010
|-----|----------------|---------------|--------|-------------|-------------
11+
|2076|[Process Restricted Friend Requests](https://leetcode.com/problems/process-restricted-friend-requests/)|[Java](../master/src/main/java/com/fishercoder/solutions/_2076.java) ||Hard||
1112
|2075|[Decode the Slanted Ciphertext](https://leetcode.com/problems/decode-the-slanted-ciphertext/)|[Java](../master/src/main/java/com/fishercoder/solutions/_2075.java) ||Medium||
1213
|2074|[Reverse Nodes in Even Length Groups](https://leetcode.com/problems/reverse-nodes-in-even-length-groups/)|[Java](../master/src/main/java/com/fishercoder/solutions/_2074.java) ||Medium||
1314
|2073|[Time Needed to Buy Tickets](https://leetcode.com/problems/time-needed-to-buy-tickets/)|[Java](../master/src/main/java/com/fishercoder/solutions/_2073.java) ||Easy||

‎src/main/java/com/fishercoder/solutions/_2076.java

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
package com.fishercoder.solutions;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
6+
public class _2076 {
7+
public static class Solution1 {
8+
/**
9+
* Credit: https://leetcode.com/SaveVMK/ on https://leetcode.com/contest/weekly-contest-267/ranking/
10+
*/
11+
public boolean[] friendRequests(int n, int[][] restrictions, int[][] requests) {
12+
int[] head = new int[n];
13+
boolean[][] isr = new boolean[n][n];
14+
for (int i = 0; i < n; i++) {
15+
head[i] = i;
16+
}
17+
List<List<Integer>> ch = new ArrayList<>();
18+
for (int i = 0; i < n; i++) {
19+
ch.add(new ArrayList<>());
20+
ch.get(i).add(i);
21+
}
22+
for (int[] res : restrictions) {
23+
isr[res[0]][res[1]] = true;
24+
isr[res[1]][res[0]] = true;
25+
}
26+
boolean[] ans = new boolean[requests.length];
27+
for (int i = 0; i < requests.length; i++) {
28+
int u = head[requests[i][0]];
29+
int v = head[requests[i][1]];
30+
if (u == v) {
31+
ans[i] = true;
32+
continue;
33+
}
34+
if (isr[u][v]) {
35+
continue;
36+
}
37+
ans[i] = true;
38+
for (int v2 : ch.get(v)) {
39+
ch.get(u).add(v2);
40+
head[v2] = u;
41+
}
42+
for (int j = 0; j < n; j++) {
43+
isr[u][j] |= isr[v][j];
44+
isr[j][u] |= isr[j][v];
45+
}
46+
}
47+
return ans;
48+
}
49+
50+
}
51+
}

‎src/test/java/com/fishercoder/_2076Test.java

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.common.utils.CommonUtils;
4+
import com.fishercoder.solutions._2076;
5+
import org.junit.BeforeClass;
6+
import org.junit.Test;
7+
8+
import static org.junit.Assert.assertArrayEquals;
9+
10+
public class _2076Test {
11+
private static _2076.Solution1 solution1;
12+
private static int[][] restrictions;
13+
private static int[][] requests;
14+
private static int n;
15+
private static boolean[] expected;
16+
17+
@BeforeClass
18+
public static void setup() {
19+
solution1 = new _2076.Solution1();
20+
}
21+
22+
@Test
23+
public void test1() {
24+
restrictions = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[0,1]");
25+
requests = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[0,2],[2,1]");
26+
expected = new boolean[]{true, false};
27+
n = 3;
28+
assertArrayEquals(expected, solution1.friendRequests(n, restrictions, requests));
29+
}
30+
31+
@Test
32+
public void test2() {
33+
restrictions = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[0,1]");
34+
requests = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[1,2],[0,2]");
35+
expected = new boolean[]{true, false};
36+
n = 3;
37+
assertArrayEquals(expected, solution1.friendRequests(n, restrictions, requests));
38+
}
39+
40+
@Test
41+
public void test3() {
42+
restrictions = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[0,1],[1,2],[2,3]");
43+
requests = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[0,4],[1,2],[3,1],[3,4]");
44+
expected = new boolean[]{true, false, true, false};
45+
n = 5;
46+
assertArrayEquals(expected, solution1.friendRequests(n, restrictions, requests));
47+
}
48+
49+
@Test
50+
public void test4() {
51+
restrictions = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[0,6],[6,2]");
52+
requests = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[0,2],[2,3],[0,2],[6,4],[6,4]");
53+
expected = new boolean[]{true, true, true, true, true};
54+
n = 7;
55+
assertArrayEquals(expected, solution1.friendRequests(n, restrictions, requests));
56+
}
57+
58+
@Test
59+
public void test5() {
60+
restrictions = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[14,2],[1,8],[4,5],[16,6],[10,8],[10,3],[17,14],[13,2],[5,1],[0,4]," +
61+
"[8,12],[6,5],[7,9],[12,16],[17,16],[15,11],[5,7],[9,16],[14,7],[7,8],[2,7],[3,5],[9,13],[10,13],[2,3],[2,17],[12,3],[9,10],[15,4],[11,13]," +
62+
"[13,7],[7,1],[13,6],[10,11],[10,17],[11,2],[7,17],[0,10],[15,1],[9,3],[1,11],[11,0],[7,6],[8,0],[6,15],[0,13],[9,15],[5,11],[6,12],[17,15]," +
63+
"[2,12],[15,0],[4,7],[16,5],[9,5],[4,3],[12,5],[1,2],[13,5],[10,7],[12,15],[11,17],[12,0],[9,14],[17,12],[4,6],[13,15],[4,10],[11,7]," +
64+
"[8,5],[5,17],[8,3],[15,7],[13,12],[9,0],[17,3],[11,8],[8,16],[2,16],[4,12],[3,1],[8,14],[15,3],[14,11],[6,0],[12,7],[0,2],[0,7]," +
65+
"[5,14],[8,2],[13,17],[17,8],[4,13],[1,0],[7,16],[5,2],[9,11],[12,9],[16,3],[5,15],[2,15],[3,6],[17,9],[4,16],[4,2]");
66+
requests = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[12,0],[4,7],[9,0],[4,5],[4,6],[0,16],[2,15],[1,2],[12,15]," +
67+
"[16,6],[13,3],[2,12],[12,15],[9,15],[2,16],[1,8],[12,5],[2,16],[14,13],[9,13],[3,1],[13,16],[8,13],[9,16],[5,2],[4,14]," +
68+
"[9,10],[6,5],[5,7],[12,3],[8,2],[12,0],[0,17],[12,16],[9,15],[4,3],[11,7],[4,13],[4,6],[10,13],[14,12],[15,0],[9,6]," +
69+
"[4,10],[7,8],[4,3],[10,17],[4,10],[1,2],[11,12],[6,5],[5,2],[9,10],[14,7],[17,15],[2,17],[11,0],[14,0],[14,11]," +
70+
"[15,7],[13,6],[4,14],[0,4],[17,3],[11,17],[8,12],[6,11],[3,11],[17,15],[17,16],[4,5],[12,7],[0,17],[15,11],[0,4]," +
71+
"[10,16],[15,7],[14,12],[1,6],[11,13],[10,13],[0,5],[1,0],[10,11],[2,17],[1,11],[13,2],[0,5],[12,7],[17,14],[12,9]," +
72+
"[0,17],[15,10],[5,2],[16,6],[0,13],[17,6],[1,11],[13,17],[11,8],[0,16],[13,17],[6,11],[0,7],[13,12],[11,16],[8,13]," +
73+
"[17,6],[8,13],[9,8],[9,0],[17,16],[4,13]");
74+
expected = new boolean[]{false, false, false, false, false, true, false, false, false, false, true, false, false, false, false,
75+
false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false,
76+
false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false,
77+
true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false,
78+
false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false,
79+
false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false,
80+
true, false, false, false, false, false, false, false, false, false, false, false, false};
81+
n = 18;
82+
assertArrayEquals(expected, solution1.friendRequests(n, restrictions, requests));
83+
}
84+
}

0 commit comments

Comments
 (0)