剑指offer上有一题：从1到N中1出现的次数，
比如N 为12时，出现1的数字有1，10，11，12，那么1总共出现5次。
思路：
使用递归思想，先考虑普通输入N = 345，从1 -- 345可以分拆为1 -- 45和46 -- 345（可以认为是分分治思想）
分别求1 -- 45 和 46 -- 345中1出现的次数
- 对1 -- 45也可以采用上述方法进行拆分为1 -- 5和6 -- 45，这就是递归的部分
- 对46--345这部分，我们需要知道有多个1：
1、首先关注345最高位3，因为大于1，所以存在100--199 属于46--345，也就是有10^(n - 1)个1(n为345的位数)。
2、对于345，因为first > 1(first为最高位数值)，这样按照上一步来计算。当first == 1时，最高位为1的出现次数从100--145，为46次，也就是非最高位数值+1。
3、然后非最高位也可能存在1，如x1x，xx1，对x1x，最高位的x可以取1，2，3，个位的x可以取0--9，所以有3 * (10^1)种，同理xx1也有3*(10^1)种。所以非最高位存在1的总数为 2 * 3 *(10^1)个，抽象为(n - 1)*first *(10 ^(n - 2))，n为345的位数。
4、求完46 -- 345中1的个数，然后求1--45中1的个数，这是就是递归了，1---45可以拆分为1--5和6--45，然后6--45执行上述的计算，1--5继续递归。
5、递归结束的条件是N的位数n == 1，这时候需要判断这个传入递归函数的N，if(N >= 1)return 1; if(N == 0)return 0;
源代码：
public static int countDigitOne(int n) {if(n < 0)return 0; //异常处理char[] ch = String.valueOf(n).toCharArray();return numOfOne(ch, 0);
}private static int numOfOne(char[] ch, int index) {int first = ch[index] - '0'; //求取当下最高位的数值if(ch.length - index == 1 && first == 0) // 递归条件判断，输入值是否为1位且为0return 0;if(ch.length - index == 1 && first >= 1) //输入值是否为1位且大于等于1return 1;int numOtherOne = 0;if(first > 1) //求取最高位为1的数字出现次数numOtherOne = power(ch.length - index - 1);if(first == 1) //求取最高位为1的数字出现次数numOtherOne = power1(ch, index);int numLowOne = first * (ch.length - index - 1) * power(ch.length - index - 2); //求取非最高位为1的数字出现次数int numRecurive = numOfOne(ch, index + 1); //递归return numOtherOne + numLowOne + numRecurive;
}private static int power(int n) { //求取10^nint m = 1;for(int i = 0; i < n; i++)m *= 10;return m;
}private static int power1(char[] ch, int index) { //求取子字符数组的数值String s = String.valueOf(ch).substring(index + 1);return Integer.valueOf(s) + 1;
}
复杂度分析：
- 时间复杂度：O(log(N))
每一次递归的时间复杂度为O(1)，一个数字N有log(N)位，所以递归深度为log(N)
总的时间复杂度O(log(N))。
- 空间复杂度：需要创建一个字符数组来存放数字N的log(N)位。