今天我们一起掌握 leetocode 的 54, 59, 61 题。用到的都是模拟法。

1. lc 54 - 螺旋矩阵

题目来源

  • 给定一个包含 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
  • 难度：中等

此题在前面有讲到，指路 - “剑指 Offer算法题中的 tricks” 第二题

简而言之，思路是 边转置边输出矩阵第一行。

重写此题时，掌握了以下extend的用法。

1
2
3
4
# 两句效果一样
out_list += matrix[0]

out_list.extend(matrix[0])

2. lc 59 - 螺旋矩阵 II

题目来源

  • 给定一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
  • 难度：中等

2.1 解题思路 - 模拟法处理边界

此题，我们可以依据题意，模拟矩形的形成。

直观分析，除了矩形第一行的赋值，后续都是对矩形的外圈顺时针赋值，走完一个外圈后内缩矩形，重复操作。

我们画图示意：每一个顺时针矩形外圈的格数有规律，第一圈：右下边 都为 n-1；左上边 都为 n-2。

  • 具体而言，生成一个 n×n 空矩阵 matrix，设定 x,y 为当前坐标，设定 tmp 用以推进顺时针矩形的内缩。初始值 num = 1，迭代终止值 tar = n * n。随后模拟整个向内环绕的填入过程：
    • 当 num <= tar 时，始终按照 从左到右，从上到下，从右到左，从下到上 填入顺序循环，每次填入后：
      1. 坐标变换：根据未来前进方向，改动 x 或 y；
      1. 执行 num += 1：得到下一个需要填入的数字；
      1. 切换前进方向：当一个方向走到尽头后，依照顺序切换前行方向；
      1. 更新边界：从左到右填完后，将开启新一轮的矩形外圈存储。用 tmp 来推进外圈的内缩，tmp = tmp - 2 后，重复步骤1，直到 num > tar。

2.2 时间复杂度

  • 时间复杂度：O(n^2)。我们填充时遍历一次矩阵，矩阵元素个数为 n^2（其中 n 为参数），所以时间复杂度为 O(n^2)。

  • 空间复杂度：O(n^2)。需要一个矩阵 Matrix 存储结果

2.3 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        num = 1 
        matrix = [[0 for _ in range(n)] for _ in range(n)]
        x,y = 0,0 # x,y 记录当前坐标

        # 填充首行元素
        for y in range(n):
            matrix[0][y] = num
            num += 1  
        
        # 用 tmp 推进顺时针矩形的收缩
        tmp = n

        while num <= n*n:
            # 顺时针矩形外圈右边 
            for _ in range((tmp)-1):
                x += 1 # 坐标进入新的顺时针矩形
                matrix[x][y] = num
                num += 1  

            # 顺时针矩形外圈下边     
            for _ in range((tmp)-1):
                y -= 1
                matrix[x][y] = num
                num += 1 

            # 顺时针矩形外圈左边     
            for _ in range((tmp)-2):
                x -= 1
                matrix[x][y] = num
                num += 1

            # 顺时针矩形外圈上边    
            for _ in range((tmp)-2):
                y += 1
                matrix[x][y] = num
                num += 1 
            
            tmp -= 2 # 走完一个外圈，顺时针矩形的收缩 2 个单位
        
        return matrix


3. lc 61 - 旋转链表

题目来源

  • 给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
  • 难度：中等

3.1 解题思路 - 链表重接

此题有其他解法。比如：1. 先将链表闭合成环；2. 找到相应的位置断开这个环，确定新的链表头和链表尾。

我的解法如图：

注意好细节就能解题了。关键注意：

  1. 什么位置是新链表的尾部？ 应该是第 size - k 个元素（size 的链表长度）。所以先求链表长度。

  2. k 如果超过链表长度size怎么办？ 设 k 为 k / size 余数即可。

3.2 时间复杂度

  • 时间复杂度：O(n)。其中 N 是链表中的元素个数
  • 空间复杂度：O(1)。 因为只需要常数的空间。个人经验，常规的链表拆解合并问题空间复杂度都是O(1)，因为我们只需要开辟额外空间用于临时储存一个Node，后面根据题意再更新这个临时空间。

3.3 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if head == None: return None
        if head.next == None or k == 0: return head
        move = head
        size = 0

        # 求链表长度的常规解法
        while move:
            move = move.next
            size += 1
        k %= size 

        if k == 0 : return head # k和链表长度一致，等于没有旋转

        # 图解的代码实现
        # case: linklist:[1,2,3,4,5], head.val=1, k=2
        start = head # 储存原表头
        for i in range(size-k-1):
            head = head.next
        tmp = head.next # tmp = node(4)
        head.next = None # node(3) -> none

        dummy_node = ListNode(0)
        dummy_node.next = tmp # dum -> node(4)

        for j in range(k-1):
            tmp = tmp.next
        tmp.next = start # node(5)->node(1)
        return dummy_node.next

参考

[1] lc 59 题解. https://leetcode-cn.com/problems/spiral-matrix-ii/solution/spiral-matrix-ii-mo-ni-fa-she-ding-bian-jie-qing-x/

[2] lc 59 解题. https://www.bilibili.com/video/BV1Up4y1U7L1