leetcode 面试题 17.06. 2出现的次数

编写一个方法，计算从 0 到 n (含 n) 中数字 2 出现的次数。

示例:

输入: 25
输出: 9
解释: (2, 12, 20, 21, 22, 23, 24, 25)(注意 22 应该算作两次)

该问题用的方法数数组dp，首先我通过总结规律写出了相关的code。使用一个dp数组记录$10^i$以内会出现多少个2，再根据我们的数字进行处理就可以了。
需要知道的是，$10^i$和$10^{i-1}$内出现的2个数的转化公式如下
$dp[i]=dp[i-1]\ast 10+10^{i-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]*10+10**(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 += (n+1)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(num+1):res += numdp(index+1,count+(i==2),isLimit and (i == num))return resreturn numdp(0,0,True)

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-2s-in-range-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。