關於 web service, unity, blogger 等軟體工程筆記

LeetCode #6 ZigZag Conversion

Edit icon 沒有留言
LeetCode using Golang

記錄 LeetCode #6 ZigZag 思考解法的過程筆記,並使用 Go 來實作。

LeetCode #6

The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (see leecode page or below example).

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert(“PAYPALISHIRING”, 3) should return “PAHNAPLSIIGYIR”.

簡單的說,要使用鋸齒形狀來排字串,然後文字的位置,來取得新的字串。因此得先畫一下圖,假設 text 還是一樣是 PAYPALISHIRING,只是其 nRows 改成 4 行,因此排序字串可以畫出以下的圖 (節省空間的鋸齒型示意圖):

PAYPALISHIRING 以四行鋸齒型排列的示意圖

因此其轉換後的字串,由上到下由左至右一行一行讀取,會是 PIN-ALSIG-YAHR-PI,其結果字串應該要是 PINALSIGYAHRPI。最簡單的解法思路是建立 nRows 字串陣列,然後一個一個根據規則塞入到該些字串,最後再將該些字串串在一起的解答:

import(
   "strings"
)

func convert(s string, numRows int) string {
   if (numRows <= 1){
      return s
   }
   
   cs := make([]string, numRows);
   idx := 0
   step := 1
   for _, c := range s{
      cs[idx] += string(c)
      idx += step
      if idx >= numRows {
         step *= -1
         idx = numRows - 2
      }else if idx < 0{
         step *= -1
         idx = 1
      }
   }
   
   return strings.Join(cs[:], "")
}

但是非常浪費記憶體空間的做法,而且需要反覆的記憶體操作,速度會比較慢。但既然是讀取字串,那麼將上圖轉換成字串的索引,String index,只要找到這 index 的規則,那麼便能較優雅解決這個問題:

四行鋸齒形排列的示意圖

四行鋸齒形排列的示意圖

假設 nRows 共有 n 行,那麼其表應該會是如此:

n 行鋸齒形排列的示意圖

n 行鋸齒形排列的示意圖

為什麼會是這樣?假設一開始是這個狀態,求 X 是多少?我們知道共有 n 列,共有 n 個數字,因此 (X) - (0) + 1 = n

計算 X 數值,已知有 n 列

計算 X 數值,已知有 n 列

接著求 Y,同理,原先 X 走到 Y 一樣有 n 個數字,因此走 n-1…,得知 Y = X + (n-1) = 2n-2,以此類推:

計算 Y 數值,已知有 n 列...

計算 Y 數值,已知有 n 列...

因此觀察其 Index 模式,可得知從青色格子走到亮綠色格子,需要 2*[(n-1)-(2)],而亮綠色格子到紅色格子剛好是 2 * (2)

觀察模式,找到規則的計算公式

觀察模式,找到規則的計算公式

因此設定目前在第 k 列,其數字變化會是如此,然後去驗證一開始的表:

  • k
  • k + 2*(n-k-1)
  • k + 2*(n-k-1) + 2*k
  • k + 2*(n-k-1) + 2k + 2(n-k-1)
  • k + 2*(n-k-1) + 2k + 2(n-k-1) + 2*k
  • …and so on

發現完全符合,已經找到其 index 變化模式,便可以改寫程式碼,完成這一次的數學歸納試煉…:

import(
   "bytes"
)

func convert(s string, numRows int) string {
   if (numRows <= 1){
      return s
   }
   
   var b bytes.Buffer
   for k := 0; k < numRows; k++{
      oft1 := 2 * (numRows - k - 1)
      oft2 := 2 * k
      idx := k
      b.WriteString(string(s[idx]))
      for idx < len(s){
         if oft1 > 0 {
            idx += oft1
            if idx < len(s){
               b.WriteString(string(s[idx]))
            }
         }
         if oft2 > 0 {
            idx += oft2
            if idx < len(s){
               b.WriteString(string(s[idx]))
            }
         }
      }
   }   
   return b.String()
}

在撰寫這篇回顧時,才熊熊想起可以使用那最直覺的方法來解決這問題,也許真的是被訓練到一定要找到自己認為的最佳解,太優化過頭了…。

沒有留言: