当前位置 : 主页 > 手机开发 > 其它 >

[Swift]LeetCode1182. 与目标颜色间的最短距离 | Shortest Distance to Target Color

来源:互联网 收集:自由互联 发布时间:2021-06-11
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ ?微信公众号:为敢(WeiGanTechnologies) ?博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/)

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
?微信公众号:为敢(WeiGanTechnologies)
?博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/)
?GitHub地址:https://github.com/strengthen/LeetCode
?原文地址:https://www.cnblogs.com/strengthen/p/11484246.html
?如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
?原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

You are given an array colors, in which there are three colors: 12 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:

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.

 

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

 

给你一个数组 colors,里面有  12、 3 三种颜色。

我们需要在 colors 上进行一些查询操作 queries,其中每个待查项都由两个整数 i 和 c 组成。

现在请你帮忙设计一个算法,查找从索引 i 到具有目标颜色 c 的元素之间的最短距离。

如果不存在解决方案,请返回 -1

 

示例 1:

输入:colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]
输出:[3,0,3]
解释: 
距离索引 1 最近的颜色 3 位于索引 4(距离为 3)。
距离索引 2 最近的颜色 2 就是它自己(距离为 0)。
距离索引 6 最近的颜色 1 位于索引 3(距离为 3)。

示例 2:

输入:colors = [1,2], queries = [[0,3]]
输出:[-1]
解释:colors 中没有颜色 3。

 

提示:

  • 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

Runtime: 1880 ms

Memory Usage: 28.9 MB
 1 class Solution {
 2     func shortestDistanceColor(_ colors: [Int], _ queries: [[Int]]) -> [Int] {
 3         let n:Int = colors.count
 4         var left:[[Int]] = [[Int]](repeating:[Int](repeating:-1,count:n),count:4)
 5         var right:[[Int]] = [[Int]](repeating:[Int](repeating:-1,count:n),count:4)
 6         for shade in 1...3
 7         {
 8             if colors[0] == shade
 9             {
10                 left[shade][0] = 0
11             }
12             for i in 1..<n
13             {
14                 if left[shade][i-1] != -1
15                 {
16                     left[shade][i] = left[shade][i-1] + 1
17                 }
18                 if colors[i] == shade
19                 {
20                     left[shade][i] = 0
21                 }
22             }
23         }
24         for shade in 1...3
25         {
26             if colors[n-1] == shade
27             {
28                 right[shade][n-1] = 0
29             }
30             for i in stride(from:n - 2,through:0,by:-1)
31             {
32                 if right[shade][i+1] != -1
33                 {
34                     right[shade][i] = right[shade][i+1] + 1
35                 }
36                 if colors[i] == shade
37                 {
38                     right[shade][i] = 0
39                 }
40             }
41         }
42         var result:[Int] = [Int]()
43         for query in queries
44         {
45             var index:Int = query[0]
46             var req_color = query[1]
47             var x:Int = left[req_color][index]
48             var y:Int = right[req_color][index]
49             var ans:Int = 0
50             if x == -1 || y == -1
51             {
52                 ans = max(x,y)
53             }
54             else
55             {
56                 ans = min(x,y)
57             }
58             result.append(ans)
59         }
60         return result
61     }
62 }
网友评论