# Ch23 矩陣
> 搭配 [Leetcode 解題系統](https://leetcode.com/)
> 回目錄：[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z)
## <font color='darkblue'>矩陣 / 二維陣列</font>
之前所教過的陣列/vector，都是一維的
我們可以在一排格子裡儲存數值，用index來表示「哪一格」
這一章我們要學的是二維陣列，會用到「第幾列第幾行」的概念
宣告一個固定大小的二維陣列
```cpp
int a[50][100];
```
這樣一來 a 就是一個有 50\*100 格的二維陣列
### 宣告
宣告一個二維的 vector
```cpp
vector<vector<int>> a;
```
這樣一來 a 就是一個空的二維 vector
像是 vector 包著 vector 的概念
### push_back
我們可以增加新的列
```cpp
vector<int> b = {1, 2, 3};
a.push_back(b);
```
這樣一來 a 的最後一列就會是 {1, 2, 3}
也可以對於某一列添加新的元素
```cpp
a[5].push_back(3);
```
這樣一來 a 的第 5 列就會多一個新的數字 3
### 賦值/取值
當我們想要把 a 的第 i 列第 j 行變成某數 x 時
可以寫成
```cpp
a[i][j] = x;
```
同樣的，當我們想要取用 a 的第 i 列第 j 行的值時
可以寫成
```cpp
int y = a[i][j];
```
### 清空
當我們想要把名為 a 的二維 vector 整個清空
可以寫成
```cpp
a.clear();
```
若我們只是想把 a 的第 i 列清空
可以寫成
```cpp
a[i].clear();
```
這樣一來，其他列都還是原本的樣子
### 長度
當我們想要知道 a 有幾列
可以寫成
```cpp
cout << a.size();
```
當我們想要知道 a 的第 i 列有多長
可以寫成
```cpp
cout << a[i].size();
```
不同於靜態的二維陣列 `int a[50][100]` 一定是固定的長寬
二維的 vector 的每一列可以是不同長度的
## <font color='darkblue'>拜訪每個值</font>
<font color='darkorange'>【例題】</font>
> 題目給一個名為 accounts 的二維 vector
> 裡面的每一列都代表某一個人的全部財產
> 例如某一列是 [1, 2, 3] ，就代表那個人有 1+2+3=6 元
> 請問最有錢的那個人有多少錢？
這是 Leetcode 上的題目，連結是 [Leetcode 1672](https://leetcode.com/problems/richest-customer-wealth/description/)
但凡是二維陣列的題目，我們通常都會要用雙層的迴圈來拜訪格子們
我們可以在迴圈的最外面用一個變數 `max_sum` 來代表最大值
中間用一個變數 `sum` 來計算和暫存每個人的財產
```cpp=
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;
```
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 2643: 最多 1 的那一列 ](https://leetcode.com/problems/row-with-maximum-ones/)
>
> 題目給我們一個名為 mat 的二維 vector，請問最多 1 的那一列是哪一列呢？他有幾個 1 呢？
注意這題要回傳的是一個一維 vector，要有兩格
第一格用來存「第幾列最多1」，第二格用來存「它有幾個1」
## <font color='darkblue'>對角線上的格子</font>
<font color='darkorange'>【例題】</font>
> 題目給一個名為 mat 的二維 vector
> 請問在"對角線"上的格子數字的總和是多少呢？
這是 Leetcode 上的題目，連結是 [Leetcode 1572](https://leetcode.com/problems/matrix-diagonal-sum/)
如果二維陣列的列數和行數相同，他就是一個正方形矩陣
如何判斷一個格子是不是在對角線上呢？
假設正方形邊長是 5
左上-右下的對角線有這些格子：(0, 0), (1, 1), (2, 2)...
右上-左下的對角線有這些格子：(0, 4), (1, 3), (2, 2)...
我們可以觀察出這樣的規律：
用 `(i, j)` 來代表某格子的座標
若 `i==j` 或是 `i+j==(n-1)`，則可知 `(i, j)` 在對角線上
```cpp=
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;
```
或是更有效率的方法
就是只拜訪對角線上的格子
```cpp=
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;
```
這樣只需要一層迴圈就能完成了
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 2614: 對角線上最大的質數 ](https://leetcode.com/problems/prime-in-diagonal/)
>
> 所有在對角線上的格子裡，最大的「質數」是多少呢？
判斷質數有點麻煩，幸好我們在 [for 迴圈](https://hackmd.io/@CLKO/H1iyHQc2b?type=view#%E7%B5%84%E5%90%88%E6%8A%80%EF%BC%9Afor%E8%88%87if%E6%90%AD%E9%85%8D%E4%BD%BF%E7%94%A8) 的單元學了簡單的做法
或是可以直接照抄：
```cpp=
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;
}
```
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 2319: X 矩陣 ](https://leetcode.com/problems/check-if-matrix-is-x-matrix/)
>
> 題目給我們一個名為 grid 的二維 vector，請問是不是所有對角線上的數字都不是 0 ，且所有不在對角線上的數字都是 0 呢？
>
> 例如這個矩陣符合條件，要回傳 true
> 
>
> 例如這個矩陣就不符合條件，要回傳 false
> 
## <font color='darkblue'>同一行或同一列的鄰居</font>
<font color='darkorange'>【例題】</font>
> 題目給一個名為 matrix 的二維 vector
> 請找出所有的「幸運數字」
> 被認為「幸運」的條件是，這個數字是他那一橫列裡最小的，又是他那一直行裡最大的
這是 Leetcode 上的題目，連結是 [Leetcode 1380](https://leetcode.com/problems/lucky-numbers-in-a-matrix/)
我們可以拜訪 matrix 裡的每個數字
檢查和他同一橫列和同一直行裡有沒有哪位鄰居害他無法成為「幸運數字」的
如果都沒有，他就是幸運的
```cpp=
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;
```
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 1582: 特別的數字 ](https://leetcode.com/problems/special-positions-in-a-binary-matrix/)
>
> 題目給一個名為 mat 的二維 vector
> 請問總共有幾個「特別的格子」呢？
> 格子被認為「特別」的條件是，他這格是1，且和他同一行同一列的其他格子全都是0
>
> 圖中的藍色是特別的格子
>  
> 左邊這個矩陣有 1 個特別格子，右邊這個矩陣有 3 個特別格子
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 2352: 相同的行列 ](https://leetcode.com/problems/equal-row-and-column-pairs/)
>
> 題目給一個名為 grid 的二維 vector
> 請問有幾對（行,列）是一樣的數字呢
>
> 以下的例子，第二列和第一行都是 [2, 7, 7]
> 總共一對
> 
>
> 以下的例子，第零列和第零行都是 [3, 1, 2, 2]
> 還有第二列和第二行都是 [2, 4, 2, 2]
> 還有第三列和第二行都是 [2, 4, 2, 2]
> 總共三對
> 
## <font color='darkblue'>一維和二維的轉換</font>
<font color='darkorange'>【例題】</font>
> 班上有 `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](https://leetcode.com/problems/convert-1d-array-into-2d-array/)
依據上述的規則
我們可以歸納出座號為 `i` 的人會被分配到第 `i/n` 排的第 `i%n` 個座位
```cpp=
// 如果學生人數不等於 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;
```
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 566: 重塑矩陣 ](https://leetcode.com/problems/reshape-the-matrix/)
>
> 學生們正依照例題的規則，照著座號坐在一間教室裡
> 他們現在被用一個名為 mat 的二維 vector 來表示
> 現在他們要換到一間新的教室
> 新教室總共有 r 排，每排有 c 個座位
> 大家依然要照座號坐，也就是第一排是`[0, 1, ..., c-1]`...
> 請依照這個規則建立一個二維的 vector 把大家放到新教室的座位上
> 但若學生的數量並非 r*c，就請回傳原本的 mat
提示：可以先用一個一維的 vector 來暫存 mat 裡的數字
再用例題的方法把一維的 vector 變成 r*c 的二維 vector
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 1260: 往右 k 格 ](https://leetcode.com/problems/shift-2d-grid/)
>
> 學生們正依照例題的規則，照著座號坐在電腦教室裡
> 他們現在被用一個名為 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可能會是很大的數字，有可能比全班人數還要大
能不能利用數學運算，設計一個公式來讓每個人都直接算出他該把考卷交給誰呢？
## <font color='darkblue'>矩陣的旋轉</font>
<font color='darkorange'>【例題】</font>
> 班上的同學們依照自己的喜好坐在座位上
> 教室裡的座位剛好是個正方形（行數和列數一樣多）
>
> 今天老師把黑板移到了教室的右側
> 大家若是想要保持原本對於座位和黑板的相對位置的喜好
> 就必須隨著黑板的移動
> 把所有人的位置也都順時針旋轉90度
> 像是這樣：
> 
>
> 請在原本的矩陣 matrix 上幫大家完成旋轉
這是 Leetcode 上的題目，連結是 [Leetcode 48](https://leetcode.com/problems/rotate-image/)
我們可以先歸納出每個坐在`(r, c)`位置的人，他的新座位該怎麼計算
假設正方形邊長是 `n`
我們發現，一個原本在`(r, c)`位置的人，他的新座位必然是`(c, n-1-r)`
接下來，請注意大家是在「原本的教室」直接換座位
而不是去新的空教室坐
所以換座位的過程會像是這樣
* 小藍跑到小綠的座位，說，起來，該我坐了
* 小綠只好跑到小黃的座位，把小黃趕走
* 小黃只好跑到小橘的座位，把小橘趕走
* 小橘於是跑到小藍的舊座位坐了下來，至此這四人順利完成了交換
用程式表示就是
```cpp=
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; // 小橘也有空位可坐了，就是小藍的舊座位
```
再來要注意的是，剛才小藍已經做一次「首先起身趕走新座位的同學」的行為了
小綠小黃小橘因此被動地完成了交換
他們三位就不需要再進行一次「首先起身趕走新座位的同學」的行為了
依照這個規則
我們可以把教室切成四個區域
然後永遠只讓藍色那塊區域的人來負責當「首先起身趕走新座位的同學」的人
其他三個區塊的人都只要被動地被移動
寫成程式就是這樣
```cpp=
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](https://leetcode.com/problems/rotate-image/) 喔！
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 1886: 能轉成目標的樣子嗎？ ](https://leetcode.com/problems/determine-whether-matrix-can-be-obtained-by-rotation/)
>
> 題目給兩個正方形矩陣，分別是 mat 和 target
> 請問我們能夠藉由旋轉 mat 若干次，把它變成和 target 一模一樣嗎？
## <font color='darkblue'>螺旋走訪矩陣</font>
<font color='darkorange'>【例題】</font>
> 老師開始點同學回答問題
> 依照「螺旋」的順序來點人
> 先從左到右點第一橫列的同學，轉彎
> 再從前到後點最右直行的同學，轉彎...以此類推
> 
>
> 請回傳一個一維 vector，依序儲存被點到的人
> 以上面的例子，就是 `[1,2,3,4,8,12,11,10,9,5,6,7]`
這是 Leetcode 上的題目，連結是 [Leetcode 54](https://leetcode.com/problems/spiral-matrix/)
我們可以觀察出一個規則：
每次點完一個橫列或直排，要轉彎的那一瞬間
剩下還沒點到的同學都是組成一個長方形
因此我們可以用四個變數 top, bottom, left, right
分別代表「還沒被點到的同學」是從第幾橫列到第幾橫列
又是從第幾直行到第幾直行
螺旋的第一步，是從左到右，在最前排 (top) 上點人
```cpp=
for(int i=left;i<=right;i++){
ans.push_back(matrix[top][i]);
}
top += 1;
```
螺旋的第二步，是從前到後，在最右排 (right) 上點人
```cpp=
for(int i=top;i<=bottom;i++){
ans.push_back(matrix[i][right]);
}
right -= 1;
```
螺旋的第三步，是從右到左，在最後一排 (bottom) 上點人
```cpp=
for(int i=right;i>=left;i--){
ans.push_back(matrix[bottom][i]);
}
bottom -= 1;
```
螺旋的第四步，是從後到前，在最左排 (left) 上點人
```cpp=
for(int i=bottom;i>=top;i--){
ans.push_back(matrix[i][left]);
}
left += 1;
```
接著再回到第一步驟，在剩餘的長方形的第一排上，由左至右點人...
直到全班都被點完為止（剩餘的長方形為空）
寫成程式就是下述的樣子：
```cpp=
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](https://leetcode.com/problems/spiral-matrix/) 喔！
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 59: 創造螺旋矩陣 ](https://leetcode.com/problems/spiral-matrix-ii/)
>
> 題目給一個整數 n，請造出一個 n\*n 的矩陣
> 裡面內容是把 1 至 n\*n 的所有整數依照螺旋位置排放
>
> 例如 n=3
> 
## <font color='darkblue'>斜線走訪矩陣</font>
<font color='darkorange'>【例題】</font>
> 老師開始點同學回答問題
> 依照「斜線」的順序來點人
> 請看圖例：
> 
> 被點到的順序是 [1,2,4,7,5,3,6,8,9]
>
> 題目給一個名為 mat 的矩陣
> 請算出大家被點到的順序並存在一維 vector 裡回傳
這是 Leetcode 上的題目，連結是 [Leetcode 498](https://leetcode.com/problems/diagonal-traverse/)
觀察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)`
交錯地拜訪「左下右上」和「右上左下」的斜線
寫成程式就是下述的樣子：
```cpp=
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](https://leetcode.com/problems/diagonal-traverse/) 喔！
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 766: 常對角矩陣 ](https://leetcode.com/problems/toeplitz-matrix/)
>
> 題目給一個二維 vector 名為 matrix
> 請問他的每條「左上-右下」的斜線，都是同一個數值嗎？
>
> 是
> 
>
> 不是
> 
提示：我們只要檢查每個格子是否等於他的「右下角」就可以了
##
> 回目錄：[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z)
Sign in with Wallet
Connect another wallet