資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的對角線遍歷
假設我們有一個 M x N 元素的矩陣，我們需要按對角線順序查詢矩陣中的所有元素。如果矩陣如下所示：
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
輸出將是 [1,2,4,7,5,3,6,8,9]
為了解決這個問題，我們將遵循以下步驟：
- 建立一個數組 ret，設定 row := 0 和 col := 0，n := 行數，m := 列數，down := false
- 對於 i 的範圍從 0 到 n – 1
- x := i，y := 0
- 建立一個數組 temp
- 當 x >= 0 且 y < m 時，執行以下操作
- 將 matrix[x,y] 插入到 temp 中，並將 x 減 1，y 加 1
- 如果 down 為 true，則反轉 temp 陣列
- 對於 i 的範圍從 0 到 temp 的大小 – 1，將 temp[i] 插入到 ret 中
- down := down 的反值
- 對於 i 的範圍從 1 到 m – 1
- x := n – 1，y := 1，建立一個數組 temp
- 當 x >= 0 且 y < m 時，
- 將 matrix[x, y] 插入到 temp 中，並將 x 減 1，y 加 1
- 對於 i 的範圍從 0 到 temp 的大小 – 1，將 temp[i] 插入到 ret 中
- down := down 的反值
- 返回 ret。
讓我們看看下面的實現來更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
vector <int> ret;
int row = 0;
int col = 0;
int n = matrix.size();
int m = n? matrix[0].size() : 0;
bool down = false;
for(int i = 0; i < n; i++){
int x = i;
int y = 0;
vector <int> temp;
while(x >= 0 && y < m){
temp.push_back(matrix[x][y]);
x--;
y++;
}
if(down) reverse(temp.begin(), temp.end());
for(int i = 0; i < temp.size(); i++)ret.push_back(temp[i]);
down = !down;
}
for(int i = 1; i < m; i++){
int x = n - 1;
int y = i;
vector <int> temp;
while(x >= 0 && y < m){
temp.push_back(matrix[x][y]);
x--;
y++;
}
if(down) reverse(temp.begin(), temp.end());
for(int i = 0; i < temp.size(); i++)ret.push_back(temp[i]);
down = !down;
}
return ret;
}
};
main(){
vector<vector<int>> v = {{1,2,3},{4,5,6},{7,8,9}};
Solution ob;
print_vector(ob.findDiagonalOrder(v));
}輸入
[[1,2,3],[4,5,6],[7,8,9]]
輸出
[1, 2, 4, 7, 5, 3, 6, 8, 9, ]
更新於: 2020年5月2日
1K+ 次檢視
廣告