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

[Swift]LeetCode880.索引处的解码字符串|DecodedStringatIndex

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

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

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

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

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

An encoded string S is given.  To find and write the decodedstring to a tape, the encoded string is read one character at a time and the following steps are taken:

  • If the character read is a letter, that letter is written onto the tape.
  • If the character read is a digit (say d), the entire current tape is repeatedly written d-1 more times in total.

Now for some encoded string S, and an index K, find and return the K-th letter (1 indexed) in the decoded string.

Example 1:

Input: S = 10
Output: 

Example 2:

Input: S = 5
Output: 

Example 3:

Input: S = 1
Output: 

Note:

  1. 2 <= S.length <= 100
  2. S will only contain lowercase letters and digits 2through 9.
  3. S starts with a letter.
  4. 1 <= K <= 10^9
  5. The decoded string is guaranteed to have less than 2^63 letters.

给定一个编码字符串 S。为了找出解码字符串并将其写入磁带,从编码字符串中每次读取一个字符,并采取以下步骤:

  • 如果所读的字符是字母,则将该字母写在磁带上。
  • 如果所读的字符是数字(例如 d),则整个当前磁带总共会被重复写 d-1 次。

现在,对于给定的编码字符串 S 和索引 K,查找并返回解码字符串中的第 K 个字母。 

示例 1:

输入:S = "leet2code3", K = 10
输出:"o"
解释:
解码后的字符串为 "leetleetcodeleetleetcodeleetleetcode"。
字符串中的第 10 个字母是 "o"。

示例 2:

输入:S = "ha22", K = 5
输出:"h"
解释:
解码后的字符串为 "hahahaha"。第 5 个字母是 "h"。

示例 3:

输入:S = "a2345678999999999999999", K = 1
输出:"a"
解释:
解码后的字符串为 "a" 重复 8301530446056247680 次。第 1 个字母是 "a"。 

提示:

  1. 2 <= S.length <= 100
  2. S 只包含小写字母与数字 2 到 9 。
  3. S 以字母开头。
  4. 1 <= K <= 10^9
  5. 解码后的字符串保证少于 2^63 个字母。

Runtime: 4 ms
Memory Usage: 19.6 MB
 1 class Solution {
 2     func decodeAtIndex(_ S: String, _ K: Int) -> String {
 3         var K = K
 4         var N:Int = 0
 5         var arrS:[Character] = Array(S)
 6         var countS:Int = S.count < K ? S.count : K        
 7         for i in 0..<countS
 8         {
 9             let num:Int = arrS[i].ascii
10             N = num >= 48 && num <= 57 ? N * (num - 48) : N + 1
11         }
12         var i = countS - 1
13         while (true)
14         {
15             let num:Int = arrS[i].ascii
16             if num >= 48 && num <= 57
17             {
18                 N /= num - 48
19                 K %= N
20             }
21             else if K % N == 0
22             {
23                 return String(arrS[i])
24             }
25             else
26             {
27                 N -= 1
28             }
29             i -= 1
30         }
31         return String()
32     }
33 }
34 
35 //Character扩展
36 extension Character  
37 {  
38   //Character转ASCII整数值(定义小写为整数值)
39    var ascii: Int {
40        get {
41            return Int(self.unicodeScalars.first?.value ?? 0)
42        }       
43     }
44 }

4ms

 1 class Solution {
 2     func decodeAtIndex(_ S: String, _ K: Int) -> String {
 3         var stack: [Character] = []
 4         
 5         var charCount: Int = 0 
 6         var movingIndex: Int = 0 
 7         var S = Array(S)
 8         
 9         while movingIndex < S.count && charCount < K {
10             let character = S[movingIndex]
11             if character.isDigit() {
12                 charCount *= character.toDigit() 
13             } else {
14                 charCount += 1
15             }
16             movingIndex += 1
17         }
18         var k = K 
19         while movingIndex > 0 {
20             movingIndex -= 1 
21             let character = S[movingIndex]
22             if character.isDigit() {
23                 charCount /= character.toDigit() 
24                 k %= charCount 
25             } else {
26                 if k == 0 || k == charCount {
27                     return String(character)
28                 }
29                 charCount -= 1 
30             }
31         }
32         
33         return "" 
34     }
35 }
36 
37 extension Character {
38     func isDigit() -> Bool {
39         return Int(String(self)) != nil 
40     }
41     
42     func toDigit() -> Int {
43         return Int(String(self))!
44     }
45 }

12ms

 1 class Solution {
 2     let digiSets = Set<Character>("123456789")
 3     func decodeAtIndex(_ S: String, _ K: Int) -> String {
 4         if K == 0 {
 5             if !digiSets.contains(S.last!) { return String(S.last!) }
 6             return decodeAtIndex(String(S.dropLast()), K)
 7         }
 8 
 9         var lastStr = [Character]()
10         var lastCount = 0, curCount = 0
11         var chars = Array(S)
12         for i in chars.indices {
13             if digiSets.contains(chars[i]) {
14                 curCount *= Int(String(chars[i]))!
15                 if curCount >= K { return decodeAtIndex(String(lastStr), K % lastCount)}
16             }
17             else {
18                 curCount += 1
19                 if curCount == K  { return String(chars[i]) }
20             }
21             lastStr.append(chars[i])
22             lastCount = curCount
23         }
24         return ""
25     }
26 }

20ms

 1 class Solution {
 2     func decodeAtIndex(_ S: String, _ K: Int) -> String {        
 3         func isNum(_ char: Character) -> Bool {
 4             if char == "2" || char == "3" || char == "4" || char == "5" || char == "6" || char == "7" || char == "8" || char == "9" {
 5                 return true
 6             }
 7             return false
 8         }
 9         var size = 0, k = K
10         for char in S {
11             if isNum(char) {
12                 let str = String(char)
13                 size *= (Int(str) ?? 1-1)
14             } else {
15                 size += 1
16             }
17         }
18         for item in S.reversed() {
19             k %= size
20             if k == 0  && !isNum(item) {
21                 return String(item)
22             }
23             if isNum(item) {
24                 let str = String(item)
25                 size /= (Int(str) ?? 1)
26             } else {
27                 size -= 1
28             }
29         }
30         return ""        
31     }
32 }

 


鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
上一篇:
用swift开发自己的MacOS锁屏软件(3)发布时间:2022-07-13
下一篇:
iOS swift项目IM实现,从长连接到底层数据解析分析之Socket发布时间: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