[Swift]LeetCode402.移掉K位数字|RemoveKDigits

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

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

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

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

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

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

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:

The length of num is less than 10002 and will be ≥ k.
The given num does not contain any leading zero.

Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。

注意:

num 的长度小于 10002 且 ≥ k。
num 不会包含任何前导零。

示例 1 :

输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。

示例 2 :

输入: num = "10200", k = 1
输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

示例 3 :

输入: num = "10", k = 2
输出: "0"
解释: 从原数字移除所有的数字，剩余为空就是0。

40ms

 1 class Solution {
 2     func removeKdigits(_ num: String, _ k: Int) -> String {
 3         let n = num.count
 4         if n == k { return "0" }
 5         var k = k
 6         var stack: [Character] = []
 7         let ca = Array(num)
 8         for i in 0..<n {
 9             while k > 0 && !stack.isEmpty && stack.last! > ca[i] {
10                 stack.removeLast()
11                 k -= 1
12             }
13             stack.append(ca[i])
14         }
15         
16         while k > 0 {
17             stack.removeLast()
18             k -= 1
19         }
20         
21         while !stack.isEmpty && stack[0] == "0" {
22             stack.removeFirst()
23         }
24         
25         return stack.isEmpty ? "0" : String(stack)
26     }
27 }

44ms

 1 class Solution {
 2     func removeKdigits(_ num: String, _ k: Int) -> String {
 3         var stack = [Character]()
 4         var removed = 0
 5         for digit in num {
 6             while removed < k && !stack.isEmpty && digit < stack.last! {
 7                 stack.removeLast()
 8                 removed += 1
 9             }
10             stack.append(digit)
11         }
12         while removed < k {
13             stack.removeLast()
14             removed += 1
15         }
16         stack = stack.reversed()
17         while let last = stack.last, last == Character("0") {
18             stack.removeLast()
19         }
20         guard !stack.isEmpty else {
21             return "0"
22         }
23         return String(stack.reversed())
24     }
25 }

52ms

 1 class Solution {
 2     func removeKdigits(_ num: String, _ k: Int) -> String {
 3         guard num.count > 0 && k > 0 else {
 4             return num
 5         }
 6         var num = num.map{ String($0) }        
 7         var stack = [String]()
 8         var k = k
 9         var i = 0
10         while i < num.count  {
11             while stack.count > 0 && num[i] < stack.last! && k > 0 {
12                 stack.removeLast()
13                 k -= 1
14             }            
15             stack.append(num[i])
16             i += 1
17         }        
18         while k > 0 && stack.count > 0 {
19             stack.removeLast()
20             k -= 1
21         }        
22         var j = 0 
23         while j < stack.count && stack[j] == "0" {
24             j += 1
25         }        
26         let result = Array(stack[j..<stack.count]).joined()        
27         return result.count == 0 || k > 0 ? "0" : result        
28     }
29 }

60ms

 1 class Solution {
 2     func removeKdigits(_ num: String, _ k: Int) -> String {
 3         if num.count == k { return "0" }
 4         var array = [Character](num)
 5         var stack = [Character]()
 6         var count = k
 7         for c in array {
 8             while stack.count > 0 && stack.last! > c && count > 0 {
 9                 stack.removeLast()
10                 count -= 1
11             }
12             stack.append(c)
13         }
14         while count > 0 {
15             stack.removeLast()
16             count -= 1
17         }
18         
19         while stack.count > 0 && stack.first! == "0" {
20             stack.removeFirst()
21         }
22         if stack.count == 0 {
23             return "0"
24         } else {
25             return String(stack)    
26         }       
27     }
28 }

84ms

 1 class Solution {
 2     func removeKdigits(_ num: String, _ k: Int) -> String {
 3 
 4         if num.isEmpty || num.count <= k {
 5             return "0"
 6         }
 7 
 8         var chars = Array(num)
 9         // var stack = Array(chars[0 ..< chars.count])
10         var k = k
11 
12         while k > 0 {
13             var idx = 0
14             while idx+1 < chars.count && charToInt(chars[idx]) <= charToInt(chars[idx+1]) {
15                 idx += 1
16             }
17             
18             if idx == chars.count-1 {
19                 chars.removeLast()
20             } else {
21                 chars.remove(at:idx)
22             }
23             
24             while chars.count > 0 && chars[0] == "0" {
25                 chars.removeFirst()
26             }
27             
28             if chars.count == 0 {
29                 return "0"
30             }
31 
32             k -= 1
33         }
34         
35         return String(chars)
36     }
37 
38     func charToInt(_ char:Character) -> Int {
39         return Int(String(char))!
40     }
41 }

100ms

 1 class Solution {
 2     func removeKdigits(_ num: String, _ k: Int) -> String {
 3     guard num.count > k else{
 4         return "0"
 5     }
 6     
 7     var stack : [Int] = []
 8     var k = k
 9     for char in num{
10         while k > 0 && !stack.isEmpty && stack.last! > int(of: char){
11             stack.removeLast()
12             k -= 1
13         }
14         if int(of: char) == 0 {
15             if !stack.isEmpty{
16                 stack.append(int(of: char))
17             }
18         }else{
19             stack.append(int(of: char))
20         }
21     }
22     
23     // there is a possibility in here that K is still greater than 1
24     var result = ""
25     for index in 0..<stack.count-k{
26         result.append("\(stack[index])")
27     }
28     
29     return result.count == 0 ? "0" : result
30   }
31 
32    func int(of char : Character)->Int{
33           return Int(String(char))!
34    }
35 }