[Swift]LeetCode821.字符的最短距离|ShortestDistancetoaCharacter

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

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

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

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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 }