★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
?微信公众号:为敢(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: 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:
input: colors = [1,1,2,3,3],querIEs = [[1,[2,2],[6,1]]Output: [3,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,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
,里面有 1
、2
、 3
三种颜色。
我们需要在 colors
上进行一些查询 *** 作 querIEs
,其中每个待查项都由两个整数 i
和 c
组成。
现在请你帮忙设计一个算法,查找从索引 i
到具有目标颜色 c
的元素之间的最短距离。
如果不存在解决方案,请返回 -1
。
示例 1:
输入:colors = [1,1]]输出:[3,3]解释: 距离索引 1 最近的颜色 3 位于索引 4(距离为 3)。距离索引 2 最近的颜色 2 就是它自己(距离为 0)。距离索引 6 最近的颜色 1 位于索引 3(距离为 3)。
示例 2:
输入:colors = [1,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 MB1 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:4) 6 for shade in 1...3 7 { 8 if colors[0] == shade 9 {10 left[shade][0] = 011 }12 for i in 1..<n13 {14 if left[shade][i-1] != -115 {16 left[shade][i] = left[shade][i-1] + 117 }18 if colors[i] == shade19 {20 left[shade][i] = 021 }22 }23 }24 for shade in 1...325 {26 if colors[n-1] == shade27 {28 right[shade][n-1] = 029 }30 for i in strIDe(from:n - 2,through:0,by:-1)31 {32 if right[shade][i+1] != -133 {34 right[shade][i] = right[shade][i+1] + 135 }36 if colors[i] == shade37 {38 right[shade][i] = 039 }40 }41 }42 var result:[Int] = [Int]()43 for query in querIEs44 {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 = 050 if x == -1 || y == -151 {52 ans = max(x,y)53 }54 else55 {56 ans = min(x,y)57 }58 result.append(ans)59 }60 return result61 }62 }总结
以上是内存溢出为你收集整理的[Swift]LeetCode1182. 与目标颜色间的最短距离 | Shortest Distance to Target Color全部内容,希望文章能够帮你解决[Swift]LeetCode1182. 与目标颜色间的最短距离 | Shortest Distance to Target Color所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)