iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 9
0
自我挑戰組

新手也能學!一起從面試題理解程式邏輯!系列 第 9

【從面試題學邏輯-9】如何旋轉矩陣/二維陣列 ?到底是轉魔術方塊還是轉大腦?(CTCI 1.7 旋轉矩陣)

題目:
寫一個方法,來旋轉輸入的N*N矩陣90度,請嘗試在原地(in-place)完成旋轉

舉例:
已上色方便大家辨識,假設我們順時針旋轉90度
左邊為原本的,右邊是旋轉過後的


那在開始前不乏提醒一下此系列的固定提醒:

這是一系列逐漸帶入解題的文章,難度會隨著進度增加,若還沒有讀過前面的文章,建議先從最前面開始來逐漸練習解題喔!


高難度題目注意:
這一題在抓取對應位置的部分需要更多思考,建議大家可以多想想,由於這塊是很容易邏輯打結的部分,如果突然邏輯打結,建議先休息一下再繼續。

首先先帶大家認知一下旋轉的概念,這個其實很像我們日常看到的魔術方塊,以下圖4*4矩陣為例:

我們可以看成兩個部分,分別是內層的2*2

以及外層的4*4

這兩個部分都分別旋轉就可以轉完整個矩陣,所以一個N*N的矩陣,實際上要轉N/2層。


接著我們看看對應矩陣中的位置是怎樣:

矩陣就是二維陣列,所以第一行是矩陣中第0個一維陣列喔!
由此可知,代表行位置的是前面的數字,代表列的則是後面的數字

再來,由於我們會分層,假設最外圈是第0層,中間灰色的是第1層,我們可以發現四個頂點的數字(我們用[X][Y]代表坐標吧)會依照層數而這樣變動:
(我們用len代表最外圈的邊長)

  1. 左上:[layer][layer]
  2. 右上:[layer][len-layer]
  3. 右下:[len-layer][len-layer]
  4. 左下:[len-layer][layer]

由於題目要求我們要in-place(若不知道意思,請當成不能額外開一堆資料結構及空間,也就是說在本題只能開一個暫存數字的位子喔),所以我們的順序應該要是:

  1. 把1的數字暫存起來
  2. 把4的數字移動到1
  3. 把3的數字移動到4
  4. 把2的數字移動到3
  5. 把暫存的數字放到2

如果是更大的矩陣呢?

順序一樣,多對應後面的-1-2-3

我們用offset代表那一排第N個要轉移的數字,那一圈的第N個位置就會變成
(一樣offset從第0個開始)

  1. 左上:[layer][layer+offset]
  2. 右上:[layer+offset][len-layer]
  3. 右下:[len-layer][len-layer-offset]
  4. 左下:[len-layer-offset][layer]

若覺得邏輯打結,請隨時滑上去對照一下喔!


好~~~的,總算是講完抓位置的部分,接下來先上程式碼再慢慢解釋/images/emoticon/emoticon06.gif

static boolean rotateMatrix(int[][] matrix) {
	if(matrix.length != matrix[0].length) return false;
	int len = matrix.length;
	for(int layer=0 ; layer<len/2 ; layer++) {
		int firstPos = layer;
		int lastPos = (len-1)-layer;
		for(int i=firstPos ; i<lastPos ; i++) {
			int offset = i-firstPos;
			int topLeft = matrix[firstPos][i];
			// 暫存
			matrix[firstPos][i] = matrix[lastPos-offset][firstPos];
			matrix[lastPos-offset][firstPos] = matrix[lastPos][lastPos-offset];
			matrix[lastPos][lastPos-offset] = matrix[i][lastPos];
			matrix[i][lastPos] = topLeft;
		}
	}
	return true;
}

開始拆開來講解

if(matrix.length != matrix[0].length) return false;

大家前面的題目應該看到煩了,不是正方形沒辦法原地轉,讓他直接起飛

int len = matrix.length;

避免我們要一直matrix.length,所以給它一個名字 + 增加可讀性

for(int layer=0 ; layer<len/2 ; layer++) {
	int firstPos = layer;
	int lastPos = (len-1)-layer;
	for(int i=firstPos ; i<lastPos ; i++) {
		// 還沒講到這邊先省略,免得太長...
	}
}

這裡我們用firstPoslastPos代表那一層正方形的邊角,請見下圖

看到了嗎?我們利用矩陣有兩個index([][])的效果,讓我們能夠更好的抓出數字,同時避免混淆。

for(int i=firstPos ; i<lastPos ; i++) {
	int offset = i-firstPos;
	int topLeft = matrix[firstPos][i];
	// 暫存
	matrix[firstPos][i] = matrix[lastPos-offset][firstPos];
	matrix[lastPos-offset][firstPos] = matrix[lastPos][lastPos-offset];
	matrix[lastPos][lastPos-offset] = matrix[i][lastPos];
	matrix[i][lastPos] = topLeft;
}

這邊要注意一件事,這個for迴圈是用firstPoslastPos的位置來loop,所以要額外開一個offset,來調整紅色及藍色區要拿的數字。

不好理解嗎?因為firstPoslastPos逐漸增加,但是紅色及藍色區,他們接下來要讀取的數字,要移動的方向是逐漸減少,所以我們不可以直接套用在firstPoslastPos移動的i。而是必須另外開一個反向的offset給紅藍兩區使用

終於!題目到此終於搞定


由於這一題的位置十分不好解釋,如果有缺漏或是講的不夠完整再請見諒/images/emoticon/emoticon10.gif
有打錯的地方也請再指教


上一篇
【從面試題學邏輯-8】我又轉過來啦,我又轉過去啦,比我啊大大(CTCI 1.9 旋轉的字串)
下一篇
【從面試題學邏輯-10】複習一下:關於位元運算(Bitwise Operation)
系列文
新手也能學!一起從面試題理解程式邏輯!30

尚未有邦友留言

立即登入留言