剑指offer 44. 从1到n整数中1出现的次数

简介: 剑指offer 44. 从1到n整数中1出现的次数

题目描述

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

例如输入 12,从 1 到 12 这些整数中包含 “1” 的数字有 1,10,11 和 12,其中 “1” 一共出现了 5 次。


数据范围

1≤n≤109

样例

输入: 12
输出: 5


方法一:数位DP O(logn)


如果按照暴力的做法,我们从 1~n 每个数都去算一遍 1 的个数,这个时间复杂度肯定会很高的,要是在面试的时候这么做估计就是出门右转的事情了 doge ~


所以这道题需要对上述操作进行优化,我们用到的方法是数位 DP ,先来看一个例子方便大家理解,假设 n = 13015 ,这时候就需要分情况进行讨论:

  • 【万位的1】
  • 1 _ _ _ _ 中第一位取 1 ,则此时已经封顶,后四位只能取 0000 ~ 3015 ,故一共出现了 1 * 3016 = 3016 次。


  • 【千位的1】
  • _ 1 _ _ _ 中第一位取 0 时,后三位可以取 000 ~ 999 ,故一共出现 1 * 1000 次。
  • 1 1 _ _ _ 中第一位封顶,则后三位可以取 000 ~ 999 ,故一共出现 1 * 1000 = 1000 次。


  • 【百位的1】
  • _ _ 1 _ _ 中前两位范围是 00 ~ 12 ,则后两位可以取 00 ~ 99 ,故一共出现 13 * 100 = 1300 次。
  • 1 3 0 _ _ 中前两位封顶,则第三位最高只能取 0 且后两位范围是 00 ~ 15 ,故一共出现 16 次。


  • 【十位的1】
  • _ _ _ 1 _ 中前三位范围是 000 ~ 129 ,则最后一位可以取 0 ~ 9 ,故一共出现 130 * 10 = 1300 次。
  • 1 3 0 1 _ 中前三位封顶且第四位发现可以取到 1 ,则最后一位可以取 0 ~ 56 次。


【个位的1】


_ _ _ _ 1 中前四位范围是 0000 ~ 1301 ,故一共出现 1 * 1302 = 1302 次。

通过上面这个例子,我们就可以得到下面这个结论:


假设给定 n = a b c d e f ,我们这里计算一下 c 这一位 1 出现的次数(其它位同理)。


(1)当前两位的范围是 00 ~ ab-1 时,后面三位可以取 000 ~ 999 ,故一共出现 ab * 1000 次。


(2)如果前两位封顶即取的就是 ab ,那么又要分三种情况,要看看给定的 n 的 c 的值是多少:


当 c = 0 时,一共出现 0 次。

当 c = 1 时,后三位可以取 000 ~ def ,故一共出现 def + 1 次。

当 c > 1 时,后三位可以取 000 ~ 999 ,故一共出现 1000 次。

综上所述,我们只用去拿到该位左边的所有数已经右边的所有数,然后根据上面的情况进行计算,每一位都是这样计算。

class Solution {
public:
    int numberOf1Between1AndN_Solution(int n) {
        if (!n)  return 0;
        vector<int> number; //用来存储每一位
        while (n)    number.push_back(n % 10), n /= 10;
        int ans = 0;
        //从最高位开始计算
        for (int i = number.size() - 1; i >= 0; i--)
        {
            int left = 0, right = 0, t = 1;
            //获得第i位左边的数
            for (int j = number.size() - 1; j > i; j--)  left = left * 10 + number[j];
            //获取第i为右边的数
            for (int j = i - 1; j >= 0; j--) right = right * 10 + number[j], t *= 10;
            //计算左边的数在0~ab-1的那种情况
            ans += left * t;
            //计算左边的数等于ab的那种情况
            if (number[i] == 1)    ans += right + 1;
            else if (number[i] > 1)    ans += t;
        }
        return ans;
    }
};

欢迎大家在评论区交流~

目录
相关文章
|
6月前
|
C++ Java Go
C/C++每日一练(20230409) 岛屿数量、出现次数最多整数、两数相除
C/C++每日一练(20230409) 岛屿数量、出现次数最多整数、两数相除
49 0
C/C++每日一练(20230409) 岛屿数量、出现次数最多整数、两数相除
|
6月前
|
机器学习/深度学习 存储 算法
数据结构与算法面试题:给定非负整数 m 和 n,计算不大于 m 的数字中,素数的个数。(提示:算法原理为埃氏筛、线性筛)
数据结构与算法面试题:给定非负整数 m 和 n,计算不大于 m 的数字中,素数的个数。(提示:算法原理为埃氏筛、线性筛)
91 0
【剑指offer】-1~n整数中1出现的次数-31/67
【剑指offer】-1~n整数中1出现的次数-31/67
【剑指offer】-数字在排序数组中出现的次数-32/67
【剑指offer】-数字在排序数组中出现的次数-32/67
|
6月前
(力扣)面试题56 - I. 数组中数字出现的次数
(力扣)面试题56 - I. 数组中数字出现的次数
28 0
|
算法
【Leetcode-190.颠倒二进制位 -191.位1的个数 -202.快乐数】
【Leetcode-190.颠倒二进制位 -191.位1的个数 -202.快乐数】
45 0
|
C++
剑指offer 55. 数字在排序数组中出现的次数
剑指offer 55. 数字在排序数组中出现的次数
83 0
|
存储
Leecode面试题43. 1~n整数中1出现的次数
Leecode面试题43. 1~n整数中1出现的次数
69 0
|
算法 C语言
剑指Offer 第53题:数字在升序数组中出现的次数
剑指Offer 第53题:数字在升序数组中出现的次数
139 0
剑指Offer 第53题:数字在升序数组中出现的次数