Skip to content

Commit a33018a

Browse files
ThanhNITThanhNIT
authored
Added tasks 2101, 2102, 2103, 2104, 2105.
1 parent 746051e commit a33018a

File tree

15 files changed

+683
-0
lines changed

15 files changed

+683
-0
lines changed

‎src/main/java/g2101_2200/s2101_detonate_the_maximum_bombs/Solution.java

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
package g2101_2200.s2101_detonate_the_maximum_bombs;
2+
3+
// #Medium #Array #Math #Depth_First_Search #Breadth_First_Search #Graph #Geometry
4+
// #2022_05_31_Time_27_ms_(94.17%)_Space_49.6_MB_(48.45%)
5+
6+
import java.util.ArrayList;
7+
import java.util.Arrays;
8+
import java.util.List;
9+
10+
public class Solution {
11+
public int maximumDetonation(int[][] bombs) {
12+
int n = bombs.length;
13+
List<Integer>[] graph = new List[n];
14+
for (int i = 0; i < n; i++) {
15+
graph[i] = new ArrayList<>();
16+
}
17+
for (int i = 0; i < n; i++) {
18+
for (int j = i + 1; j < n; j++) {
19+
double dx = bombs[i][0] - (double) bombs[j][0];
20+
double dy = bombs[i][1] - (double) bombs[j][1];
21+
double r1 = bombs[i][2];
22+
double r2 = bombs[j][2];
23+
double dist = dx * dx + dy * dy;
24+
if (dist <= r1 * r1) {
25+
graph[i].add(j);
26+
}
27+
if (dist <= r2 * r2) {
28+
graph[j].add(i);
29+
}
30+
}
31+
}
32+
boolean[] visited = new boolean[n];
33+
int ans = 0;
34+
for (int i = 0; i < n; i++) {
35+
ans = Math.max(ans, dfs(graph, i, visited));
36+
if (ans == n) {
37+
return ans;
38+
}
39+
Arrays.fill(visited, false);
40+
}
41+
return ans;
42+
}
43+
44+
private int dfs(List<Integer>[] graph, int i, boolean[] visited) {
45+
int cc = 0;
46+
if (visited[i]) {
47+
return 0;
48+
}
49+
visited[i] = true;
50+
for (int neigh : graph[i]) {
51+
cc += dfs(graph, neigh, visited);
52+
}
53+
return cc + 1;
54+
}
55+
}

