ETH官方钱包

前往
大廳
主題

LeetCode - 944. Delete Columns to Make Sorted 解題心得

Not In My Back Yard | 2021-02-22 00:00:01 | 巴幣 2 | 人氣 244

題目連結:


題目意譯:
給定你一個有 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 值即是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作