Leetcode-D44-数组-48. 旋转图像&54. 螺旋矩阵(明天复习)

一、复习

1、47. 全排列 II
写的还不错,思路大体上对,就是还是小小的调试了一下——当size=0的时候,是进不去for循环的,所以需要在size=1的时候就判断,然后直接append(path),然后return

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def dsf(size,nums,path,res):
            for index in range(size):
                if index!=0 and nums[index]==nums[index-1]:
                    continue
                if size==1:
                    res.append(path+[nums[index]])
                    return
                dsf(size-1,nums[:index]+nums[index+1:],path+[nums[index]],res)
        nums.sort()
        res=[]
        path=[]
        dsf(len(nums),nums,path,res)

        return res

48. 旋转图像

1、想到了一种先做转置,再根据中间的纵轴对称的方法
2、看下答案~
对于矩阵中第 i 行的第 j个元素,在旋转后,它出现在倒数第 i 列的第 j个位置
试着写一下代码

3、注意规律是出现在倒数第i列的第j个位置,是倒数的!!!怪不得没人用,不如最直白的,先转置再对称好用哈哈哈哈,但是写起来蛮简单的~

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        new_matrix = [[0]*n for _ in range(n)]

        for i in range(n):
            for j in range(n):
                new_matrix[j][n-1-i]=matrix[i][j]

        matrix[:]=new_matrix[:]

Leetcode-D44-数组-48. 旋转图像&54. 螺旋矩阵(明天复习)

54. 螺旋矩阵(明天复习)

1、又是矩阵哈哈哈
2、我想到了哈希表,用来记录是否走过。
用递归来表示上下左右方向移动。
3、很好的是想到了递归,并加以尝试,但问题在于不行啊

在做的时候也发现了一个其它问题,就是如果返回path,则得到None,但如果直接 return ,再取path就没事,不懂。

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        def clock(begin, l, w, matrix, path):
            if begin >= l - begin and begin + 1 >= w - begin and l - begin - 1 <= begin and w - begin - 1 <= begin+1:
                return
            if begin < l - begin:
                for i in range(begin, l - begin):
                    path += [matrix[begin][i]]
            if begin + 1 < w - begin:
                for j in range(begin + 1, w - begin):
                    path += [matrix[j][l - begin-1]]
            if l - begin - 1 > begin:
                for s in range(l - begin - 1, begin, -1):
                    path += [matrix[w - begin-1][s-1]]
            if w - begin - 1 > begin:
                for k in range(w - begin - 1, begin+1, -1):
                    path += [matrix[k-1][begin]]

            clock(begin + 1, l,w, matrix, path)

        path = []
        clock(0, len(matrix[0]), len(matrix), matrix, path)
        return path

Leetcode-D44-数组-48. 旋转图像&54. 螺旋矩阵(明天复习)

3、看下答案叭
这个答案和我最初的想法很相似。这里方向向量和用%4来循环用的很妙~

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:     
        rows, columns = len(matrix), len(matrix[0])
        visited = [[False] * columns for _ in range(rows)]
        total = rows * columns
        order = [0] * total

        directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        row, column = 0, 0
        directionIndex = 0
        for i in range(total):
            order[i] = matrix[row][column]
            visited[row][column] = True
            nextRow, nextColumn = row + directions[directionIndex][0], column + directions[directionIndex][1]
            if not (0 <= nextRow < rows and 0 <= nextColumn < columns and not visited[nextRow][nextColumn]):
                directionIndex = (directionIndex + 1) % 4
            row += directions[directionIndex][0]
            column += directions[directionIndex][1]
        return order

4、尝试自己写一下~
还是需要很大程度上看别人的代码,总结一下叭。
(1)以是否把所有遍历完作为是否返回的判断(在for循环内,每次记录一个量,总共进行size次for循环)
(2)directions的方向别弄错了,怎么移动的,是变横轴还是纵轴。用%4不断改变方向。
(3)用哈希矩阵visited记录是否访问过
(4)判断下一个是否越界或者已经访问过,如果是的话,就立即在原来的基础上调转船头,改变方向。如果不越界的话,就在原方向上操作。
(5)再次进行遍历,直到所有都记录下来

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:     
        rows,cols = len(matrix),len(matrix[0])
        total = rows*cols
        res = [0]*total
        directions =[[0,1],[1,0],[0,-1],[-1,0]]
        row,col=0,0
        direction_index = 0
        visited=[[False]*cols for _ in range(rows)]
        for i in range(total):
            res[i] = matrix[row][col]
            visited[row][col]=True
            nextrow,nextcol = row+directions[direction_index][0],col+directions[direction_index][1]
            if nextrow>=rows or nextcol>=cols or visited[nextrow][nextcol]==True:
                direction_index = (direction_index+1)%4
            row = row+directions[direction_index][0]
            col = col +directions[direction_index][1]
        return res
        
上一篇:LeetCode刷题笔记 字节每日打卡 去除重复字母


下一篇:LeetCode上的各种股票最大收益