いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode medium 221 Maximal Square

更新日:

こんにちは

今回の学びは

最大求める!で二次元配列だったら、DPでしょ。

なぜ、これがすり抜ける?だって、現在の状態から正方形を作れなかったんだもん。。。だったら=>

-> もっとも簡単なパターン2x2で考えてみるkと。そして、基本はそれが使い魔せると信じること

 

問題はmaximal-square

(時間配分は5分問題理解=restate&clarify 10分検討multip-sol, analysis, reasons 10分実装  20分振り返り の一文45分構成)をできればgoogle docで笑&真剣。

終始、わからないことは声にだして、明確にしていきましょう。

1,まずは入出力をしっかりおさえましょう。(問題を自分の言葉で復唱すること、わからないことをクリアにすると、前提も声にだすこと)

 

2,いくつかのソリューションを声にだして出してみましょう。(もちろんtime complexit, space complexityの分析や理由を付け加えて)

 

3,どれでいくか、一緒に決定しましょう。(理由付きでね、よろしく)

timespace analysis (時間とスペースの分析)は 〇〇です

 

場合によっては、pseudocode(擬似コード)をかいてみてもよい。

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example:Input: 

1 0 1 0 0

1 0 1 1 1

1 1 1 1 1

1 0 0 1 0

 

Output: 4

 

1 0 1 0 0

1 0 1 1 1

1 1 1 1 1

1 0 0 1 0

 

Q: Size of the input?

Q: expected runtime?

C: return max area

 

Solutions

  1. loop(m) -> loop(n) validate

 

全然validateの方法がわからんぞ。10分経過

人間だったらどうするか?

・視点をきめる、縦横、それぞれ最大はいくつか?

例えば(1, 2)のポイントの横は3縦は2である。その情報をもとに

それらがすべて1か確認する。

横縦を一個づつ増やして、成立するか確認するwhile 1続く * O(M)

 

def is_range(matrix, i, j):

  N = len(matrix)

  M = len(matrix[0])

  if i < 0 or i >= N: return False

  if j < 0 or j >= M: return False

  return True

 

def validate(matrix, x, y, length):

  for n in range(length+1):

    i, j = x + n, y + n

    if matrix[i][j] != 1:

      return False

  return True

 

def get_max_square(matrix, x, y):

  counter = 0

  i, j = x, y

  while is_range(i, j) and matrix[i][j] == 1:

    if validate(matrix, i, j, counter)

    counter += 1

    i += 1

    j += 1

  return counter ** 2

 

def solve(matrix: List[List[int]]) -> int:

  N = len(matrix)

  M = len(matrix[0])

 

1 0 1 0 0

1 0 1 1 1

1 1 1 1 1

1 0 0 1 0

 

とけなかったので回答みたらdpつかってたのがまず目にはいったので

 

dpでいきましょう。

 

dp[i][j]はi,jが1で最大のmax areaとすると

dp[i][j] = dp[1][i-1][j-1] 

 

#それでも思いつかないので

https://leetcode.com/problems/maximal-square/discuss/496199/DP-O(MN)-space-O(MN)-time-Easy-to-understand.-Can-optimize-to-O(1)-space-easily.

をみた。

初見、わからない。

 

最大求める!で二次元配列だったら、DPでしょ。

なぜ、これがすり抜ける?だって、現在の状態から正方形を作れなかったんだもん。。。

2x2まあではできるよ。

そのあとの3x3とがむずくね?

 

1

 

11

11

 

111  111

111  122

 

111  111

111  122

111  123

 

奇跡やん、こんなん。

状態はi, jが{0, 1} 

価値関数はf(i, j)まできた時の, max area

方策関数は上、左上、左のminに対して、i,jが1なら +1 そうでないなら0

-> もっとも簡単なパターン2x2で考えてみるkと。そして、基本はそれが使い魔せると信じること

 

100011

101111

111011

011001

 

1111

1111

1111

 

 

4、実装しましょう。

できませんでした。

最初のボツ実装はこちら。

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        def is_range(matrix, i, j):
            N = len(matrix)
            M = len(matrix[0])
            if i < 0 or i >= N: return False
            if j < 0 or j >= M: return False
            return True

        def validate(matrix, h, w, length):
            for n in range(length):
                for m in range(length):
                    i, j = h + n, w + m
                    if matrix[i][j] != 1:
                        return False
            return True

        def get_max_square(matrix, x, y):
            counter = 0
            i, j = x, y
            while is_range(matrix, i, j) and matrix[i][j] == 1:
                if validate(matrix, x, y, counter):
                    counter += 1
                i += 1
                j += 1
            return counter ** 2

        def solve(matrix: List[List[int]]) -> int:
            N = len(matrix)
            if N == 0: return 0
            M = len(matrix[0])
            maxi = 0
            for i in range(N):
                for j in range(M):
                    local = get_max_square(matrix, i, j)
                    maxi = max(local, maxi)
            return maxi

        matrix2 = [list(map(int, row)) for row in matrix]
        return solve(matrix2)

