题目描述：
输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
示例1: 输入：n = 12 输出：5
示例2: 输入：n = 13 输出：6
解题思路：
1、利用递归： countDigitOne(n)表示1~n整数中1出现的次数，为了找出规律，使用划分数字范围的思想来解答该题：将数字n划分为两部分，一部分是最高位high,一个是其他位的数字last。例如，对于数字1234，high为1，last为234，记pow为1000。
所有数字对于high来说，可以分为两种情况：
（1）一种是high等于1的情况，例如，当n=1234时，可以划分为两个部分：1-999和1000-1234。对于1-999来说，其中1出现的次数为countDigitOne(pow - 1)；对于1000-1234，最高位1出现的次数为235次，即last + 1，而其他位出现1的次数为countDigitOne(last）。因此对于high等于1的情况来说，countDigitOne(n) = countDigitOne(pow - 1) + last + 1 + countDigitOne(last)。
（2）另一种是high不等于1的情况，例如，当n=3234时，其中high = 3，last = 234，pow = 1000，可以划分为四个部分：1-999、1000-1999、2000-2999、3000-3234。对于1-999来说，其中1出现的次数为countDigitOne(pow - 1)；对于1000-1999，最高位1出现的次数为1000次，即pow，其他位出现1的次数为countDigitOne(pow - 1）；对于2000-2999，最高位1出现的次数为0次，其他位出现1的次数为countDigitOne(pow - 1）；对于2999-3234，最高位1出现的次数为0次，其他位出现1的次数为countDigitOne(last）。因此对于high不等于1的情况来说，countDigitOne(n) = high * countDigitOne(pow - 1) + pow + countDigitOne(last)。
2、模拟密码锁： 设数字n是个x位数，记n的第i位为ni，则n可以表示为nxnx-1…n1n0。
记ni为当前位，即cur将ni-1…n0记为低位，即low将nx…ni+1记为低位，即high将10i记为位因子，即digit当前位cur中出现1的的计算方式如下：
(1)当cur = 0时，此位1的出现次数只由高位 high决定，计算公式为：high * digit，例如对于数字2305来说，high = 23，digit = 10（当前位为“10”位），“10”位出现的数字范围为0010-2219，那么固定“10”位，其他位为000-229，一共有229-0+1= 230 = 23 X10次，即high * digit。（这个计算过程有点类似于解密码锁）
(2)当cur = 1时，此位1的出现次数由高位 high和低位low决定，计算公式为：high * digit + low + 1，例如对于数字2315来说，high = 23，digit = 10（当前位为“10”位），low = 5，“10”位出现的数字范围为0010-2315，那么固定“10”位，其他位为000-235，一共有235-0+1= 236= 23 X10 + 5 + 1次，即high * digit + low + 1。
(3)当cur为其他数字时，此位1的出现次数只由高位 high决定，计算公式为：(high + 1)* digit，例如对于数字2325来说，high = 23，digit = 10（当前位为“10”位），“10”位出现的数字范围为0010-2319，那么固定“10”位，其他位为000-239，一共有239-0+1= 240= (23 + 1) X10次，即(high + 1)* digit。
因此，可以从最低位开始依次遍历数字n的所有位，然后逐步计算，即可算出表示1~n整数中1出现的次数。
以上两种解法分别参考：xujunyi大佬的题解和Krahets大佬的题解
时间复杂度和空间复杂度： 第二种解法的时间复杂度为O(log10n)，空间复杂度为O(1)。
实现代码：
//解法1：递归 public int countDigitOne(int n) { if(n <= 0) return 0; String s = String.valueOf(n); int high = s.charAt(0) - '0';//最高位 int pow = (int) Math.pow(10, s.length() - 1); int last = n - high * pow; if(high == 1) return countDigitOne(pow - 1) + last + 1 + countDigitOne(last); else return high * countDigitOne(pow - 1) + pow + countDigitOne(last); } //解法2：找规律 public int countDigitOne1(int n){ int digit = 1, res = 0; int high = n / 10, cur = n % 10, low = 0; while (high != 0 || cur != 0){ if(cur == 0) res += high * digit; else if(cur == 1) res += high * digit + low + 1; else res += (high + 1) * digit; //更新high，low，digit，cur low += cur * digit; cur = high % 10; high /= 10; digit *= 10; } return res; }