[数据结构与算法]python–leetcode–数组之形状变化

python–leetcode–数组之形状变化

6.Z字形变换

Z字形变换：将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
思路：根据给定行数构建默认行数空串，根据z字型变换，设置flag方向，到达临界转换方向，添加到默认空串中，最后再进行拼接。

def convert(s: str, numRows: int):
    if numRows < 2:
        return s
    res = ['' for _ in range(numRows)]
    i = 0
    flag = -1
    for c in s:
        res[i] += c
        if i == 0 or i == numRows - 1:
            flag = -flag
        i += flag
    return ''.join(res)

48.旋转图像

旋转图像：给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。
思路：先对称交换，再每一行反转；或者使用解包加zip封装的方式

def rotate(matrix):
    n = len(matrix[0])
    for i in range(n):
        for j in range(i, n):
            matrix[j][i], matrix[i][j] = matrix[i][j], matrix[j][i]
    for i in range(n):
        matrix[i].reverse()
    # matrix[:] = [list(x) for x in zip(*matrix[::-1])]  # 使用解包加zip封装的方式
    # return matrix

54.螺旋矩阵

螺旋矩阵:给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序。
思路：设置右下左上的顺序，同时使用used标记已访问节点，整体遍历

def spiralOrder(matrix):
    if not matrix:
        return []
    row, col = len(matrix), len(matrix[0])
    used = [[False]*row for _ in range(col)]  # 标记已访问节点
    res = []
    dr = [0, 1, 0, -1]
    dc = [1, 0, -1, 0]  # 按照右下左上顺序
    r = c = di = 0
    for _ in range(row * col):
        res.append(matrix[r][c])
        used[r][c] = True
        cr, cc = r + dr[di], c + dc[di]
        if 0 <= cr < row and 0 <= cc < col and not used[cr][cc]:
            r, c = cr, cc
        else:
            di = (di + 1) % 4
            r, c = r + dr[di], c + dc[di]
    return res