描述

题目描述

输入一个整数 n ，求1～n 这 n 个整数的十进制表示中1出现的次数。
例如，1~13 中包含1的数字有1、10、11、12、13 因此共出现6次。

示例

输入：n = 13
输出：6

这道题简单意思就是：找出小于等于 n 的非负整数中数字 1 出现的个数。

初看这道题，无非都会想到一个简单解法：要么从 1 开始遍历到 n 统计 1 出现的次数。可惜时间复杂度过高，基本都会超时。

既然简单的方法不行，看起来也跟动态规划、递归、数据结构等等无关，也排除贪心或者暴力解法，那不妨考虑用笔在纸上画一画，推导出规律。

知识点：数学推导
难度：三星

题解

解题思路

很多问题，都可以将复杂问题简单化，大问题化解为多个小问题，最终推算出最终问题的解法，类似分治法。而且很多问题，如果对于变量过多或者过于负责，我们可以将变量 n 用简单的常数表示，先解决常见情况，再解决所有情况的问题，也叫化繁为简，逐个击破。

学习解题思路前，不妨先了解下我们使用的行李箱的 “ 滚动密码锁 ” 的开锁，脑海里要有个印象，方便待会理解思路

我们不妨先剖解为小问题，分情况剖析问题：找出小于等于 1234 的非负整数中的百位上，数字 1 出现的个数。即只统计百位数上1出现的次数？

这个小问题主要可以分三种情况，cur 为 0、1、 2~9

1. cur = 0 ：

设 n = 1034 的百位数 “0” 为 cur，作为当前位，则 “1” 为 high，作为高位数，“34” 为 low，表示低位数

公式解释：

因为 cur 始终不变，而我们只统计出现不同数字情况的数量，因此可忽略不变量，此处可通过刚刚说过的行李箱 “滚动密码锁” 的开锁帮助理解

对高低位分别计算：如上面的 0100-0199，忽略当前位： 0-099，高位 0 忽略，低位 99

而 99 有 0~99 的情况，则有 100 种结果

公式 count = high * bitNum 可以这样理解：忽略不变的 cur，相当于 99，count = 高位数的结果 + 低位数的结果，即 0 + (99 + 1) = 1 * 100 = 0 + (99 + 1) = (high - 1) * bitNum + (99 + 1)，也是计算高位和低位的结果数之和

2. 当 cur = 1

设 n = 1134 的百位数 “1” 为 cur，作为当前位，则最左边的 “1” 为 high，作为高位数，“34” 为 low，表示低位数

公式解释：

因为 cur 始终不变，而我们只统计出现不同数字情况的数量，因此可忽略不变量，此处可通过刚刚说过的行李箱 “滚动密码锁” 的开锁帮助理解

对高低位分别计算：如上面的 0100-1134，忽略当前位： 000 - 134，对于134，高位为 1，低位为 34

而 134 有 0 ~ 134 的情况，则有 135 种结果

好比使用滚轮密码锁，保持 cur 为 1 不变，不断从 0100 到 1134 改变高位和低位的数字，总共就有 135 种结果

公式 count = high * bitNum + low + 1 可以这样理解：忽略不变的 cur，相当于 134，count = 高位数的结果 + 低位数的结果，即 134 + 1 = 1 * 100 + 34 + 1 = (1 * 100) + (34 + 1) = (high * bitNum) + (low + 1), 最后的 (low + 1) 表示低位数都为 0 的情况

3. 当 cur > 1

设 n = 1334 的百位数 “3” 为 cur，作为当前位，则 “3” 为 high，作为高位数，“34” 为 low，表示低位数

公式解释：

因为 cur 始终不变，而我们只统计出现不同数字情况的数量，因此可忽略不变量，此处可通过刚刚说过的行李箱 “滚动密码锁” 的开锁帮助理解

对高低位分别计算：如上面的 0100-0199，忽略当前位： 0-099，高位 0 忽略，低位 99

而 99 有 0~99 的情况，则有 100 种结果

