Ch23 矩陣

搭配 Leetcode 解題系統
回目錄：國立科學園區實驗中學C++程式語言自學講義

矩陣 / 二維陣列

之前所教過的陣列/vector，都是一維的
我們可以在一排格子裡儲存數值，用index來表示「哪一格」
這一章我們要學的是二維陣列，會用到「第幾列第幾行」的概念

宣告一個固定大小的二維陣列

int a[50][100];

這樣一來 a 就是一個有 50*100 格的二維陣列

宣告

宣告一個二維的 vector

vector<vector<int>> a;

這樣一來 a 就是一個空的二維 vector
像是 vector 包著 vector 的概念

push_back

我們可以增加新的列

vector<int> b = {1, 2, 3};
a.push_back(b);

這樣一來 a 的最後一列就會是 {1, 2, 3}

也可以對於某一列添加新的元素

a[5].push_back(3);

這樣一來 a 的第 5 列就會多一個新的數字 3

賦值/取值

當我們想要把 a 的第 i 列第 j 行變成某數 x 時
可以寫成

a[i][j] = x;

同樣的，當我們想要取用 a 的第 i 列第 j 行的值時
可以寫成

int y = a[i][j];

清空

當我們想要把名為 a 的二維 vector 整個清空
可以寫成

a.clear();

若我們只是想把 a 的第 i 列清空
可以寫成

a[i].clear();

這樣一來，其他列都還是原本的樣子

長度

當我們想要知道 a 有幾列
可以寫成

cout << a.size();

當我們想要知道 a 的第 i 列有多長
可以寫成

cout << a[i].size();

不同於靜態的二維陣列 int a[50][100] 一定是固定的長寬
二維的 vector 的每一列可以是不同長度的

拜訪每個值

【例題】

題目給一個名為 accounts 的二維 vector
裡面的每一列都代表某一個人的全部財產
例如某一列是 [1, 2, 3] ，就代表那個人有 1+2+3=6 元
請問最有錢的那個人有多少錢？

這是 Leetcode 上的題目，連結是 Leetcode 1672
但凡是二維陣列的題目，我們通常都會要用雙層的迴圈來拜訪格子們
我們可以在迴圈的最外面用一個變數 max_sum 來代表最大值
中間用一個變數 sum 來計算和暫存每個人的財產

int max_sum = 0;
for(int i=0;i<accounts.size();i++){
    // 計算第 i 個人的財產
    int sum = 0;
    for(int j=0;j<accounts[i].size();j++){
        sum+=accounts[i][j];
    }
    // 更新最大值
    if(sum>max_sum) max_sum = sum;
}
return max_sum;

【學生練習題】

• Leetcode 2643: 最多 1 的那一列

題目給我們一個名為 mat 的二維 vector，請問最多 1 的那一列是哪一列呢？他有幾個 1 呢？

注意這題要回傳的是一個一維 vector，要有兩格
第一格用來存「第幾列最多1」，第二格用來存「它有幾個1」

對角線上的格子

【例題】

題目給一個名為 mat 的二維 vector
請問在"對角線"上的格子數字的總和是多少呢？

這是 Leetcode 上的題目，連結是 Leetcode 1572

如果二維陣列的列數和行數相同，他就是一個正方形矩陣
如何判斷一個格子是不是在對角線上呢？
假設正方形邊長是 5
左上-右下的對角線有這些格子：(0, 0), (1, 1), (2, 2)…
右上-左下的對角線有這些格子：(0, 4), (1, 3), (2, 2)…
我們可以觀察出這樣的規律：
用 (i, j) 來代表某格子的座標
若 i==j 或是 i+j==(n-1)，則可知 (i, j) 在對角線上

int sum = 0;
int n = mat.size(); // 正方形邊長
for(int i=0;i<n);i++){
    for(int j=0;j<n;j++){
        if(i==j||i+j==n-1) sum+=mat[i][j];
    }
}
return sum;

或是更有效率的方法
就是只拜訪對角線上的格子

int sum = 0;
int n = mat.size(); // 正方形邊長
for(int i=0;i<n);i++){
    // 左上右下對角線的格子
    sum += mat[i][i];
    // 右上左下對角線的格子
    // 注意如果是正中央，會被重複加一次，要避免
    if(n-1-i != i) sum+=mat[i][n-1-i];
}
return sum;

這樣只需要一層迴圈就能完成了

【學生練習題】

• Leetcode 2614: 對角線上最大的質數

所有在對角線上的格子裡，最大的「質數」是多少呢？

