05 August 2008
给定一个数组颜色，其中有三种颜色：1、2 和 3。
还会收到一些查询。每个查询由两个整数 i 和 c 组成，返回给定索引 i 与目标颜色 c 之间的最短距离。如果没有解决方案返回-1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Example 1:
Input: colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]
Output: [3,0,3]
Explanation:
The nearest 3 from index 1 is at index 4 (3 steps away).
The nearest 2 from index 2 is at index 2 itself (0 steps away).
The nearest 1 from index 6 is at index 3 (3 steps away).
Example 2:
Input: colors = [1,2], queries = [[0,3]]
Output: [-1]
Explanation: There is no 3 in the array.
Pre Computed || DP || O(N + Q)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public List<Integer> shortestDistanceColor(int[] colors, int[][] queries) {
int len = colors.length;
int[][] dp = new int[len][4];
for (int i = 1; i < 4; i++) {
int[] left = new int[len];
int[] right = new int[len];
left[0] = i == colors[0] ? 0 : Integer.MAX_VALUE;
//finding minimum from left side
for (int j = 1; j < len; j++) {
if (i != colors[j])
left[j] = left[j - 1] != Integer.MAX_VALUE ? left[j - 1] + 1 : left[j - 1];
else
left[j] = 0;
}
right[len - 1] = i == colors[len - 1] ? 0 : Integer.MAX_VALUE;
dp[len - 1][i] = i == colors[len - 1] ? 0 : left[len - 1] == Integer.MAX_VALUE ? -1 : left[len - 1];
for (int j = len - 2; j >= 0; j--) {
if (i != colors[j])
right[j] = right[j + 1] != Integer.MAX_VALUE ? right[j + 1] + 1 : right[j + 1];
else
right[j] = 0;
int min = Math.min(left[j], right[j]);
dp[j][i] = min == Integer.MAX_VALUE ? -1 : min;
}
}
List<Integer> result = new ArrayList<>();
for (int[] query : queries) {
int idx = query[0];
int t = query[1];
result.add(dp[idx][t]);
}
return result;
}
}