给定一个整数n,将数字1到按螺旋的顺序填入n×n的矩阵
例如:
给出的n=3,
你应该返回如下矩阵:
[ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
import java.util.*; public class Solution { /** * * @param n int整型 * @return int整型二维数组 */ public int[][] generateMatrix (int n) { int[][] arr = new int[n][n]; if(n == 0){ return arr; } int s = 0; int num = 2; int end = n * n; int i = 0; int j = 0; arr[0][0] = 1; for (int k = 1; k < end; k++) { if (s == 0) { j++; } else if (s == 1) { i++; } else if (s == 2) { j--; } else if (s == 3) { i--; } arr[i][j] = num++; if (s == 0 && (j >= n - 1 || arr[i][j + 1] != 0)) { s++; } else if (s == 1 && (i >= n - 1 || arr[i + 1][j] != 0)) { s++; } else if (s == 2 && (j == 0 || arr[i][j - 1] != 0)) { s++; } else if (s == 3 && (arr[i - 1][j] != 0)) { s = 0; } } return arr; } }
/*每一个螺旋可以由起始位置确定,四角坐标表示为: (start,start),(start,n-start-1) (n-start-1,start),(n-start-1,n-start-1) */ int[][] res = new int[n][n]; int startIndex = 0; int val = 1; if (n < 1 || n > 1000) { return res; } while (startIndex <= (n - 1) / 2) { if (startIndex == (n - 1 / 2)) { res[startIndex][startIndex] = val; break; } for (int right = startIndex; right < (n - startIndex); right++) { //向右 res[startIndex][right] = val; val++; } for (int height = startIndex + 1; height < (n - startIndex); height++) {//下 res[height][n - startIndex - 1] = val; val++; } for (int left = (n - startIndex) - 2; left >= startIndex; left--) { //左 res[n - startIndex - 1][left] = val; val++; } for (int up = (n - startIndex) - 2; up > startIndex; up--) { //上 res[up][startIndex] = val; val++; } startIndex++; } return res;
public class Solution { public int[][] generateMatrix(int n) { int num = n * n; int c = 0; int row = 1; int m = 1; int x = 0; int count = 0; count = n; int[][] arr = new int[n][n]; for(int i = 1; i <= num; i++) { if(c >= 0 && c < count) { arr[row - 1][x++] = i; c ++; } else if(c >= count && c < count * 2 - 2) { arr[m++][n - row] = i; c ++; }else if(c >= count * 2 - 2 && c < count * 3 - 2) { arr[n - row][--x] = i; c ++; }else if(c >= count * 3 - 2 && c < count * 4 - 4){ arr[--m][row - 1] = i; c ++; } if(c == count * 4 - 4) { count = n - 2 * row; row++; x++; m++; c = 0; } } return arr; } }
public class Solution { public int[][] generateMatrix(int n) { int[][] result = new int[n][n]; int num = 1; int rowBegin = 0, rowEnd = n - 1; int colBegin = 0, colEnd = n - 1; while(rowBegin <= rowEnd && colBegin <= colEnd) { for(int i = rowBegin; i <= rowEnd; i++) { result[rowBegin][i] = num; num ++; } rowBegin ++; for(int i = rowBegin; i <= rowEnd; i++) { result[i][colEnd] = num; num ++; } colEnd --; for(int i = colEnd; i >= colBegin; i--) { result[rowEnd][i] = num; num ++; } rowEnd --; for (int i = rowEnd; i >= rowBegin; i--) { result[i][colBegin] = num; num ++; } colBegin ++; } return result; } }
public class Solution { public int[][] generateMatrix(int n) { if(n < 0) return null; int[][] matrix = new int[n][n]; int left = 0, right = n - 1; int up = 0, down = n - 1; int count = 0; //动态修改上下左右边界,并同时判断是否越界 while(true){ for(int i = left; i <= right; i++){ matrix[up][i] = ++count; } up++; if(up > down) break; for(int i = up; i <= down; i++){ matrix[i][right] = ++count; } right--; if(right < left) break; for(int i = right; i >= left; i--){ matrix[down][i] = ++count; } down--; if(up > down) break; for(int i = down; i >= up; i--){ matrix[i][left] = ++count; } left++; if(right < left) break; } return matrix; } }
public class Solution { public int[][] generateMatrix(int n) { int[][] a = new int[n][n]; if(n==0) return a; int now = 1; int r,c; for(int i=0;i<(n+1)/2;i++){ for(c=i;c<n-i;c++) a[i][c]=now++; c--; for(r=i+1;r<n-i;r++) a[r][c]=now++; r--; for(c--;c>=i;c--) a[r][c]=now++; c++; for(r--;r>i;r--) a[r][c]=now++; r++; } return a; } }
/**
Created by forcht on 2018/5/21.
*/
public class Solution {
public int[][] generateMatrix(int n) {
int[][] p=new int[n][n]; int x=0,y=0,i=1; int[] dx={0,1,0,-1}; int[] dy={1,0,-1,0}; int row=0,column=0; while (i<=n*n){ while (row<n&&row>=0&&column<n&&column>=0&&p[row][column]==0){ p[row][column]=i++; row+=dx[x]; column+=dy[y]; } row-=dx[x]; column-=dy[y]; x=(x+1)%4; y=(y+1)%4; row+=dx[x]; column+=dy[y]; } return p;
}
}
public class Solution { public int[][] generateMatrix(int n) { int[][] matrix = new int[n][n]; int left = 0, top = 0, right = n-1, bottom = n-1; int num = 0; while(top <= bottom && left <= right) { for(int i=left; i <= right && top <= bottom; i++) { matrix[top][i] = ++num; } top++; for(int i=top; i <= bottom && left <= right; i++) { matrix[i][right] = ++num; } right--; for(int i=right; i >= left && top <= bottom; i--) { matrix[bottom][i] = ++num; } bottom--; for(int i=bottom; i >= top && left <= right; i--) { matrix[i][left] = ++num; } left++; } return matrix; } }
This is my solution for Spiral Matrix I, https://oj.leetcode.com/discuss/12228/super-simple-and-easy-to-understand-solution. If you can understand that, this one is a no brainer :)
Guess what? I just made several lines of change (with comment "//change") from that and I have the following AC code:
public class Solution { public int[][] generateMatrix(int n) { // Declaration int[][] matrix = new int[n][n]; // Edge Case if (n == 0) { return matrix; } // Normal Case int rowStart = 0; int rowEnd = n-1; int colStart = 0; int colEnd = n-1; int num = 1; //change while (rowStart <= rowEnd && colStart <= colEnd) { for (int i = colStart; i <= colEnd; i ++) { matrix[rowStart][i] = num ++; //change } rowStart ++; for (int i = rowStart; i <= rowEnd; i ++) { matrix[i][colEnd] = num ++; //change } colEnd --; for (int i = colEnd; i >= colStart; i --) { if (rowStart <= rowEnd) matrix[rowEnd][i] = num ++; //change } rowEnd --; for (int i = rowEnd; i >= rowStart; i --) { if (colStart <= colEnd) matrix[i][colStart] = num ++; //change } colStart ++; } return matrix; } }
Obviously, you could merge colStart and colEnd into rowStart and rowEnd because it is a square matrix. But this is easily extensible to matrices that are m*n.
public class Solution { public int[][] generateMatrix(int n) { int[][] m = new int[n][n]; int value = 1; for (int round = 0; round < n / 2 + n % 2; round ++ ) { for (int i = round; i < n - round; i ++ ) m[round][i] = value ++ ; for (int i = round + 1; i < n - round; i ++ ) m[i][n - round - 1] = value ++ ; for (int i = n - round - 2; i >= round; i -- ) m[n - round - 1][i] = value ++ ; for (int i = n - round - 2; i >= round + 1; i -- ) m[i][round] = value ++ ; } return m; } }