[Swift]LeetCode821. 字符的最短距离 | Shortest Distance to a Character

it2022-05-06  7

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

Given a string S and a character C, return an array of integers representing the shortest distance from the character C in the string.

Example 1:

Input: S = "loveleetcode", C = 'e' Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0] 

Note:

S string length is in [1, 10000].C is a single character, and guaranteed to be in string S.All letters in S and C are lowercase.

给定一个字符串 S 和一个字符 C。返回一个代表字符串 S 中每个字符到字符串 S 中的字符 C 的最短距离的数组。

示例 1:

输入: S = "loveleetcode", C = 'e' 输出: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

说明:

字符串 S 的长度范围为 [1, 10000]。C 是一个单字符,且保证是字符串 S 里的字符。S 和 C 中的所有字母均为小写字母。

16ms

1 class Solution { 2 func shortestToChar(_ S: String, _ C: Character) -> [Int] { 3 var sArray = Array(S) 4 var ans = [Int]() 5 6 var prev = Int.min/2 7 for i in 0..<sArray.count { 8 let char = sArray[i] 9 if char == C { 10 prev = i 11 } 12 ans.append(i-prev) 13 } 14 prev = Int.max/2 15 for i in stride(from: sArray.count-1, through: 0, by: -1) { 16 let char = sArray[i] 17 if char == C { 18 prev = i 19 } 20 let minVal = min(ans[i], prev-i) 21 ans[i] = minVal 22 } 23 return ans 24 } 25 }

20ms

1 class Solution { 2 func shortestToChar(_ S: String, _ C: Character) -> [Int] { 3 var results = Array(repeating: 0, count: S.count) 4 5 var low = S.startIndex 6 let high = S.firstIndex(where: { $0 == C })! 7 8 while low < high { 9 results[low.encodedOffset] = high.encodedOffset - low.encodedOffset 10 11 low = S.index(after: low) 12 } 13 14 low = S.index(after: high) 15 16 while case let hi = S[low..<S.endIndex].firstIndex(where: { $0 == C }), 17 var hh = hi { 18 var value = 1 19 hh = S.index(before: hh) 20 while low < hh { 21 results[low.encodedOffset] = value 22 results[hh.encodedOffset] = value 23 low = S.index(after: low) 24 hh = S.index(before: hh) 25 value += 1 26 } 27 if low == hh { 28 results[hh.encodedOffset] = value 29 } 30 low = S.index(after: hi!) 31 32 if low == S.endIndex { 33 break 34 } 35 } 36 37 var value = 1 38 39 while low < S.endIndex { 40 results[low.encodedOffset] = value 41 value += 1 42 low = S.index(after: low) 43 } 44 45 return results 46 } 47 }
Runtime: 28 ms Memory Usage: 19.6 MB 1 class Solution { 2 func shortestToChar(_ S: String, _ C: Character) -> [Int] { 3 let num:Int = S.count 4 var res:[Int] = [Int](repeating:num,count:num) 5 var arrChar = Array(S) 6 for i in 0..<num 7 { 8 if arrChar[i] == C {res[i] = 0} 9 else if i > 0 10 { 11 res[i] = res[i - 1] + 1 12 } 13 } 14 for i in stride(from:num - 2,through:0,by:-1) 15 { 16 res[i] = min(res[i], res[i + 1] + 1) 17 } 18 return res 19 } 20 }

28ms

1 class Solution { 2 func shortestToChar(_ S: String, _ C: Character) -> [Int] { 3 var forward = 0 4 var backward = 0 5 var first = true 6 var result = [Int]() 7 for char in S { 8 forward += 1 9 if char == C { 10 while forward > 0 { 11 forward -= 1 12 backward += 1 13 if first { 14 result.append(forward) 15 } else { 16 result.append(min(forward, backward)) 17 } 18 } 19 forward = 0 20 backward = 0 21 first = false 22 } 23 } 24 while forward > 0 { 25 forward -= 1 26 backward += 1 27 result.append(backward) 28 } 29 return result 30 } 31 }

28ms

1 class Solution { 2 func shortestToChar(_ S: String, _ C: Character) -> [Int] { 3 var back = [Int]() 4 var left = -1 5 var right = -2 6 for (index,t) in S.enumerated() { 7 if t == C{ 8 if left < right { left = right } 9 if right < index { right = index } 10 for i in back.count...right{ 11 let r = right - i 12 if left == -1 { 13 back.append(r) 14 }else{ 15 let l = abs(left - i) 16 let m = min(l, r) 17 back.append(m) 18 } 19 } 20 } 21 } 22 if S.count - 1 > right { 23 for i in 1..<S.count - right{ 24 back.append(i) 25 } 26 } 27 return back 28 } 29 }

36ms

1 class Solution { 2 func shortestToChar(_ S: String, _ C: Character) -> [Int] { 3 var a = [Int]() 4 var indicies = [Int]() 5 for (i,c) in S.unicodeScalars.enumerated() { 6 if Character(c) == C { 7 indicies.append(i) 8 } 9 } 10 print(indicies) 11 for i in 0..<S.count { 12 var t = (-1,-1) 13 var f = false 14 for ind in indicies { 15 if i < ind { 16 if t.0 == -1 { 17 t.0 = -5 18 t.1 = ind 19 } else { 20 t.1 = ind 21 } 22 } 23 if i > ind { 24 t.0 = ind 25 } 26 if ind == i { 27 f = true 28 } 29 if t.0 != -1 && t.1 != -1 { 30 // print(t) 31 break 32 } 33 } 34 if f { 35 a.append(0) 36 } else if (t.0 == -1 && t.1 != -1) || t.0 == -5 { 37 a.append(abs(t.1-i)) 38 } else if t.1 == -1 && t.0 != -1 { 39 a.append(abs(t.0-i)) 40 } else { 41 let ind = min(abs(t.0-i), abs(t.1-i)) 42 a.append(ind) 43 } 44 } 45 46 return a 47 48 } 49 }

36ms

1 class Solution { 2 func shortestToChar(_ S: String, _ C: Character) -> [Int] { 3 let chars = Array(S) 4 let count = S.count 5 var res = Array(repeating: 0, count: count) 6 var currentPosition = -count 7 8 for i in 0..<count { 9 if chars[i] == C { 10 currentPosition = i 11 } 12 res[i] = i - currentPosition 13 } 14 15 for i in Array(0..<count).reversed() { 16 if chars[i] == C { 17 currentPosition = i 18 } 19 res[i] = min(res[i], abs(currentPosition - i)) 20 } 21 22 return res 23 } 24 }

52ms

1 class Solution { 2 func shortestToChar(_ S: String, _ C: Character) -> [Int] { 3 let occurances = S.enumerated() 4 .filter { (_, char) in return char == C } 5 .map { (index, _ ) in index } 6 7 var results: [Int] = Array(repeating: 0, count: S.count) 8 for (index, _) in S.enumerated() { 9 var result = Int.max 10 occurances.forEach { occurance in 11 let diff = abs(occurance - index) 12 result = min(diff, result) 13 } 14 15 results[index] = result 16 } 17 18 return results 19 } 20 }

 

 

转载于:https://www.cnblogs.com/strengthen/p/10567029.html


最新回复(0)