iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 7
0
自我挑戰組

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

【從面試題學邏輯-7】如果在矩陣內玩炸彈威力滿點的炸彈超人的話…(CTCI 1.8 矩陣清道夫)

題目:
輸入一個二緯陣列,如果第I行、第J列的某個東西為0,就把第I行及第J列的所有東西都變成0

舉例:

左邊是輸入,我們可以看到有一個0
右邊是要求的輸出,就是把0所在的行(row)及列(col)都變成0

簡單來說0就是炸彈超人裡的炸彈,只是威力預設可以炸穿所有十字範圍內的東西,最後看地圖剩下什麼殘骸之類的……/images/emoticon/emoticon34.gif


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

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


乍看之下我們可能會直覺性想到「Loop整個陣列時,遇到0就同時改」,但這樣做其實會有非常大的問題,請看圖:

好像哪裡怪怪的……
對!後來增加的0會被程式誤判是原本有0的位置,導致接下來的東西都變成0!

所以我們可以找到第一個要求:

  1. 找哪裡有0時不可以一起變更陣列內的東西

那接下來一定會有人想到「複製整個陣列,一個找0一個改0」,像下圖這樣:

這個方法可行,但有一個非常嚴重的問題,那就是它有夠貴

我們上面舉的例子是5*5的陣列,大不了就多一個5*5的陣列,看起來似乎沒有佔很多記憶體,但如果今天進來的是1000*1000的陣列呢!?

如果我們把陣列當作一格一格的置物櫃,假設輸入是1000*1000,那這個做法就會需要額外的1,000,000個置物櫃,真的是。而如果這個程式是任何人都可以同時使用的話……哇!置物櫃天堂!/images/emoticon/emoticon06.gif

宇宙偵探556

這時候我們再增一個要求:

  1. 找哪裡有0時不可以一起變更陣列內的東西
  2. 不要暴力解,因為這一題的暴力解會花費很多記憶體

這裡我們可以透過一個簡單的小邏輯來節省大量的空間,一行內的數字只要一個是0,整行就要變成0對吧?那一行內多個0,整行還是變成0對吧?

一行內一個0或多個0要記住的東西其實一模一樣,就是那一行要改成0
同理
一列內一個0或多個0要記住的東西其實一模一樣,就是那一列要改成0

看起來似乎有個頭緒了,其實我們只要記住哪一行哪一列要變成0就好了,根本不用開另一個同樣大小的陣列。

那不就和前面的開燈泡記數字一樣了嗎!?太棒了,又是應用前面看到的方法來解題呢/images/emoticon/emoticon12.gif
所以最終的三個要求就出來了

  1. 找哪裡有0時不可以一起變更陣列內的東西
  2. 不要暴力解,因為這一題的暴力解會花費很多記憶體
  3. 記住哪幾行/列要換0就好了

同時可以得出這段程式碼,由於內容十分簡單,就不多做說明了

static int[][] cleanMatrix(int[][] matrix) {
	boolean[] rowHasZero = new boolean[matrix.length];
	boolean[] colHasZero = new boolean[matrix[0].length];
	for(int i=0 ; i<matrix.length ; i++) {
		for(int j=0 ; j<matrix[0].length ; j++) {
               // 逐一讀過,把哪些行哪些列要換成0標記起來
			if(matrix[i][j] == 0) {
				rowHasZero[i] = true;
				colHasZero[j] = true;
			}
		}
	}
    
    // 下面就依照記住的行列玩炸彈超人
	for(int i=0 ; i<matrix.length ; i++) {
		if(rowHasZero[i] == true) {
			for(int j=0 ; j<matrix[0].length ; j++) {
				matrix[i][j] = 0;
			}
		}
	}
	for(int i=0 ; i<matrix[0].length ; i++) {
		if(colHasZero[i] == true) {
			for(int j=0 ; j<matrix.length ; j++) {
				matrix[j][i] = 0;
			}
		}
	}
	return matrix;
}

我們小結一下:
假設輸入的陣列有N行M列

  • 如果暴力解的話需要N*M個置物櫃空間
  • 而單純記清哪些行,只要N+M個置物櫃空間就好了

上一篇
【從面試題學邏輯-6】檢查單字大小寫是否合理(leetcode 520. Detect Capital)
下一篇
【從面試題學邏輯-8】我又轉過來啦,我又轉過去啦,比我啊大大(CTCI 1.9 旋轉的字串)
系列文
新手也能學!一起從面試題理解程式邏輯!30

尚未有邦友留言

立即登入留言