力扣233(java)-数字1的个数（困难）

题目：

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例 1：

输入：n = 13
输出：6
示例 2：

输入：n = 0
输出：0
 

提示：

0 <= n <= 109

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-digit-one
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

这个题是真的很打脑壳啊~参考【 liweiwei1419】和 【2021293707L2】的题解，谢谢大佬！

主要运用数位dp的思路，采用【自底向上】的递推求解，实际是【动态规划】关于数位的入门问题。

题目的意思是：在1~n 的所有整数中出现1的个数，不是整数的个数，而是整数中包含的1的个数！

例如：15

包含1的整数有：1, 10, 11, 12, 13, 14, 15, 一共有 1 + 1 + 2  + 1 + 1 + 1 + 1 = 8 ，所以1~15的所有整数中一共包含8个1。

数位：是把一个数按照个位、十位、百位拆开来看。因此本题就可以拆分为：个位出现1的个数、十位出现1的个数、百位出现1的个数…

定义状态1：A[i] 表示0~10ⁱ⁺¹-1的所有i+1位数里1的总数。

例如：

• 0~9 所有的 1 位数里的1的总数；
• 0~99 所有的 2 位数里的1的总数；
• 0~999所有的 3 位数里的1的总数；
• ……
• 0~999999所有的 6 位数里的1的总数；

故

• A[0] =1,0~9所有的1位数里含有的1的个数只有1个；
• A[1]考虑的范围为0~99所有两位数中含有的1的个数，分类讨论：
  • 个位数固定为1（ _1 ）,十位数可能为0~9（01,11,21,31,41,51,61,71,81,91），一共10种可能，十位为1这个1先不统计，这种情况下的结果是 10 * A[0];
  • 十位数固定为1，个位数为0~9（10,11,12,13,14,15,16,17,18,19），一共10种可能，这时候把十位为1这个1统计到了，这种情况下的结果是10种。因此A[1]= 10 * A[0] +10¹
• A[2]考虑的范围为0~999所有的三位数中含有的1的个数，分类讨论：
  • 最高位是0，剩下的是0~99，即为A[1], 最高位是1，剩下的是0~99即为A[1],…..,最高位是9，剩下是A[1],这里也暂时不统计最高位的这个1，一共是 10*A[1];
  • 最高位固定为1，十位，个位为0~99，一共100个。因此A[2]= 10 * A[1] +10²
    

根据上述规律，总结归纳出：A[i]= 10 * A[i -1 ] +10ⁱ

定义状态2：dp[i]表示：从右向左数截取到第 i + 1位到最后一个数组成的数字里面包含1的总个数。

例如：2875

• dp[0]表示截取到1位数4中（1~4）所有数里1的总数；
• dp[1]表示截取到2位数75中（1~75）所有数里1的总数；
• dp[2]表示截取到3位数875中（1~875）所有数里1的总数；
• dp[3]表示截取到4位数2875中（1~2875）所有数里1的总数；

因此从右向左遍历 给定整数n的每一位 i ,假设当前遍历到的数是m(0 <= m <= 9),根据遍历到的数值进行分类讨论：

dp[0]代表的是个位数包含的1的个数，如果m =0,表示个位数为0即dp[0] == 0,当m==0~9时，这10个数只有一个1即dp[0] == 1

• 当m == 0时，此时的状态值取决于m右边一位的状态值，dp[ i ] = dp[ i-1 ];
• 当m == 1时，例如166：
  • 首先：求出0~66中元素1的个数，即 dp[ i-1 ]
  • 其次：求出100~166中元素1的个数，最高位是1，只需要看他右边的数，即共有67个（100、101、……、166）
  • 最后：求出0~99中元素1的个数即为A[i-1](注意：这里我还想过会和首先：0~66重合，其实不会，因为166分为三批次：0~99小于100的元素1的个数,100~166首位为1的三位数，0~66这里是算100以上的数中1的个数)。
• 当m > 1时，例如465：
  • 首先：最高位不是1，看它后一位的状态值即dp[i-1],0~65中元素1的个数；
  • 其次：最高位是1，数出最高位是1的元素的个数即 10ⁱ,100~199中元素1的个数；
  • 最后：算其他模块中包含1的个数即m* A[i-1]，465中0~99,100~199(与其次不是同一种)，200~299,300~399各模块中包含的1的个数，即4 * A[1]。

代码：

 1 class Solution {
 2     public int countDigitOne(int n) {
 3         //将整数转换成字符串
 4         String s = String.valueOf(n);
 5         char[] ca = s.toCharArray();
 6         int m = s.length();
 7         //如果只有个位数则只包含一个1
 8         if(m == 1){
 9             return n == 0 ? 0 : 1;
10         }
11         //求状态1:A[i]: 0~10^(i+1) -1包含1的个数
12         //0~9,0~99,0~999
13         //如果是5位数，只需要求0~9999中出现1的个数
14         int[] A = new int[m-1];
15         // 0~9
16         A[0] = 1;
17         for(int i = 1; i < m-1; i++){
18             A[i] = 10 * A[i-1] + (int) Math.pow(10, i);
19         }
20         //求状态2：dp[i]
21         int[] dp = new int[m];
22         //如果最后一位为0
23         if(ca[m - 1] == '0'){
24             dp[0] = 0;
25         }else{
26         //最后一位不为0，即为0~9
27           dp[0] = 1;
28         }
29         for(int i = 1; i < m; i++){
30             //从右向左截取每一数位
31             char currChar = ca[m - i - 1];
32             if (currChar == '0'){
33                 //当前位为0，状态值取决于它右边的1的个数
34                 dp[i] = dp[i - 1];
35             } else if (currChar == '1'){
36                 //最高位为1，分为三个步骤相加
37                 //例如166，其次：求出100~166中元素1的个数
38                 int res = Integer.parseInt(s.substring(m - i, m)) + 1;
39                 //166中0~66,和小于100d 0~99中1的个数
40                 dp[i] = res + dp[i-1] + A[i-1];
41             }else{
42                 //最高位大于1的情况，例如465
43                 //最高位不是1个数，dp[i-1]
44                 //最高位是1，即为10^i
45                 //算其他模块：m * A[i-1]
46                dp[i] = (currChar - '0') * A[i-1] + dp[i-1] + (int) Math.pow(10,i);
47             }
48         }
49         return dp[m - 1];
50     }
51 }