设为首页 加入收藏

TOP

LeetCode 59. 螺旋矩阵 II
2023-07-23 13:28:55 】 浏览:26
Tags:LeetCode 59.

题目链接:LeetCode 59. 螺旋矩阵 II
本题不涉及算法,只是简单的模拟,但是由于边界条件比较多,因此容易出错。
分析题干:题目要求按照右、下、左、上、这样的顺序对数组进行填充,填充的值为 1 ~ n*n,因此问题的关键就是找到待填充的位置,将其值赋值为 i 即可。
由于填充的顺序是有规律的,因此可以将 右、下、左、上、这四种填充方式看作成四个方向上的移动,此时就可以发现:

  • 当向右填充时,横坐标不变,纵坐标 +1
  • 当向下填充时,横坐标 +1,纵坐标不变
  • 当向左填充时,横坐标不变,纵坐标 -1
  • 当向上填充时,横坐标 -1,纵坐标不变
    因此对于四个方向上的横纵坐标的变化,可以用两个数组进行表示:
dx :=[]int{0,1,0,-1} //四种移动方向,右、下、左、上   dx表示行,dy表示列
dy :=[]int{1,0,-1,0} 

此时在移动过程中,横纵坐标的变化,就是 a=x+dx[d]b=y+dy[d] (这里d 表示移动的方向,取值为0,1,2,3)
当发现需要改变移动方向时,即到达数组边界时,采用取余的操作,更新移动方向 d=(d+1)%4
这样,循环填充下去,直到填充到 n*n 为止。
完整代码如下:

func generateMatrix(n int) [][]int {

    res:=make([][]int,n)
    for i,_ :=range res{
        res[i] = make([]int,n)
    }
    
    dx :=[]int{0,1,0,-1} //四种移动操作,右、下、左、上   dx表示行,dy表示列
    dy :=[]int{1,0,-1,0} 
    // i表示数值i,初始时为1, x,y表示当前位置的横纵坐标,d表示当前移动的方向
    for i,x,y,d:=1,0,0,0;i <= n*n;i++{
        res[x][y] = i //将当前位置填上i
        a := x + dx[d]  //将当前位置按照当前的方向,更新成新的位置(a,b)即求得当前方向的下一个格子位置
        b := y + dy[d]

        if a < 0 || b < 0 || a >=n || b >= n ||res[a][b] != 0{ //如果下一个格子越界 或者 这个格子已经有数
            d=(d+1)%4   //换下一个方向
            a=x+dx[d]
            b=y+dy[d]  //得到新的格子位置
        } 
        x=a   //更新待填写的格子的位置
        y=b
    }
    return res
}


当然你也可以分别去处理右、下、左、上 四个方向的情况,代码如下:

func generateMatrix(n int) [][]int {
    top, bottom := 0, n-1
    left, right := 0, n-1
    num := 1
    tar := n * n
    matrix := make([][]int, n)
    for i := 0; i < n; i++ {
        matrix[i] = make([]int, n)
    }
    for num <= tar {
        for i := left; i <= right; i++ {
            matrix[top][i] = num
            num++
        }
        top++
        for i := top; i <= bottom; i++ {
            matrix[i][right] = num
            num++
        }
        right--
        for i := right; i >= left; i-- {
            matrix[bottom][i] = num
            num++
        }
        bottom--
        for i := bottom; i >= top; i-- {
            matrix[i][left] = num
            num++
        }
        left++
    }
    return matrix
}
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇Go语言入门14(channel通道01) 下一篇openAI发布v0.2.0了

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目