題目:
給定由 N 個(gè)小寫字母字符串組成的數(shù)組 A,其中每個(gè)字符串長度相等。
你需要選出一組要?jiǎng)h掉的列 D,對(duì) A 執(zhí)行刪除操作,使 A 中剩余的每一列都是 非降序 排列的,然后請(qǐng)你返回 D.length 的最小可能值。
刪除 操作的定義是:選出一組要?jiǎng)h掉的列,刪去 A 中對(duì)應(yīng)列中的所有字符,形式上,第 n 列為 [A[0][n], A[1][n], ..., A[A.length-1][n]])。(可以參見 刪除操作范例)
示例 1:
輸入:["cba", "daf", "ghi"]
輸出:1
解釋:
當(dāng)選擇 D = {1},刪除后 A 的列為:["c","d","g"] 和 ["a","f","i"],均為非降序排列。
若選擇 D = {},那么 A 的列 ["b","a","h"] 就不是非降序排列了。
示例 2:
輸入:["a", "b"]
輸出:0
解釋:D = {}
示例 3:
輸入:["zyx", "wvu", "tsr"]
輸出:3
解釋:D = {0, 1, 2}
思路一:
意思理解為:字符串?dāng)?shù)組中,每個(gè)字符串相同的索引所對(duì)應(yīng)的字符如果是降序則舒服,對(duì)應(yīng)索引的個(gè)數(shù)。
代碼如下:
public int minDeletionSize(String[] A) {
int ans = 0;
String first = A[0];
for (int i = 0; i < first.length(); i++) {// i為列下標(biāo)
char c = first.charAt(i);
for (int j = 1; j < A.length; j++) {// j為行下標(biāo)
if (c - A[j].charAt(i) > 0) {
ans++;
break;
} else {
c = A[j].charAt(i);
}
}
}
return ans;
}
-------------------------------小白學(xué)算法