判斷質數有點麻煩，幸好我們在 for 迴圈 的單元學了簡單的做法
或是可以直接照抄：

bool is_prime(int n){
    if(n==1) return false;
    for(int i=2;i*i<=n;i++){
        if(n%i==0) return false;
    }
    return true;
}

【學生練習題】

• Leetcode 2319: X 矩陣

題目給我們一個名為 grid 的二維 vector，請問是不是所有對角線上的數字都不是 0 ，且所有不在對角線上的數字都是 0 呢？

例如這個矩陣符合條件，要回傳 true

例如這個矩陣就不符合條件，要回傳 false

同一行或同一列的鄰居

【例題】

題目給一個名為 matrix 的二維 vector
請找出所有的「幸運數字」
被認為「幸運」的條件是，這個數字是他那一橫列裡最小的，又是他那一直行裡最大的

這是 Leetcode 上的題目，連結是 Leetcode 1380

我們可以拜訪 matrix 裡的每個數字
檢查和他同一橫列和同一直行裡有沒有哪位鄰居害他無法成為「幸運數字」的
如果都沒有，他就是幸運的

vector<int> ret;
int num_of_rows = matrix.size();
int num_of_cols = matrix[0].size();
for(int i=0;i<num_of_rows;i++){
    for(int j=0;j<num_of_cols;j++){
        // 無論如何，先假定他是幸運的
        bool lucky = true;
        // 檢查同一橫列的鄰居們，有沒有比他小？若有，他就無法幸運
        for(int c=0;c<num_of_cols;c++){
            if(matrix[i][c]<matrix[i][j]) lucky = false;
        }
        // 檢查同一直行的鄰居們，有沒有比他大？若有，他就無法幸運
        for(int r=0;r<num_of_rows;r++){
            if(matrix[r][j]>matrix[i][j]) lucky = false;
        }
        // 若他依然幸運，就把它加到答案裡
        if(lucky) ret.push_back(matrix[i][j]);
    }
}
return ret;

【學生練習題】

• Leetcode 1582: 特別的數字

題目給一個名為 mat 的二維 vector
請問總共有幾個「特別的格子」呢？
格子被認為「特別」的條件是，他這格是1，且和他同一行同一列的其他格子全都是0

圖中的藍色是特別的格子

左邊這個矩陣有 1 個特別格子，右邊這個矩陣有 3 個特別格子

【學生練習題】

• Leetcode 2352: 相同的行列

題目給一個名為 grid 的二維 vector
請問有幾對（行,列）是一樣的數字呢

以下的例子，第二列和第一行都是 [2, 7, 7]
總共一對

以下的例子，第零列和第零行都是 [3, 1, 2, 2]
還有第二列和第二行都是 [2, 4, 2, 2]
還有第三列和第二行都是 [2, 4, 2, 2]
總共三對

一維和二維的轉換

【例題】

班上有 k 位學生，座號分別是 [0, 1, ..., k]
他們一起到了電腦教室
電腦教室總共有 m 排，每一排有 n 個座位
所以座號為 [0, 1, ..., n-1] 的這 n 個人要坐在第 0 排
座號為 [n, n+1, ..., 2n-1] 的這 n 個人要坐在第 1 排
以此類推
請依這個規則建立一個二維的 vector 把大家放到正確的座位上
但若 m*n 個座位不夠坐，或是坐不滿，就回傳空的二維 vector

這是 Leetcode 上的題目，連結是 Leetcode 2022
依據上述的規則
我們可以歸納出座號為 i 的人會被分配到第 i/n 排的第 i%n 個座位

// 如果學生人數不等於 m*n，就回傳空的二維 vector
if(original.size()!=m*n) return vector<vector<int>>();
// 宣告一個 m*n 的 vector 來存答案
vector<vector<int>> ret(m, vector<int>(n));
for(int i=0;i<original.size();i++){
    ret[i/n][i%n] = original[i];
}
return ret;

【學生練習題】

• Leetcode 566: 重塑矩陣

學生們正依照例題的規則，照著座號坐在一間教室裡
他們現在被用一個名為 mat 的二維 vector 來表示
現在他們要換到一間新的教室
新教室總共有 r 排，每排有 c 個座位
大家依然要照座號坐，也就是第一排是[0, 1, ..., c-1]…
請依照這個規則建立一個二維的 vector 把大家放到新教室的座位上
但若學生的數量並非 r*c，就請回傳原本的 mat

提示：可以先用一個一維的 vector 來暫存 mat 裡的數字
再用例題的方法把一維的 vector 變成 r*c 的二維 vector

【學生練習題】

