Introduction to 2D Array

本文蒐集

• LeetCode 498
• LeetCode 54
• LeetCode 118

LeetCode 498: Diagonal Traverse

Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order. Example 1:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]

Example 2:

Input: mat = [[1,2],[3,4]]
Output: [1,2,3,4]

Constraints :

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= \(10^4\)
• 1 <= m * n <= \(10^4\)
• \(-10^5\) <= mat[i][j] <= \(10^5\)

我的解法 1

利用原始 dict 字典 mapping 和原始 list 串列 當作 queue

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        d={}
        for i in range(len(mat)):
            for j in range(len(mat[i])):
                if i + j not in d:
                    d[i+j] = [mat[i][j]]
                else:
                    d[i+j].append(mat[i][j])
        ans= []
        for entry in d.items():
            if entry[0] % 2 == 0:
                entry[1].reverse()
            ans.extend(entry[1])
        return ans

我的解法 2

利用 python 內建實用 Lib collections

1. 增加便利性
2. 減低時間複雜度

collections.defaultdict() mapping 和 collections.deque() queue

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        ans = deque()
        d = defaultdict(deque)
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                d[i+j].append(mat[i][j])
        for k, v in d.items():
            if k % 2 == 0:
                v.reverse()
            ans.extend(v)
        return ans

LeetCode 54: Spiral Matrix

Given an m x n matrix, return all elements of the matrix in spiral order. Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

Example 1:

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Constraints :

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

我的解法

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        visited = set()
        ans = deque()
        m = len(matrix)
        n = len(matrix[0])
        i = -1
        j = -1
        flag = 0
        
        while len(visited) != m * n:
            if flag % 4 == 0:
                i += 1
                j += 1
                while 0 <= j < n and (i, j) not in visited:
                    ans.append(matrix[i][j])
                    visited.add((i, j))
                    j += 1
                flag += 1
            elif flag % 4 == 1:
                j -= 1
                i += 1
                while 0 <= i < m and (i, j) not in visited:
                    ans.append(matrix[i][j])
                    visited.add((i, j))
                    i += 1
                flag += 1
            elif flag % 4 == 2:
                i -= 1
                j -= 1
                while 0 <= j < n and (i, j) not in visited:
                    ans.append(matrix[i][j])
                    visited.add((i, j))
                    j -= 1
                flag += 1
            else:
                j += 1
                i -= 1
                while 0 <= i < m and (i, j) not in visited:
                    ans.append(matrix[i][j])
                    visited.add((i, j))
                    i -= 1
                flag += 1
        return ans

LeetCode 118: Pascal's Triangle

Given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1
Output: [[1]]

Constraints :

• 1 <= numRows <= 30

我的解法

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ans = deque()
        for i in range(numRows):
            temp = deque()
            for j in range(i+1):
                if j == 0 or j == i:
                    temp.append(1)
                else:
                    temp.append(ans[i-1][j-1] + ans[i-1][j])
            ans.append(temp)
        return ans