LeetCode Weekly Contest 27

週末にはLeetCodeのコンテストが開催されている。最近はアルゴリズムから離れすぎていたので、これからは復習がてら積極的に参加していこうかと思っている。相変わらず厳しさしか感じないのだけど、それでも問題が綺麗に解けるとスッキリする。今回の４題のうち解けたのは最初の２つ。一番最初のeasyのは飛ばして、下記のmediumの方について書いてみる。

554. Brick Wall

長さの異なるレンガが綺麗に長方形状に並べられている。これを縦に斬るとしたらどこが一番抵抗が少なそうかという問題だ。（違う？）

まぁとりあえず、斬らないといけないレンガの数が列ごとに分かればいいよね。普通にインプットの２次元配列をループで回すけど、次の行に移ったときに、各列の抵抗を覚えておかないといけないから、ハッシュテーブルが便利そう。列の番号をkey、レンガの切れ目数をvalueとしてハッシュテーブル（Pythonではdict）に格納する。それ終われば、レンガ数を計算するのは簡単だ。

class Solution(object):
    def leastBricks(self, wall):
        """
        :type wall: List[List[int]]
        :rtype: int
        """
        d = {}
        for r in wall:
            sum = 0
            for b in r[:-1]:
                sum += b
                if sum not in d:
                    d[sum] = 1
                else:
                    d[sum] += 1
        if d:
            return len(wall) - max(d.values())
        else:
            return len(wall)

dictに格納する際の処理はもうちょいエレガントに書けた気がするし、最後の条件分岐のところもあまり美しくない気がする。てゆーかこの辺は関数使わなくてもループの中でも計算できるかも。