48. 旋轉(zhuǎn)圖像（中等）
54. 螺旋矩陣（中等）
59. 螺旋矩陣 II（中等）
有不少讀者說(shuō)，看過(guò)很多公眾號(hào)歷史文章之后掌握了框架思維，可以解決大部分有套路框架可循的題目。
但是框架思維也不是萬(wàn)能的，有一些特定技巧呢，屬于會(huì)者不難，難者不會(huì)的類型，只能通過(guò)多刷題進(jìn)行總結(jié)和積累。
那么本文我分享一些巧妙的二維數(shù)組的花式操作，你只要有個(gè)印象，以后遇到類似題目就不會(huì)懵圈了。
順/逆時(shí)針旋轉(zhuǎn)矩陣
對(duì)二維數(shù)組進(jìn)行旋轉(zhuǎn)是常見(jiàn)的筆試題，力扣第 48 題「旋轉(zhuǎn)圖像」就是很經(jīng)典的一道：
題目很好理解，就是讓你將一個(gè)二維矩陣順時(shí)針旋轉(zhuǎn) 90 度，難點(diǎn)在于要「原地」修改，函數(shù)簽名如下：
void rotate(int[][] matrix)
如何「原地」旋轉(zhuǎn)二維矩陣？稍想一下，感覺(jué)操作起來(lái)非常復(fù)雜，可能要設(shè)置巧妙的算法機(jī)制來(lái)「一圈一圈」旋轉(zhuǎn)矩陣：
但實(shí)際上，這道題不能走尋常路，在講巧妙解法之前，我們先看另一道谷歌曾經(jīng)考過(guò)的算法題熱熱身：
給你一個(gè)包含若干單詞和空格的字符串s，請(qǐng)你寫(xiě)一個(gè)算法，原地反轉(zhuǎn)所有單詞的順序。
比如說(shuō)，給你輸入這樣一個(gè)字符串：
s = 'hello world labuladong'
你的算法需要原地反轉(zhuǎn)這個(gè)字符串中的單詞順序：
s = 'labuladong world hello'
常規(guī)的方式是把s按空格split成若干單詞，然后reverse這些單詞的順序，最后把這些單詞join成句子。但這種方式使用了額外的空間，并不是「原地反轉(zhuǎn)」單詞。
正確的做法是，先將整個(gè)字符串s反轉(zhuǎn)：
s = 'gnodalubal dlrow olleh'
然后將每個(gè)單詞分別反轉(zhuǎn)：
s = 'labuladong world hello'
這樣，就實(shí)現(xiàn)了原地反轉(zhuǎn)所有單詞順序的目的。
我講這道題的目的是什么呢？
旨在說(shuō)明，有時(shí)候咱們拍腦袋的常規(guī)思維，在計(jì)算機(jī)看來(lái)可能并不是最優(yōu)雅的；但是計(jì)算機(jī)覺(jué)得最優(yōu)雅的思維，對(duì)咱們來(lái)說(shuō)卻不那么直觀。也許這就是算法的魅力所在吧。
回到之前說(shuō)的順時(shí)針旋轉(zhuǎn)二維矩陣的問(wèn)題，常規(guī)的思路就是去尋找原始坐標(biāo)和旋轉(zhuǎn)后坐標(biāo)的映射規(guī)律，但我們是否可以讓思維跳躍跳躍，嘗試把矩陣進(jìn)行反轉(zhuǎn)、鏡像對(duì)稱等操作，可能會(huì)出現(xiàn)新的突破口。
我們可以先將n x n矩陣matrix按照左上到右下的對(duì)角線進(jìn)行鏡像對(duì)稱：
然后再對(duì)矩陣的每一行進(jìn)行反轉(zhuǎn)：
發(fā)現(xiàn)結(jié)果就是matrix順時(shí)針旋轉(zhuǎn) 90 度的結(jié)果：
將上述思路翻譯成代碼，即可解決本題：
// 將二維矩陣原地順時(shí)針旋轉(zhuǎn) 90 度
public void rotate(int[][] matrix) {
int n = matrix.length;
// 先沿對(duì)角線鏡像對(duì)稱二維矩陣
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
// swap(matrix[i][j], matrix[j][i]);
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// 然后反轉(zhuǎn)二維矩陣的每一行
for (int[] row : matrix) {
reverse(row);
}
}
// 反轉(zhuǎn)一維數(shù)組
void reverse(int[] arr) {
int i = 0, j = arr.length - 1;
while (j > i) {
// swap(arr[i], arr[j]);
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
肯定有讀者會(huì)問(wèn)，如果沒(méi)有做過(guò)這道題，怎么可能想到這種思路呢？
其實(shí)我覺(jué)得這個(gè)思路還是挺容易想出來(lái)的，如果學(xué)過(guò)線性代數(shù)，這道算法題的思路本質(zhì)就是矩陣變換，肯定可以想出來(lái)。
即便沒(méi)學(xué)過(guò)線性代數(shù)，旋轉(zhuǎn)二維矩陣的難點(diǎn)在于將「行」變成「列」，將「列」變成「行」，而只有按照對(duì)角線的對(duì)稱操作是可以輕松完成這一點(diǎn)的，對(duì)稱操作之后就很容易發(fā)現(xiàn)規(guī)律了。
既然說(shuō)道這里，我們可以發(fā)散一下，如何將矩陣逆時(shí)針旋轉(zhuǎn) 90 度呢？
思路是類似的，只要通過(guò)另一條對(duì)角線鏡像對(duì)稱矩陣，然后再反轉(zhuǎn)每一行，就得到了逆時(shí)針旋轉(zhuǎn)矩陣的結(jié)果：
翻譯成代碼如下：
// 將二維矩陣原地逆時(shí)針旋轉(zhuǎn) 90 度
void rotate2(int[][] matrix) {
int n = matrix.length;
// 沿左下到右上的對(duì)角線鏡像對(duì)稱二維矩陣
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i; j++) {
// swap(matrix[i][j], matrix[n-j-1][n-i-1])
int temp = matrix[i][j];
matrix[i][j] = matrix[n - j - 1][n - i - 1];
matrix[n - j - 1][n - i - 1] = temp;
}
}
// 然后反轉(zhuǎn)二維矩陣的每一行
for (int[] row : matrix) {
reverse(row);
}
}
void reverse(int[] arr) { /* 見(jiàn)上文 */}
至此，旋轉(zhuǎn)矩陣的問(wèn)題就解決了。
矩陣的螺旋遍歷
我的公眾號(hào) 動(dòng)態(tài)規(guī)劃系列文章 經(jīng)常需要遍歷二維dp數(shù)組，但難點(diǎn)在于狀態(tài)轉(zhuǎn)移方程而不是數(shù)組的遍歷，頂多就是倒序遍歷。
今天我們講一下力扣第 54 題「螺旋矩陣」，看一看二維矩陣可以如何花式遍歷：
函數(shù)簽名如下：
List<Integer> spiralOrder(int[][] matrix)
解題的核心思路是按照右、下、左、上的順序遍歷數(shù)組，并使用四個(gè)變量圈定未遍歷元素的邊界：
隨著螺旋遍歷，相應(yīng)的邊界會(huì)收縮，直到螺旋遍歷完整個(gè)數(shù)組：
只要有了這個(gè)思路，翻譯出代碼就很容易了：
List<Integer> spiralOrder(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int upper_bound = 0, lower_bound = m - 1;
int left_bound = 0, right_bound = n - 1;
List<Integer> res = new LinkedList<>();
// res.size() == m * n 則遍歷完整個(gè)數(shù)組
while (res.size() < m * n) {
if (upper_bound <= lower_bound) {
// 在頂部從左向右遍歷
for (int j = left_bound; j <= right_bound; j++) {
res.add(matrix[upper_bound][j]);
}
// 上邊界下移
upper_bound++;
}
if (left_bound <= right_bound) {
// 在右側(cè)從上向下遍歷
for (int i = upper_bound; i <= lower_bound; i++) {
res.add(matrix[i][right_bound]);
}
// 右邊界左移
right_bound--;
}
if (upper_bound <= lower_bound) {
// 在底部從右向左遍歷
for (int j = right_bound; j >= left_bound; j--) {
res.add(matrix[lower_bound][j]);
}
// 下邊界上移
lower_bound--;
}
if (left_bound <= right_bound) {
// 在左側(cè)從下向上遍歷
for (int i = lower_bound; i >= upper_bound; i--) {
res.add(matrix[i][left_bound]);
}
// 左邊界右移
left_bound++;
}
}
return res;
}
力扣第 59 題「螺旋矩陣 II」也是類似的題目，只不過(guò)是反過(guò)來(lái)，讓你按照螺旋的順序生成矩陣：
函數(shù)簽名如下：
int[][] generateMatrix(int n)
有了上面的鋪墊，稍微改一下代碼即可完成這道題：
int[][] generateMatrix(int n) {
int[][] matrix = new int[n][n];
int upper_bound = 0, lower_bound = n - 1;
int left_bound = 0, right_bound = n - 1;
// 需要填入矩陣的數(shù)字
int num = 1;
while (num <= n * n) {
if (upper_bound <= lower_bound) {
// 在頂部從左向右遍歷
for (int j = left_bound; j <= right_bound; j++) {
matrix[upper_bound][j] = num++;
}
// 上邊界下移
upper_bound++;
}
if (left_bound <= right_bound) {
// 在右側(cè)從上向下遍歷
for (int i = upper_bound; i <= lower_bound; i++) {
matrix[i][right_bound] = num++;
}
// 右邊界左移
right_bound--;
}
if (upper_bound <= lower_bound) {
// 在底部從右向左遍歷
for (int j = right_bound; j >= left_bound; j--) {
matrix[lower_bound][j] = num++;
}
// 下邊界上移
lower_bound--;
}
if (left_bound <= right_bound) {
// 在左側(cè)從下向上遍歷
for (int i = lower_bound; i >= upper_bound; i--) {
matrix[i][left_bound] = num++;
}
// 左邊界右移
left_bound++;
}
}
return matrix;
}
至此，兩道螺旋矩陣的題目也解決了。