• Leetcode 1260: 往右 k 格

學生們正依照例題的規則，照著座號坐在電腦教室裡
他們現在被用一個名為 grid 的二維 vector 來表示
今天考完了期中考，考卷由同學互相改
每個人的考卷都要"向右傳" k 次
每次向右傳，grid[i][j] 要被移到 grid[i][j+1]
grid[i][n-1] 也就是那一排的最後一位，要移到 [i+1][0] 也就是下一排的第一位
grid[m-1][n-1] 也就是最後一排最後一位，要移到 grid[0][0] 也就是第一排第一位
請依照這個規則建立一個二維的 vector 把考卷移到正確的批改人手上

提示：老師有點瘋狂，k可能會是很大的數字，有可能比全班人數還要大
能不能利用數學運算，設計一個公式來讓每個人都直接算出他該把考卷交給誰呢？

矩陣的旋轉

【例題】

班上的同學們依照自己的喜好坐在座位上
教室裡的座位剛好是個正方形（行數和列數一樣多）

今天老師把黑板移到了教室的右側
大家若是想要保持原本對於座位和黑板的相對位置的喜好
就必須隨著黑板的移動
把所有人的位置也都順時針旋轉90度
像是這樣：

請在原本的矩陣 matrix 上幫大家完成旋轉

這是 Leetcode 上的題目，連結是 Leetcode 48

我們可以先歸納出每個坐在(r, c)位置的人，他的新座位該怎麼計算

假設正方形邊長是 n
我們發現，一個原本在(r, c)位置的人，他的新座位必然是(c, n-1-r)

接下來，請注意大家是在「原本的教室」直接換座位
而不是去新的空教室坐

所以換座位的過程會像是這樣

• 小藍跑到小綠的座位，說，起來，該我坐了
• 小綠只好跑到小黃的座位，把小黃趕走
• 小黃只好跑到小橘的座位，把小橘趕走
• 小橘於是跑到小藍的舊座位坐了下來，至此這四人順利完成了交換

用程式表示就是

int hold = matrix[r4][c4]; // 小橘先起來遊蕩
matrix[r4][c4] = matrix[r3][c3]; // 小黃去小橘的舊座位
matrix[r3][c3] = matrix[r2][c2]; // 小綠去小黃的舊座位
matrix[r2][c2] = matrix[r1][c1]; // 小藍去小綠的舊座位
matrix[r1][c1] = hold; // 小橘也有空位可坐了，就是小藍的舊座位

再來要注意的是，剛才小藍已經做一次「首先起身趕走新座位的同學」的行為了
小綠小黃小橘因此被動地完成了交換
他們三位就不需要再進行一次「首先起身趕走新座位的同學」的行為了
依照這個規則
我們可以把教室切成四個區域
然後永遠只讓藍色那塊區域的人來負責當「首先起身趕走新座位的同學」的人
其他三個區塊的人都只要被動地被移動

寫成程式就是這樣

int n=matrix.size();
for(int i=0;i<n/2;i++){ // 只讓藍色區域的人擔任小藍
    for(int j=0;j<(n+1)/2;j++){ // 只讓藍色區域的人擔任小藍
        int r1=i, c1=j;       // 小藍
        int r2=c1, c2=n-1-r1; // 小綠
        int r3=c2, c3=n-1-r2; // 小黃
        int r4=c3, c4=n-1-r3; // 小橘
        // 剛才介紹過的移動
        int hold = matrix[r4][c4];
        matrix[r4][c4]=matrix[r3][c3];
        matrix[r3][c3]=matrix[r2][c2];
        matrix[r2][c2]=matrix[r1][c1];
        matrix[r1][c1]=hold;
    }
}

記得這是 Leetcode 48 喔！

【學生練習題】

• Leetcode 1886: 能轉成目標的樣子嗎？

題目給兩個正方形矩陣，分別是 mat 和 target
請問我們能夠藉由旋轉 mat 若干次，把它變成和 target 一模一樣嗎？

螺旋走訪矩陣

【例題】

老師開始點同學回答問題
依照「螺旋」的順序來點人
先從左到右點第一橫列的同學，轉彎
再從前到後點最右直行的同學，轉彎…以此類推

請回傳一個一維 vector，依序儲存被點到的人
以上面的例子，就是 [1,2,3,4,8,12,11,10,9,5,6,7]

這是 Leetcode 上的題目，連結是 Leetcode 54

我們可以觀察出一個規則：
每次點完一個橫列或直排，要轉彎的那一瞬間
剩下還沒點到的同學都是組成一個長方形

