DIV CSS 佈局教程網

JavaScript 陣列有多靈活:用 shift 與 pop 優雅拆解螺旋矩陣
編輯:關於JavaScript     

前言

Array 物件用來封裝多個任意型別的資料並加以管理,所有主流瀏覽器都支援。大家都知道它有四個基本方法:push、pop、shift、unshift;也知道 push 配 pop 是堆疊、shift 配 push 是佇列。本文不談先進後出或先進先出,而是看這幾個方法搭配起來能做出多優雅的成績。

題目:螺旋矩陣

後端語言裡對螺旋矩陣應該不陌生,它是個二維陣列,排列規則從外圍開始一圈圈往內繞,像一條盤旋的蛇:

當年沒做出來的那題

某年校招線上筆試就出現了「傳入 n,印出 n×n 螺旋矩陣」這一題。當時我沒寫出來,事後在電腦前慢慢想才恍然大悟。我的做法很笨:先建立 n×n 二維陣列,算出要繞幾層(上圖是兩層),外層跑迴圈、內層用上下左右四個 for 依序填值。方法可行,但程式碼又長又不優雅,也不是本文重點。

前幾天在 codewars 上又碰到螺旋矩陣,這次要求相反:給一個二維陣列,回傳一維陣列,元素順序就是螺旋路徑。

function getLinear (spiral) {
  // ...做一些操作
}
var arr = [ [1,2,3], [4,5,6], [7,8,9] ]
getLinear(arr) // 回傳 [1,2,3,6,9,8,7,4,5]

我照老方法寫了四個 for 迴圈送出,答對了。這個網站有個不錯的機制:交完題可以參考別人的解法。我點開第一名,映入眼簾的程式碼讓我愣了一下——大致是這樣:

function getLinear(spiral) {
  var item;
  var linear = []
  while (item = spiral.shift()) {
    // 上
    linear = linear.concat(item)
    // 右
    for (var i = 0; i < spiral.length; i++) {
      linear.push( spiral[i].pop() )
    }
    // 下
    linear = linear.concat( spiral.pop().reverse())
    // 左
    for (var i = spiral.length - 1; i >= 0; i --) {
      linear.push(spiral[i].shift())
    }
  }
  return linear
}

思維方向和我完全不同,看了一會兒才摸清其中的奧妙。它不必預先判斷是不是 n×n,2×3、3×5 這類不規則矩陣也照樣能處理,程式碼還短得驚人。

逐步拆解

上:shift 把第一列整個取出並回傳,concat 直接接上:

linear = linear.concat(item)

此時原始陣列剩下:

右:每一列的最後一個元素,用 pop 取出:

for (var i = 0; i < spiral.length; i++) {
  linear.push( spiral[i].pop() )
}

下:把最後一列 pop 出來,reverse 之後接上,順序就對了:

linear = linear.concat(spiral.pop().reverse())

左:與右對稱,只要把 pop 換成 shift,並反向遍歷:

for (var i = spiral.length - 1; i >= 0; i --) {
  linear.push(spiral[i].shift())
}

一圈結束,while 條件再判斷是否還有下一圈——由於 shift 與 pop 會真的把元素從原陣列移除,陣列被削空時迴圈自然停止,不需要額外維護「已走到第幾層」這種狀態變數。這正是它比我原版漂亮的地方:用資料結構本身的消耗來表達遍歷進度。

總結

看起來棘手的題目,在 Array 的靈活操作下變得相當簡潔。重點不是背下這段程式碼,而是養成一個習慣:遇到「邊界層層剝離」這類問題,先想想 shift / pop / unshift / splice 能不能直接幫你把邊界吃掉。希望對 JS 新手有幫助,有疑問歡迎留言交流。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved