 125. Valid Palinedrome与えられた文字列のアルファベットのみを抽出して回文かどうかを判定する問題

(そもそもメソッドや関数に関する知識が無くて困ることが多いのだが…)
    def isPalindrome(self, s: str) -> bool:
        new_s = []
        for x in s:
            if x.isalpha() or x.isdecimal():
                new_s.append(x)

        mid_index = len(new_s) // 2
        for_str = new_s[:mid_index]
        back_str = new_s[mid_index:]
        back_str.reverse()
        for i in range(mid_index):
            if for_str[i].lower() != back_str[i].lower():
                return False
        return True
reverse()はmutableな（更新可能な）リストのメソッド

reversed()は要素を逆順に取り出すイテレータを生成。非破壊的処理。

https://note.nkmk.me/python-reverse-reversed/

lower(), upper()はそれぞれアルファベットを小文字へ、大文字へと変換するメソッド

is.decimalは文字列が十進数であるかを判定
どうやらめんどくさいことをやっていそうなこのコード…半分にしなくてもそのままコピーして反転させればよいらしい。これだと、time complexityが O(n), space complexityがO(n)（文字列をコピーしている）で理想的ではないらしい。space complexityはO(1)にできるそう。なるほど。
alphanumerical（英数字）の判定はisalnum

x[::-1]でreversed()と同じ
左右にポインター用意して比較すれば空間計算量がO(1)になるらしい。

shiori

Valid Parentheses

かっこ（(){}[]）が正しい順番で並んでいて閉じているかの判定

remove()：配列の指定した値と同じ要素の最初の要素を削除するメソッド。mutable
pop()：配列の指定したインデックスの要素を削除して取得するメソッド。mutable
replace()：文字列のうち、指定した文字列と完全に一致する文字列を置き換えることができる。空文字列を指定すると削除できる。replace(x, '') immutable

    def isValid(self, s: str) -> bool:
        while len(s) > 0:  
            print(s)  
            if '()' in s:
                s = s.replace('()', '')
            elif '{}' in s:
                s = s.replace('{}', '')
            elif '[]' in s:
                s = s.replace('[]', '')
            else: return False
        return True

もう少しすっきりかけるらしい…whileの条件もs != ''のほうがいいか？？
これより時間計算量を減らすにはstackを使うそうだ、うむ。

shiori

Bset Time to Buy and Sell Stock

    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        for i in range(len(prices)-1):
            new_profit = max(prices[i+1:]) - prices[i]
            if profit < new_profit:
                profit = new_profit
        return profit

スライス操作はスライスされる要素の数を $k$ としたときに、時間計算量は $O(k)$ になる。
これだと時間計算量は $O(n^2)$ 、空間計算量は $O(n)$

shiori

revers Linked List

問題文の意味が分からなかった。singly linked list、単方向連結リスト。なんじゃそらー。
連結リストとはデータとポインタで構成されたデータ構造なのだとか。あとはメモリ空間を連続的に確保しなくていいとか、先頭から順番にたどってアクセスしないといけないとか。

イテラブル：for文で繰り返せるオブジェクトやそのクラス