ゼロから始めるLeetCode Day4「1030. Matrix Cells in Distance Order」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインでだそうです。

その対策としてLeetCodeなるサイトで対策を行うようです。

※LeetCodeとは
本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトです。

せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていきます。

LeetCode

未経験のエンジニアなので、基本的に簡単なもの（easyでacceptanceが高い順）から解いていきます。

問題

1030. Matrix Cells in Distance Order

rows x colsのサイズの行列があり、座標 (rCenter, cCenter) のセルにいる。
行列内のすべてのセルの座標と(rCenter、cCenter）からの距離を計算し、小さい順に並べ替えて座標を返すもの。

※距離の計算方法：|r1 - r2| + |c1 - c2|

例1:
入力: rows = 1, cols = 2, rCenter = 0, cCenter = 0
出力: [[0,0],[0,1]]
(0, 0)から他のセルまでの距離は次の通りである：[0,1]

例2:
入力: rows = 2、cols = 2、rCenter = 0、cCenter = 1
出力: [[0,1],[0,0],[1,1],[1,0]]
(0, 1)から他のセルまでの距離：[0,1,1,2]
[[0,1],[0,0],[1,1],[1,0]]も正しいものとして受け入れられる。

例3:
入力: rows = 2、cols = 3、rCenter = 1、cCenter = 2
出力: [[1,2]、[0,2]、[1,1]、[0,1]、[1,0]、[0,0]]
(1, 2)から他のセルまでの距離：[0,1,1,2,2,3]

制約:
1 <= rows, cols <= 100
0 <= rCenter < rows
0 <= cCenter < cols

解答

class Solution:
    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:
        cells = []
        for r in range(rows):
            for c in range(cols):
                distance = abs(r - rCenter) + abs(c - cCenter)
                cells.append(((r,c), distance))
        
        cells.sort(key=lambda item: item[1])

        result = [list(cell) for cell, distance in cells]
        return result

解説

1.セルの初期化と距離の計算

cells = []
for r in range(rows):
    for c in range(cols):
        distance = abs(r - rCenter) + abs(c - cCenter)
        cells.append(((r,c), distance))

cells = []
後でソートするために、各セルとその中心からの距離を格納する空のリストを用意する。

for r in range(rows)、for c in range(cols)
rows（行数）とcols（列数）を全て反復処理する。 r は現在の行、c は現在の列。

distance = abs(r - rCenter) + abs(c - cCenter)
各セル(r, c)から指定された中心点(rCenter, cCenter)までの距離を計算する。

cells.append(((r,c), distance))
計算されたセル座標(r, c)とその距離のペアを、タプル((r,c), distance)としてcellsリストに追加する。

例

入力: rows = 2、cols = 2、rCenter = 0、cCenter = 1
出力: [[0,1],[0,0],[1,1],[1,0]]

セル (r, c)	距離の計算 (abs(r - rCenter) + abs(c - cCenter))	cellsリストに追加される要素
(0, 0)	abs(0 - 0) + abs(0 - 1) = 0 + 1 = 1	((0, 0), 1)
(0, 1)	abs(0 - 0) + abs(1 - 1) = 0 + 0 = 0	((0, 1), 0)
(1, 0)	abs(1 - 0) + abs(0 - 1) = 1 + 1 = 2	((1, 0), 2)
(1, 1)	abs(1 - 0) + abs(1 - 1) = 1 + 0 = 1	((1, 1), 1)

このステップが完了した時点でのcellsリストは以下になる。

• cells : [((0, 0), 1), ((0, 1), 0), ((1, 0), 2), ((1, 1), 1)]

2.距離によるソート

cells.sort(key=lambda item: item[1])

cells.sort()
リストを昇順でソートする。

key=lambda item: item[1]
key引数にlambda関数が渡されており、リスト内の各要素itemがソートされる際に、その要素のどの値に基づいてソートするかを指定する。
itemは((r,c), distance)という形式のタプルであり、item[1]はこのタプルの2番目の要素であるdistanceを指す。
したがって、この行はcellsリストを、各セルの距離が昇順になるようにソートする。

例

このステップが完了した時点でのcellsリストは以下になる。

• cells : [((0, 1), 0), ((0, 0), 1), ((1, 1), 1), ((1, 0), 2)]

距離が同じセル(この例では(0,0)と(1,1))の順序は考慮されない。どちらが先に来ても正解。

3.結果の整形と返却

result = [list(cell) for cell, distance in cells]
return result

result = [list(cell) for cell, distance in cells]
ソートされた cells リストをイテレートする。

for cell, distance in cells: cells
リストの各要素（(r,c), distance)タプルを分解し、cellに(r,c)を、distanceに距離を代入する。

list(cell)
cellがタプルなので、これを[r, c]というリストに変換する。

最終的に、resultリストには、中心からの距離が近い順に並べられた各セルの座標が[行, 列]の形式のリストとして格納される。

例

• cells : [((0, 1), 0), ((0, 0), 1), ((1, 1), 1), ((1, 0), 2)]

ソートされたcellsリストの要素	抽出される座標リスト	resultリストに追加される要素
((0, 1), 0)	[0, 1]	[0, 1]
((0, 0), 1)	[0, 0]	[0, 0]
((1, 1), 1)	[1, 1]	[1, 1]
((1, 0), 2)	[1, 0]	[1, 0]

最終的なresultリストは以下になる。

• result : [[0, 1], [0, 0], [1, 1], [1, 0]]