1-n中1的出现次数

以你之姓@ 2024-04-08 10:48 72阅读 0赞

[力扣\_1-n中1的出现次数][1-n_1]

eg:3101592

![fef8fe61684a4623878acac05b267830.png][]

![88909915ea56475eb42e89dd20e1857a.png][]

所以，3101592中百位千位万位上1的出现次数总共是(a+1)\*base+\[a\*base+1\*(b+1)\]+a\*base

> 分析：将各个位置的1的个数都求出来，将数字分为\[前\]\[cur\]\[后\]三部分，cur代表当前位，当前位1的个数=前\*后
> 
> 1）当前位cur>1时，\[前\]都可以直接取，因为无论取多少都不会大于要计算的数字，如3101529求百位1的个数，cur=5>1，求这个位1的个数，\[前\]取0-3101（3101129<3101529），后面直接也可以取满0-99
> 
> 2）当前位cur==1时，需要分情况，如3101529的求千位1个数，千位为1，\[前\]需要分情况，0-309时，\[后\]可取0-999，但310时，\[后\]只能取0-592，否则数字就会大于原数字
> 
> 3）当前位cur<1时，如3101592取万位1的个数，万位cur=0，此时\[前\]只能取0-30，否则数字(3111...)就会大于原数字(3101...)

public class Num43_1到n中1出现的次数 {
        public int countDigitOne(int n) {
            // "1"出现的次数 = sum ("1"在各个计数位上出现的次数)
            // 从1在个位开始向最高位统计
            // 3101592
            // 将数字拆分为[a...][cur][b...]
            // cur为当前位：当前位1出现次数=[a...]*[b...]
            long base = 1, res = 0;//base=1表示从个位开始
            while (base <= n) {
                // 计算 a..., cur, b...
                long a, cur, b;
                a = n / base / 10;
                cur = (n / base) % 10;
                b = n % base;
                // 将当前位设为1，考察其他部分的变化范围
                if (cur > 1) {
                    // 一、cur > 1，
                    // [3101 ] 5 [92]
                    // 变化范围：[0-3101] 1 [0-99]
                    // 总个数： (a+1) * base
                    res += (a + 1) * base;
                } else if (cur == 1) {
                    // 二、cur == 1，
                    // [310] 1 [592]
                    // 1、变化范围 [0-309] 1 [0-999]
                    // a * base
                    // 2、变化范围 [310] 1 [0-592]
                    // 1 * (b+1)
                    // 总个数：a *base + (b + 1)
                    res += a*base + b + 1;
    
                } else {
                    // 三、cur < 1，
                    // [31] 0 [1592]
                    // 变化范围 [0-30] 1 [0-9999]
                    // 总个数 a * base
                    res += a * base;
                }
                // 统计更高一位
                base *= 10;
            }
            return (int) res;
        }
    }

[1-n_1]: https://leetcode.cn/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/
[fef8fe61684a4623878acac05b267830.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/ba8ddb2635194454ad6f36c1d8f93a0f.png
[88909915ea56475eb42e89dd20e1857a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/5e417ccf78544416b83eb4d2ad9f52ed.png