遙かなるマチョジニア

マッチョXエンジニアを目指すブログ

【LeetCode】Maximum Product Subarray 解法【Python】

leetcode.com

Maximum Subarrayの総乗バージョン。

しかし、解法が全然違う(自分が思いついた解法は)。

総和の場合と同じように、スプレッドシートで計算する。 f:id:shuheilocale:20200526063051p:plain

ここから見えてきたものをルール化する。

inputの配列の内、最大になる候補を「特定範囲」とすると。

  • 特定範囲に0がはいると総乗は0
  • 特定範囲に負が奇数個入ると、総乗は負
  • 特定範囲に負が偶数個入ると、総乗は正

これらを踏まえてロジックは下記のようにする。

  • 配列内に0が出てくるまでの範囲を特定配列とする
  • 特定範囲に負が偶数個の場合は、特定範囲の総乗を最大値候補にする
  • 特定範囲に負が奇数個の場合は、先頭の負を除く範囲での総乗と、最後尾の負を除く範囲での総乗を比較し、大きい方法を最大値候補にする
  • 最大値候補から、最も大きい値を返却する

ソースは汚いのでいつかのタイミングで修正したい。

def prod(nums):
    if len(nums) == 0:
        return None
    
    result = nums[0]
    for num in nums[1:]:
        result *= num
    return result
        

class Solution:
    
        
        
    def maxProduct(self, nums: List[int]) -> int:
        """
        負を偶数個含むなら、最大になる
        負を奇数個含むなら、最小になる
        0を含むとかならず0
        
        0がある場合は,0で区切る
        その範囲で、
        負が偶数個の範囲が、ローカルマックス
        左右のどっちを削れば、最大になるか。
        1つだけならそれ正だろうが負だろうが
        """
        if len(nums) == 1:
            return nums[0]
        
        local_nums=[]
        max_ = nums[0]
        count_minus = 0
        local_sumproduct = 1
        local_minus_idx_l = -1
        local_minus_idx_r = -1
        zero_idx_l = -1
        zero_idx_r = -1
        for idx, num in enumerate(nums):
            
            if num != 0:
                local_sumproduct *= num
                if num < 0:
                    count_minus += 1
                    
                    if local_minus_idx_l == -1:
                        local_minus_idx_l = idx
                    local_minus_idx_r = idx
                    
                local_nums.append(num)
            # 0がきたら一回計算
            else:
                zero_idx_r = idx
                if len(local_nums) != 0:
                    
                    if len(local_nums) == 1:
                        max_ = max(max_, local_sumproduct)
                    # 偶数のときは単純に全ての積
                    elif count_minus % 2 == 0:
                        max_ = max(max_, local_sumproduct)
                    # 奇数のときは、マイナスを外す
                    elif count_minus == 1:
                        a = prod(nums[zero_idx_l+1:local_minus_idx_l])
                        b = prod(nums[local_minus_idx_l+1:zero_idx_r])
                        n = []
                        if a is not None:
                            n.append(a)
                        if b is not None:
                            n.append(b)
                        max_ = max(n+[max_])
                    else:
                        a = prod(nums[local_minus_idx_l+1:zero_idx_r])
                        b = prod(nums[zero_idx_l+1:local_minus_idx_r])
                        max_ = max(a,b,max_)
                        n = []
                        if a is not None:
                            n.append(a)
                        if b is not None:
                            n.append(b)
                        max_ = max(n+[max_])
                        
                    max_ = max(0, max_)
                        
                # 初期化
                zero_idx_l = idx
                zero_idx_r = -1
                local_minus_idx_l = local_minus_idx_r = -1
                local_sumproduct = 1
                local_nums= []
                count_minus = 0
        
        # 最後の処理
        if len(local_nums) != 0:

            if len(local_nums) == 1:
                max_ = max(max_, local_sumproduct)

            # 偶数のときは単純に全ての積
            elif count_minus % 2 == 0:
                max_ = max(max_, local_sumproduct)
            # 奇数のときは、マイナスを外す
            elif count_minus == 1:
                a = prod(nums[zero_idx_l+1:local_minus_idx_l])
                b = prod(nums[local_minus_idx_r+1:])
                n = []
                if a is not None:
                    n.append(a)
                if b is not None:
                    n.append(b)
                max_ = max(n+[max_])
            else:
                a = prod(nums[local_minus_idx_l+1:])
                b = prod(nums[zero_idx_l+1:local_minus_idx_r])
                n = []
                if a is not None:
                    n.append(a)
                if b is not None:
                    n.append(b)
                max_ = max(n+[max_])
        
        
        return max_

