Leetcode 233. Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example: Given n = 13, Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

给一个数,计算不超过这个数的所有正数中,1出现的次数。

一开始的想法,分段计算 0-9,10-99,100-999......除了个位,每一段1出现的次数 = 数字总数 * k - k * 8*9^(k - 1),k为位数,即用这一段所有数字的总和减去不使用1构成的数字的个数乘上位数,这种想法太不简洁。

优美解法:枚举不超过n的每一位,对每一位1出现的次数进行统计。

参考这里:https://discuss.leetcode.com/topic/18054/4-lines-o-log-n-c-java-python

以算百位上1为例子: 

假设百位上是0, 1, 和 >=2 三种情况:

 case 1: n=3141092, a= 31410, b=92. 计算百位上1的个数应该为 3141 *100 次.

 case 2: n=3141192, a= 31411, b=92. 计算百位上1的个数应该为 3141 *100 + (92+1) 次.

 case 3: n=3141592, a= 31415, b=92. 计算百位上1的个数应该为 (3141+1) *100 次.

所以可以将每一位归纳成这样一个公式:

(a + 8) / 10 * m + (a % 10 == 1) * (b + 1)

需要注意的坑,虽然最终结果不会超过int范围,但是因为中间计算涉及乘法,所以会出现溢出,需要用long long存储中间变量。

class Solution {
public:
    int countDigitOne(int n) {
        int res = 0;
        for(long long i = 1; i <= n ; i *= 10)
        {
            int pre = n / i;
            int suf = n % i;
            long long temp = (pre + 8) / 10 * i;
            if(pre % 10 == 1) temp += suf + 1;
            res += temp;
        }
        return res;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏落影的专栏

程序员进阶之算法练习(三十三)LeetCode专场

BAT常见的算法面试题解析: 程序员算法基础——动态规划 程序员算法基础——贪心算法 工作闲暇也会有在线分享,算法基础教程----腾讯课堂地址。 今天继续Lee...

1151
来自专栏chenjx85的技术专栏

leetcode-39-组合总和(有趣的递归)

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

1312
来自专栏落影的专栏

程序员进阶之算法练习(三十三)LeetCode专场

BAT常见的算法面试题解析: 程序员算法基础——动态规划 程序员算法基础——贪心算法 工作闲暇也会有在线分享,算法基础教程----腾讯课堂地址。 今天继...

911
来自专栏欧阳大哥的轮子

常用的数学函数以及浮点数处理函数

在编程中我们总要进行一些数学运算以及数字处理,尤其是浮点数的运算和处理,这篇文章主要介绍C语言下的数学库。而其他语言中的数学库函数的定义以及最终实现也是通过对C...

2002
来自专栏算法channel

冒泡排序到快速排序做的那些优化

本公众号主要推送关于对算法的思考以及应用的消息。算法思想说来有,分而治之,搜索,动态规划,回溯,贪心等,结合这些思想再去思考如今很火的大数据,云计算和机器学习,...

4229
来自专栏aCloudDeveloper

公司数据结构+算法面试100题

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 ...

9519
来自专栏林德熙的博客

C# 搜索算法 Bdf 算法

数据“aaacbc”,匹配“abc”,也是匹配,因为数据按照“abc”的顺序,算法不管数据有多长,只要数据存在和匹配相同的顺序,那么就匹配。

1311
来自专栏猿人谷

对快速排序算法的分析

开篇 在实际的过程中,总需要对一些数据进行排序,在众多的排序算法中,快速排序是较为常用的排序算法之一。而网上对于快速排序的中文资料还不是很全。写 这篇博文主要记...

23110
来自专栏DHUtoBUAA

快速排序算法思路分析和C++源代码(递归和非递归)

  快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试...

4087
来自专栏决胜机器学习

有趣的算法(十一) ——分治法:大数相乘

有趣的算法(十一)——分治法:大数相乘 (原创内容,转载请注明来源,谢谢) 太大的两个数字相乘,有可能会超出计算机的位数,需要人工进行转化。 1、原始解法 最...

3413

扫码关注云+社区

领取腾讯云代金券