Skip to content

Commit d14df37

Browse files
fishercoder1534fishercoder1534
committed
add 1182
1 parent ace9fba commit d14df37

File tree

3 files changed

+128
-0
lines changed

3 files changed

+128
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -72,6 +72,7 @@ _If you like this project, please leave me a star._ ★
7272
|1189|[Maximum Number of Balloons](https://leetcode.com/problems/maximum-number-of-balloons/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1189.java) |[:tv:](https://youtu.be/LGgMZC0vj5s) |Easy||
7373
|1185|[Day of the Week](https://leetcode.com/problems/day-of-the-week/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1185.java) | |Easy||
7474
|1184|[Distance Between Bus Stops](https://leetcode.com/problems/distance-between-bus-stops/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1184.java) | [:tv:](https://www.youtube.com/watch?v=RFq7yA5iyhI)|Easy||
75+
|1182|[Shortest Distance to Target Color](https://leetcode.com/problems/shortest-distance-to-target-color/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1182.java) ||Medium|Binary Search|
7576
|1180|[Count Substrings with Only One Distinct Letter](https://leetcode.com/problems/count-substrings-with-only-one-distinct-letter/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1180.java) | |Easy|Math, String|
7677
|1176|[Diet Plan Performance](https://leetcode.com/problems/diet-plan-performance/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1176.java) | |Easy|Array, Sliding Window|
7778
|1175|[Prime Arrangements](https://leetcode.com/problems/prime-arrangements/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1175.java) | |Easy||

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

Lines changed: 86 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,86 @@
1+
package com.fishercoder.solutions;
2+
3+
import java.util.ArrayList;
4+
import java.util.Collections;
5+
import java.util.Comparator;
6+
import java.util.HashMap;
7+
import java.util.List;
8+
import java.util.Map;
9+
10+
/**
11+
* 1182. Shortest Distance to Target Color
12+
*
13+
* You are given an array colors, in which there are three colors: 1, 2 and 3.
14+
* You are also given some queries. Each query consists of two integers i and c,
15+
* return the shortest distance between the given index i and the target color c. If there is no solution return -1.
16+
*
17+
* Example 1:
18+
* Input: colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]
19+
* Output: [3,0,3]
20+
* Explanation:
21+
* The nearest 3 from index 1 is at index 4 (3 steps away).
22+
* The nearest 2 from index 2 is at index 2 itself (0 steps away).
23+
* The nearest 1 from index 6 is at index 3 (3 steps away).
24+
*
25+
* Example 2:
26+
* Input: colors = [1,2], queries = [[0,3]]
27+
* Output: [-1]
28+
* Explanation: There is no 3 in the array.
29+
*
30+
* Constraints:
31+
* 1 <= colors.length <= 5*10^4
32+
* 1 <= colors[i] <= 3
33+
* 1 <= queries.length <= 5*10^4
34+
* queries[i].length == 2
35+
* 0 <= queries[i][0] < colors.length
36+
* 1 <= queries[i][1] <= 3
37+
* */
38+
public class _1182 {
39+
public static class Solution1 {
40+
public List<Integer> shortestDistanceColor(int[] colors, int[][] queries) {
41+
Map<Integer, List<Integer>> map = buildMap(colors);
42+
List<Integer> result = new ArrayList<>();
43+
for (int[] query : queries) {
44+
result.add(binarySearch(query[0], map.get(query[1])));
45+
}
46+
return result;
47+
}
48+
49+
private Integer binarySearch(int index, List<Integer> indices) {
50+
if (indices == null) {
51+
return -1;
52+
}
53+
int left = 0;
54+
int right = indices.size() - 1;
55+
int minDistance = Integer.MAX_VALUE;
56+
while (left <= right) {
57+
int mid = left + (right - left) / 2;
58+
if (indices.get(mid) == index) {
59+
return 0;
60+
} else if (indices.get(mid) > index) {
61+
minDistance = Math.min(minDistance, indices.get(mid) - index);
62+
right = mid - 1;
63+
} else {
64+
minDistance = Math.min(minDistance, index - indices.get(mid));
65+
left = mid + 1;
66+
}
67+
}
68+
return minDistance;
69+
}
70+
71+
private Map<Integer, List<Integer>> buildMap(int[] colors) {
72+
Map<Integer, List<Integer>> map = new HashMap<>();
73+
for (int i = 0; i < colors.length; i++) {
74+
if (!map.containsKey(colors[i])) {
75+
map.put(colors[i], new ArrayList<>());
76+
}
77+
map.get(colors[i]).add(i);
78+
}
79+
for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
80+
Collections.sort(entry.getValue());
81+
entry.setValue(entry.getValue());
82+
}
83+
return map;
84+
}
85+
}
86+
}

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

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

0 commit comments

Comments
 (0)