Halo

A magic place for coding

0%

LeetCode解题报告（481）-- 1182. Shortest Distance to Target Color

Posted on Edited on Valine:

Problem

You are given an array colors, in which there are three colors: 1, 2 and 3.

You are also given some queries. Each query consists of two integers i and c, return the shortest distance between the given index i and the target color c. If there is no solution return -1.

Example 1:

1
2
3
4
5
6
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:

1
2
3
Input: colors = [1,2], queries = [[0,3]]
Output: [-1]
Explanation: There is no 3 in the array.

Constraints:

  • 1 <= colors.length <= 5*10^4
  • 1 <= colors[i] <= 3
  • 1 <= queries.length <= 5*10^4
  • queries[i].length == 2
  • 0 <= queries[i][0] < colors.length
  • 1 <= queries[i][1] <= 3

Analysis

  题目给出一个colors数组代表每个位置的颜色，然后还有一个queries数组，里面每个query包括[i, c]，代表查找距离i位置最近的颜色c的距离，要求返回查询的答案。实际上这道题目可以转化为，求每个位置上距离三种颜色最近的距离各是多少，如果我们计算出来这个的话，每个query都可以很快计算出来。

  距离某个位置最近，只有两种可能，一个在左边，一个在右边，所以需要两次处理，我们先来计算color在位置i的右边的情况，左边是同理的。我们用一个大小为3的rightMost数组表示每个颜色当前出现过最靠右边的坐标（coding时再加上1，是为了更新方便），这个数组的意义是这个下标左边的位置就不需要care了，因为所有小于这个下标的位置计算右边的距离时，最短距离不可能超过这个数组。比如exmaple1中，遍历到i = 4之后，rightMost = [3, 2, 4]，但是上面说到coding时加1，所以应该是rightMost=[4, 3, 5]，也就是说当下标小于4时，如果计算下标右边与颜色1的距离，最短的距离肯定是和4 - 1 = 3去计算，当下标小于3时，如果计算下标右边与颜色2的距离，最短的距离肯定是和3 - 1 = 2去计算，当下标小于5时，如果计算下标右边与颜色3的距离，最短的距离肯定是和5 - 1 = 4去计算。那么当处理i = 5时，color是2，所以我们要把从位置[3, 5]与color 2的距离都更新一遍。

  同理，处理color在位置i左边的情况，我们可以用一个大小为3的leftMost数组，这里在更新时就需要注意取一个极小值，实际的意义就是对于某个位置i，看看是在它的左边找到color比较近，还是在它的右边找到color比较近。

Solution

  无。

Code

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
class Solution {
public:
    vector<int> shortestDistanceColor(vector<int>& colors, vector<vector<int>>& queries) {
        int size = colors.size();
        vector<int> rightMost(3, 0);
        vector<int> leftMost(3, size - 1);
        vector<vector<int>> distance(3, vector<int>(size, -1));
    
        for (int i = 0; i < size; ++i) {
            int color = colors[i] - 1;
            for (int j = rightMost[color]; j < i + 1; j++) {
                distance[color][j] = i - j;
            }
            rightMost[color] = i + 1;
        }
        
        for (int i = size - 1; i >= 0; --i) {
            int color = colors[i] - 1;
            for (int j = leftMost[color]; j > i - 1 ; --j) {
                if (distance[color][j] == -1 || distance[color][j] > j - i) {
                    distance[color][j] = j - i;
                }
            }
            leftMost[color] = i - 1;
        }
        
        vector<int> result;
        for (vector<int> &query: queries) {
            result.push_back(distance[query[1] - 1][query[0]]);
        }
        return result;
    }
};

Summary

  这道题目有点像dp但又不是很典型的dp，可以直接理解为用两个数组先存储左右两边的信息，再计算。这道题目的分享到这里，感谢你的支持！

Welcome to my other publishing channels