问题一
问题描述
给出策略打印旋转矩阵
问题分析
$\left[\begin{array}{cccc}a_{11} & a_{12} & \cdots & a_{1 n} \ a_{21} & a_{22} & \cdots & a_{2 n} \ a_{31} & a_{32} & \cdots & a_{3 n} \ \cdots & \cdots & & \cdots \ a_{m 1} & a_{m 2} & \cdots & a_{m n}\end{array}\right]$
对于上述矩阵，假定采用顺时针进行旋转打印
对打印顺序进行分析，顺时针旋转一圈，打印的是在外面的一层元素
因此对矩阵进行分层，从外向内划分依次得到以下分层：
$[1,1,1,1,1,1,1]$
$[1,2,2,2,2,2,1]$
$[1,2,3,3,3,2,1]$
$[1,2,2,2,2,2,1]$
$[1,1,1,1,1,1,1]$
采用左上$(top,left)$、左下$(bottom,left)$、右上$(top,right)$、右下$(top,right)$四个点定位各层的位置，将打印层分为上下左右四个片区分别进行打印，遍历完当前层的元素后left++、top++、right–、bottom–，进入下一层开始遍历，最终得到整个旋转矩阵。
算法实现
#include<iostream>
#include<vector>
using namespace std;
void PrintMatrix(vector<vector<int>>& matrix) {
int r = matrix.size();
int c = matrix[0].size();
int top = 0, bottom = r - 1, left = 0, right = c - 1;
while (left <= right && top <= bottom) {
for (int i = left; i <= right; i++) {
cout << matrix[top][i] << " ";
}
for (int i = top + 1; i <= bottom; i++) {
cout << matrix[i][right] << " ";
}
if (left < right && top < bottom) {
for (int i = right - 1; i > left; i--) {
cout << matrix[bottom][i] << " ";
}
for (int i = bottom; i > top; i--) {
cout << matrix[i][left] << " ";
}
}
top++;
left++;
right--;
bottom--;
}
cout << endl;
}
int main() {
vector<vector<int>> matrix = { {1,2,3},{4,5,6},{7,8,9} };
vector<vector<int>> matrix1 = { {1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16} };
PrintMatrix(matrix);
PrintMatrix(matrix1);
}在这个问题中，每一元素都要被遍历一次，因此算法的时间复杂度是$O(r*c)$，r为矩阵行数，c为矩阵列数，本算法并不需要开辟额外的空间，故空间复杂度为$O(1)$。
附加思考
顺时针旋转矩阵$90°$
vector<vector<int>> RotateMatrix(vector<vector<int>>& matrix) {
vector<vector<int> > rotate;
vector<int> temp;
int r = matrix.size(), c = matrix[0].size();
for (int j = 0; j < c; j++) {
for (int i = r - 1; i >= 0; i--) {
temp.push_back(matrix[i][j]);
}
rotate.push_back(temp);
temp.clear();
}
return rotate;
}“之”字形打印矩阵
使用两个指针分别从00位置开始，一个指针沿右下的路线抵达矩阵右下角元素，另一个沿下右的路线抵达矩阵右下角，两指针确定的直线上再根据奇偶性判断打印方向
void ZhiPrint(vector<vector<int>>& matrix) {
int r = matrix.size();
int c = matrix[0].size();
int ar = 0, ac = 0;
int br = 0, bc = 0;
int n;
do {
n = ar + ac;
if ( n % 2 == 0) {
for (int i = ar; i <= br; i++) {
cout << matrix[i][n - i] << " ";
}
}
else {
for (int i = br; i >= ar; i--) {
cout << matrix[i][n - i] << " ";
}
}
if (br < r) {
br++;
}
else {
bc++;
}
if (ac < c) {
ac++;
}
else {
ar++;
}
} while (ar != br && ac != bc);
cout << matrix[r - 1][c - 1] << endl;
}问题二
问题描述
给出策略返回一个m*n矩阵中从[1,1]到[m,n]的和最小的一条路径。
问题分析
已知在某一点时想要确定路径下一个元素的位置，路径方向只能是向下/向右，因此网格的第一行/第一列上的元素下一位置只能是该元素的右边/左边，然后确定剩下路径
对于每一待定元素可由其左边/上边的元素到达，比较两数的大小，确定更小的那一个，然后依次得到不同路径，直至抵达[m,n]，再通过回溯得到最小路径。
- 当 $i>0$ 且 $j=0$ 时， $d p[i][0]=d p[i-1][0]+\operatorname{grid}[i][0]$
- 当 $i=0$ 且 $j>0$ 时， $d p[0][j]=d p[0][j-1]+\operatorname{grid}[0][j]$
- 当 $i>0$ 且 $j>0$ 时， $d p[i][j]=\min (d p[i-1][j], d p[i][j-1])+\operatorname{grid}[i][j]$
算法实现
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int MinPath(vector<vector<int>>& matrix) {
int r = matrix.size(), c = matrix.size();
auto dp = vector<vector<int> >(r, vector<int>(c));
dp[0][0] = matrix[0][0];
for (int i = 1; i < r; i++) {
dp[i][0] = dp[i - 1][0] + matrix[i][0];
}
for (int i = 1; i < c; i++) {
dp[0][i] = dp[0][i - 1] + matrix[0][i];
}
for (int i = 1; i < r; i++) {
for (int j = 1; j < c; j++) {
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];
}
}
return dp[r - 1][c - 1];
}
int main() {
vector<vector<int> > matrix = { {1,3,1},{1,5,1},{4,2,1} };
cout << MinPath(matrix) << endl;
}需要遍历整个数组，时间复杂度是$O(mn)$
重新开辟了一个大小相同的向量空间，空间复杂度是$O(mn)$，在空间方面可以进行优化，直接在原矩阵上进行dp操作，不使用额外空间，改进到$O(1)$
