在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ We are given an array 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 an array Suppose we chose a set of deletion indices Return the minimum possible value of Example 1: Input: 1
Explanation:
After deleting the first column, A = ["a", "b", "c"].
Now A is in lexicographic order (ie. A[0] <= A[1] <= A[2]).
We require at least 1 deletion since initially A was not in lexicographic order, so the answer is 1.
Example 2: Input: ["xc","yb","za"]
Output: 0
Explanation:
A is already in lexicographic order, so we don't need to delete anything.
Note that the rows of A are not necessarily in lexicographic order:
ie. it is NOT necessarily true that (A[0][0] <= A[0][1] <= ...)
Example 3: Input: 3
Explanation:
We have to delete every column.
Note:
给定由 选取一个删除索引序列,对于 比如,有 假设,我们选择了一组删除索引 示例 1: 输入:["ca","bb","ac"] 输出:1 解释: 删除第一列后,A = ["a", "b", "c"]。 现在 A 中元素是按字典排列的 (即,A[0] <= A[1] <= A[2])。 我们至少需要进行 1 次删除,因为最初 A 不是按字典序排列的,所以答案是 1。 示例 2: 输入:["xc","yb","za"] 输出:0 解释: A 的列已经是按字典序排列了,所以我们不需要删除任何东西。 注意 A 的行不需要按字典序排列。 也就是说,A[0][0] <= A[0][1] <= ... 不一定成立。 示例 3: 输入:["zyx","wvu","tsr"] 输出:3 解释: 我们必须删掉每一列。 提示:
72ms 1 class Solution { 2 func minDeletionSize(_ A: [String]) -> Int { 3 var n:Int = A.count 4 var ss:[String] = [String](repeating:"",count:n) 5 var ret:Int = 0 6 outer: 7 for i in 0..<A[0].count 8 { 9 for j in 0..<(n - 1) 10 { 11 if ss[j] == ss[j+1] && A[j][i] > A[j+1][i] 12 { 13 ret += 1 14 continue outer 15 } 16 } 17 for j in 0..<n 18 { 19 ss[j].append(A[j][i]) 20 } 21 } 22 23 return ret 24 } 25 } 26 27 extension String { 28 //subscript函数可以检索数组中的值 29 //直接按照索引方式截取指定索引的字符 30 subscript (_ i: Int) -> Character { 31 //读取字符 32 get {return self[index(startIndex, offsetBy: i)]} 33 34 } 35 } 100ms 1 class Solution { 2 func minDeletionSize(_ A: [String]) -> Int { 3 let R = A.count 4 guard A.count > 1 else { 5 return 0 6 } 7 let C = A[0].count 8 var del = [Int](repeating: 0, count: C) 9 var pc = [Int](repeating: 0, count: R) 10 for c in 0 ..< C { 11 var npc = [Int](repeating: 0, count: R) 12 for r in 1 ..< R { 13 let ic = A[r].index(A[r].startIndex, offsetBy: c) 14 let v = A[r][ic] < A[r-1][ic] ? 1 : A[r][ic] == A[r-1][ic] ? 0 : -1 15 npc[r] = pc[r] == -1 ? -1 : v 16 //print(A[r][ic], A[r-1][ic], v) 17 if npc[r] > 0 { 18 del[c] = 1 19 } 20 } 21 //print(pc, npc, del) 22 if del[c] == 0 { 23 pc = npc 24 } 25 } 26 return del.reduce(0, +) 27 } 28 }
|
请发表评论