回答をみる。

https://leetcode.com/problems/maximal-square/discuss/496199/DP-O(MN)-space-O(MN)-time-Easy-to-understand.-Can-optimize-to-O(1)-space-easily.

そのあと、

それぞれのi,jまでの範囲ででの最大をだしていく。 つまりdp[i][j]は範囲を右下をi,jとした時の最大面積は?という価値関数になる。 状態は、0か1のどちらか 0の場合は、0となる。これまでの最高を引鶴と、うまく行かないのは自明。 だから1の場合は、上、左、左上の3店のminに1を加える とここまでいうと dp[i][j]は範囲を右下をi,jとした時、右下を含む範囲全体の最大面積は?という価値関数になる。 なので、毎回dp[i][j]を計算していって、maxを更新する作業O(1)が必要です

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        """
        それぞれのi,jまでの範囲ででの最大をだしていく。
        つまりdp[i][j]は範囲を右下をi,jとした時の最大面積は?という価値関数になる。
        状態は、0か1のどちらか
        0の場合は、0となる。これまでの最高を引鶴と、うまく行かないのは自明。
        だから1の場合は、上、左、左上の3店のminに1を加える
        とここまでいうと
        dp[i][j]は範囲を右下をi,jとした時、右下を含む範囲全体の最大面積は?という価値関数になる。
        なので、毎回dp[i][j]を計算していって、maxを更新する作業O(1)が必要です
        """
        n = len(matrix)
        if n == 0: return 0
        m = len(matrix[0])
        dp = [[0] * m for _ in range(n)]
        maxi = 0
        for i in range(n):
            dp[i][0] = int(matrix[i][0])
            maxi = max(dp[i][0], maxi)
        for j in range(m):
            dp[0][j] = int(matrix[0][j])
            maxi = max(dp[0][j], maxi)

        for i in range(1, n):
            for j in range(1, m):
                dp[i][j] = 0 if matrix[i][j] == "0" else min(
                    dp[i-1][j-1],
                    dp[i][j-1],
                    dp[i-1][j]
                ) + 1
                maxi = max(dp[i][j]**2, maxi)
        return maxi

5、エッジケースとサンプルテストを忘れずに!

 

 

ついでにtopdownでも。これだとTLEエラーになるので、

class Solution: # topdown
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        n = len(matrix)
        if n == 0: return 0
        m = len(matrix[0])
        maxi = 0

        def square_matrix(matrix, i, j):
            if i >= n or j >= m: return 0
            if matrix[i][j] == "0": return 0
            return 1 + min(
                square_matrix(matrix, i+1, j),
                square_matrix(matrix, i  , j+1),
                square_matrix(matrix, i+1, j+1),
            )

        for i in range(0, n):
            for j in range(0, m):
                local = square_matrix(matrix, i, j)
                maxi = max(local**2, maxi)
        return maxi

キャッシュをいれてみましょうー

あら不思議、@lru_cache(maxsize=None)をいれただけでTLEがクリアされて通りましたよ!

matrix, listはhashableではないので、インターフェースをすこし替えてますが。(理由はpythonのしくみで書いてます。)

from functools import lru_cache
class Solution: # topdown
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        n = len(matrix)
        if n == 0: return 0
        m = len(matrix[0])
        maxi = 0

        @lru_cache(maxsize=None)
        def square_matrix(i, j):
            if i >= n or j >= m: return 0
            if matrix[i][j] == "0": return 0
            return 1 + min(
                square_matrix(i+1, j),
                square_matrix(i  , j+1),
                square_matrix(i+1, j+1),
            )

        for i in range(0, n):
            for j in range(0, m):
                local = square_matrix(i, j)
                maxi = max(local**2, maxi)
        return maxi

 

 

振り返り

「次のこの問題を解くばあい知っていればよい一つの事実とは?」

 

まとめ

最大求める!で二次元配列だったら、DPでしょ。

なぜ、これがすり抜ける?だって、現在の状態から正方形を作れなかったんだもん。。。だったら=>

-> もっとも簡単なパターン2x2で考えてみるkと。そして、基本はそれが使い魔せると信じること

以上です

-アルゴリズム
-,

Copyright© CTOの日記 , 2020 All Rights Reserved.