[算法]旋转矩阵问题(Spiral Matrix)
2024-10-11 06:11:02
题目一:
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
You should return [1,2,3,6,9,8,7,4,5]
.
解答:
采用从最外层一层一层向内操作的方法。
public class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
if(matrix==null||matrix.length==0||matrix[0].length==0) return res;
//每一圈左上角数字的坐标为(top,left),右下角的数字的坐标为(bottom,right)
int top = 0, left = 0;
int bottom = matrix.length - 1, right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
outEdge(res, matrix, left++, top++, right--, bottom--);
}
return res;
}
private static void outEdge(List<Integer> res, int[][] matrix, int left, int top, int right, int bottom) {
if (top == bottom) {
for (int i = left; i <= right; i++) {
res.add(matrix[top][i]);
}
} else if (left == right) {
for (int i = top; i <= bottom; i++) {
res.add(matrix[i][left]);
}
} else {
int curRow = top;
int curCol = left;
while (curCol < right) {
res.add(matrix[top][curCol++]);
}
while (curRow < bottom) {
res.add(matrix[curRow++][right]);
}
while (curCol > left) {
res.add(matrix[bottom][curCol--]);
}
while (curRow > top) {
res.add(matrix[curRow--][left]);
}
}
}
}
题目二:
Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
For example,
Given n = 3
,
You should return the following matrix:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
public static int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
int top = 0, left = 0;
int bottom = n - 1, right = n - 1;
int num = 1;
while (left<=right&&top<=bottom) {
num= inputEdge(num, res, left++, top++, right--, bottom--);
}
return res;
}
private static int inputEdge(int num, int[][] res, int left, int top, int right, int bottom) {
int curRow = top;
int curCol = left;
if (top==bottom&&left==right){
res[top][left]=num;
return num;
} while (curCol < right) {
res[top][curCol++] = num++;
}
while (curRow < bottom) {
res[curRow++][right] = num++;
}
while (curCol > left) {
res[bottom][curCol--] = num++;
}
while (curRow > top) {
res[curRow--][left] = num++;
}
return num;
}
最新文章
- eclipse快捷键以及使用技巧大全
- 防止apache下面直接输入目录访问文件
- python-unexpected content storage modification出错
- SRM 442(1-250pt, 1-500pt)
- javascript——处理(获取)浏览器版本、操作系统
- Qt install Phonon
- 定制一个winCE5.0操作系统
- python实现TCP/UDP通信
- 超绚丽CSS3多色彩发光立方体旋转动画
- Nginx与ftp服务器
- 在Web根目录下建立testdb.php文件内容
- Redis和RabbitMQ在项目中的使用
- 浅析ARM公司在物联网领域的战略布局
- [Android] 修图工具Draw9patch使用小结(附ubuntu快捷截图方法)
- delphi 实现文件上传下载
- Flash Player离线安装包下载指南
- GitLab项目迁移到Gerrit
- 【LeetCode】 617. 合并二叉树
- JSP/Servlet中文乱码处理总结
- 申请单位iOS开发者账号