LeetCode演算法題-Reshape the Matrix（Java實現）
這是悅樂書的第264 次更新，第277 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第131題（順位題號是566）。在MATLAB中，有一個非常有用的函式叫做'reshape'，它可以將矩陣重新整形為一個不同大小的矩陣，但保留其原始資料。您將獲得一個由二維陣列表示的矩陣，以及兩個正整數r和c，分別表示所需重新整形矩陣的行號和列號。重新形成的矩陣需要以相同的行遍歷順序填充原始矩陣的所有元素。如果具有給定引數的“重塑”操作是可能且合法的，則輸出新的重新整形矩陣;否則，輸出原始矩陣。例如：
輸入：nums = [[1,2]，[3,4]]，r = 1，c = 4
輸出：[[1,2,3,4]]
說明：行遍歷的是[1,2,3,4]。新的重新形狀矩陣是1 x 4矩陣，使用前面的列表逐行填充。
輸入：nums = [[1,2]，[3,4]]，r = 2，c = 4
輸出：[[1,2]，[3,4]]
說明：無法將2 x 2矩陣重塑為2 x 4矩陣。所以輸出原始矩陣。
注意：
-
給定矩陣的高度和寬度在[1,100]範圍內。
-
給定的r和c都是正數。
本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。
02 第一種解法
題目要求我們把二維陣列，根據給出的行和列，進行行列互換，不能換就返回原陣列。我們需要考慮的是小行大列轉成大行小列，或者大行小列轉成小行大列這兩種情況，兩層迴圈肯定是逃不掉的。
第一種情況：小行大列轉成大行小列，迴圈內部，原陣列的陣列迴圈一次，會往新數組裡插入同樣多的資料，但是會分成（原陣列的列/新陣列的列c）行。比如原來是2行4列的陣列，在第一次內層迴圈後，會往新陣列中插入2行2列，在第二次內層迴圈的時候，再插入2行2列，變成新陣列4行2列。
第二種情況：大行小列轉成小行大列，原陣列外部迴圈（新陣列的列/原陣列的列）次，才能將一行資料寫入到新陣列中去。比如原來是4行2列的陣列，外部迴圈第二次時，會往新陣列中插入1行4列，在第四次外部迴圈時，再插入1行4列，變成新陣列2行4列。
所以，新陣列的行列起始值在迴圈外部，在內層迴圈裡，每次都是列自加1，如果列自加到等於c，那麼表明要換行了，此時行再加1，然後列重置為0，直到轉換完所有資料。
public int[][] matrixReshape(int[][] nums, int r, int c) {
if (nums.length == 0 || nums.length*nums[0].length != r*c) {
return nums;
}
int[][] result = new int[r][c];
int row = 0;
int col = 0;
for (int i=0; i<nums.length; i++) {
for (int j=0; j<nums[0].length; j++) {
result[row][col] = nums[i][j];
col++;
if (col == c) {
col = 0;
row++;
}
}
}
return result;
}
03 第二種解法
第一種解法的內層迴圈那裡，我們可以觀察下，新陣列的列col是有周期的，每次都是從0開始，到c結束，然後row就加1，那麼我們可不可以利用取餘來替換col，因為取餘也是具有周期性的，藉助col%c來處理列，那麼行呢？
行可以看做逢c進一，也就是迴圈處理c次資料後，row才會加1。所以結合兩者，使用一個次數變數count，col的值就變成了count對c取餘，row的值就變成了count除以c的商。
public int[][] matrixReshape2(int[][] nums, int r, int c) {
if (nums.length == 0 || nums.length*nums[0].length != r*c) {
return nums;
}
int[][] result = new int[r][c];
int count = 0;
for (int i=0; i<nums.length; i++) {
for (int j=0; j<nums[0].length; j++) {
result[count/c][count%c] = nums[i][j];
count++;
}
}
return result;
}
04 第三種解法
我們也可以使用佇列來進行輔助操作，利用佇列先進先出的特性。使用一次兩層迴圈，將原陣列元素依次入隊，然後再使用一次兩層迴圈，將佇列中的元素依次出隊，插入到新陣列中去即可。
public int[][] matrixReshape3(int[][] nums, int r, int c) {
if (nums.length == 0 || nums.length*nums[0].length != r*c) {
return nums;
}
int[][] result = new int[r][c];
Queue<Integer> queue = new LinkedList<Integer>();
for (int i=0; i<nums.length; i++) {
for (int j=0; j<nums[0].length; j++) {
queue.offer(nums[i][j]);
}
}
for (int i=0; i<r; i++) {
for (int j=0; j<c; j++) {
result[i][j] = queue.poll();
}
}
return result;
}
05 小結
演算法專題目前已日更超過四個月 ，演算法題文章131 +篇，公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！