Open youngyangyang04 opened 6 months ago
我用gpt生成的, 稍微简洁一些, 模拟过程也好理解一点...
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> Matrix(n, vector<int>(n, 0));
int top = 0, bottom = n - 1, left = 0, right = n-1;
int num = 1;
while(num <= n * n){
for (int i = left; i<= right; ++i){
Matrix[top][i] = num ++;
}
++top ;
for (int i = top; i <= bottom; ++i){
Matrix[i][right] = num ++;
}
--right ;
for (int i = right; i >= left; --i){
Matrix[bottom][i] = num++;
}
--bottom;
for (int i = bottom; i >= top; --i){
Matrix[i][left] = num++;
}
++left;
}
return Matrix;
}
};
理解了老师的解法之后,自己闭卷手动写了一遍,其实思路不难就是把手工画圈的过程模拟为程序运行的过程,最关键的地方当然就在于始终都要保证区间一致性,不然容易把自己绕晕。
另外,第三个和第四个for循环,虽然是j--和i--的过程,但不必拘泥于左右区间的开闭,保证指针运动的“起始区间”为闭,“结束区间”为开即可。
class Solution {
public:
vector<vector
思路应该是一样的,不过我把他抽象成了函数的形式,没考虑开闭区间 C++
class Solution {
public:
int index = 1;
void horizontal(bool isRight,vector<vector<int>> & res,int row,int n){
if(isRight){
for(int i = 0;i<n;i++){
if(res[row][i] == 0) res[row][i] = index++;
}
}else{
for(int i = n-1;i>-1;i--){
if(res[row][i] == 0) res[row][i] = index++;
}
}
}
void vertical(bool isDown,vector<vector<int>> & res,int col,int n){
if(isDown){
for(int i = 0;i<n;i++){
if(res[i][col] == 0) res[i][col] = index++;
}
}else{
for(int i = n-1;i>-1;i--){
if(res[i][col] == 0) res[i][col] = index++;
}
}
}
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res(n,vector<int>(n));
int maxN = (n+1)/2;
for(int i = 0;i<maxN;i++){
horizontal(true,res,i,n);
vertical(true,res,n-1-i,n);
horizontal(false,res,n-1-i,n);
vertical(false,res,i,n);
}
return res;
}
};
java的 稍微简化了一下,把各种中间变量抽象成turn
class Solution {
public int[][] generateMatrix(int n) {
int[][] matrix = new int[n][n];
int count = 1; // count 记录需要填的值
int turn = 1; // turn记录当前转圈轮数
int x = 0, y = 0; // 初始化数组坐标
while(turn <= n/2){ // 当 当前轮数turn <= n/2(每轮按1/2缩减),按左闭右开赋值,即[turn, n-turn-1)
x = turn - 1;
y = turn - 1; // 初始化每一轮转圈的起始坐标(x++, y++)
for (; y < n - turn; y++) { // 转圈赋值的上边,
matrix[x][y] = count++;
}
for (; x < n - turn; x++) { // 转圈赋值的右边
matrix[x][y] = count++;
}
for (; y > turn - 1; y--) { // 转圈赋值的下边
matrix[x][y] = count++;
}
for (; x > turn - 1; x--) { // 转圈赋值的左边
matrix[x][y] = count++;
}
turn++;
}
if (n % 2 == 1) { // n为奇数,需单独处理中心位置
matrix[turn - 1][turn - 1] = count;
}
return matrix;
}
}
class Solution {
public int[][] generateMatrix(int n) {
int [][] nums = new int[n][n];
int startX = 0, startY = 0;
int loop = 1, count = 1, offset = 1;
int i, j;
while(loop <= n / 2){
i = startX; j = startY;
for(; j < n - offset; j++){ // 1. n - offset, not n
nums[i][j] = count++;
}
for(; i < n - offset; i++){
nums[i][j] = count++;
}
for(; j >= offset; j--){ // 2. offset, not 0
nums[i][j] = count++;
}
for(; i >= offset; i--){
nums[i][j] = count++;
}
startX++; startY++; offset++; loop++;
}
if(n % 2 == 1){ // n 为奇数时, 单独处理矩阵中心的值
nums[startX][startY] = count;
}
return nums;
}
}
打卡
为啥会有[x][y]这样的表示方式?太奇怪了,从几何想怎么都是[y][x]
好复杂啊😵
文中Java写法处理n为奇数的if语句应该放在while循环外面才能处理n=1的情况,代码如下:class Solution { public int[][] generateMatrix(int n) { int count = 1; int i, j; int loop = 1; int startX = 0, startY = 0; int offSet = 1; int[][] arrs = new int[n][n]; while (loop <= n / 2) {//左闭右开 //上 for (j = startY; j < n - offSet; j++) { //<= 与 <,前者数组越界 arrs[startX][j] = count++; }
//右
for (i = startX; i < n - offSet; i++) {
arrs[i][j] = count++;
}
//下
for (; j > startY; j--) { //>startY
arrs[i][j] = count++;
}
//左
for (; i > startX; i--) { //>startX
arrs[i][j] = count++;
}
offSet++;
startX++;
startY++;
loop++;
}
if (n % 2 == 1) { //放在外面,处理n=1的情况
arrs[startX][startY] = count;
}
return arrs;
}
}
打卡
public static int[][] generateMatrix(int n) {
int[][] res = new int[n][n]; // 结果二维数组
int left = 0; // 左边界
int right = n - 1; // 右边界
int top = 0; // 上边界
int bottom = n - 1; // 下边界
int startnum = 1; // 从 1 开始填
int endnum = n * n; // 填充结束值
while (startnum <= endnum) {
for (int i = left; i <= right; i++) { // 1. 从左到右填充上行
res[top][i] = startnum; // 行不变,一直是上边界
startnum++; // 值自增
}
top++; // 一行填充完毕
for (int i = top; i <= bottom; i++) { // 2. 从上到下填充右列
res[i][right] = startnum; // 列不变,一直是右边界
startnum++;
}
right--; // 一列填充完毕
for (int i = right; i >= left; i--) { // 3. 从右到左填充下行
res[bottom][i] = startnum; // 行不变,一直是下边界
startnum++;
}
bottom--; // 一行填充完毕
for (int i = bottom; i >= top; i--) { // 4. 从下到上填充左列
res[i][left] = startnum; // 列不变,一直是左边界
startnum++;
}
left++; // 一列完毕
}
return res;
}
0802打卡
不如我这个 class Solution {
private int fillNum = 0;
private int[][] nextStep = new int[4][2];
public int[][] generateMatrix(int n) {
int[][] matrix = new int[n][n];
for (int i = 0; i < n; i ++) {
matrix[0][i] = i + 1;
fillNum++;
}
buildNextStep();
int startRow = 0;
int startCol = n - 1;
int direction = 1;
while (fillNum != n * n) {
int[] nextStarts=fill(matrix, direction, startRow, startCol);
direction++;
if (direction > 3) {
direction = 0;
}
startRow = nextStarts[0];
startCol = nextStarts[1];
}
return matrix;
}
private void buildNextStep() {
// 右,下,左,上,右,下,左,上
nextStep[0][0] = 0;
nextStep[0][1] = 1;
nextStep[1][0] = 1;
nextStep[1][1] = 0;
nextStep[2][0] = 0;
nextStep[2][1] = -1;
nextStep[3][0] = -1;
nextStep[3][1] = 0;
}
private int[] fill(int[][] matrix, int direction, int startRow, int startCol) {
int num = matrix[startRow][startCol];
num++;
int n = matrix.length;
int i = startRow + nextStep[direction][0];
int j = startCol + nextStep[direction][1];
while (i >= 0 && i < n && j >= 0 && j < n && matrix[i][j] == 0) {
matrix[i][j] = num;
num++;
i = i + nextStep[direction][0];
j = j + nextStep[direction][1];
fillNum++;
}
return new int[]{i - nextStep[direction][0], j - nextStep[direction][1]};
}
}
打卡:大循环条件中,若循环条件为count <= n, 无法规避n=1无法执行的情况,而loop--可以
打卡
class Solution {
public int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
int k = 1;
int t = 0;
if (n % 2 == 1)
res[n / 2][n / 2] = n * n;
while(t < n / 2){
for (int j = 0; j < 4; j++){
for(int p = 0; p < n-1-2*t;p++){
if(j == 0)
{
res[t][p+t] = k;
k++;
}
else if(j == 1)
{
res[p+t][n-t-1] = k;
k++;
}
else if(j == 2)
{
res[n-t-1][n - p - 1 - t] = k;
k++;
}
else if(j==3)
{
res[n - p - 1 - t][t] = k;
k++;
}
}
}
t += 1;
}
return res;
}
}
class Solution {
public int[][] generateMatrix(int n) {
int row = 0; // row pointer
int col = 0; // column pointer
int count = 1; // The actual number we are putting in the matrix
int loopCount = 1;
int startRow = 0; // The row number where we start to draw the matrix in the specifc loop.
int startCol = 0;
int[][] res = new int[n][n];
int loop = n / 2; // The total loop number needed to draw the matrix.
while(loopCount <= loop){
col = startCol; // Make sure to start the column/row in the right start point of each loop;
row = startRow;
/* Going from left column to the right column */
for(; col < n - loopCount; col++){
//row == 0, col's range :[0, n - loopCount)
res[row][col] = count++;
}
/* Going from the upper row to the bottom row */
for(; row < n - loopCount; row++){
//row's range: [0, n - loopCount); col == n - loopCount
res[row][col] = count++;
}
/* Going from the right column to the left column */
for(; col > startCol; col--){
//col's range: [n - loopCount, startCol); row == n - loopCount
res[row][col] = count++;
}
/* Going from the bottom row to the upper row */
for(; row > startRow; row--){
//row's range: [n - loopCount, startRow); col == startCol
res[row][col] = count++;
}
/* Update the start point of the next loop */
startRow++;
startCol++;
loopCount++;
}
//When n is a odd number , the center point of the matrix cannot be reached in the loop, because we are using the [) interval.
if((n % 2) != 0){
res[n/2][n/2] = count;
}
return res;
}
}
打卡 循环变量不变原则
1111
打卡
https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html