给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
示例 1：
输入：n = 13
输出：6
示例 2：
输入：n = 0
输出：0
提示：
0 <= n <= 2 * 109
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-digit-one
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
数组存储每个数量级1的个数
1：按照各个数量级，创建两个树，nums数组来记录每个数量级， arr数组来记录每个数量级中1的个数。
2：拿到n之后，就从高位到地位的计算其1的个数。
3：需要注意的是，1需要单独处理一下。
当每一位的数字 大于 1 的时候，就说明，此数量级中包含了 nums[i] 个1 了 ,
例如 567 ，百位是 5 大于 1，说明 100-199中，包含了100个1.200-999中没有百位的1.
例如 167 ，百位是 1 等于 1， 说明 有 100-167 共 68个1在百位上。
public int countDigitOne(int n) { int sum = 0; if (n == 1000000000) { n--; sum++; } int[] arr = {0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000}; int[] nums = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000}; int length = String.valueOf(n).length(); for (int i = length - 1; i > 0; i--) { int m = n / nums[i]; n = n % nums[i]; sum = sum + m * arr[i]; if (m > 1) { sum = sum + nums[i]; } else if (m == 1) { sum = sum + n + 1; } } if (n >= 1) { sum++; } return sum; }