[Swift]LeetCode944.删除列以使之有序|DeleteColumnstoMakeSorted

OGeek|极客世界-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

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

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

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

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

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

We are given an array A of N lowercase letter strings, all of the same length.

Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.

For example, if we have a string "abcdef" and deletion indices {0, 2, 3}, then the final string after deletion is "bef".

Suppose we chose a set of deletion indices D such that after deletions, each remaining column in A is in non-decreasing sorted order.

Formally, the c-th column is [A[0][c], A[1][c], ..., A[A.length-1][c]]

Return the minimum possible value of D.length.

Example 1:

Input: 1

Example 2:

Input: 0

Example 3:

Input: 3

Note:

1 <= A.length <= 100
1 <= A[i].length <= 1000

给出由 N 个小写字母串组成的数组 A，所有小写字母串的长度都相同。

现在，我们可以选择任何一组删除索引，对于每个字符串，我们将删除这些索引中的所有字符。

举个例子，如果字符串为 "abcdef"，且删除索引是 {0, 2, 3}，那么删除之后的最终字符串为 "bef"。

假设我们选择了一组删除索引 D，在执行删除操作之后，A 中剩余的每一列都是有序的。

形式上，第 c 列为 [A[0][c], A[1][c], ..., A[A.length-1][c]]

返回 D.length 的最小可能值。

示例 1：

输入：["cba","daf","ghi"]
输出：1

示例 2：

输入：["a","b"]
输出：0

示例 3：

输入：["zyx","wvu","tsr"]
输出：3

提示：

1 <= A.length <= 100
1 <= A[i].length <= 1000

232ms

 1 class Solution {
 2   func minDeletionSize(_ A: [String]) -> Int {
 3     var dl = 0
 4     var Ab : [[UInt8]] = []
 5     for var s in A {
 6       Ab.append(Array<UInt8>(s.utf8))
 7     }
 8     for var i in 0..<Ab[0].count {
 9       for var j in 0..<A.count-1 {
10         if Ab[j][i] > Ab[j+1][i] {
11           dl += 1
12           break
13         }
14       } 
15     }
16     return dl
17   }
18 }

264ms

 1 class Solution {
 2     func minDeletionSize(_ A: [String]) -> Int {
 3         guard A.count > 1 else { return 0 }
 4         var minSet = Set<Int>()
 5         for i in 0..<A.count-1 {
 6             let strArr = Array(A[i])
 7             let strArr2 = Array(A[i+1])
 8             for k in 0..<strArr.count {
 9                 if strArr[k] > strArr2[k] {
10                     minSet.insert(k)
11                 }
12             }
13         }
14         return minSet.count
15     }
16 }

272ms

 1 class Solution {
 2     func minDeletionSize(_ A: [String]) -> Int {
 3         var chars: [[Character]] = []
 4         chars = A.map { Array($0) }
 5         let numColumns = A.first!.count
 6         var count = 0
 7         for i in 0..<numColumns {
 8             inner: for j in 1..<chars.count {
 9                 if chars[j][i] < chars[j - 1][i] {
10                     count += 1
11                     break inner
12                 }
13             }
14         }
15         return count
16     }
17 }

280ms

 1 class Solution {
 2   func minDeletionSize(_ A: [String]) -> Int {
 3     var deleteCount = 0
 4     
 5     var arr = [[Character]]()
 6     for i in 0..<A.count {
 7       arr.append(Array(A[i]))
 8     }
 9     
10     for i in 0..<arr[0].count {
11       for j in 1..<arr.count {
12         if arr[j-1][i] > arr[j][i] {
13           deleteCount += 1
14           break
15         }
16       }
17     }
18     return deleteCount
19   }
20 }

384ms

 1 class Solution {
 2     func minDeletionSize(_ A: [String]) -> Int {
 3        var d_size = [Int]()
 4     for index_a in A.indices {
 5         if (index_a+1) < A.count {
 6             let a_s1 = Array(A[index_a])
 7             let a_s2 = Array(A[index_a+1])
 8             for s_i in 0..<a_s1.count {
 9                 if String(a_s1[s_i]) > String(a_s2[s_i]) && !d_size.contains(s_i)  {
10                     d_size.append(s_i)
11                 }
12             }
13         }
14         
15     }
16     return d_size.count 
17     }
18 }