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

zltzlt

今天的题目：

给定正整数 n，返回小于等于 n 且具有至少 1 位重复数字的正整数的个数。

示例 1：

输入：20
输出：1
解释：具有至少 1 位重复数字的正数（<= 20）只有 11。

示例 2：

输入：100
输出：10
解释：具有至少 1 位重复数字的正数（<= 100）有 11，22，33，44，55，66，77，88，99 和 100。

示例 3：

输入：1000
输出：262

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

TJBEST

2020-1-18 21:32:13

又写了一个长代码，不知道速率如何

1. def fun309(n):
   
2.     def splitNum(n):
   
3.         res = []
   
4.         while n:
   
5.             re = n % 10
   
6.             n = n // 10
   
7.             res.append(re)
   
8.         return list(reversed(res))
   
9.     def ByNine(index):
   
10.         res = 9
    
11.         for k in range(0,index):
    
12.            res= res * (9 - k)
    
13.         return res
    
14.     def MulByall(start,end):#start >= end <表示 到个位了
    
15.         res = 1
    
16.         for i in range(end , start + 1):
    
17.             res = res * i
    
18.         return res
    
19.     def firstNum(num,arr):
    
20.         res = 0
    
21.         for i in range(0,num):
    
22.             if i not in arr:
    
23.                 res = res + 1
    
24.         return res
    
25.             
    
26. 
    
27.     NotHave_Nine = [9]#常数 <= 999..999 的不重复个数
    
28.     for i in range(1,10):
    
29.         temp = NotHave_Nine[len(NotHave_Nine) - 1] + ByNine(i)
    
30.         NotHave_Nine.append(temp)
    
31.     numList = splitNum(n)
    
32.     N = len(numList)#位数
    
33.     if N == 1:
    
34.         return 0
    
35.     if N >= 11:
    
36.         return n - NotHave_Nine[9]
    
37.     arr = []#记录已处理的数
    
38.     isnot = NotHave_Nine[N - 2]
    
39.    
    
40.     if numList[0] == 1:
    
41.         arr.append(1)
    
42.     else:
    
43.         isnot += (numList[0] - 1) * MulByall(9,11 - N)
    
44.         arr.append(numList[0])
    
45.    
    
46.     state = 1
    
47.     for i in range(1,N - 1):
    
48.         temp = numList[i]
    
49.         isnot += firstNum(temp,arr) * MulByall(9 - i,11 - N)
    
50.         if temp in arr:
    
51.             state = 0
    
52.             break
    
53.         else:
    
54.             arr.append(temp)
    
55.     if state == 1:
    
56.         isnot += firstNum(numList[N - 1] + 1,arr)
    
57.     else:
    
58.         pass  
    
59.     return n - isnot

复制代码

   

跳转到最佳答案楼层

Croper

题目少写了俩字儿吧

给定正整数 n，返回小于等于 n 且具有至少 1 位重复数字的正整数

应该是正整数的个数。。不然我直接return一个11就行了。。。。

冬雪雪冬

1. def func(n):
   
2.     return sum([1 for i in range(11, n + 1) if len(set(str(i))) < len(str(i))])

复制代码

zltzlt

冬雪雪冬 发表于 2020-1-18 21:25

输入 750000 超时

TJBEST

又写了一个长代码，不知道速率如何

1. def fun309(n):
   
2.     def splitNum(n):
   
3.         res = []
   
4.         while n:
   
5.             re = n % 10
   
6.             n = n // 10
   
7.             res.append(re)
   
8.         return list(reversed(res))
   
9.     def ByNine(index):
   
10.         res = 9
    
11.         for k in range(0,index):
    
12.            res= res * (9 - k)
    
13.         return res
    
14.     def MulByall(start,end):#start >= end <表示 到个位了
    
15.         res = 1
    
16.         for i in range(end , start + 1):
    
17.             res = res * i
    
18.         return res
    
19.     def firstNum(num,arr):
    
20.         res = 0
    
21.         for i in range(0,num):
    
22.             if i not in arr:
    
23.                 res = res + 1
    
24.         return res
    
25.             
    
26. 
    
27.     NotHave_Nine = [9]#常数 <= 999..999 的不重复个数
    
28.     for i in range(1,10):
    
29.         temp = NotHave_Nine[len(NotHave_Nine) - 1] + ByNine(i)
    
30.         NotHave_Nine.append(temp)
    
31.     numList = splitNum(n)
    
32.     N = len(numList)#位数
    
33.     if N == 1:
    
34.         return 0
    
35.     if N >= 11:
    
36.         return n - NotHave_Nine[9]
    
37.     arr = []#记录已处理的数
    
38.     isnot = NotHave_Nine[N - 2]
    
39.    
    
