アルゴリズム(4)-leetcode-explore-learn-データ構造-配列2

leetcode-explore-learn-データ構造-配列2

1.概要

2.例題

2.1二次元配列の対角線は

を遍歴する

2.2螺旋遍歴

2.3楊輝三角

このシリーズのブログはleetcode-explore-learnサブ欄の学習ノートです.不明な点があれば、leetcode公式サイトを参照してください.https://leetcode-cn.com/explore/learn/card/array-and-string/198/introduction-to-array/768/
1.簡単に述べる
本文は主に2次元データと関連する例題を記録する.
2 D配列の要素は、直線ではなく長方形のメッシュに配置されます.
いくつかの言語では、2次元配列内部が実際に1次元配列を使用して実装されている–c++のa[i][j]内部インデックスの場合、実際にはa[i*n+j](nは各行の要素の個数)
1 Dダイナミック配列と同様に2 Dダイナミック配列を定義できますが、実際にはネストされたダイナミック配列にすぎません.
2.例題
2.1 2 D配列の対角線遍歴
同じ対角線上の要素の下付きインデックスと一致します.n*mの行列は全部でn+m-1本の対角線インデックスと偶数の場合、上へ遍歴し、遍歴順は(x,0)(x-1,1),(x-2,2),…,(0,x)インデックスと奇数の場合、下へ遍歴し、遍歴順は(0,y),(1,y-1),…,(y,0)28/32である

class Solution(object):
    def findDiagonalOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        if not matrix:
            return []
        hor = len(matrix)
        ver = len(matrix[0])
        leng = hor+ver-1
        listmatrix = []
        
        for x in range(leng+1):
            if x%2 ==0:
                for i in range(x,-1,-1):
                    j = x-i
                    if i<hor and j<ver:
                        listmatrix.append(matrix[i][j])
                    elif j>ver:
                        continue
            
            else:
                for j in range(x,-1,-1):
                    i = x-j
                    if i<hor and j<ver:
                        listmatrix.append(matrix[i][j])
                    elif j>hor:
                        continue
        return listmatrix

参考文献:https://blog.csdn.net/qq_36022260/article/details/103651894
2.2螺旋遍歴
leetcode 54

class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        if not matrix:
            return []
        R,C=len(matrix),len(matrix[0])
        flag=[[False]*C for _ in matrix]
        res=[]
        dr=[0,1,0,-1]    # [r+0,c+1]           
        dc=[1,0,-1,0]
        r,c=0,0
        di=0
        for _ in range(R*C):
            res.append(matrix[r][c])
            flag[r][c]=True
            n_r,n_c=r+dr[di],c+dc[di]
            if 0<=n_r<R and 0<=n_c<C and not flag[n_r][n_c]:
                r,c=n_r,n_c
            else:
                di=(di+1)%4
                r,c=r+dr[di],c+dc[di]
        return res

2.3楊輝三角
i行目の要素数はi+1個、iの値範囲は0,1,...,numRows-1 i行目の要素の最初の要素(インデックスは0)と最後の要素(インデックスはi)であり、この行の他の要素のインデックスjの値範囲は0,1,...,i-1である.

class Solution(object):
    def generate(self, c):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        res=[]
        for i in range(numRows):
            if i==0:
                res.append([1])
            elif i==1:
                res.append([1,1])
            else:
                res.append([1]*(i+1))    
                for j in range(1,i):
                    res[i][j]=res[i-1][j-1]+res[i-1][j]
        return res