建立购物网站的目的,搭建 wordpress 简书,手机qq空间登录网页入口,扬中seo编写一个方法#xff0c;计算从 0 到 n (含 n) 中数字 2 出现的次数。 示例: 输入: 25 输出: 9 解释: (2, 12, 20, 21, 22, 23, 24, 25)(注意 22 应该算作两次) 该问题用的方法数数组dp#xff0c;首先我通过总结规律写出了相关的code。使用一个dp数组记录10i10^i10i以内会出…编写一个方法计算从 0 到 n (含 n) 中数字 2 出现的次数。 示例: 输入: 25 输出: 9 解释: (2, 12, 20, 21, 22, 23, 24, 25)(注意 22 应该算作两次) 该问题用的方法数数组dp首先我通过总结规律写出了相关的code。使用一个dp数组记录10i10^i10i以内会出现多少个2再根据我们的数字进行处理就可以了。 需要知道的是10i10^i10i和10i−110^{i-1}10i−1内出现的2个数的转化公式如下 dp[i]dp[i−1]∗1010i−1dp[i] dp[i-1]*1010^{i-1}dp[i]dp[i−1]∗1010i−1
class Solution:def numberOf2sInRange(self, n: int) - int:if n 2: return 0length len(str(n))dp [0 for _ in range(length)]for i in range(1,length):dp[i] dp[i-1]*1010**(i-1)res 0string str(n)for i in range(length-1,-1,-1):num int(string[length-1-i])res num*dp[i]n n %(10**(i))if num 2:res (n1)elif num 2:res 10**(i)return res 但是写出该方法需要找规律在面试的时候可能推理整个规律的细节不是很现实。所以我们需要学习问题的经典模板。 以下是回溯的版本但是回溯过于耗时了我们还是要使用一些内存来减少迭代的次数。
class Solution:def numberOf2sInRange(self, n: int) - int:if n 2: return 0string str(n)length len(string)def numdp(index,count,isLimit):if index length:return countres 0num int(string[index]) if isLimit else 9for i in range(num1):res numdp(index1,count(i2),isLimit and (i num))return resreturn numdp(0,0,True)来源力扣LeetCode 链接https://leetcode.cn/problems/number-of-2s-in-range-lcci 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