公式 count = (high + 1) * bitNum 可以这样理解：忽略不变的 cur，相当于 199，count = 高位数的结果 + 低位数的结果，即 199 + 1 = (1 + 1) * 100 = (1 * 100) + (99 + 1) = (high * bitNum) + (低位数结果数)

如果只计算百位数的情况，代码如下：

public class Solution {
    // 这里假设n>=1000的情况
    public int NumberOf1Between1AndN_Solution(int n) {
        int count = 0, bitNum = 100, high = n / 100, cur = (n / 10) % 10, low = n % 10;
        if(cur == 0) {
            // case 1: cur == 0
            // cur=0时，高位需要减去一位用于低位进行计算
            // 相当于 count = (high - 1) * bitNum + (99 + 1)
            count += high * bitNum;
        } else if(cur == 1) {
            // case 2: cur == 1
            // 相当于高位+低位计算结果，即(high * bitNum) + (low + 1)     
            count += high * bitNum + low + 1;
        } else {
            // case3: cur > 1
            // 相对于cur=0的情况，就不需要高位减去一位来计算低位的结果数了
            // 相当于(high * bitNum) + (低位数结果数)
            count += (high + 1) * bitNum;
        }
        return count;
    }
}

理解了计算某一个位为 1 的结果数这个小问题，那么接下来计算所有位的结果数就简单多了

方法：数学推导

Java 版本代码如下：

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int count = 0, bitNum = 1, high = n / 10, cur = n % 10, low = 0;
        // cur遍历n每一数位
        while(cur != 0 || high != 0) {
            if(cur < 1) {
                // case 1: cur == 0
                // cur=0时，高位需要减去一位用于低位进行计算
                // 相当于 count = (high - 1) * bitNum + (99 + 1)
                count += high * bitNum;
            } else if(cur == 1) {
                // case 2: cur == 1
                // 相当于高位+低位计算结果，即(high * bitNum) + (low + 1)     
                count += high * bitNum + low + 1;
            } else {
                // case3: cur > 1
                // 相对于cur=0的情况，就不需要高位减去一位来计算低位的结果数了
                // 相当于(high * bitNum) + (低位数结果数)
                count += (high + 1) * bitNum;
            }
            // low、cur、high都像左偏移一个位
            // bitNum表示cur的数位
            low += cur * bitNum;
            cur = high % 10;
            high = high / 10;
            bitNum = bitNum * 10;
        }
        return count;
    }
}

Go 版本代码如下：

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param n int整型 
 * @return int整型
*/
func NumberOf1Between1AndN_Solution( n int ) int {
    // write code here
    bitNum, count := 1, 0
    high, cur, low := n/10, n%10, 0
    for high != 0 || cur != 0 {
        if cur < 1 {
            // case 1: cur == 0
            // cur=0时，高位需要减去一位用于低位进行计算
            count += high * bitNum
        } else if cur == 1 {
            // case 2: cur == 1
            // 相当于高位+低位计算结果，即(high * bitNum) + (low + 1)   
            count += high*bitNum + low + 1
        } else {
            // case3: cur > 1
            // 相对于cur=0的情况，就不需要高位减去一位来计算低位的结果数了
            // 相当于(high * bitNum) + (低位数结果数)
            count += (high + 1) * bitNum
        }
        // low、cur、high都像左偏移一个位
        // bitNum表示cur的数位
        low = low + cur*bitNum
        high, cur = high/10, high%10
        bitNum = bitNum * 10
    }
    return count

}

时间复杂度 O(log n) ：时间复杂度只需要看 while 循环的级别，循环内的操作使用 O(1) 的时间，而循环数字 n 的位数，相当于使用了 log10 (n)，因此时间复杂度为 O(log n)
空间复杂度 O(1)：没有用到类似数组、队列等需要开辟大量空间的数据类型，只使用了几个变量，因此空间复杂度为 O (1)

整数中1出现的次数(Java&Go)

描述