[Swift]LeetCode1182. 与目标颜色间的最短距离 | Shortest Dist
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ You are given an array? You are also given some queries. Each query consists of two integers? ? 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 = [1,1]] 输出:[3,3] 解释: 距离索引 1 最近的颜色 3 位于索引 4(距离为 3)。 距离索引 2 最近的颜色 2 就是它自己(距离为 0)。 距离索引 6 最近的颜色 1 位于索引 3(距离为 3)。 示例 2: 输入:colors = [1,3]] 输出:[-1] 解释:colors 中没有颜色 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: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 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |