螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
定义当前左右上下边界 leftr,right,yop,bottom，初始值 num =0，迭代终止值 sum= m * n；
当 num < sum 时，始终按照 从左到右 从上到下 从右到左 从下到上 填入顺序循环，每次填入后：
执行 num += 1：得到下一个需要填入的数字；
更新边界：例如从左到右填完后，上边界 top += 1，相当于上边界向内缩 1。
使用for循环一直带上num < sum，是为了解决当n为奇数时，矩阵中心数字无法在迭代过程中被填充的问题。
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> rr = new ArrayList<>();
if(matrix==null||matrix.length==0) return rr;
int m = matrix.length;
int n = matrix[0].length;
int left = 0, right = n - 1, top = 0, bottom = m - 1;
int num = 0, sum = m * n;
while(num<sum){
for(int i = left;i<=right&&num<sum;i++){
rr.add(matrix[top][i]);
num++;
}
top++;
for(int i=top;i<=bottom&&num<sum;i++){
rr.add(matrix[i][right]);
num++;
}
right--;
for(int i=right;i>=left&&num<sum;i--){
rr.add(matrix[bottom][i]);
num++;
}
bottom--;
for(int i=bottom;i>=top&&num<sum;i--){
rr.add(matrix[i][left]);
num++;
}
left++;
}
return rr;
}
}
螺旋矩阵2(生成矩阵)
给你一个正整数 n ，生成一个包含 1 到 n平方 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
也是上面的思路反过来
class Solution {
public int[][] generateMatrix(int n) {
int[][] rr = new int[n][n];
int num = 0;
int sum = n*n;
int left = 0;int right = n-1;int top=0;int bottom=n-1;
while(num<sum){
for(int i=left;i<=right&&num<sum;i++){
num++;
rr[top][i] = num;
}
top++;
for(int i=top;i<=bottom&&num<sum;i++){
num++;
rr[i][right] = num;
}
right--;
for(int i=right;i>=left&&num<sum;i--){
num++;
rr[bottom][i] = num;
}
bottom--;
for(int i=bottom;i>=top&&num<sum;i--){
num++;
rr[i][left] = num;
}
left++;
}
return rr;
}
}
螺旋矩阵3(链表生成矩阵)
给你两个整数：m 和 n ，表示矩阵的维数。
另给你一个整数链表的头节点 head 。
请你生成一个大小为 m x n 的螺旋矩阵，矩阵包含链表中的所有整数。链表中的整数从矩阵 左上角 开始、顺时针 按 螺旋 顺序填充。如果还存在剩余的空格，则用 -1 填充。
返回生成的矩阵。
和第二题一样
class Solution {
public int[][] spiralMatrix(int m, int n, ListNode head) {
int[][] rr = new int[m][n];
int num = 0;
int sum = m*n;
int left = 0;int right = n-1;int top=0;int bottom=m-1;
while(num<sum){
for(int i=left;i<=right&&num<sum;i++){
num++;
rr[top][i] = head.val;
if(head.next!=null){
head = head.next;
}else{
head = new ListNode(-1);
}
}
top++;
for(int i=top;i<=bottom&&num<sum;i++){
num++;
rr[i][right] = head.val;
if(head.next!=null){
head = head.next;
}else{
head = new ListNode(-1);
}
}
right--;
for(int i=right;i>=left&&num<sum;i--){
num++;
rr[bottom][i] = head.val;
if(head.next!=null){
head = head.next;
}else{
head = new ListNode(-1);
}
}
bottom--;
for(int i=bottom;i>=top&&num<sum;i--){
num++;
rr[i][left] = head.val;
if(head.next!=null){
head = head.next;
}else{
head = new ListNode(-1);
}
}
left++;
}
return rr;
}
}
旋转矩阵90°
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
//对角线互换
for(int i = 0 ; i < n; i++){
for(int j = i; j < n; j++){
int t = matrix[i][j]; //交换
matrix[i][j] = matrix[j][i];
matrix[j][i] = t;
}
}
//镜像对称
for(int k = 0;k<n;k++){
int q=0;
int p=n-1;
while(q<p){
int t = matrix[k][q];
matrix[k][q] = matrix[k][p];
matrix[k][p] = t;
q++;
p--;
}
}
}
}
矩阵中的最长递增路径-字节tiktok一面
给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。
当场做出来的代码-超时
class Solution {
private int[][] f = new int[][]{{-1,0},{0,1},{1,0},{0,-1}};
private int m,n;
private int result = 0;
public int longestIncreasingPath(int[][] matrix) {
this.m = matrix.length;
this.n = matrix[0].length;
int[][] used = new int[this.m][this.n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
DFS(matrix,used,1,i,j,-1);
}
}
return result;
}
public void DFS(int[][] matrix,int[][] used,int deep,int i,int j,int c){
if(i<0||i>=m||j<0||j>=n||matrix[i][j]<=c||used[i][j]==1){
return;
}
if(deep>result){
result = deep;
}
used[i][j]=1;
for(int k=0;k<4;k++){
int i2 = i+f[k][0];
int j2 = j+f[k][1];
DFS(matrix,used,deep+1,i2,j2,matrix[i][j]);
}
used[i][j]=0;
}
}
将矩阵看成一个有向图，每个单元格对应图中的一个节点，如果相邻的两个单元格的值不相等，则在相邻的两个单元格之间存在一条从较小值指向较大值的有向边。问题转化成在有向图中寻找最长路径。
深度优先搜索是非常直观的方法。从一个单元格开始进行深度优先搜索，即可找到从该单元格开始的最长递增路径。对每个单元格分别进行深度优先搜索之后，即可得到矩阵中的最长递增路径的长度。
但是如果使用朴素深度优先搜索，时间复杂度是指数级，会超出时间限制，因此必须加以优化。
朴素深度优先搜索的时间复杂度过高的原因是进行了大量的重复计算，同一个单元格会被访问多次，每次访问都要重新计算。由于同一个单元格对应的最长递增路径的长度是固定不变的，因此可以使用记忆化的方法进行优化。用矩阵 memo 作为缓存矩阵，已经计算过的单元格的结果存储到缓存矩阵中。
使用记忆化深度优先搜索，当访问到一个单元格 (i,j) 时，如果 memo[i][j] =0，说明该单元格的结果已经计算过，则直接从缓存中读取结果，如果 memo[i][j]=0，说明该单元格的结果尚未被计算过，则进行搜索，并将计算得到的结果存入缓存中。
遍历完矩阵中的所有单元格之后，即可得到矩阵中的最长递增路径的长度。
class Solution {
private int[][] f = new int[][]{{-1,0},{0,1},{1,0},{0,-1}};
private int m,n;
private int result = 0;
public int longestIncreasingPath(int[][] matrix) {
this.m = matrix.length;
this.n = matrix[0].length;
int[][] record = new int[this.m][this.n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
result = Math.max(result,DFS(matrix,record,i,j));
}
}
return result;
}
public int DFS(int[][] matrix,int[][] record,int i,int j){
if(record[i][j]!=0){
return record[i][j];
}
record[i][j]++;
for(int k=0;k<4;k++){
int i2 = i+f[k][0];
int j2 = j+f[k][1];
if(i2<0||i2>=m||j2<0||j2>=n||matrix[i2][j2]<=matrix[i][j]){
continue;
}
record[i][j] = Math.max(record[i][j],DFS(matrix,record,i2,j2)+1);
}
return record[i][j];
}
}
