[已解决]Python：每日一题 346

zltzlt

今天的题目：

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。

一个数字可能有多个翻译。实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例 1：

输入：12258
输出：5
解释：12258 有 5 种不同的翻译，分别是 "bccfi", "bwfi", "bczi", "mcfi" 和 "mzi"

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

Unicorn#

2020-3-7 23:49:20

basis = [str(i) for i in range(26)]
def solve(s):
    if type(s) is int:
        s = str(s)
    if len(s) <= 1:
        return 1
    m = len(s)//2
    l = solve(s[:m])
    r = solve(s[m:])
    if s[m-1]+s[m] in basis:
        e = solve(s[:m-1])*solve(s[m+1:])
    else:
        e = 0
    return l*r + e

跳转到最佳答案楼层

Unicorn#

basis = [str(i) for i in range(26)]
def solve(s):
    if type(s) is int:
        s = str(s)
    if len(s) <= 1:
        return 1
    m = len(s)//2
    l = solve(s[:m])
    r = solve(s[m:])
    if s[m-1]+s[m] in basis:
        e = solve(s[:m-1])*solve(s[m+1:])
    else:
        e = 0
    return l*r + e

fan1993423

Unicorn# 发表于 2020-3-7 23:49

大佬，这是你自己想的吗?

flamezyy

def switch(num):  
    num = str(num)
    length = len(num)
    if length < 3:
        if int(num) in range(10,26):
            return 2 
        else:
            return 1
    elif int(num[:2]) in range(10,26):
        return(switch(num[1:]) + switch(num[2:]))      
    else:
        return(switch(num[1:]))

ouyunfu

def f346(n:int)->int:
    s=str(n)
    global res
    res=0
    def f(s):
        global res
        if len(s)==1:
            res+=1
        elif len(s)==2:
            res+=1
            if 10<=int(s)<=25:
                res+=1
        else:
            f(s[1:])
            if 10<=int(s[0:2])<=25:
                f(s[2:])
        return res 
    return f(s)

tzczjh

def solve(num):
    if not isinstance(num, int):
        return None
    
    s = str(num)
    ls = len(s)
    dp = [[0] * 2 for i in range(ls)]
    # dp[i][0]表示从左到右第i(下标)位如果不和前一位结合 有多少种可能
    # dp[i][1]表示从左到右第i(下标)位如果和前一位结合 有多少种可能   
    # 对于dp[i][0]无论前面状态如何 每一种dp[i - 1]*的状态都会有dp[i][0]的状态
    # 所以dp[i][0] = dp[i - 1][0] + dp[i - 1][1]
    # 对于dp[i][1]如果与前一位可以结合 此时前一位不能和更前一位结合 故 dp[i][1] = dp[i - 1][0]
    # 如果当前位与前一位无法结合 则dp[i][1] = 0   
    # i=0时无法与前面结合 dp[0][0] = 1 dp[0][1] = 0
    # 结果为dp[ls-1][0] + dp[ls - 1][1]
    dp[0][0] = 1
    for i in range(1, ls):
        dp[i][0] = dp[i - 1][0] + dp[i - 1][1]
        if 0 <= int(s[i - 1] + s[i]) < 26:
            dp[i][1] = dp[i-1][0]
    return dp[ls - 1][0] + dp[ls - 1][1]

塔利班

def f346(x):
    s=str(x)
    l=len(s)
    t=[1]+[0]*l
    t[1]=1
    b=[str(e) for e in range(10,26)]
    for i in range(2,l+1):
        t[i]=t[i-1]+(s[i-2:i] in b)*t[i-2]
    return t[l]

Croper

def func346(n):
    l=[1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189, 2880067194370816120, 4660046610375530309, 7540113804746346429, 12200160415121876738, 19740274219868223167, 31940434634990099905, 51680708854858323072, 83621143489848422977, 135301852344706746049, 218922995834555169026, 354224848179261915075, 573147844013817084101]
    def fib(n):
        while len(l)<n+1:
            l.append(l[-1]+l[-2])
        return l[n]

    b=[str(n) for n in range(10,26)]
    t,sz=0,str(n)
    ret=1
    for i in range(1,len(sz)+1):
        if i==len(sz) or not sz[i-1:i+1] in b:
            ret*=fib(t)
            t=0
        else:
            t+=1
    return ret

寻风

硬给玩成了数学题，希望不要错

from math import sqrt
def Feb(n):
    a=(1/sqrt(5))*((((1+sqrt(5))/2)**(n+1))-(((1-sqrt(5))/2)**(n+1)))
    return int(a)
def fun346():
    num = input()
    list1=[0]
    end = 1
    l = len(num)
    for i in range(l-1):
        if 25 < int(num[i:i+2]):
            list1.append(i+1)
    list1.append(l)
    for i in range(len(list1)-1):
        a=list1[i+1]-list1[i]
        end*=Feb(a)
    print(end)

寻风

Croper 发表于 2020-3-8 10:43

