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）所遇到的程序开发问题。

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