題目連結:
題目意譯:
你被給定一個 m × n 的字元矩陣 box ,其代表著一個箱子的側視圖。每個 box 中的格子為以下之一:
一個石頭 '#'
一個固定的障礙物 '*'
空格子 '.'
箱子被順時針旋轉 90 度,使得某些石頭因為重力的影響而墜落。每個石頭墜落直到碰到一個障礙物、另一個石頭或是箱子的底部。重力不會影響障礙物的位置,而且來自箱子的轉動慣性不會影響石頭的水平位置。
保證每個石頭將停留在一個障礙物、另一個石頭或是箱子底部之上。
回傳一個 n × m 矩陣,代表著如上所述之箱子旋轉後的樣子。
限制:
m == box.length
n == box[i].length
1 ≦ m 、 n ≦ 500
box[i][j] 只會是 '#' 、 '*' 或是 '.' 。
範例測資:
範例 1:
輸入: box = [["#",".","#"]]
輸出: [["."],
["#"],
["#"]]
範例 2:
輸入: box = [["#",".","*","."],
["#","#","*","."]]
輸出: [["#","."],
["#","#"],
["*","*"],
[".","."]]
範例 3:
輸入: box = [["#","#","*",".","*","."],
["#","#","#","*",".","."],
["#","#","#",".","#","."]]
輸出: [[".","#","#"],
[".","#","#"],
["#","#","*"],
["#","*","."],
["#",".","*"],
["#",".","."]]
解題思維:
先依照類似這題的方式將原本 m × n 的矩陣 box 填入另一個新的 n × m 矩陣 newBox 。
所以像是 box =
##*.*.
###*..
###.#.
我們會得到 newBox =
###
###
##*
.*.
#.*
...
接著我們需要模擬重力,因此我們可以從箱子的底部開始每一行都往上統計石頭的總數 C,也就是計算有多少石頭會往下掉。
當我們每碰到一個「*」或是箱子頂部時,代表不會再有石頭掉超過這裡,也就代表著上一個「*」(或是箱子底部)到這個位置之間會有 C 顆石頭掉到上一個「*」(或箱子底部)。因此我們將這個區間的字元先全部設為「.」,然後將這個區間最底下 C 個字元設為「#」,代表這 C 顆石頭將停留於此。然後將 C 歸零並繼續往上統計。
例如上面的 newBox 的最左邊那一行:
#
#
#
.
#
.
我們從最下面的「.」開始往上一路到箱子頂部(這邊剛好沒有「*」的存在),途中我們經過了四顆石頭。因此我們先將該行設為
.
.
.
.
.
.
然後將最下面四個字元改為「#」:
.
.
#
#
#
#
而其他行也是類似的情形。
當我們將每一行都進行完以上的動作之後,最後的 newBox 即是所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。