f:id:shuheilocale:20200526064349p:plain

【LeetCode】Maximum Subarray 解法【Python】

Maximum Subarray leetcode.com

inputの配列の内、隣接する数字の合計が最も高くなる値を求めよ。 制限:O(n)

二重loop使えば簡単に解けるがもちろんそれはダメ。 サンプルのINPUTを可視化すると↓

f:id:shuheilocale:20200522073955p:plain

4, -1, 2, 1 の範囲が最大で6になる。

それぞれ開始位置をずらしてcumsumしていく。 と下記になる。

f:id:shuheilocale:20200522074105p:plain

太字の部分が各列で最大値となり、 太字の中で最大の値は6、つまり4,-1,2,1の数字の合計ということがわかる。

この太字をなぞるようにしてループを回し、最大値を保存すればOK。

さらに制約として、 全て正の場合は単純な合計、全て負の場合は、配列の中の最大値を返すようにして多少の高速化を行う。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        
        max_ = max(nums)

        if max_ <= 0:
            return max_
    
        if min(nums) > 0:
            return sum(nums)
        
        cumsum = nums[0]
        for num in nums[1:]:
            cumsum = max(num, cumsum + num)
            max_ = max(max_, cumsum)
            
        return max_

f:id:shuheilocale:20200522074410p:plain

テレワークのお供にAudibleはいかがですか。

自分は元々読書好きだが、隙間時間に本を読むだけでは満足できない。 移動中はpodcastやvoicyも聴いているが、できれば読書も楽しみたい。

てことで本を読み上げてくれるamazonが提供しているサービスを紹介したい。

本を読み上げてくれる

いや、まんまじゃん!と思うかもしれないが、そう、まんまである。

本を読み上げる、以外の何もない。でも求めていたのはそれだけなのだから、それで満足している。 本の種類は、そこそこある。著名な本はある程度抑えていると言った感じ。

f:id:shuheilocale:20200521062428p:plain

音声は気にならないし、むしろ感動した

音声については、人によって評価はまちまちなので好みによると思うが、個人的には気にならない。というか、ビジネス書が多いから、別にいいとも思わないし、悪いとも思わない。 ただ、三体を聴いたときは、すごいなあと思った。

三体

三体

  • 作者:劉 慈欣
  • 発売日: 2019/07/04
  • メディア: ハードカバー

これ、ナレーター1人でやってるのか!!という感動。読書だけだと決して体験できなかったのですごく嬉しかった。

倍速再生対応

結構細かい刻みでx3まで対応している。

f:id:shuheilocale:20200521062905p:plain

再生時間が書いているので、そこから倍数をかけてあげて、どのくらいで読み終えるのかが把握できるのも良い。

1コイン無料

登録すると初月は1コイン無料で配布される。それで試して、気に入らなければやめれば、料金は発生しない。 コインというのは、毎月配布されて、好きなオーディオと交換することができる。 もちろんコインがなくても、オーディオを購入することは可能だが、その際は、コインではなくてお金で直接購入する。 なのでコインは価格が高い作品と交換するのがよい。もちろん、興味のない作品と交換する必要はないが、 購入候補があれば、その中から一番高いものをコインで、一番安いものをお金で買ったほうがいい。

ながら聴きは移動時間だけではなくなった

普段は移動中にaudibleを使っていたが、最近はそれ以外でも使う時間が増えた。そう、テレワーク中である。シャローワーク(単純作業)の際は、 手が勝手に動くため、脳味噌をaudibleに集中することができる。流石に読書はできないが耳で聴く分には問題ない。 素晴らしい、テレワークと相性ぴったしかよ!

【LeetCode】Product of Array Except Self 解法【python】

leetcode.com

これはかなり考えたけどO(N)かつ除算なしという制限をクリアする解放が思い付かずにいた。 solutionをちらっと見たら図が載っていてそれでなるほど、となった(ソースと解説は読んでいない)。

ある1次配列について、自分以外の要素を乗算した配列を返す、という問題。図にするとこんな感じ↓

f:id:shuheilocale:20200520071148p:plain

ハイフン以外の要素をかける。

除算していいなら、全てを掛け合わせたあとでループして各要素を除算すればOKだがこれは禁止。 各要素について、各要素を除いた数を乗算というブルートフォースが考えられるがO(N)という制限があるので禁止。