斐波那契数列，我们撞思路了

Unicorn#

fan1993423 发表于 2020-3-8 00:03
大佬，这是你自己想的吗?

是
不是大佬...

Windypper

希望沒bug

basis = [str(i) for i in range(10, 26)]
def F346(num):
    n = str(num)
    count = 1
    if len(n) <=3:
        for i in range(len(n)-1):
            if n[i:i + 2] in basis:
                count += 1
        return count
    else:
        for i in range(len(n) - 1):
            if n[i:i + 2] in basis:
                count += F346(n[i + 2:])
        return count

546623863

def fun346(num : int):
    s = str(num)
    Pway = 0
    Cway = 1
    Pnum = ""
    for Cnum in s:
        tmp = Pway
        Pway = Cway
        Cway = int(Cnum > "0") * Cway + (9 < int(Pnum + Cnum) < 26) * tmp
        Pnum = Cnum
    return Cway

又是一道之前刷题的时候做过的题。。。。。

TJBEST

大家都这么厉害啊，我没办法 只能暴力一点了 当然我这里默认 连续1和2的个数不能太大 否则 递归就超了

def fun346(num):
    def ZeroSplit(num):
        if num in fenCount:
            return fenCount[num]
        else:
            if num < 0:
                return 0
            elif num == 0:
                fenCount[0]=1
            else:
                fenCount[num] = ZeroSplit(num-1)+ZeroSplit(num-2)
            return fenCount[num]

    string = str(num)
    sample = [['1','2'],['0','3','4','5'],['6','7','8','9']]
    fenCount = {}
    
    status = []
    many = []
    for pre in range(0,3):
        if string[0] in sample[pre]:
            break
    count = 0
    for each in string:
        if each in sample[pre]:
            count += 1
        else:
            status.append(pre)
            many.append(count)
            for pre in range(0,3):
                if each in sample[pre]:
                    break
            count = 1
    else:
        status.append(pre)
        many.append(count)
    if 0 not in status:
        return 1
    result = 1
    M = len(status)
    start = status.index(0)
    first = start
    for index in range(start,M):
        if index < M - 1:
            if status[index + 1] == 0:
                #进行计算
                special = sum(many[:(first+1)]) - 1
                if string[special] == '1':
                    result = result * (ZeroSplit(many[first]-2)+2*ZeroSplit(many[first]-1))
                else:
                    if status[first + 1] == 1:
                        result = result * (ZeroSplit(many[first]-2)+2*ZeroSplit(many[first]-1))
                    else:
                        result = result * ZeroSplit(many[first])
                first = index + 1
            else:
                pass
        else:
            if status[index] == 0:
                result = result * ZeroSplit(many[-1])
            else:
                special = sum(many[:(first+1)]) - 1
                if string[special] == '1':
                    result = result * (ZeroSplit(many[first]-2)+2*ZeroSplit(many[first]-1))
                else:
                    if status[first + 1] == 1:
                        result = result * (ZeroSplit(many[first]-2)+2*ZeroSplit(many[first]-1))
                    else:
                        result = result * ZeroSplit(many[first])
    return result

Geoffreylee

# 构造斐波那契数列
def fib(n):
    a, b = 0, 1
    while True:
        a, b, n = b, a+b, n-1
        if n == 0:
            return b


def f_346(string: str):
    over_25_count = 0
    # 遍历相邻两个字符组成的数字，记录有多少个数字大于25
    for i in range(len(string)-1):
        over_25_count += 1 if int(string[i:i+2]) > 25 else over_25_count
    # 返回string长度减over_25_count对应的斐波那契数
    return fib(len(string)-over_25_count)

print(f_346('12258'))

蒋博文

请求楼主测试（还好我做过 ）

def fun346(s):
    if isinstance(s,int):
        s=str(s)
    a = 0
    b = 1
    for i in range(len(s)):
        if s[i - 1] == '1' or s[i - 1] == '2' and s[i] < '6':
            c = a + b
        else:
            c = b
        a = b
        b = c
    return c

蒋博文

楼主，以后能不能多举一点例子，方便检查

suchocolate

蒋博文 发表于 2020-3-8 20:09
请求楼主测试（还好我做过 ）

hello，可以写一下说明吗，我学习学习。

蒋博文

suchocolate 发表于 2020-3-8 20:29
hello，可以写一下说明吗，我学习学习。

def fun346(s):
    if isinstance(s,int):
        s=str(s)
    a = 0
    b = 1
    for i in range(len(s)):
        if s[i - 1] == '1' or s[i - 1] == '2' and s[i] < '6':# 判断是否可以和前面的数字合并
            c = a + b
        else:
            c = b
        a = b
        b = c
    return c

其实只要用斐波那契数列的思想来做就可以了。

蒋博文

suchocolate 发表于 2020-3-8 20:29
hello，可以写一下说明吗，我学习学习。

https://baike.so.com/doc/5389470-5626050.html
这里面有斐波那契数列的公式和思想讲解，看完后就应该明白了