題目連結:
題目意譯:
給定你一個有 n 個字串之陣列 strs,每個字串長度都相同。
這些字串可以排列成每列一個字串,形成一個字元網格。例如,strs = ["abc", "bce", "cae"] 可以排列成:
abc
bce
cae
你想要刪除所有那些沒有按照字典序排列的字元行。上例中(索引值從 0 開始),第 0 行('a' 、 'b' 、 'c')以及第 2 行('c' 、 'e' 、 'e')有排序好,而第 1 行('b' 、 'c' 、 'a')則沒有,所以你會刪除掉第 1 行。
回傳你會刪除的行數。
限制:
n == strs.length
1 ≦ n ≦ 100
1 ≦ strs[i].length ≦ 1000
strs[i] 只由小寫英文字母組成。
範例測資:
範例 1:
輸入: strs = ["cba","daf","ghi"]
輸出: 1
解釋: 網格的樣子如下:
cba
daf
ghi
第 0 、 2 行有排序好,而第 1 行則沒有,所以你只須刪除 1 行。
範例 2:
輸入: strs = ["a","b"]
輸出: 0
解釋: 網格的樣子如下:
a
b
第 0 行是唯一一個行且為已排序,所以不須刪除任何行。
範例 3:
輸入: strs = ["zyx","wvu","tsr"]
輸出: 3
解釋: 網格的樣子如下:
zyx
wvu
tsr
3 行都未排序,所以你需要刪除 3 行全部。
解題思維:
直接掃過每一行並用一變數 C 計錄要刪除的行數即可,如下:
for j = 0 to strs[0].length - 1 // 行索引值
for i = 1 to strs.length - 1 // 列索引值
if strs[i - 1][j] > strs[i][j]
C += 1
break
掃完後的 C 值即是所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。