【问题描述】
小蓝特别喜欢 2，今年是公元 2020 年，他特别高兴。
他很好奇，在公元 1 年到公元 2020 年（包含）中，有多少个年份的数位中
包含数字 2？

 

　　虽说暴力求解也能快速求出，只需要for循环从0开始到2021，转换为字符串判断字串有无“2”即可。不过还是尝试用分治法求解一下。

　　数据量不大，直接用int

public class ContainsTwo {

    private static int power(int n, int exp) {
        int res = 1;
        while(exp != 0) {
            if((exp & 1) == 1) {
                res = (res * n);
            }
            exp >>= 1;
            n = (n*n);
        }
        return res;
    }
    
    private static int count2(int num) {
        if (num<2) {
            return 0;
        }
        if (num < 12) {
            return 1;
        }
        if (num < 19) {
            return 2;
        }
        if (num < 30) {
            return 3 + num - 20;
        }
        if (num < 100) {
            int temp = (num - (num/10)*10)>=2?1:0;
            return 9 + (num/10) + temp;
        }
        int result = 0;
        int n = ("" + num).length();
        int unit = power(10, n-1);
        int a = num / unit;
        int b = num - a*unit;
        if (a > 2) {
            return (a-1) * count2(unit-1)+ unit + count2(b);
        }
        else if(a == 2) {
            return a * count2(unit-1) + (num + 1 - a * unit);
        }
        else {
            return result + a * count2(unit-1) + count2(b);
        }
    }

    public static void main(String[] args) {
        System.out.println(count2(2020));
    }
}