螺旋矩阵(java实现)
程序员文章站
2022-07-15 18:25:30
...
题目一
对于一个 n 行 m 列的表格,我们可以使用螺旋的方式给表格依次填上正整数,我们称填好的表格为一个螺旋矩阵。
例如,一个 4 行 5 列的螺旋矩阵如下:
1 2 3 4 5
14 15 16 17 6
13 20 19 18 7
12 11 10 9 8
输入格式
输入的第一行包含两个整数 n, m,分别表示螺旋矩阵的行数和列数。
第二行包含两个整数 r, c,表示要求的行号和列号。
输出格式
输出一个整数,表示螺旋矩阵中第 r 行第 c 列的元素的值。
样例输入
4 5
2 2
样例输出
15
评测用例规模与约定
对于 30% 的评测用例,2 <= n, m <= 20。
对于 70% 的评测用例,2 <= n, m <= 100。
对于所有评测用例,2 <= n, m <= 1000,1 <= r <= n,1 <= c <= m。
图解:(按照下图所示的方向进行遍历)
1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18-19-20
螺旋矩阵的思路:
- 定义上下左右四个方向
- 左方向的初始值就是二维数组的最左一列下标(left)
- 右方向的初始值就是二维数组的最右一列下标(right)
- 上方向的初始值就是二维数组的最上一行下标(top)
- 下方向的初始值就是二维数组的最下一行下标(bottom)
- 按照"右->下->左->上"的方向对二维数组进行填充,初始就是往右方向进行遍历,注意的是外层循环的条件就是左方向的值要小于等于右方向并且上方向的值要小于等于下方向
- 右方向遍历:for循环变量的初始值就是left,当达到right边界的时候,说明上面已经遍历完一行了,所以top++,准备向下遍历,需要将遍历的方向改为bottom;
- 下方向遍历:for循环变量的初始值就是top,当达到bottom边界的时候,说明右边已经遍历完一列了,所以right- -,准备向左遍历,需要将遍历的方向改为left;
- 左方向遍历:for循环变量的初始值就是right,当达到left边界的时候,说明下面已经遍历完一行了,所以bottom- -,准备向上遍历,需要将遍历的方向改为top;
- 上方向遍历:for循环变量的初始值就是bottom,当达到top边界的时候,说明左边已经遍历完一列了,所以left++,准备向右遍历,需要将遍历的方向改为right;
代码实现:
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();//行
int m=sc.nextInt();//列
int r=sc.nextInt();//第几行,不是指行下标
int c=sc.nextInt();//第几列,不是指列下标
sc.close();
int[][] arr=new int[n][m];
int left=0;//左方向
int right=arr[0].length-1;//右方向
int top=0;//上方向
int bottom=arr.length-1;//下方向
String direction="right";//要遍历的方向
int temp=1;
while(left<=right&&top<=bottom){
if(direction.equals("right")){
for(int i=left;i<=right;i++){
arr[top][i]=temp++;
}
//从左遍历到右边界,准备向下遍历,上面已经遍历完一行了,所以top++
top++;
direction="bottom";
}else if(direction.equals("bottom")){
for(int i=top;i<=bottom;i++){
arr[i][right]=temp++;
}
//从上遍历到下边界,准备向左遍历,右边已经遍历完一列了,所以right--
right--;
direction="left";
}else if(direction.equals("left")){
for(int i=right;i>=left;i--){
arr[bottom][i]=temp++;
}
//从右遍历到左边界,准备向上遍历,下面已经遍历完一行了,所以bottom--
bottom--;
direction="top";
}else if(direction.equals("top")){
for(int i=bottom;i>=top;i--){
arr[i][left]=temp++;
}
//从下遍历到上边界,准备向右遍历,左边已经遍历完一列了,所以left++
left++;
direction="right";
}
}
System.out.println(arr[r-1][c-1]);
}
}
题目二
给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。
示例 1:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
示例2:
输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]
思路跟上一题类似,只是把给二维数组赋值的操作转化成读取二维数组的值,同样是以螺旋矩阵的方式进行读取
代码实现:
public class Main {
public static void main(String[] args) {
int[][] arr={{1,2,3,4},{5,6,7,8},{9,10,11,12}};
int[] a = spiralMatrix(arr);
System.out.println(Arrays.toString(a));
}
public static int[] spiralMatrix(int[][] arr){
int m=arr.length;//行
int n=arr[0].length;//列
int left=0;//左方向
int right=arr[0].length-1;//右方向
int top=0;//上方向
int bottom=arr.length-1;//下方向
int[] a=new int[m*n];
int temp=0;
String direction="right";//要遍历的方向
while(left<=right&&top<=bottom){
if(direction.equals("right")){
for(int i=left;i<=right;i++){
a[temp++]=arr[top][i];
}
//从左遍历到右边界,准备向下遍历,上面已经遍历完一行了,所以top++
top++;
direction="bottom";
}else if(direction.equals("bottom")){
for(int i=top;i<=bottom;i++){
a[temp++]=arr[i][right];
}
//从上遍历到下边界,准备向左遍历,右边已经遍历完一列了,所以right--
right--;
direction="left";
}else if(direction.equals("left")){
for(int i=right;i>=left;i--){
a[temp++]=arr[bottom][i];
}
//从右遍历到左边界,准备向上遍历,下面已经遍历完一行了,所以bottom--
bottom--;
direction="top";
}else if(direction.equals("top")){
for(int i=bottom;i>=top;i--){
a[temp++]=arr[i][left];
}
//从下遍历到上边界,准备向右遍历,左边已经遍历完一列了,所以left++
left++;
direction="right";
}
}
return a;
}
}
学习螺旋矩阵的参考视频:
https://www.bilibili.com/video/BV1zJ411v7MJ?from=search&seid=3253936520677759108