当前位置:网站首页>Leetcode skimming -- count the number of numbers with different numbers 357 medium
Leetcode skimming -- count the number of numbers with different numbers 357 medium
2022-07-02 15:28:00 【Fire breathing dragon and water arrow turtle】
The train of thought and source code of counting the number of different numbers
The topic of counting the number of different figures is shown in the figure below , This problem belongs to mathematics and backtracking type , It mainly examines the use of backtracking methods and the understanding of mathematical ideas of the topic . The title of this article, the author thought 2 Methods , They are permutation and combination method and recursive method , The permutation and combination method uses Java Compiling , The recursive method uses Python Compiling , Of course, this may not be the optimal solution , I also hope you guys can give a faster algorithm .
I think this problem can be solved by using the idea of permutation and combination , First, judge whether the number is 0 perhaps 1, If it is 0 Just go back to 1; If it is 1 Just go back to 10, Then start initializing the result variables and subscript variables . Start traversing the loop , Record the temporary arrangement result with the current subscript result , Then add it to the result variable , Until the end of the traversal returns the final result . Then according to this idea, our Java The code is as follows :
# Fire breathing dragon and water arrow turtle
class Solution {
public int countNumbersWithUniqueDigits(int n) {
if (n == 0) {
return 1;
}
if (n == 1) {
return 10;
}
int resFinal = 10;
int ind = 9;
for (int jr = 0; jr < n - 1; jr++) {
ind = ind * (9 - jr);
resFinal = resFinal + ind;
}
return resFinal;
}
}
obviously , We can see that the effect of the permutation row combination method is ok , At the same time, we can also use the recursive method to solve . First, initialize a list , And the assignment 9 individual 0 Is the initialization result . Let the first list element be 1, The second list element is 10, Then start traversing the loop from the second element , After deduction and summary, use mathematical recurrence formula to calculate , Get the traversal result and return the element of the last list . So according to this idea, we can solve , Here is Python Code :
# Fire breathing dragon and water arrow turtle
class Solution:
def countNumbersWithUniqueDigits(self, n: int) -> int:
vc = []
for ij in range(9):
vc.append(0)
vc[0] = 1
vc[1] = 10
for jr in range(2,9):
vc[jr] = vc[jr-1] + (vc[jr-1]-vc[jr-2])*(10-(jr-1))
return vc[n]
As a result Java The efficiency of the permutation and combination method of version is good , and Python The speed of the recursive method of version is also ok , But there should be more ways to further speed up , I hope friends can give me more advice , Thank you very much .
边栏推荐
猜你喜欢
【网络安全】网络资产收集
Beijing rental data analysis
I made an istio workshop. This is the first introduction
Build your own semantic segmentation platform deeplabv3+
19_Redis_宕机后手动配置主机
21_Redis_浅析Redis缓存穿透和雪崩
Set set you don't know
yolo格式数据集处理(xml转txt)
Solve the problem that El radio group cannot be edited after echo
学习使用php将时间戳转换为大写日期的方法代码示例
随机推荐
10_ Redis_ geospatial_ command
kibana 基础操作
11_Redis_Hyperloglog_命令
16_ Redis_ Redis persistence
05_ queue
如何用 Sysbench 测试 TiDB
Learn the method code of using PHP to realize the conversion of Gregorian calendar and lunar calendar
NBA player analysis
Sharp tool SPL for post SQL calculation
Tidb cross data center deployment topology
13_ Redis_ affair
Equipped with Ti am62x processor, Feiling fet6254-c core board is launched!
Table responsive layout tips
. Net again! Happy 20th birthday
LeetCode刷题——去除重复字母#316#Medium
Kibana basic operation
使用 TiUP 部署 TiDB 集群
Points clés de l'examen de principe de compilation pour l'année scolaire 2021 - 2022 [Université chinoise d'outre - mer]
Force deduction solution summarizes the lucky numbers in 1380 matrix
数据分析常见的英文缩写(一)