微信公众号：路人zhang
扫码关注微信公众号

回复“面试手册”，获取本站PDF版

回复“简历”，获取高质量简历模板

回复“加群”，加入程序员交流群

回复“电子书”，获取程序员类电子书

当前位置： 算法 > 剑指offer > 剑指offer 43. 1~n整数中1出现的次数

剑指offer 43. 1~n整数中1出现的次数

题目描述

输入一个整数 n ，求1～n 这 n 个整数的十进制表示中 1 出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

示例 1：

输入：n = 12
输出：5

示例 2：

输入：n = 13
输出：6

限制：

  • 1 <= n < 2^31

算法

(数位统计) O(log_{10}n)

分情况讨论 假设当前枚举到了第 i 位，left 表示 i 左边数字，right 表示 i 右边数字

  1. 左边数字是 0 ~ (ab – 1)，出现次数 ab * t（假设当前枚举位右边数字的位数为 x，则 t = 10^x
  2. 左边数字是 ab 2.1 当前位是 0，不做处理 2.2 当前位是 1，出现次数 right + 1 2.3 当前位大于 1，出现次数 t

时间复杂度

两次循环枚举每一位，所以时间复杂度为 O(log_{10}n)。

空间复杂度

O(1)

C++ 代码

class Solution {
public:
    int countDigitOne(int n) {
        if (!n) return 0;
        vector<int> number;
        while (n) number.push_back(n % 10), n /= 10;
        
        int res = 0;
        // 从最高位开始枚举
        for (int i = number.size() - 1; i >= 0; i -- ) {
            // left: i 左边数字，right: i 右边数字，t: right 有几位，t 就是 10 的几次方
            int left = 0, right = 0, t = 1;
            // 求正在枚举的当前位的左边数字
            for (int j = number.size() - 1; j > i; j -- ) left = left * 10 + number[j];
            // 求正在枚举的当前位的右边数字
            for (int j = i - 1; j >= 0; j -- ) right = right * 10 + number[j], t *= 10;
            
            // 1. 左边数字是 0 ~ (ab - 1)
            res += left * t;
            // 2. 左边数字是 ab
            // 2.1 当前位是 0，不做处理
            // 2.2 当前位是 1
            if (number[i] == 1) res += right + 1;
            // 2.3 当前位大于 1
            else if (number[i] > 1) res += t;
        }
        
        return res;
    }
};

Java 代码

class Solution {
    public int countDigitOne(int n) {
        if (n == 0) return 0;
        List<Integer> number = new ArrayList<>();
        while (n > 0) {
            number.add(n % 10);
            n /= 10;
        }
        
        int res = 0;
        for (int i = number.size() - 1; i >= 0; i -- ) {
            int left = 0, right = 0, t = 1;
            for (int j = number.size() - 1; j > i; j -- ) left = left * 10 + number.get(j);
            for (int j = i - 1; j >= 0; j -- ) {
                right = right * 10 + number.get(j);
                t *= 10;
            }
            
            res += left * t;
            if (number.get(i) == 1) res += right + 1;
            else if (number.get(i) > 1) res += t;
        }
        
        return res;
    }
}

Python 代码

class Solution:
    def countDigitOne(self, n: int) -> int:
        if n == 0:
            return 0
        number = []
        while n > 0:
            number.append(n % 10)
            n //= 10
        
        res = 0
        for i in range(len(number) - 1, -1, -1):
            left, right, t = 0, 0, 1
            for j in range(len(number) - 1, i, -1):
                left = left * 10 + number[j]
            for j in range(i - 1, -1, -1):
                right = right * 10 + number[j]
                t *= 10
            
            res += left * t
            if number[i] == 1:
                res += right + 1
            elif number[i] > 1:
                res += t
        
        return res

本文由读者提供，Github地址：https://github.com/tonngw

点击面试手册，获取本站面试手册PDF完整版

剑指offer