• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode1182.与目标颜色间的最短距离|ShortestDistancetoTargetColor ...

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

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

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
openstackswift节点安装手册2-创建rings发布时间:2022-07-13
下一篇:
iOSSwift3open发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap