【数组和字符串】(二) 二维数组简介_二维数组字符串

目录

二、二维数组简介

2.1 旋转矩阵

2.2 零矩阵

2.3 对角线遍历 ☆

---

二、二维数组简介

2.1 旋转矩阵

2.1.1 问题描述

2.1.2 求解过程

法一：不允许占用额外空间，那就只能原地操作 (in-place)。换言之，每次变换都必须一次完成，不可再访问。为此，可以选择从外层到内层，每次对四个相应位置元素按顺时针旋转 90°。循环层数 floor 由 n/2 向上取整确定。复杂度由 n*n/4 向上取整确定，即为 O(n^2)

2020/06/01 - 解法基本唯一

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        # 每次调整4个, 共需 n*n/4 向上取整 次
        n = len(matrix)
        if n <= 1:
            return matrix
        
        #quo, rem = divmod(n, 2)
        #floor = quo + rem
        floor = sum(divmod(n, 2))  # 从外到内, 处理层数
        # i 是每层的起始 index, 如最外层/第一次从[0][0]开始, 第二层从[1][1]开始 ...
        for i in range(floor):  # 层数
            limit = n-i-1  # 当前层的 index 上限
            k = 0  # index 调整辅助变量
            for j in range(i, limit):  # 每次同时顺时针调整4个元素位置
                matrix[i][j], matrix[j][limit], matrix[limit][limit-k], matrix[limit-k][i] = \
                matrix[limit-k][i], matrix[i][j], matrix[j][limit], matrix[limit][limit-k]
                k += 1   
        return matrix

2.2 零矩阵

2.2.1 问题描述

2.2.2 求解过程

法一：朴素/暴力法，第一次遍历用于查找和记录 0 元素，第二次遍历对行元素清零，第三次遍历对列元素清零。由于包含许多冗余操作，因此效率较低。复杂度 O(n^2)。

此外，用列表推导式比 [0]*x 好，因为可以避免每行 0 都指向同一个 0 列表对象！(尽管本题并未体现危害性)

2020/06/01 - 81.48% - 基本属于最佳方法了

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        if (len(matrix) <= 1) and (0 not in matrix[0]):  # 特殊情况 [[0,1]]
                pass
        else:
            zero_row = set()  # 保存 0 元素的横坐标
            zero_col = set()  # 保存 0 元素的纵坐标
            # 搜索并记录零
            for i, row in enumerate(matrix):
                for j, num in enumerate(row):
                    if num == 0:
                        zero_row.add(i)
                        zero_col.add(j)
            # 行清零                 
            for r_i in zero_row:
                matrix[r_i] = [0 for _ in range(len(matrix[0]))]  
            # 列清零
            for c_j in zero_col:
                for k in range(len(matrix)):
                    matrix[k][c_j] = 0

法二：朴素法优化 I。新增 hasZero 作为 Flag 标识当前行是否有 0，若有则本行遍历完直接整行清零，省得再开一个 for 循环专门对行清零。但列不行，因为不确定是否会有新列 index 加入，故必须新开一个 for 循环对列清零。复杂度 O(n^2)。

2020/06/01 - 

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        if (len(matrix) <= 1) and (0 not in matrix[0]):  # 特殊情况 [[0,1]]
            pass
        else:
            zero_col = set()  # 保存 0 元素的纵坐标
            # 搜索并记录零
            for i, row in enumerate(matrix):
                hasZero = False
                for j, num in enumerate(row):
                    if num == 0:
                        zero_col.add(j)  # 0 元素纵坐标
                        hasZero = True
                if hasZero:
                    matrix[i] = [0 for _ in range(len(matrix[0]))]  # 顺手行清零 
            # 列清零
            for c_j in zero_col:
                for k in range(len(matrix)):
                    matrix[k][c_j] = 0

法三：朴素法优化 II。重新增加 zero_row 用于存放没有 0 的行 index，从而结合 zero_column 实现其余 0 的处理。复杂度 O(n^2)。

2020/06/01 - 

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        if (len(matrix) <= 1) and (0 not in matrix[0]):  # 特殊情况 [[0,1]]
            pass
        else:
            zero_row = set()  # 保存没有0元素的行 index
            zero_col = set()  # 保存0元素的纵坐标
            # 搜索并记录0
            for i, row in enumerate(matrix):
                hasZero = False  # 本行有0 flag
                for j, num in enumerate(row):
                    if num == 0:
                        zero_col.add(j)  # 0 元素纵坐标
                        hasZero = True
                if hasZero:
                    matrix[i] = [0 for _ in range(len(matrix[0]))]  # 本行有0, 直接整行清零 
                else:
                    zero_row.add(i)  # 本行无0, 记录行 index 以便后续清扫       
            # 其余元素清零
            for r_i in zero_row:
                for c_j in zero_col:
                    matrix[r_i][c_j] = 0

2.3 对角线遍历

2.3.1 问题描述

2.2.2 求解过程 (☆)

法一 (直观法/朴素法)：实例中，输入的二维数组 范围均是 0～2。不妨先观察一下遍历规律：(0, 0) → (0, 1) → (1, 0) → (2, 0) → (1, 1) → (0, 2) → (1, 2) → (2, 1) → (2, 2)。设 数组索引为 (m, n)，则索引有两种 改变方式：(m-1, n+1) 或 (m+1, n-1)。

数组从 (0,0) 开始，索引改变方式先是 (m-1, n+1)，即 (0, 0) → (-1, 1) (即 0-1=-1, 0+1=1)，但此时横坐标 m = -1 超出范围 (0~2)，令 m = 0 (以限定在 0~2 范围内) 得到下次遍历的起点 (0, 1)。

然后，切换索引改变方式为 (m+1, n-1)，依次执行 (0, 1) → (1, 0) → (2, -1)，但此时纵坐标 n=-1 超出范围 (0~2)，同理令 n = 0 (以限定在 0~2 范围内) 得到下次遍历的起点 (2, 0)。

再次切换索引改变方式为 (m-1, n+1)，依次执行 (2, 0) → (1, 1) → (0, 2) → (-1, 3) 直到又超出范围 (0~2)。然而，不同之处在于：此时 m<0 且 n>2 均超出范围。此时应当优先判断 n 是否超出范围，然后特殊地，执行 (m+2, n-1) 实现 (-1,3) → (1,2)，避免因为 m<0 导致再次切换索引改变方式。

然后，索引改变方式正常切换回 (m+1, n-1)，依次执行 (1, 2) → (2, 1) → (3, 0)，因为 m>2 超出范围，所以特殊地执行 (m-1, n+2) 实现 (3, 0) → (2, 2) 完成遍历。

可见，两种正常遍历方向 (右上、左下) 分别对应两种索引改变方式；四种特殊超界情况 (横、纵坐标超上、下届) 分别对应四种索引修正方式，同时调整遍历方向。复杂度 O(n)

2020/06/03 - 51.32% - 网上资料，但实际是第二快的算法了！

class Solution:
    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
        # 特殊情况处理机制
        if not matrix:  # matrix = []
            return []
        
        col = len(matrix)  # 行数 / 纵坐标最大值
        row = len(matrix[0])  # 列数 / 横坐标最大值
        nums = col * row  # 总元素数
        m = 0  # 起始点横坐标 index
        n = 0  # 起始点纵坐标 index
        flag = True  # 用于确定坐标变换机制 (m-1, n+1) or (m+1, n-1)
        res = []  # 初始化对角线遍历元素列表
        
        # 开始对角线遍历矩阵内所有元素
        for i in range(nums):
            # 计入元素
            res.append(matrix[m][n])
            # 正常情况遍历
            if flag:        # 坐标变换机制 (m-1, n+1)
                m -= 1
                n += 1
            else:           # 坐标变换机制 (m+1, n-1)
                m += 1
                n -= 1
            # 特殊情况修正    
            if m >= col:    # 如果横坐标 m 大于范围, 一次性令 (m-1, n+2)
                m -= 1
                n += 2
                flag = True
            elif n >= row:  # 如果纵坐标 n 大于范围, 一次性令 (m+2, n-1)
                m += 2
                n -= 1
                flag = False
            if m < 0:       # 如果横坐标 m 小于范围, 一次性令 m=0
                m = 0
                flag = False
            elif n < 0:     # 如果纵坐标 n 小于范围, 一次性令 n=0
                n = 0
                flag = True
                
        return res

法二：相同的 未知原理。前者用嵌套 list 加入元素；后者用 defaultdict 加入元素，故效率最高！

2020/06/03 - (前)97% - (后)99% - 参考答案

class Solution:
    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
        # 特殊情况处理
        if not matrix:
            return []
        row = len(matrix)  # 行数 / 纵坐标最大值
        col = len(matrix[0])  # 列数 / 横坐标最大值
        l = row + col - 1  # 总元素数-1
        # 使用列表推导式生成空嵌套列表 作为辅助表
        rets = [[] for _ in range(l)]  # 比 [[]*l] 更快更安全！
        
        for i in range(row):
            for j, num in enumerate(matrix[i]):
                rets[i+j].append(num)
        print(rets)
        # 初始化输出结果
        ret = []
        for k, x in enumerate(rets):
            ret += x if (k % 2 == 1) else x[::-1]  # 一行式, 原理未知
            print(ret)
        return ret
# -------------------------------------------------------------------------------
class Solution:
    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
        # 特殊情况处理
        if not matrix: 
            return []
        
        # 构造默认 list 字典
        dic = collections.defaultdict(list)
        # 按 index 之和加入元素
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                dic[i+j].append(matrix[i][j])
        print(dic)
        
        # 初始化输出结果
        res = []
        for i in range(len(matrix)+len(matrix[0])-1):
            if i%2==0:
                res += dic[i][::-1]
            else:
                res += dic[i]
            print(res)
        return res