题解 | 整数中1出现的次数

找规律的题，官方的题解看得云里雾里，自己找了一下规律，这题有点动态规划的意思。

找规律

首先就是将0 ~ n分段，分段的原则按位数，如

• 1位数：0 ~ 9
• 2位数：10 ~ 99
• 3位数：100 ~ 999
• ...

分段之后，使用表格查看1出现的规律：

以n = 50345为例，分段如下：

从表格可以看到，当前位数由两部分构成，以100 ~ 999为例：

• 最高位固定1，计算1出现在最高位的次数
• 1出现在100 ~ 199中100次，正好时当前的base，即100
• 计算1出现在后续位的个数
• 后续位，包含100 ~ 199，200 ~ 299，... , 900 ~ 999共9个0 ~ 99
• 0 ~ 99中，1出现的个数是0 ~ 9，10 ~ 99的累加即20

可知100 ~ 999中，1出现的次数是：当前base 100 + 9个0 ~ 99。

所以0 ~ 999中，再加上一个0 ~ 99，即base 100 + 10个0 ~ 99。

可以总结出规律：

• 0 ~ 9：1的个数是1
• 0 ~ 99：1的个数是10 + 10个 0 ~ 9
• 0 ~ 999：1的个数为：100 + 10个 0 ~ 99

以此类推，0 ~ 99999的个数是10000 + 10个0 ~ 9999。

10000 ~ 50345不满足完整的规律，需要再细分：

• 10000 ~ 19999有10000次
• 不够9个0 ~ 9999，只有四个
• 50000 ~ 50345有345个数，所以递归求345有多少个1
• 中间的0都需要跳过

代码实现

step1：先计算每个完整base下的1出现的次数，并存储到HashMap备用

base定义：

• 1：0 ~ 9
• 10： 0 ~ 99
• 100：0 ~ 999
• ...

把每个可以到999...的称为完整base。

step2：递归计算最高base中1出现的次数，即上一个base是完整的，当前最高base并不完整

根据最高位是否大于1有不同的路径：

• 大于1：如最高位是5，则个数是5 * 上一个完整base + 当前base（10/100/1000...） + 去掉最高位后递归
• 等于1：上一个完整base + 去掉最高位后的数字 + 1
• 小于1：递归中不允许出现的情况

递归计算下一个base，如果下一位是0，则跳过，直到出现不为0位，再进行递归。

java代码：

import java.util.*;
public class Solution {
    HashMap<Integer, Integer> dp = new HashMap<>();
    public int NumberOf1Between1AndN_Solution(int n) {
        int maxBase = 1;
        int count = 1;
        dp.put(maxBase, count);
        while (n / maxBase >= 10) {
            maxBase *= 10;
            count = maxBase + 10 * count; // 当前base中1的个数为 base + 10 * 上一个base个数
            dp.put(maxBase, count);
        }

        if (1 == maxBase) return  n >= 1 ? 1 : 0; // n是个位数，直接返回

        return count(String.valueOf(n), maxBase); // 将n转化成字符串计算
    }

    /*
        nStr：传入的数字字符串，保证第一个字符不是0
        maxBase：最高位对应的十进制位，如1，10，100 ...
     */
    int count(String nStr, int maxBase) {
        int maxBaseNum = nStr.charAt(0) - '0'; // 当前base最高位的值
        if (1 == maxBase) { // 计算到个位, 无需再计算next base
            return maxBaseNum >= 1 ? 1 : 0;
        }

        int nextBase = maxBase / 10;
        int cnt = dp.get(nextBase); // 先计算上一个base的个数,如当前base是1000,则上一个base是100,且表示0 ~ 999之间的1的个数
        String nextStr = nStr.substring(1); // 最高位之后的数

        if (1 == maxBaseNum) { // 最高位是1,则当前1出现的次数为 0 ~ nextStr, 即nextStr + 1
            cnt += Integer.valueOf(nextStr) + 1;
        } else if (maxBaseNum > 1) { // 最高位大于1,例:最高位是4, 当且maxBase是1000, 则1000 ~ 1999共1000个1, 1000 ~ 1999/3000 ~ 3999共三个0 ~ 999
            cnt = cnt * maxBaseNum + maxBase; // 加上next base的,共4个0 ~ 999,即cnt的值
        } else {
            // maxBaseNum < 1, 不存在的情况
        }

        // 递归计算最高位后边的情况, 最高位后边有0, 则直接跳过
        int i = 0;
        while (i < nextStr.length() && '0' == nextStr.charAt(i)) {
            i ++;
            nextBase /= 10;
        }
        if (0 == nextBase) return cnt; // 最高位后边都是0, 无需递归计算

        // 递归计算后边不为0的情况
        cnt += count(nextStr.substring(i), nextBase);
        return cnt;
    }
}