概要

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

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

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

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day51 「647. Palindromic Substrings」

今はTop 100 Liked QuestionsのMediumを優先的に解いています。
Easyは全て解いたので気になる方は目次の方へどうぞ。

Twitterやってます。

問題

1351. Count Negative Numbers in a Sorted Matrix

難易度はEasy。

m*nの行列gridが与えられます。その行と列両方とも増加が起こらないような形式でソートされています。
（つまり、要素の値が現状維持、ないしは減少する順である、ということです。）

そのgridのなかに存在する負の数を返すようなアルゴリズムを設計してください、という問題です。

Example 1:

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.

Example 2:

Input: grid = [[3,2],[1,0]]
Output: 0
Example 3:

Example 3:
Input: grid = [[1,-1],[-1,-1]]
Output: 3

Example 4:

Input: grid = [[-1]]
Output: 1

解法

import itertools

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        count = 0
        lists = []
        lists = list(itertools.chain.from_iterable(grid))
        for i in lists:
            if i < 0:
                count += 1
        return count
# Runtime: 128 ms, faster than 63.80% of Python3 online submissions for Count Negative Numbers in a Sorted Matrix.
# Memory Usage: 14.9 MB, less than 20.02% of Python3 online submissions for Count Negative Numbers in a Sorted Matrix.

こんな感じです。
まあ各要素をとりあえずfor文で回すのは想像が付くと思います。

ただ、itertools.chain.from_iterableについてはそこまで馴染みがない人もいらっしゃるのではないでしょうか。

chain() のためのもう一つのコンストラクタです。遅延評価される iterable 引数一つから連鎖した入力を受け取ります。この関数は、以下のコードとほぼ等価です:
def from_iterable(iterables):
    # chain.from_iterable(['ABC', 'DEF']) --> A B C D E F
    for it in iterables:
        for element in it:
            yield element

公式ドキュメントにもある通り、以上のように動きます。
ちなみにchain()の方は以下のような説明がされています。

itertools.chain(*iterables)
先頭の iterable の全要素を返し、次に2番目の iterable の全要素を返し、と全 iterable の要素を返すイテレータを作成します。連続したシーケンスを一つのシーケンスとして扱う場合に使用します。およそ次と等価です:
def chain(*iterables):
    # chain('ABC', 'DEF') --> A B C D E F
    for it in iterables:
        for element in it:
            yield element

何が違うんだよ！となるかもしれませんが、
chain, chain.from_iterableの紹介(pythonのitertoolsを使いこなすために)
こちらの記事でよく解説されており、こちらを参照した方が速いため紹介させていただきます。

楽ができるのはPythonの良いところですね。

話変わりますけどPythonの勉強会（オンライン開催）に参加しました。久しぶりに勉強会に参加したのでそちらの方が楽しくて更新が遅れてしまいました。
そちらについての記事（おそらくSphinx）についての記事も書く予定なのでよければ見てください〜。

今回はここまで。お疲れ様でした。

ゼロから始めるLeetCode Day52 「1351. Count Negative Numbers in a Sorted Matrix」

概要

問題

解法