LeetCode 233 : Number of Digit One (java)

i_garfileo 发布于2019-08-14 15:54 / 2904人阅读

摘要：题目给一个数求从到所有数中数字在各个位上出现的总次数。解法可以做循环从到挨个找。更好的是用归纳法总结出出现的次数的规律。

题目：
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.

给一个数n,求从1到n所有数中数字1在各个位上出现的总次数。

解法：

可以做循环从1到n挨个找。慢。

更好的是用归纳法总结出1出现的次数的规律。

假设n=abcde五位数字的时候，我们分析百位c，有三种情况：

1）c == 0的时候，比如12013，此时百位出现1的是：00 100 ~ 00 199， 01 100~01 199，……，11 100~ 11 199，共1200个，显然这个有高位数字决定，并且受当前位数影响；个数就是 ab*100

2）c == 1的时候，比如12113，此时百位出现1的肯定包括c=0的情况，另外还需要考虑低位的情况即：00100 ~ 00113共14个; 个数等于ab*100+ de + 1

3）c >= 2的时候，比如12213，此时百位出现1的是：00 100 ~ 00 199， 01 100~01 199，……，11 100~ 11 199，12 100 ~ 12 199，共1300个，这个有高位数字决定，其实是加一，并且乘以当前位数; 个数就是 (ab+1)*100

总结起来，对于一个 n = abcde 来说，百位出现1的个数计算方法为：

if(c==0) ans = ab*100;
if(c==1) ans = ab*100+cd+1
if(c>1) ans = (ab+1)*100

代码：

public class Solution {
    public int countDigitOne(int n) {
        if(n <= 0) return 0;
        int q = n; int x = 1; int ans = 0; int temp = 0;
        do{
            temp = q%10;
            q/=10;
            if(temp == 0) ans+=q*x;
            else if(temp == 1) ans+=q*x + n%x + 1;
            else
                ans+=(q+1)*x;
            x*=10;
        } while (q > 0);
        return ans;
    }
}

Ref：

java one pass easy understand

leetcode 233

云服务器 GPU云服务器 233服 Digit LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66097.html

LeetCode[233] Number of Digit One

摘要：递归复杂度思路每次将一个数拆分成两部分考虑，并考虑当前最高是不是比如，将数拆分成，和，这两部分分别计算。每次抹去高位，观察重复情况。代码代表位数，代表最高的值除了高位的剩余部分 LeetCode[23] Number of Digit One Given an integer n, count the total number of digit 1 appearing in alln...

v1 2019-08-14 14:58 评论0 收藏0
leetcode233. 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...

UnixAgain 2019-08-16 11:02 评论0 收藏0
[LeetCode] Number of Digit One

摘要：只有大于左边界才部分包含，且只有大于右边界的数才完整包含，这些中多余的。对于而言，部分包含用余数做，完整包含用进位后的商做。逐位向上累加，可得结果。千位万位，大致如此。例如个位十位百位千位 Problem Given an integer n, count the total number of digit 1 appearing in all non-negative integer...

supernavy 2019-08-14 14:02 评论0 收藏0
Leetcode加一（java、python3）

摘要：加一给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。示例输入输出解释输入数组表示数字。思路指针从最后往前移动，若值为逐个加一，并赋值。不等于则退出循环。首位如果为是则证明需要进一。只需首位赋值即可。加一给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位，数组中每个元素只存储一个数字。你可以假设除了整数 0 之外，这个...

沈建明 2019-07-31 10:30 评论0 收藏0
Leetcode加一（java、python3）

摘要：加一给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。示例输入输出解释输入数组表示数字。思路指针从最后往前移动，若值为逐个加一，并赋值。不等于则退出循环。首位如果为是则证明需要进一。只需首位赋值即可。加一给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位，数组中每个元素只存储一个数字。你可以假设除了整数 0 之外，这个...

Apollo 2019-08-16 17:51 评论0 收藏0