40.     if numList[0] == 1:
    
41.         arr.append(1)
    
42.     else:
    
43.         isnot += (numList[0] - 1) * MulByall(9,11 - N)
    
44.         arr.append(numList[0])
    
45.    
    
46.     state = 1
    
47.     for i in range(1,N - 1):
    
48.         temp = numList[i]
    
49.         isnot += firstNum(temp,arr) * MulByall(9 - i,11 - N)
    
50.         if temp in arr:
    
51.             state = 0
    
52.             break
    
53.         else:
    
54.             arr.append(temp)
    
55.     if state == 1:
    
56.         isnot += firstNum(numList[N - 1] + 1,arr)
    
57.     else:
    
58.         pass  
    
59.     return n - isnot

复制代码

   

伏惜寒

1. a = int(input("输入:"))
   
2. num = 0
   
3. for i in range(a+1):
   
4.     b = list(str(i))
   
5.     for e in b:
   
6.         if b.count(e) > 1:
   
7.             num += 1
   
8.             break
   
9.             
   
10. print(num)
    

复制代码

zltzlt

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

输入 750000 超时

阴阳神万物主

楼主最近高产呐

wanting-for

1. count=0
   
2. for i in range(100+1):
   
3.     if len(str(i))>len(set(str(i))):
   
4.         count+=1
   
5. print(count)
   

复制代码

直接用set这个特使的函数，完美

Croper

今天的有点绕啊

1. def func(n):
   
2.     n+=1
   
3.     l=[0]
   
4.     for i in range(len(str(n))-2):
   
5.         l.append(l[-1]*10+(9*10**i-l[-1])*(i+1))
   
6.     prev=sum(l)
   
7. 
   
8.     l=[int(c) for c in str(n)]
   
9.     n=l[0]-1
   
10.     p,q=0,n
    
11.     same_digit=False
    
12.     for i in range(1,len(l)):
    
13.         n=n*10+l[i]
    
14.         t1=p*10+q*i
    
15.         t2=n-t1
    
16.         if same_digit:
    
17.             t2-=l[i]
    
18.             t1+=l[i]
    
19.         else:
    
20.             for j in l[:i]:
    
21.                 if j<l[i]:
    
22.                     t2-=1
    
23.                     t1+=1
    
24.         if l[i] in l[:i]:
    
25.             same_digit=True
    
26.         p,q=t1,t2
    
27.     return p+prev

复制代码

深海中燃烧

初学Python 不会什么高级方法
大数超时的问题暂时没有什么优化思路

1. n = int(input("Input N: "))
   
2. cnt = 0
   
3. passthisnum = False
   
4. 
   
5. #检查 11 ~ n 范围内的整数
   
6. for i in range(11,n+1):
   
7.     str_i = str(i)
   
8.     #对当前第 i 个整数的每一位进行判断
   
9.     for j in range(len(str_i)):
   
10.         if passthisnum == True :
    
11.             passthisnum = False
    
12.             break
    
13.         temp = str_i[j]
    
14.         #判断第 j 位后面是否有与第 j 位相同的数字
    
15.         for k in range(j+1,len(str_i)):
    
16.             if  temp == str_i[k]:
    
17.                 cnt += 1
    
18.                 #如果有相同则需要标记跳过此数
    
19.                 #否则在处理如 999、10000
    
20.                 #这种三个相同数字时会产生重复计数
    
21.                 passthisnum = True
    
22.                 #print(str_i)
    
23.                 break
    
24. print("cnt:",cnt)
    

复制代码

深海中燃烧

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

Input N: 750000
cnt: 618390
不知道答案对不

godfishs

回帖的时候怎么可以贴上好看的代码块啊？

godfishs

def fun309(x):
    if x<=10:
        return 0
    re = 0
    for i in range(11,x+1):
        k = str(i)
        if len(set(k)) < len(k):
            re += 1
    return re

if __name__ == '__main__':
    print(fun309(1000000))

九黎34

我还是先好好学习前面的，在不久的以后，我就可以答题了，

伏惜寒

zltzlt 发表于 2020-1-18 21:45
输入 750000 超时

没有超时啊？
我运行了很多次都是1秒到2秒的时间。

hrp

伏惜寒 发表于 2020-1-19 14:53
没有超时啊？
我运行了很多次都是1秒到2秒的时间。

超时应该是超过题目限定的时间，而不是用了多少时间

伏惜寒

hrp 发表于 2020-1-19 14:56
超时应该是超过题目限定的时间，而不是用了多少时间

题目没给限定时间啊

wanting-for

伏惜寒 发表于 2020-1-19 14:57
题目没给限定时间啊

这个是拿到指定的平台来判定的

TJBEST

楼主写完了，在五楼，您测试一下