で、よくみると、ハイフンを境に、左と右で数字が分かれている。 なので、左の乗算と右の乗算をそれぞれ計算して最後に各要素で掛け話せればO(N)で実現できる。

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        
        length = len(nums)
        l = [1] * (length-1)
        r = [1] * (length-1)
        
        l[0] = nums[0]
        r[0] = nums[-1] 
        
        rnums = nums[::-1]
        
        for i in range(1, len(nums)-1):
            l[i] = nums[i]*l[i-1]
            r[i] = rnums[i]*r[i-1]
            
        return [lv*rv for lv, rv in zip([1]+l, r[::-1]+[1])]
        

処理速度は全体的にみると少し遅いけど、solutionに書かれているものよりは速い。 f:id:shuheilocale:20200520071724p:plain

dicussに書かれていた解法(120ms)は↓

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        
        if not nums: return False
        
        arr = [1] * len(nums)
        pi = pj = 1

        for i in range(len(nums)):
            j = -1-i

            arr[i]*=pi; arr[j]*=pj
            pi *= nums[i]; pj *= nums[j]        
                    
        return arr

【LeetCode】Contains Duplicate 解法 【python】

leetcode.com

これはpythonだから簡単だった。set(集合)で重複が削除できるので、 listとsetでサイズが同じかどうかを判定すればOK。

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(nums) != len(set(nums))

ML Study Jams Vol.4 完了したから軽く感想

ML Study Jams Vol.4

developers-jp.googleblog.com

とりあえず対象のハンズオンを8つクリアした。

↓は対象外のも含む。

f:id:shuheilocale:20200517110619p:plain

f:id:shuheilocale:20200517110632p:plain

f:id:shuheilocale:20200517110643p:plain

4つでマグカップがもらえるが、8つ以上だと、過去のグッズ(Tシャツとバッグ)ももらえるのだ。

感想

以下はどっちかというとqwiklabsの感想になる。

有用か?

基本的には、文章読みながら理解して、ソースコードコピペしながら進めていくので、学ぶ姿勢がなければただの作業になる。 ただし、一部は与えられた課題にたいして過去のハンズオンを参考に自分で考える必要があるものもある。 学ぶ姿勢があれば有用だとは感じる。ただの作業にしても、4,5回同じことしてたら流石に覚えそうな気もする。

致命的な不具合

qwiklabsについては、ちょいちょいエラーが気になった。 今回は8つクリアしたが、実際途中で諦めたのも2つあった。 なぜかエラーで進めないなどがあるのだが、まあ無料だから仕方ないとして、 Dataprepのコースはやつは結構やばい↓

f:id:shuheilocale:20200517110921p:plain

個人的にやっておきたいもの

AutoMLでさくっと学習はやってみたい。業務で作ってるモデルよりこちらのほうがよければもうこれでいいんじゃね? って思ってしまう。ベンチマークとしてさくっと使いたい。

www.qwiklabs.com

【GCP】Cloud DataprepのTransformerはデータ分析向けに心地良すぎた

Qwiqlabsの下記講義でgcpのサービスであるCloud Dataprepの使い方を学んだのだが、 その中にあるTransofrmerと言うのがすごく良かった。

Dataprep: Qwik Start

次世代版エクセルというか、これをjupyterと組み合わせてインタラクティブにできたら最高だなあと思う。

デーブルデータをロードすると、各カラムに統計やtypeが表示される。 f:id:shuheilocale:20200516100917p:plain

これだけでデータ分析コンペはかなり嬉しいんじゃないか、pandas-profilingみたいなもんだ。

ヒストグラムはただの画像ではなく、グラフとして機能している。 f:id:shuheilocale:20200516101102p:plain

カーソルを合わせると、対象binの数値が表示さるのだ。すげえ。

カラムのヘッダから簡易的なフィルタリングも可能。 f:id:shuheilocale:20200516101205p:plain

対話型のGUIでぽちぽち条件を設定すると、自動的にクエリに変換される。 f:id:shuheilocale:20200516101239p:plain

こう言うの本当に嬉い。直感的に操作した後で微調整や繰り返しはコードでっていうことができる。 wangle言語というDSL(なのかな?)を用いれば、このようなクエリをコードで表現することも可能だ。

cloud.google.com

さらにそれらをデータ処理フローとして登録できる。他のテーブルデータとの結合も簡単。 f:id:shuheilocale:20200516101349p:plain

ネットをクソ適当に探したけど、まだそんなに知られてないのか日本語の文献が全然出てこない。 見つけた資料としてはcourseraの動画があったので、見て欲しい。

www.coursera.org