首页 > 其他分享 >LeetCode 59. 螺旋矩阵 II

LeetCode 59. 螺旋矩阵 II

时间:2023-05-05 17:11:48浏览次数:54  
标签:59 填充 int 纵坐标 II num dx dy LeetCode

题目链接: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
}

标签:59,填充,int,纵坐标,II,num,dx,dy,LeetCode
From: https://www.cnblogs.com/lxing-go/p/17374654.html

相关文章

  • LeetCode 209. 长度最小的子数组
    题目链接:LeetCode209.长度最小的子数组本题是一个滑动窗口的题,所谓滑动窗口,就是不断的调节子序列的起始位置和终止位置,从而得出我们要想的结果。在本题中实现滑动窗口,主要确定如下三点:窗口内是什么?窗口就是满足其和≥target的长度最小的连续子数组。如何移动窗口的起......
  • 350. 两个数组的交集 II
     分析: 跟上道题一样,但是可以重复代码:classSolution(object):defintersect(self,nums1,nums2):""":typenums1:List[int]:typenums2:List[int]:rtype:List[int]"""count=[]......
  • LeetCode 977. 有序数组的平方
    题目链接:LeetCode977.有序数组的平方本题直接暴力求解就是先求出每个元素平方后的值,再对平方后的值进行排序,双指针解法由于数组其实是有序的,只不过负数平方之后可能成为最大数了。那么数组平方的最大值就在数组的两端,不是最左边就是最右边,不可能是中间。此时可以考虑双指......
  • LeetCode 27. 移除元素 题解
    题目链接:LeetCode27.移除元素本题大意是要对一个数组进行原地删除数值等于val的元素。双指针算法:通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。快指针(p指针):寻找新数组的元素,新数组就是不含有目标元素的数组慢指针(q指针):指向更新新数组下标的位置当......
  • LeetCode 704. 二分查找 题解
    本题考查的就是一个基本的整数二分查找问题对于整数二分,有单调性一定可以二分,没有单调性的有时候也可以二分。算法思想(分为两种方法):查找结果是在左边区间的情况区间被划分为[l,mid]和[mid+1,r]1、确定分界点,mid=q[(l+r)/2]2、判断是否满足是:区间变成[l,mid]因此:r=mid否......
  • LeetCode 1049. 最后一块石头的重量 II
    思路任何时刻,某个石头的重量永远都是若干石头加减运算的绝对值如a-b+c合并石头都是减法,但仍可能出现+运算符,如a-(b-c)=a-b+c任何一种合并方法,最后一个石头的重量都可以表示成一种代数形式,如a+b-c+d+e+f-g不是所有的代数形式都可以转换为一种合并方法,如a+b+c因此......
  • ETF2100/5900 Introductory Econometrics
    ETF2100/5900IntroductoryEconometricsAssignment2—ACaseStudyontheBirth-weightofBabyImportantnotes:1.Thisisanindividualassignment.Thisassignmentisworth20%ofthisunit’stotalmark.Markswillbedeductedforlatesubmissiononthefoll......
  • [Leetcode] 0697.数组的度
    697.数组的度点击上方标题跳转至leetcode题目描述给定一个非空且只包含非负数的整数数组 nums,数组的度的定义是指数组里任一元素出现频数的最大值。你的任务是在nums中找到与 nums 拥有相同大小的度的最短连续子数组,返回其长度。 示例1:输入:nums=[1,2,2,3,1]输......
  • AcWing 754. 平方矩阵 II
    AcWing754.平方矩阵II1.地址https://www.acwing.com/problem/content/756/2.题解#include<iostream>#include<cstdio>#include<cmath>usingnamespacestd;//每个元素的值为:各个元素下标相减的绝对值+1intmain(){intmatrix[102][102];intn;......
  • 一个stm23移植u8g2驱动iic屏SSD1306方案12864的左边竖着两列没有显示的奇怪问题
    初始化后画一个方框u8g2_DrawLine(&u8g2,0,0,127,0);u8g2_DrawLine(&u8g2,1,0,1,63);//左边框u8g2_DrawLine(&u8g2,0,63,127,63);u8g2_DrawLine(&u8g2,127,0,127,63);左边框地址为0不显示,设置为1还是不显示设置为2可以看到竖线了中景园......