栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Python

leetcode 54 59螺旋矩阵

Python 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

leetcode 54 59螺旋矩阵

例一、54. 螺旋矩阵 错误范本:

程序的主体思想是:按照左闭右开的原则遍历矩阵,如下:

中心思想是:设置一个count,每次走完一个1,2,3,4大循环后,count+=1,实际也是在用count一个数更新上下左右四个边界,但是问题在于:

此程序的主体判断部分不够完善,理由是没有考虑到比如单行单列或者最后1X1的“菜心”5的访问,总结来说就是没有处理好边界。

  1. 比如处理示例[[6,9,7]],会得到答案[6,9,7,9],理由在于它不仅会走从左到右的循环,还会走从右到左的循环,导致数字9的循环访问;
  2. 而对于示例[[1,2,3],[4,5,6],[7,8,9]],得到答案[1,2,3,6,9,8,7,4],而缺少中心数5,理由在于二次循环时
    count=1 n-1-cnt=1 所以for j in range(cnt,n-1-cnt)等这四个循环一个都不会进入,5不会被加入到res中
  3. 还有一个问题,count是变量,虽然python不能在 for 循环range中加变量,但是,对于每个循环count不变,可以看成非变量
class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        ##难点:需要规划好规则,采用左闭右开的原则
        #1X1的“菜心”怎么处理?
        #m行n列
        #需要特殊注意的示例[[6,9,7]] 不能得到[6,9,7,9]
        # matrix=[[6,9,7]]
        m=len(matrix)
        n=len(matrix[0])
        # print(m)
        if m%2==0:
            loop=m/2 #多少次循环
        else:
            loop=m/2+1
        # print(loop)
        res=[]
        cnt=0


        while loop:
            # print(cnt)
            # if cnt==n-1-cnt:
            #     res.append(matrix[cnt][n-1-cnt])
            for j in range(cnt,n-1-cnt): #从左到右
                res.append(matrix[cnt][j])
                # print(res)
            for i in range(cnt,m-1-cnt): #从上到下
                res.append(matrix[i][n-1-cnt])
                # print(res)
            for j in range(n-1-cnt,cnt,-1): #从右到左
                res.append(matrix[m-1-cnt][j])
                # print(res)
            for i in range(m-1-cnt,cnt,-1):#从下到上
                res.append(matrix[i][cnt])
            # print(res)
            cnt+=1
            loop-=1
        # print(res) 
        if m==n:
            if n%2:
                res.append(matrix[n/2][n/2])
        # 如果m=n且n为奇数的话,需要单独给矩阵最中间的位置赋值
        #之所以要单独判断,因为

        return res
正确版本:
  1. 首先设定上下左右边界
  2. 其次向右移动到最右,此时第一行因为已经使用过了,可以将其从图中删去,体现在代码中就是重新定义上边界
  3. 判断若重新定义后,上下边界交错,表明螺旋矩阵遍历结束,跳出循环,返回答案
  4. 若上下边界不交错,则遍历还未结束,接着向下向左向上移动,操作过程与第一,二步同理
  5. 不断循环以上步骤,直到某两条边界交错,跳出循环,返回答案

对上下左右都设置了明显的边界,并且每次循环都会更新边界,不会出现上面程序中示例[[6,9,7]],得到答案[6,9,7,9]的回退现象。
并且对于示例[[1,2,3],[4,5,6],[7,8,9]],在第一次循环中l,r=0,3 第二次l,r=1,2,可以把5顺利读取到

class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        ##难点:需要规划好规则,采用左闭右开的原则
        #实际上还需要特别设置边界的情况,一旦到达边界,需要退出循环
        #m行n列
        #需要特殊注意的示例[[6,9,7]] 不能得到[6,9,7,9]
        #还需要考虑如果中间包着的是“一行”或者“一列的情况”
        #[[2,3,4],[5,6,7],[8,9,10],[11,12,13],[14,15,16]]
        #输出:[2,3,4,7,10,13,16,15,14,11,8,5,6,9,12,9]
        #预期:[2,3,4,7,10,13,16,15,14,11,8,5,6,9,12]
        m=len(matrix)
        n=len(matrix[0])
        # print(m)
        if m%2==0:
            loop=m/2 #多少次循环
        else:
            loop=m/2+1
        # print(loop)
        res=[]
        
        u=0 #上边界
        d=m-1 #下边界
        l=0 #左边界
        r=n-1 #右边界

        while loop:

            for j in range(l,r+1): #从左到右
                res.append(matrix[u][j]) #重新设定上边界
                
            u+=1
            if u>d: #若上边界大于下边界,则遍历完成
                break
            
            for i in range(u,d+1): #从上到下
                res.append(matrix[i][r])
                # print(res)
            r-=1 #重新设定右边界
            if rr:
                break
            # print(res)

            loop-=1

        return res
例二,59. 螺旋矩阵 II

照着例一的思路,不同在于例一访问,例二填数。

class Solution(object):
    def generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        matrix=[[0 for _ in range(n)] for _ in range(n)]

        if n%2==0:
            loop=n/2 #多少次循环
        else:
            loop=n/2+1

        u=0
        d=n-1
        l=0
        r=n-1

        val=1

        while loop:
            for i in range(l,r+1): #从左到右
                matrix[u][i]=val
                val+=1
            u+=1
            if u>d:#若上边界大于下边界,则遍历完成
                break

            for i in range(u,d+1):
                matrix[i][r]=val
                val+=1
            r-=1
            if rr:
                break

            loop-=1
            
        return matrix

参考:https://leetcode.cn/problems/spiral-matrix/solution/cxiang-xi-ti-jie-by-youlookdeliciousc-3/

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/915814.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号