JAVA程序设计：2出现的次数（面试题 17.06）

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

示例:

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

n <= 10^9

思路：本题数位dp是可以无脑过的，而我选择另一种方法，该方法能够处理0~n甚至是任意区间内0到9分别出现的次数，并且写法相对数位dp简洁很多。

具体思路是我们采用递归的形式枚举每一位，对于每一位我们分别看低位对当前位、高位对当前位以及高位对低位的影响即可。

class Solution {
private int[] ans;
public int numberOf2sInRange(int n) {
ans = new int[10];
dfs(n, 1);
return ans[2];
}
private void dfs(int n, int num) {
int x = n % 10;
n /= 10;
for (int i = 0; i <= x; i++)
ans[i] += num;
for (int i = 0; i < 10; i++)
ans[i] += num * n;
ans[0] -= num;
int tmp = n;
while (tmp > 0) {
ans[tmp % 10] += (x + 1) * num;
tmp /= 10;
}
if (n > 0)
dfs(n - 1, num * 10);
}
}

最后

以上就是风中热狗为你收集整理的JAVA程序设计：2出现的次数（面试题 17.06）的全部内容，希望文章能够帮你解决JAVA程序设计：2出现的次数（面试题 17.06）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。