剣指offerシリーズ-面接問題46.数字を文字列に訳す

文書ディレクトリ

1. タイトル

2. 解題構想

2.1再帰

2.2反復(ダイナミックプランニング)

3. コード実装

3.1再帰

3.2文字列

を巡回

3.3数字は残りの

を求めます

4. まとめ

5. 参考文献

1.テーマ
1つの数字を与えて、私達は以下の規則に従ってそれを文字列に訳します:0は“a”に訳して、1は“b”に訳して、......、11は“l”に訳して、......、25は“z”に訳します.1つの数字に複数の翻訳がある可能性があります.プログラミングして1つの関数を実現して、1つの数字がどれだけ異なる翻訳方法があるかを計算してください.
2.問題の解き方
詳しくは試験問題46にお会いします.数字を文字列に訳す(ダイナミックプランニング、明確な図解)
2.1再帰
上から下へ
例えば、入力数1068385920は、末尾の20が単独の2と0とみなすことができるため、20とみなすこともできる.すなわち、「106838590」=「1068388592」+「0」+「10683859」+「20」とみなすことができるので、f(10683885920)=f(1068388592)+f(106838859)が106885930であれば、f(10683885930)=f(1068388593)が10~25の範囲内の数には2つの分配方法がある.この範囲にない数は1つの分配方法だけがこの法則に従って再帰すればよい.
2.2反復(動的計画)
下から上へ,初期条件と繰返し式に基づいて次の状態の結果を推定した.
前のカエルが階段を跳ぶような問題がある.10~25の範囲内の数には2つの分配方法があり、この範囲外の数は1つの分配方法a,b=1,1 if 10<=num<=25 a,b=b,a+b else:a,b=b,b
3.コード実装
3.1再帰
もちろん文字列で再帰することもできますが、数字のほうがいいです.

class Solution:
    def translateNum(self, num: int) -> int:
        """
          
        """
        if 0 <= num <= 9: return 1
        a = num % 100
        if 10 <= a <= 25:
            return self.translateNum(num//100) + self.translateNum(num//10)
        else:
            return self.translateNum(num//10)

3.2文字列遍歴
もちろん右から左へ遍歴することもできますが、結果は同じです.

class Solution:
    def translateNum(self, num: int) -> int:
        s = str(num)
        a = b = 1
        for i in range(2, len(s) + 1):
            tmp = s[i - 2:i]
            c = a + b if "10" <= tmp <= "25" else a
            b = a
            a = c
        return a

3.3数字の余剰を求める
数字で余分を求めてより少ない空間を使う.

class Solution:
    def translateNum(self, num: int) -> int:
        a = b = 1
        y = num % 10
        while num != 0:
            num //= 10
            x = num % 10
            tmp = 10 * x + y
            c = a + b if 10 <= tmp <= 25 else a
            a, b = c, a
            y = x
        return a

4.まとめ
通常、数字に関するアルゴリズムに出会ったら、余を求めたり、商を求めたりする操作が望ましいが、文字列に変換して処理することはできない.
5.参考文献
[1]剣指offer叢書[2]剣指Offer-有名企業の面接官が典型的なプログラミング問題を詳しく話す