【LeetCode】Longest Substring Without Repeating Characters 解法【Python】

Longest Substring Without Repeating Characters

leetcode.com

与えられた文字列内で、文字が重複しない範囲の最大の文字数を返却する。

解法

１文字見ていって、重複した時点の１文字前までの文字数を最大候補として、 重複した文字の最初に出てきた場所から再度カウントし直す。 それを繰り返して最大候補の中から最大文字数を返却する。

毎回、重複した文字の最初に出てきた文字まで戻るのはコストなので、 その場所を覚えておき、現在の場所までの文字列をスライス、みたいなふうにして高速化。

コード

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        if s == "":
            return 0
        if len(set(s)) == len(s):
            return len(s)
        
        max_len = str_len = 1
        local_s = [s[0]]
        s_idx = 0
        for i in range(1, len(s)):

            if s[i] in local_s:   
                str_len = i - s_idx
                max_len = max(max_len, str_len)
                
                find_idx = local_s.index(s[i])
                s_idx = find_idx+s_idx+1
                local_s = local_s[find_idx+1:]
            
            local_s.append(s[i])
        else:
            str_len = len(s) - s_idx
            max_len = max(max_len, str_len)
                
        return max_len
            

ハッシュ使ったらもっと速そう。

solutionに書いていたシンプルなコード（にちょっとだけ手を加えて高速化したもの）

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """

        str_list = []
        max_length = 0

        for x in s:
            if x in str_list:
                max_length = max(max_length, len(str_list))
                str_list = str_list[str_list.index(x)+1:]
            str_list.append(x)    
        else:
            max_length = max(max_length, len(str_list))

        return max_length

さらに、solutionに書いていた、めちゃ速い解法。 やはりdict使っている。

class Solution:
    def lengthOfLongestSubstring(self, s):
        dicts = {}
        maxlength = start = 0
        for i,value in enumerate(s):
            if value in dicts:
                sums = dicts[value] + 1
                if sums > start:
                    start = sums
            num = i - start + 1
            if num > maxlength:
                maxlength = num
            dicts[value] = i
        return maxlength

【書評】入門Python3 ：とりあえず読んでおくべき

ある程度pythonを触った身からすると、読んでおいて損はない本。

入門 Python 3

これが全く触ったことがな人だともしかしたら読みづらいかもしれない。 そもそもオラ本が全般的に初心者に易しくない気はする（head firstシリーズは易しい？）。

• pythonを触ったことがある人
• python以外の言語を触ったことがある人

上記に当てはまる場合（自分はそう）は、間違いなく優良な本だった。 というのは、やはり実践主義でコードを書いていると、変な癖がつく気がしていて、 それはpythonのポリシーと合っているかわからないし、そもそも無駄な実装をしている可能性もあり、 標準ライブラリを使えば簡単に解決できるのではないか、という不安を抱いて、 この本を読んだらその不安が的中していたからである。

例えば、setクラスはずっと重複なしリストだと思い込んでいた。 「リストから重複を除外したい」と調べたら大体setを使った解法が出てくるため、 そのために作られたクラスなのだと思い込んでしまっていた。実際は集合クラスなので集合演算ができる。 他にもcsvにあるDictReaderやDictWriterも便利だなと思った（pandas使う場面が多いけど）。

とはいえ、イディオムやデザインパターンなどの内容は書いていないため、 この本を読めばシステム開発ができるとまではいかない。 にしても、どのような道具があるのかを知ることできるし、どの場面で使えばいいのかもわかるため、 今後pythonを触るエンジニアは早めに読むことをおすすめする。

個人的付箋

集合クラス

setは集合クラス。重複なしリストかと思ってたが違った。 なので集合演算ができる。

a  = {1, 2}
b = {2, 3}

a & b
a.intersection(b)
a + b
a.union(b)

elseによるbreakチェック

whileやforは、正常終了したかどうかをチェックするオプションのelseを持っている。 ループがbreak呼び出して途中で終了しておらず、最後まで実行されたときにelse内が実行される。

for c in cs:
    print('hoge')
    break
else: # breakしていない
    print('fuga')

例外

exrcept exceptiontype as name

short_list = [1, 2, 3]
while True:
    value = input('Position [ q to quit ] ? ')
    if value = 'q':
        break
    try:
        position = int(value)
        print(short_list[position])
    except IndexError as err:
        print('Bad index:', position)
    except Exception as other:
        print('Something else broke:' other)

存在しないキーの処理

存在しないキーで辞書にアクセスする際の振る舞いについて、 get()関数を使ってデフォルト値を返すようにすれば例外を避けられる。 setdefault()関数はキーがなければさらに辞書を要素に追加することができる。

periodic_table = {'Hydrogen' : 1, 'Helium' : 2}
carbon = periodic_table.setdefault('Carbon', 12)

# carbon => 12
# periodic_table =>  {'Hydrogen' : 1, 'Helium' : 2, 'Carbon', 12}

# すでにキーがある場合は更新されない
helium = periodic_table.setdefault('Helium',  923)
# helium => 2
# periodic_table =>  {'Hydrogen' : 1, 'Helium' : 2, 'Carbon', 12}

defaultdictは辞書作成時にあらゆる新キーのためにあらかじめデフォルト値を設定する。

from collections import defaultdict
periodic_table = defaultdict(int)
periodic_table['Hydrogen'] = 1
periodic_table['Lead']

periodic_table
# defaultdict(<class 'int'>, {'Lead': 0, 'Hydrogen': 1})

特殊メソッド

比較のための特殊メソッド

メソッド	意味
__eq__( self, other )	self == other
__ne__( self, other )	self != other
__lt__( self, other )	self < other
__gt__( self, other )	self > other
__le__( self, other )	self <= other
__ge__( self, other )	self >= other

算術演算のための特殊メソッド

メソッド	意味
__add__( self, other )	self + other
__sub__( self, other )	self - other
__mul__( self, other )	self * other
__floordiv__( self, other )	self // other
__truediv__( self, other )	self / other
__mod__( self, other )	self % other
__pow__( self, other )	self ** other

その他の特殊メソッド

メソッド	意味
__str__( self, other )	str(self)
__repr__( self, other )	repr(self)
__len__( self, other )	len(self)

下記でドキュメント化されている。

https://docs.python.org/3/reference/datamodel.html#special-method-names

Guidoのアドバイス

Guido van Rossum

データ構造を作り込みすぎないようにしよう。オブジェクトよりもタプルの方がいい。ゲッター／セッター関数よりも単純なフィールドを選ぶようにしよう。組み込みデータ型はプログラマーの友達だ。数値、文字列、タプル、リスト、集合、辞書をもっと使おう。そして、コレクションライブラリ、特にデックをチェックしよう。

collections --- コンテナデータ型 — Python 3.8.3 ドキュメント

名前つきタプル

from collections import namedtuple
Duck = namedtuple( 'Duck', 'bill tail' )
duck = Duck('wide orange', 'long')
# duck => Duck(bill='wide orange', tail='long)
# duck.bill => wide orange
# duck.tail => 'long'

csv

DictReaderを使って辞書リストにすることができる。 各行のキーが、各列のヘッダーとなる。

import csv
with open('villains', 'rt') as fin:
    cin = csv.DictReader(fin, fieldname=['first', 'last'])
    villanins = [row for row in cin]

DictWriterを使って辞書リストからヘッダー付きのcsvファイルを作成することができる。

with open('dst_villains', 'wt') as fout:
    cout = csv.DictWriter(fout, ['first', 'last']
    cout.writeheader()
    cout.writerows(villains)

yaml

PyYAMLは文字列からPythonオブジェクトをロードできるが、これは危険なことだ。 load()ではなくsafe_load()を使うべき。

Ned Batchelder: War is peace

timedelta

from datetime import date, timedelta
now = date.today()
one_day = timedelta(day=1)
tomorrow = now + one_day
yesterday = now - one_day

# 17日後
now + 17 * one_day

リスト内表記はappend()を使ったリストへの要素追加より速い

result =[]
for value in range(1000):
    result.append(value)

# こちらのほうが2倍以上速い
result = [value for value in range(1000)]

【LeetCode】Maximum Product Subarray 解法【Python】

leetcode.com

Maximum Subarrayの総乗バージョン。

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

総和の場合と同じように、スプレッドシートで計算する。

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

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で区切る
        その範囲で、
        負が偶数個の範囲が、ローカルマックス
        左右のどっちを削れば、最大になるか。
        １つだけならそれ正だろうが負だろうが
        """
        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_

【LeetCode】Maximum Subarray 解法【Python】

Maximum Subarray leetcode.com

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

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

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

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

太字の部分が各列で最大値となり、 太字の中で最大の値は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_

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

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

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

本を読み上げてくれる

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

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

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

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

三体

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

倍速再生対応

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

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

1コイン無料

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

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

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

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

leetcode.com

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

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

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

除算していいなら、全てを掛け合わせたあとでループして各要素を除算すれば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に書かれているものよりは速い。

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))