Skip to content

Latest commit

 

History

History
 
 

2999.Count-the-Number-of-Powerful-Integers

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

2999.Count-the-Number-of-Powerful-Integers

首先,对于区间内的计数,常用的技巧就是转化为helper(to_string(finish), limit, s) - helper(to_string(start-1), limit, s),其中helper(string a, int limit, string s)表示在[1:a]区间内有多少符合条件的数(即每个digit不超过limit且后缀为s)。

接下来写helper函数。令上限a的长度为d,那么我们计数的时候只需要逐位填充、循环d次即可。对于第k位而言,分两种情况:

  1. 如果填充的前k-1位小于a同样长度的前缀,那么第k位可以任意填充0 ~ limit都不会超过上限a。甚至从第k+1位起,直至固定的后缀s之前,总共有d = a.size()-s.size()-k位待填充的数字,都可以任意填充为0~limit。故直接返回计数结果:pow(1+limit, d).
  2. 如果填充的前k-1位等于a同样长度的前缀,那么第k位可以填充为0 ~ min(limit, a[k])。确定之后,接下来递归处理下一位即可。注意,如果填充为a[k]的话,需要告知递归函数“已构造的前缀继续与a相同”,否则告知递归函数“已构造的前缀小于a”。这样下一轮递归函数知道选择哪一个分支。