class Solution {
public:
int minDeletionSize(vector<string>& strs) {
}
};
955. 删列造序 II
给定由 n 个字符串组成的数组 strs，其中每个字符串长度相等。
选取一个删除索引序列，对于 strs 中的每个字符串，删除对应每个索引处的字符。
比如，有 strs = ["abcdef", "uvwxyz"]，删除索引序列 {0, 2, 3}，删除后 strs 为["bef", "vyz"]。
假设，我们选择了一组删除索引 answer，那么在执行删除操作之后，最终得到的数组的元素是按 字典序（strs[0] <= strs[1] <= strs[2] ... <= strs[n - 1]）排列的，然后请你返回 answer.length 的最小可能值。
示例 1：
输入：strs = ["ca","bb","ac"] 输出：1 解释： 删除第一列后，strs = ["a", "b", "c"]。 现在 strs 中元素是按字典排列的 (即，strs[0] <= strs[1] <= strs[2])。 我们至少需要进行 1 次删除，因为最初 strs 不是按字典序排列的，所以答案是 1。
示例 2：
输入：strs = ["xc","yb","za"] 输出：0 解释： strs 的列已经是按字典序排列了，所以我们不需要删除任何东西。 注意 strs 的行不需要按字典序排列。 也就是说，strs[0][0] <= strs[0][1] <= ... 不一定成立。
示例 3：
输入：strs = ["zyx","wvu","tsr"] 输出：3 解释： 我们必须删掉每一列。
提示：
n == strs.length1 <= n <= 1001 <= strs[i].length <= 100strs[i] 由小写英文字母组成原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 4.8 MB, 提交时间: 2023-09-05 22:19:54
func minDeletionSize(strs []string) int {
rows := len(strs)
cols := len(strs[0])
curs := make([]string, rows) // 维护已经排序的字符串
for x := 0; x < cols; x++ {
for y := 0; y < rows; y++ {
curs[y] += string(strs[y][x])
}
if isSorted(curs) == false {
for j := 0; j < rows; j++ {
curs[j] = curs[j][:len(curs[j])-1]
}
}
}
return cols - len(curs[0])
}
func isSorted(strs []string) bool {
for i := 1; i < len(strs); i++ {
if strs[i] < strs[i-1] {
return false
}
}
return true
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.7 MB, 提交时间: 2023-09-05 22:19:29
// 依次比较，遇到排序不符合的 删除那一行，从头再来
func minDeletionSize(A []string) int {
aL,subL,ret :=len(A),len(A[0]),0
if aL ==1 {
return 0
}
index:=make([]int,subL)
for i:=0;i<subL;i++ {
index[i]=i
}
j:=1
for j<aL{
if len(index) == 0{
break
}
ok,i := bigger(A[j-1],A[j],index)
if ok {
j++
}else {
index = append(index[0:i],index[i+1:]...)
ret++
j=1
}
}
return ret
}
func bigger(a,b string,index []int) (bool,int) {
for k,i:=range index {
if a[i] < b[i] {
return true,0
}else if a[i] > b[i] {
return false,k
}
}
return true,0
}
java 解法, 执行用时: 15 ms, 内存消耗: 43.1 MB, 提交时间: 2023-09-05 22:18:44
class Solution {
public int minDeletionSize(String[] A) {
int N = A.length;
int W = A[0].length();
int ans = 0;
// cur : all rows we have written
// For example, with A = ["abc","def","ghi"] we might have
// cur = ["ab", "de", "gh"].
String[] cur = new String[N];
for (int j = 0; j < W; ++j) {
// cur2 : What we potentially can write, including the
// newest column col = [A[i][j] for i]
// Eg. if cur = ["ab","de","gh"] and col = ("c","f","i"),
// then cur2 = ["abc","def","ghi"].
String[] cur2 = Arrays.copyOf(cur, N);
for (int i = 0; i < N; ++i)
cur2[i] += A[i].charAt(j);
if (isSorted(cur2))
cur = cur2;
else
ans++;
}
return ans;
}
public boolean isSorted(String[] A) {
for (int i = 0; i < A.length - 1; ++i)
if (A[i].compareTo(A[i+1]) > 0)
return false;
return true;
}
}
java 解法, 执行用时: 1 ms, 内存消耗: 39.6 MB, 提交时间: 2023-09-05 22:18:24
class Solution {
public int minDeletionSize(String[] A) {
int N = A.length;
int W = A[0].length();
// cuts[j] is true : we don't need to check any new A[i][j] <= A[i][j+1]
boolean[] cuts = new boolean[N-1];
int ans = 0;
search: for (int j = 0; j < W; ++j) {
// Evaluate whether we can keep this column
for (int i = 0; i < N-1; ++i)
if (!cuts[i] && A[i].charAt(j) > A[i+1].charAt(j)) {
// Can't keep the column - delete and continue
ans++;
continue search;
}
// Update 'cuts' information
for (int i = 0; i < N-1; ++i)
if (A[i].charAt(j) < A[i+1].charAt(j))
cuts[i] = true;
}
return ans;
}
}
python3 解法, 执行用时: 60 ms, 内存消耗: 16.1 MB, 提交时间: 2023-09-05 22:18:10
# 优化贪心
class Solution:
def minDeletionSize(self, A: List[str]):
# cuts[i] is True : we don't need to check col[i] <= col[i+1]
cuts = [False] * (len(A) - 1)
ans = 0
for col in zip(*A):
if all(cuts[i] or col[i] <= col[i+1] for i in range(len(col) - 1)):
for i in range(len(col) - 1):
if col[i] < col[i+1]:
cuts[i] = True
else:
ans += 1
return ans
python3 解法, 执行用时: 56 ms, 内存消耗: 16.2 MB, 提交时间: 2023-09-05 22:17:01
# 贪心
class Solution:
def minDeletionSize(self, A: List[int]):
def is_sorted(A):
return all(A[i] <= A[i+1] for i in range(len(A) - 1))
ans = 0
# cur : all rows we have written
# For example, with A = ["abc","def","ghi"] we might have
# cur = ["ab", "de", "gh"].
cur = [""] * len(A)
for col in zip(*A):
# cur2 : What we potentially can write, including the
# newest column 'col'.
# Eg. if cur = ["ab","de","gh"] and col = ("c","f","i"),
# then cur2 = ["abc","def","ghi"].
cur2 = cur[:]
for i, letter in enumerate(col):
cur2[i] = cur2[i] + letter
if is_sorted(cur2):
cur = cur2
else:
ans += 1
return ans