NeetCodeのSolutionを書いていく

#

Happy Number

#

「非循環数」とは次のアルゴリズムで定義される整数です。

• 整数が与えられ、それぞれの数字の2条を積算する。
• 上記を繰り返し、1が得られたら終了する。あるいは1を含まないループを繰り返す。
• 1で止まったらそれは非循環数です。

非循環数であればTrueを、循環数であればFalseを返します。 計算結果を記録しておけばいいだけか？結構簡単？

class Solution:
    calced: list[int] = []
    def calc(self, n) -> bool:
        strn = str(n)
        retval = 0
        for c in strn:
            retval += int(c) * int(c)
        if retval == 1:
            return True
        elif retval in self.calced:
            return False

        self.calced.append(retval)
        return self.calc(retval)

    def isHappy(self, n: int) -> bool:
        return self.calc(n)

行けない！？ なんだか、Runだとpassするんだけど、Submitすると通らない謎の現象が発生。

Runの場合

#

Submitの場合

#

わからん・・・ まあいいや。答えを見たところ、listよりsetのほうがin演算が早いことを学べた ✏️

Plus One

#

整数の配列digitsが与えられます。 それぞれ0番目が最も大きな桁、1番目が次、のように続きます。0が最初に来ることはありません。 1を足した結果を同様の整数配列で返してください。

Input: digits = [1,2,3,4] Output: [1,2,3,5]

Input: digits = [9,9,9] Output: [1,0,0,0]

これは、文字列を数字にキャストして、演算して、文字列に直せないかな？

class Solution:
    def plusOne(self, digits: list[int]) -> list[int]:
        snumber = ""
        len_digits = len(digits)
        for i in digits:
            digit = str(i)
            snumber += digit
        number = int(snumber) + 1
        snumber = str(number)
        digits = []
        for c in snumber:
            digits.append(int(c))
        return digits

いけたー。 でもなんの工夫もしていないな。 計算量はO(2n)?

回答だと一番下の桁が9かどうか判定して、9ではない場合は足すだけ。 9の場合は最後の桁を0に、最後の桁以外を使って再帰的に計算。 確かにこれだとO(n)でいけていいね。