‎src/main/java/g2101_2200/s2101_detonate_the_maximum_bombs/readme.md

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
2101\. Detonate the Maximum Bombs
2+
3+
Medium
4+
5+
You are given a list of bombs. The **range** of a bomb is defined as the area where its effect can be felt. This area is in the shape of a **circle** with the center as the location of the bomb.
6+
7+
The bombs are represented by a **0-indexed** 2D integer array `bombs` where <code>bombs[i] = [x<sub>i</sub>, y<sub>i</sub>, r<sub>i</sub>]</code>. <code>x<sub>i</sub></code> and <code>y<sub>i</sub></code> denote the X-coordinate and Y-coordinate of the location of the <code>i<sup>th</sup></code> bomb, whereas <code>r<sub>i</sub></code> denotes the **radius** of its range.
8+
9+
You may choose to detonate a **single** bomb. When a bomb is detonated, it will detonate **all bombs** that lie in its range. These bombs will further detonate the bombs that lie in their ranges.
10+
11+
Given the list of `bombs`, return _the **maximum** number of bombs that can be detonated if you are allowed to detonate **only one** bomb_.
12+
13+
**Example 1:**
14+
15+
![](https://assets.leetcode.com/uploads/2021/11/06/desmos-eg-3.png)
16+
17+
**Input:** bombs = [[2,1,3],[6,1,4]]
18+
19+
**Output:** 2
20+
21+
**Explanation:**
22+
23+
The above figure shows the positions and ranges of the 2 bombs.
24+
25+
If we detonate the left bomb, the right bomb will not be affected.
26+
27+
But if we detonate the right bomb, both bombs will be detonated.
28+
29+
So the maximum bombs that can be detonated is max(1, 2) = 2.
30+
31+
**Example 2:**
32+
33+
![](https://assets.leetcode.com/uploads/2021/11/06/desmos-eg-2.png)
34+
35+
**Input:** bombs = [[1,1,5],[10,10,5]]
36+
37+
**Output:** 1
38+
39+
**Explanation:** Detonating either bomb will not detonate the other bomb, so the maximum number of bombs that can be detonated is 1.
40+
41+
**Example 3:**
42+
43+
![](https://assets.leetcode.com/uploads/2021/11/07/desmos-eg1.png)
44+
45+
**Input:** bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]
46+
47+
**Output:** 5
48+
49+
**Explanation:** The best bomb to detonate is bomb 0 because:
50+
51+
- Bomb 0 detonates bombs 1 and 2. The red circle denotes the range of bomb 0.
52+
53+
- Bomb 2 detonates bomb 3. The blue circle denotes the range of bomb 2.
54+
55+
- Bomb 3 detonates bomb 4. The green circle denotes the range of bomb 3.
56+
57+
Thus all 5 bombs are detonated.
58+
59+
**Constraints:**
60+
61+
* `1 <= bombs.length <= 100`
62+
* `bombs[i].length == 3`
63+
* <code>1 <= x<sub>i</sub>, y<sub>i</sub>, r<sub>i</sub> <= 10<sup>5</sup></code>

‎src/main/java/g2101_2200/s2102_sequentially_ordinal_rank_tracker/SORTracker.java

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
package g2101_2200.s2102_sequentially_ordinal_rank_tracker;
2+
3+
// #Hard #Design #Heap_Priority_Queue #Ordered_Set #Data_Stream
4+
// #2022_05_31_Time_194_ms_(79.48%)_Space_79.6_MB_(69.32%)
5+
6+
import java.util.TreeSet;
7+
8+
public class SORTracker {
9+
static class Location {
10+
String name;
11+
int score;
12+
13+
public Location(String name, int score) {
14+
this.name = name;
15+
this.score = score;
16+
}
17+
18+
public String getName() {
19+
return name;
20+
}
21+
22+
public int getScore() {
23+
return score;
24+
}
25+
}
26+
27+
TreeSet<Location> tSet1;
28+
TreeSet<Location> tSet2;
29+
30+
public SORTracker() {
31+
tSet1 =
32+
new TreeSet<>(
33+
(a, b) -> {
34+
if (a.score != b.score) {
35+
return b.getScore() - a.getScore();
36+
} else {
37+
return a.getName().compareTo(b.getName());
38+
}
39+
});
40+
41+
tSet2 =
42+
new TreeSet<>(
43+
(a, b) -> {
44+
if (a.score != b.score) {
45+
return b.getScore() - a.getScore();
46+
} else {
47+
return a.getName().compareTo(b.getName());
48+
}
49+
});
50+
}
51+
52+
public void add(String name, int score) {
53+
tSet1.add(new Location(name, score));
54+
tSet2.add(tSet1.pollLast());
55+
}
56+
57+
public String get() {
58+
Location res = tSet2.pollFirst();
59+
tSet1.add(res);
60+
assert res != null;
61+
return res.name;
62+
}
63+
}

‎src/main/java/g2101_2200/s2102_sequentially_ordinal_rank_tracker/readme.md

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
2102\. Sequentially Ordinal Rank Tracker
2+
3+
Hard
4+
5+
A scenic location is represented by its `name` and attractiveness `score`, where `name` is a **unique** string among all locations and `score` is an integer. Locations can be ranked from the best to the worst. The **higher** the score, the better the location. If the scores of two locations are equal, then the location with the **lexicographically smaller** name is better.
6+
7+
You are building a system that tracks the ranking of locations with the system initially starting with no locations. It supports:
8+
9+
* **Adding** scenic locations, **one at a time**.
10+
* **Querying** the <code>i<sup>th</sup></code> **best** location of **all locations already added**, where `i` is the number of times the system has been queried (including the current query).
11+
* For example, when the system is queried for the <code>4<sup>th</sup></code> time, it returns the <code>4<sup>th</sup></code> best location of all locations already added.
12+
13+
Note that the test data are generated so that **at any time**, the number of queries **does not exceed** the number of locations added to the system.
14+
15+
Implement the `SORTracker` class:
16+
17+
* `SORTracker()` Initializes the tracker system.
18+
* `void add(string name, int score)` Adds a scenic location with `name` and `score` to the system.
19+
* `string get()` Queries and returns the <code>i<sup>th</sup></code> best location, where `i` is the number of times this method has been invoked (including this invocation).
20+
21+
**Example 1:**
22+
23+
**Input** ["SORTracker", "add", "add", "get", "add", "get", "add", "get", "add", "get", "add", "get", "get"] [[], ["bradford", 2], ["branford", 3], [], ["alps", 2], [], ["orland", 2], [], ["orlando", 3], [], ["alpine", 2], [], []]
24+
25+
**Output:** [null, null, null, "branford", null, "alps", null, "bradford", null, "bradford", null, "bradford", "orland"]
26+
27+
**Explanation:**
28+
29+
SORTracker tracker = new SORTracker(); // Initialize the tracker system.
30+
tracker.add("bradford", 2); // Add location with name="bradford" and score=2 to the system.
31+
tracker.add("branford", 3); // Add location with name="branford" and score=3 to the system.
32+
tracker.get(); // The sorted locations, from best to worst, are: branford, bradford.
33+
// Note that branford precedes bradford due to its **higher score** (3 > 2).
34+
// This is the 1<sup>st</sup> time get() is called, so return the best location: "branford".
35+
tracker.add("alps", 2); // Add location with name="alps" and score=2 to the system.
36+
tracker.get(); // Sorted locations: branford, alps, bradford.
37+
// Note that alps precedes bradford even though they have the same score (2).
38+
// This is because "alps" is **lexicographically smaller** than "bradford".
39+
// Return the 2<sup>nd</sup> best location "alps", as it is the 2<sup>nd</sup> time get() is called.
40+
tracker.add("orland", 2); // Add location with name="orland" and score=2 to the system.
41+
tracker.get(); // Sorted locations: branford, alps, bradford, orland.
42+
// Return "bradford", as it is the 3<sup>rd</sup> time get() is called.
43+
tracker.add("orlando", 3); // Add location with name="orlando" and score=3 to the system.
44+
tracker.get(); // Sorted locations: branford, orlando, alps, bradford, orland.
45+
// Return "bradford".
46+
tracker.add("alpine", 2); // Add location with name="alpine" and score=2 to the system.
47+
tracker.get(); // Sorted locations: branford, orlando, alpine, alps, bradford, orland.
48+
// Return "bradford".
49+
tracker.get();
50+
// Sorted locations: branford, orlando, alpine, alps, bradford, orland.
51+
// Return "orland".
52+
53+
**Constraints:**
54+
55+
* `name` consists of lowercase English letters, and is unique among all locations.
56+
* `1 <= name.length <= 10`
57+
* <code>1 <= score <= 10<sup>5</sup></code>
58+
* At any time, the number of calls to `get` does not exceed the number of calls to `add`.
59+
* At most <code>4 * 10<sup>4</sup></code> calls **in total** will be made to `add` and `get`.

‎src/main/java/g2101_2200/s2103_rings_and_rods/Solution.java

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package g2101_2200.s2103_rings_and_rods;
2+
3+
// #Easy #String #Hash_Table #2022_05_31_Time_2_ms_(46.84%)_Space_42.2_MB_(29.77%)
4+
5+
import java.util.HashMap;
6+
import java.util.Map;
7+
8+
public class Solution {
9+
public int countPoints(String rings) {
10+
Map<Integer, Integer> redHashMap = new HashMap<>();
11+
Map<Integer, Integer> greenHashMap = new HashMap<>();
12+
Map<Integer, Integer> blueHashMap = new HashMap<>();
13+
for (int i = 0; i <= rings.length() - 2; i = i + 2) {
14+
char charOne = rings.charAt(i);
15+
char charTwo = rings.charAt(i + 1);
16+
17+
if (charOne == 'R') {
18+
redHashMap.put(Character.getNumericValue(charTwo), 123);
19+
} else if (charOne == 'G') {
20+
greenHashMap.put(Character.getNumericValue(charTwo), 123);
21+
} else {
22+
blueHashMap.put(Character.getNumericValue(charTwo), 123);
23+
}
24+
}
25+
int result = 0;
26+
for (int i = 0; i <= 9; i++) {
27+
if (redHashMap.containsKey(i)
28+
&& greenHashMap.containsKey(i)
29+
&& blueHashMap.containsKey(i)) {
30+
result++;
31+
}
32+
}
33+
return result;
34+
}
35+
}

‎src/main/java/g2101_2200/s2103_rings_and_rods/readme.md

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
2103\. Rings and Rods
2+
3+
Easy
4+
5+
There are `n` rings and each ring is either red, green, or blue. The rings are distributed **across ten rods** labeled from `0` to `9`.
6+
7+
You are given a string `rings` of length `2n` that describes the `n` rings that are placed onto the rods. Every two characters in `rings` forms a **color-position pair** that is used to describe each ring where:
8+
9+
* The **first** character of the <code>i<sup>th</sup></code> pair denotes the <code>i<sup>th</sup></code> ring's **color** (`'R'`, `'G'`, `'B'`).
10+
* The **second** character of the <code>i<sup>th</sup></code> pair denotes the **rod** that the <code>i<sup>th</sup></code> ring is placed on (`'0'` to `'9'`).
11+
12+
For example, `"R3G2B1"` describes `n == 3` rings: a red ring placed onto the rod labeled 3, a green ring placed onto the rod labeled 2, and a blue ring placed onto the rod labeled 1.
13+
14+
Return _the number of rods that have **all three colors** of rings on them._
15+
16+
**Example 1:**
17+
18+
![](https://assets.leetcode.com/uploads/2021/11/23/ex1final.png)
19+
20+
**Input:** rings = "B0B6G0R6R0R6G9"
21+
22+
**Output:** 1
23+
24+
**Explanation:**
25+
26+
- The rod labeled 0 holds 3 rings with all colors: red, green, and blue.
27+
28+
- The rod labeled 6 holds 3 rings, but it only has red and blue.
29+
30+
- The rod labeled 9 holds only a green ring.
31+
32+
Thus, the number of rods with all three colors is 1.
33+
34+
**Example 2:**
35+
36+
![](https://assets.leetcode.com/uploads/2021/11/23/ex2final.png)
37+
38+
**Input:** rings = "B0R0G0R9R0B0G0"
39+
40+
**Output:** 1
41+
42+
**Explanation:**
43+
44+
- The rod labeled 0 holds 6 rings with all colors: red, green, and blue.
45+
46+
- The rod labeled 9 holds only a red ring.
47+
48+
Thus, the number of rods with all three colors is 1.
49+
50+
**Example 3:**
51+
52+
**Input:** rings = "G4"
53+
54+
**Output:** 0
55+
56+
**Explanation:** Only one ring is given. Thus, no rods have all three colors.
57+
58+
**Constraints:**
59+
60+
* `rings.length == 2 * n`
61+
* `1 <= n <= 100`
62+
* `rings[i]` where `i` is **even** is either `'R'`, `'G'`, or `'B'` (**0-indexed**).
63+
* `rings[i]` where `i` is **odd** is a digit from `'0'` to `'9'` (**0-indexed**).

‎src/main/java/g2101_2200/s2104_sum_of_subarray_ranges/Solution.java

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
package g2101_2200.s2104_sum_of_subarray_ranges;
2+
3+
// #Medium #Array #Stack #Monotonic_Stack #2022_05_31_Time_21_ms_(77.85%)_Space_46.4_MB_(23.68%)
4+
5+
import java.util.ArrayDeque;
6+
import java.util.Deque;
7+
8+
public class Solution {
9+
public long subArrayRanges(int[] nums) {
10+
int n = nums.length;
11+
long sum = 0;
12+
Deque<Integer> q = new ArrayDeque<>();
13+
14+
q.add(-1);
15+
for (int i = 0; i <= n; i++) {
16+
while (q.peekLast() != -1 && (i == n || nums[q.peekLast()] <= nums[i])) {
17+
int cur = q.removeLast();
18+
int left = q.peekLast();
19+
int right = i;
20+
sum += 1L * (cur - left) * (right - cur) * nums[cur];
21+
}
22+
q.add(i);
23+
}
24+
25+
q.clear();
26+
q.add(-1);
27+
for (int i = 0; i <= n; i++) {
28+
while (q.peekLast() != -1 && (i == n || nums[q.peekLast()] >= nums[i])) {
29+
int cur = q.removeLast();
30+
int left = q.peekLast();
31+
int right = i;
32+
sum -= 1L * (cur - left) * (right - cur) * nums[cur];
33+
}
34+
q.add(i);
35+
}
36+
return sum;
37+
}
38+
}

0 commit comments

Comments
 (0)