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

fan1993423

1. from scipy.special import perm
   
2. def count1(length):
   
3.     num=0
   
4.     for i in range(3,length):
   
5.         num+=9*10**(i-1)-(perm(10,i)-perm(9,(i-1)))
   
6.     return num+10
   
7. def count2(n,length):
   
8.     num=0
   
9.     num+=(int(str(n)[0])-1)*perm(9,length-1)
   
10.     i=1
    
11.     while i<=length-2:
    
12.         k=sorted(set(str(n)[:i+1])).index(str(n)[i])
    
13.         num+=(int(str(n)[i])-k)*perm(9-i,length-i-1)
    
14.         i+=1
    
15.     last=n%10-sorted(set(str(n))).index(str(n)[-1])+1
    
16.     return n-10**(length-1)-num-last
    
17. def fun309(n):
    
18.     length=len(str(n))
    
19.     if n<=10:return 0
    
20.     elif length==2:
    
21.         if str(n)[0]<=str(n)[1]:
    
22.             return int(str(n)[0])
    
23.         else:
    
24.             return int(str(n)[0])-1
    
25.     else:
    
26.         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那里出了点错误，已改

1. from scipy.special import perm
   
2. def count1(length):
   
3.     num=0
   
4.     for i in range(3,length):
   
5.         num+=9*10**(i-1)-(perm(10,i)-perm(9,(i-1)))
   
6.     return num+10
   
7. def count2(n,length):
   
8.     num=0
   
9.     num+=(int(str(n)[0])-1)*perm(9,length-1)
   
10.     i=1
    
11.     while i<=length-2:
    
12.         k=sorted(set(str(n)[:i+1])).index(str(n)[i])
    
13.         num+=(int(str(n)[i])-k)*perm(9-i,length-i-1)
    
14.         i+=1
    
15.     last=n%10-sorted(set(str(n))).index(str(n)[-1])
    
16.     return n-10**(length-1)-num-last
    
17. def fun309(n):
    
18.     length=len(str(n))
    
19.     if n<=10:return 0
    
20.     elif length==2:
    
21.         if str(n)[0]<=str(n)[1]:
    
22.             return int(str(n)[0])
    
23.         else:
    
24.             return int(str(n)[0])-1
    
25.     else:
    
26.         return int(count1(length)+count2(n,length))

复制代码

zltzlt

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

解答错误

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

fan1993423

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

1. from math import factorial
   
2. def perm(a,b):
   
3.     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

1. def solve(A:int):
   
2.     count=0
   
3.     if A<=0:
   
4.         return 0
   
5.     else:
   
6.         for i in range(A+1):
   
7.             if len(str(i))>len(set(str(i))):
   
8.                 count+=1
   
9.     return count

复制代码

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

wanting-for

1. def solve(A:int):
   
2.     count=0
   
3.     for i in range(A):
   
4.         m = str(i)
   
5.         if len(m)>len(set(m)):
   
6.             count+=1
   
7.     return count

复制代码

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

fan1993423

1. from scipy.special import perm
   
2. from string import digits
   
3. def count1(length):
   
4.     num=0
   
5.     for i in range(3,length):
   
6.         num+=9*10**(i-1)-(perm(10,i)-perm(9,(i-1)))
   
7.     return num+10
   
8. def count2(n,length):
   
9.     num=0
   
10.     num+=(int(str(n)[0])-1)*perm(9,length-1)
    
11.     i=1
    
12.     while i<=length-2:
    
13.         k=sorted(set(str(n)[:i+1])).index(str(n)[i])
    
14.         num+=(int(str(n)[i])-k)*perm(9-i,length-i-1)
    
15.         i+=1
    
16.     if len(str(n)[:-1])==len(set(str(n)[:-1])):
    
17.         last_num=int(str(n)[-1])
    
18.         digit=digits[:last_num+1]
    
19.         for i in str(n)[:-1]:
    
20.             digit=digit.replace(i,'')
    
21.         last=len(digit)
    
22.     else:last=0
    
23.     return n-10**(length-1)-num-last
    
24. def fun309(n):
    
25.     length=len(str(n))
    
26.     if n<=10:return 0
    
27.     elif length==2:
    
28.         if str(n)[0]<=str(n)[1]:
    
29.             return int(str(n)[0])
    
30.         else:
    
31.             return int(str(n)[0])-1
    
32.     else:
    
33.         return int(count1(length)+count2(n,length))

复制代码

@zlzlt

newbison

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

1. def duplicate_num(n):
   
2.     return True if len(str(n)) > len(set(str(n))) else False  
   
3. 
   
4. def func309(n):
   
5.     if n <= 10:
   
6.         return 0
   
7.     else:
   
8.         res = 0
   
9.         for i in range(10, n+1):
   
10.             if duplicate_num(i) == True:
    
11.                 res += 1
    
12.         return res

复制代码

fan1993423

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