因此我們可以用四個變數 top, bottom, left, right
分別代表「還沒被點到的同學」是從第幾橫列到第幾橫列
又是從第幾直行到第幾直行

螺旋的第一步，是從左到右，在最前排 (top) 上點人

for(int i=left;i<=right;i++){
    ans.push_back(matrix[top][i]);
}
top += 1;

螺旋的第二步，是從前到後，在最右排 (right) 上點人

for(int i=top;i<=bottom;i++){
    ans.push_back(matrix[i][right]);
}
right -= 1;

螺旋的第三步，是從右到左，在最後一排 (bottom) 上點人

for(int i=right;i>=left;i--){
    ans.push_back(matrix[bottom][i]);
}
bottom -= 1;

螺旋的第四步，是從後到前，在最左排 (left) 上點人

for(int i=bottom;i>=top;i--){
    ans.push_back(matrix[i][left]);
}
left += 1;

接著再回到第一步驟，在剩餘的長方形的第一排上，由左至右點人…
直到全班都被點完為止（剩餘的長方形為空）
寫成程式就是下述的樣子：

int m = matrix.size(), n = matrix[0].size();
vector<int>  ans;
int top=0, bottom=m-1, left=0, right=n-1;
while(true){ // 無限迴圈
    // 從左到右，最前排
    for(int i=left;i<=right;i++){
        ans.push_back(matrix[top][i]);
    }
    top += 1;
    if(top>bottom) break; // 長方形為空的話，就跳脫離開迴圈
    // 從前到後，最右排
    for(int i=top;i<=bottom;i++){
        ans.push_back(matrix[i][right]);
    }
    right -= 1;
    if(left>right) break; // 長方形為空的話，就跳脫離開迴圈
    // 從右到左，最後排
    for(int i=right;i>=left;i--){
        ans.push_back(matrix[bottom][i]);
    }
    bottom -= 1;
    if(top>bottom) break; // 長方形為空的話，就跳脫離開迴圈
    // 從後到前，最左排
    for(int i=bottom;i>=top;i--){
        ans.push_back(matrix[i][left]);
    }
    left += 1;
    if(left>right) break; // 長方形為空的話，就跳脫離開迴圈
}
return ans;

記得這是 Leetcode 54 喔！

【學生練習題】

• Leetcode 59: 創造螺旋矩陣

題目給一個整數 n，請造出一個 n*n 的矩陣
裡面內容是把 1 至 n*n 的所有整數依照螺旋位置排放

例如 n=3

斜線走訪矩陣

【例題】

老師開始點同學回答問題
依照「斜線」的順序來點人
請看圖例：

被點到的順序是 [1,2,4,7,5,3,6,8,9]

題目給一個名為 mat 的矩陣
請算出大家被點到的順序並存在一維 vector 裡回傳

這是 Leetcode 上的題目，連結是 Leetcode 498

觀察1:
用(r, c)來表示格子的座標，我們發現
屬於同一條斜線上的格子，他們的r+c 都是相同的值
r+c 最小為0，最大為 (n-1)+(m-1)

觀察2：
那些「左下到右上的斜線」，也就是sum=r+c 是偶數的那幾條線
c 從小走到大，從 0 開始或是從 sum-(m-1) 開始，看哪個大

觀察3:
那些「右上到左下的斜線」，也就是sum=r+c 是奇數的那幾條線
r 從小走到大，從 0 開始或是從 sum-(n-1) 開始，看哪個大

因此我們可以以 sum 為主角，從 0 到(n-1)+(m-1)
交錯地拜訪「左下右上」和「右上左下」的斜線
寫成程式就是下述的樣子：

vector<int> ret;
int m = mat.size();
int n = mat[0].size();
for(int sum = 0; sum<=n+m-2;sum++){
    // 左下到右上的斜線
    for(int c = max(0, sum-m+1);c<n;c++){
        int r = sum-c;
        if(r<0) break;
        ret.push_back(mat[r][c]);
    }
    sum++;
    // 右上到左下的斜線
    for(int r = max(0, sum-n+1);r<m;r++){
        int c = sum-r;
        if(c<0) break;
        ret.push_back(mat[r][c]);
    }
}
return ret;

記得這是 Leetcode 498 喔！

【學生練習題】

• Leetcode 766: 常對角矩陣

題目給一個二維 vector 名為 matrix
請問他的每條「左上-右下」的斜線，都是同一個數值嗎？

是

不是

提示：我們只要檢查每個格子是否等於他的「右下角」就可以了

回目錄：國立科學園區實驗中學C++程式語言自學講義