当前位置:网站首页>leetcode--357. Count the number of different figures
leetcode--357. Count the number of different figures
2022-04-23 14:03:00 【Amelia who loves learning】
-
Give you an integer
n
, Count and return numbers with different numbersx
The number of , among0 <= x < 10n
. 1 -
Example :
# Example 1
Input :n = 2
Output :91
explain : The answer should be to remove 11、22、33、44、55、66、77、88、99 Outside , stay 0 ≤ x < 100 All numbers in the range .
# Example 2
Input :n = 0
Output :1
-
Tips :
0 <= n <= 8
-
Ideas :
Recursion , First set the exit of recursion , if n Reduced to 0 了 , return 1
The loop logic is :
f(0) = 1
f(1) = 9 + f(0)
f(2) = 9 * 9 + f(1)
f(3) = 9 * 9 * 8 + f(2)
…
Set a value to 9, Then set a loop in the input value from 1 Traversing n, Analysis shows that to define a 9 And another one. 9 unchanged , Then the sum must be equal to 10, Then the realization of the function is as follows: solution 1
Returns the of the previous value ans Plus the recursion of the function
- Solution 1 – recursive :
class Solution:
def countNumbersWithUniqueDigits(self, n: int) -> int:
if n == 0:
return 1
ans = 9
for i in range(1, n):
ans *= (10 - i)
return ans + self.countNumbersWithUniqueDigits(n - 1)
- Ideas :
Two functions are set , First of all to see cntpo, This function returns the sum of unqualified numbers between every few digits
countNumbersWithUniqueDigits The function is to add up the sum of each unqualified number , Then return a total minus the unqualified number , That is, the number of qualified
- Solution 2 – Violence solution :
class Solution:
def countNumbersWithUniqueDigits(self, n):
s = 0
for i in range(1, n + 1):
j = self.cntpo(i)
s += j
s_sum = pow(10, n)
return s_sum - s
def cntpo(self, n):
cnt = 0
for i in range(pow(10, n-1), pow(10, n)):
for j in str(i):
if str(i).count(j) > 1:
cnt += 1
break
return cnt
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/count-numbers-with-unique-digits/ ︎
版权声明
本文为[Amelia who loves learning]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204231341317327.html
边栏推荐
猜你喜欢
随机推荐
groutine
SQL数据库
村上春树 --《当我谈跑步时,我谈些什么》句子摘录
Interesting talk about network protocol
What is the difference between blue-green publishing, rolling publishing and gray publishing?
多线程 @Async 线程池
Problems encountered in the project (V) understanding of operating excel interface poi
Analysis and understanding of atomicintegerarray source code
Qt Designer怎样加入资源文件
蓝绿发布、滚动发布、灰度发布,有什么区别?
基础知识学习记录
linux安装mysql后修改密码
Record a strange bug: component copy after cache component jump
分库分表 & ShardingSphere
基于Ocelot的gRpc网关
Pytorch 经典卷积神经网络 LeNet
关于stream流,浅记一下------
[VMware] address of VMware Tools
程序编译调试学习记录
Restful WebService和gSoap WebService的本质区别