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

fan1993423

from scipy.special import perm
def count1(length):
    num=0
    for i in range(3,length):
        num+=9*10**(i-1)-(perm(10,i)-perm(9,(i-1)))
    return num+10
def count2(n,length):
    num=0
    num+=(int(str(n)[0])-1)*perm(9,length-1)
    i=1
    while i<=length-2:
        k=sorted(set(str(n)[:i+1])).index(str(n)[i])
        num+=(int(str(n)[i])-k)*perm(9-i,length-i-1)
        i+=1
    last=n%10-sorted(set(str(n))).index(str(n)[-1])+1
    return n-10**(length-1)-num-last
def fun309(n):
    length=len(str(n))
    if n<=10:return 0
    elif length==2:
        if str(n)[0]<=str(n)[1]:
            return int(str(n)[0])
        else:
            return int(str(n)[0])-1
    else:
        return int(count1(length)+count2(n,length))

fan1993423

伏惜寒 发表于 2020-1-18 21:43

你输入10000000，你看你程序什么时候能出结果

Croper

我觉得python不太适合做这种算法方面的东西。。。，
内置的东西底层是C的，而自己写的东西还要经解释器过一遍。。速度差距太大了。。

很多时候写的一大串但是时间复杂度很低的代码，
打不过别人用内置函数但是时间复杂度高一个数量级的代码。。。

zltzlt

wanting-for 发表于 2020-1-18 22:55
直接用set这个特使的函数，完美

请编写一个函数

zltzlt

Croper 发表于 2020-1-19 21:33
我觉得python不太适合做这种算法方面的东西。。。，
内置的东西底层是C的，而自己写的东西还要经解释器过 ...

有时候内置函数其实比自己写的代码还要慢很多，比如 map() 和 filter()

zltzlt

深海中燃烧 发表于 2020-1-19 01:27
初学Python 不会什么高级方法
大数超时的问题暂时没有什么优化思路

输入 500000 超时

zltzlt

godfishs 发表于 2020-1-19 09:32
def fun309(x):
    if x

zltzlt

godfishs 发表于 2020-1-19 09:32
def fun309(x):
    if x

输入 750000 超时

zltzlt

fan1993423 发表于 2020-1-19 19:22

解答错误

输入：100
输出：9
预期结果：10

fan1993423

zltzlt 发表于 2020-1-19 21:55
解答错误

输入：100

last那里出了点错误，已改

from scipy.special import perm
def count1(length):
    num=0
    for i in range(3,length):
        num+=9*10**(i-1)-(perm(10,i)-perm(9,(i-1)))
    return num+10
def count2(n,length):
    num=0
    num+=(int(str(n)[0])-1)*perm(9,length-1)
    i=1
    while i<=length-2:
        k=sorted(set(str(n)[:i+1])).index(str(n)[i])
        num+=(int(str(n)[i])-k)*perm(9-i,length-i-1)
        i+=1
    last=n%10-sorted(set(str(n))).index(str(n)[-1])
    return n-10**(length-1)-num-last
def fun309(n):
    length=len(str(n))
    if n<=10:return 0
    elif length==2:
        if str(n)[0]<=str(n)[1]:
            return int(str(n)[0])
        else:
            return int(str(n)[0])-1
    else:
        return int(count1(length)+count2(n,length))

zltzlt

fan1993423 发表于 2020-1-19 22:06
last那里出了点错误，已改

解答错误

输入：102
输出：12
预期结果：11

fan1993423

那个perm如果不能使用scipy，那就用我自己写的定义式吧

from math import factorial
def perm(a,b):
    return factorial(a)//factorial(a-b)

zltzlt

fan1993423 发表于 2020-1-19 22:08
那个perm如果不能使用scipy，那就用我自己写的定义式吧

嗯，还是会错

fan1993423

zltzlt 发表于 2020-1-19 22:10
嗯，还是会错

我再想哈，大数据好没问题，小细节好像反而被忽略了

zltzlt

fan1993423 发表于 2020-1-19 22:13
我再想哈，大数据好没问题，小细节好像反而被忽略了

wanting-for

def solve(A:int):
    count=0
    if A<=0:
        return 0
    else:
        for i in range(A+1):
            if len(str(i))>len(set(str(i))):
                count+=1
    return count

我不知道咋回事没法进行回复了

wanting-for

def solve(A:int):
    count=0
    for i in range(A):
        m = str(i)
        if len(m)>len(set(m)):
            count+=1
    return count

测试了一下，能减少接近0.2S

fan1993423

from scipy.special import perm
from string import digits
def count1(length):
    num=0
    for i in range(3,length):
        num+=9*10**(i-1)-(perm(10,i)-perm(9,(i-1)))
    return num+10
def count2(n,length):
    num=0
    num+=(int(str(n)[0])-1)*perm(9,length-1)
    i=1
    while i<=length-2:
        k=sorted(set(str(n)[:i+1])).index(str(n)[i])
        num+=(int(str(n)[i])-k)*perm(9-i,length-i-1)
        i+=1
    if len(str(n)[:-1])==len(set(str(n)[:-1])):
        last_num=int(str(n)[-1])
        digit=digits[:last_num+1]
        for i in str(n)[:-1]:
            digit=digit.replace(i,'')
        last=len(digit)
    else:last=0
    return n-10**(length-1)-num-last
def fun309(n):
    length=len(str(n))
    if n<=10:return 0
    elif length==2:
        if str(n)[0]<=str(n)[1]:
            return int(str(n)[0])
        else:
            return int(str(n)[0])-1
    else:
        return int(count1(length)+count2(n,length))

@zlzlt

newbison

初学者代码，估计超时了~~~

def duplicate_num(n):
    return True if len(str(n)) > len(set(str(n))) else False  

def func309(n):
    if n <= 10:
        return 0
    else:
        res = 0
        for i in range(10, n+1):
            if duplicate_num(i) == True:
                res += 1
        return res

fan1993423

我这个测一下对不对，@zlzlt