帅气咕杂货间

Leetcode233 数字1的个数题解

Leetcode 233
Word count: 453 / Reading time: 2 min
2018/08/07 Share

题目

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例:

1
2
3
输入: 13
输出: 6 
解释: 数字 1 出现在以下数字中: 1, 10, 11, 12, 13 。

思路

看到这道题的第一反应是用一种类似于筛法的方式,比如数字3虽然没有包含1,可以在数字3左右添加1构造出 31和13,似乎可以使用这种方式由一位数开始用递归将所有包含1的数字都构造出来.但是发现并不能很好解决数字重复的问题 以及包含1的数字的构造不是很好实现.于是作罢.

进一步挖掘问题,一个数字每位数之间相互独立互不影响,我们可以先统计范围内个位数是1的数字有多少个.然后以此类推，其中又分为三种情况 数字n中该为数 为0 为 1 或者大于1.

  1. n = 233333333 left = 2333333 right = 33, 百位数上总数应为233334 *100
  2. n = 233333033,left = 2333330,right = 33 ,因为在百位数为1时,左右数字组合可能大于233333033,比如233333100, 所以百位数上1的总数为233333*100
  3. n = 233333133,left = 2333331,right = 33,左方数字为2333331时,结果可能大于n,比如233333134,所以百位数上1的总数为233333*100+33+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 long countDigitOne(long n) {
        long  result = 0;
        long  left = 0;
        long  right = 0;
        long  index = 1;
        while(n>=index){
            left = n/index;
            right = n%index;
            result += (left+8)/10*index;
            if(left%10==1)
                result+=right+1;
            index*=10;
        }
        return result;
    }
};

其中result += (left+8)/10*index;

个人认为是一种很技巧性的方法将数字与处理结果对于,省去了多个if判断.

原文作者: Arch Yi

原文链接: http://watermelon1gugu.github.io/2018/08/07/LeetCode233-countDigitOne/

发表日期: August 7th 2018, 11:42:58 pm

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 题目
  2. 2. 思路
Total : 34
2019
2018
百度 控诉 笔试 springBoot JPA TIM Leetcode 233 JVM memory model eps 进程间通信 HelloWorld 解决办法 isdc jetbrain leetcode 39 makefile 正则表达式 modelMapper mutex semaphore mapper mybatis oneToMany ubuntu18.04 mysql opencv mybatis-generator pip SpringBoot SpringMVC Mybatis stream C++ systemd ubuntu volatile 春招 后端 图谱