首页 > 剑指offer > 统计0到n之间1的个数[数学]
2015
06-15

统计0到n之间1的个数[数学]

问题描述

给定一个十进制整数N,求出从1到N的所有整数中出现”1”的个数。 

例如:N=2时 1,2出现了1个 “1” 。

N=12时 1,2,3,4,5,6,7,8,9,10,11,12。出现了5个“1”。

方法一 暴力求解

最直接的方法就是从1开始遍历到N,将其中每一个数中含有“1”的个数加起来,就得到了问题的解。

代码如下:

/**
 * Created by GaoTong on 2014/11/19.
 * copyright: www.acmerblog.com
 */
public class CountOnes {

    public long CountOnes(long n){
        long i = 0,j = 1;
        long count = 0;
        for (i = 1; i <= n; i++)
        {
            j = i;
            while (j != 0)
            {
                if (j % 10 == 1)
                    count++;
                j = j / 10;
            }
        }
        return count;
    }

    public static void main(String args[]){
        CountOnes c = new CountOnes();
        System.out.println(c.CountOnes(12));
        System.out.println(c.CountOnes(120));
    }
}

该算法的时间复杂度为O(N*lgN)

解法二 

1位数的情况:

在解法二中已经分析过,大于等于1的时候,有1个,小于1就没有。

 2位数的情况:

N=13,个位数出现的1的次数为2,分别为1和11,十位数出现1的次数为4,分别为10,11,12,13,所以f(N) = 2+4。

N=23,个位数出现的1的次数为3,分别为1,11,21,十位数出现1的次数为10,分别为10~19,f(N)=3+10。

由此我们发现,个位数出现1的次数不仅和个位数有关,和十位数也有关,如果个位数大于等于1,则个位数出现1的次数为十位数的数字加1;如果个位数为0,个位数出现1的次数等于十位数数字。而十位数上出现1的次数也不仅和十位数相关,也和个位数相关:如果十位数字等于1,则十位数上出现1的次数为个位数的数字加1,假如十位数大于1,则十位数上出现1的次数为10。

 3位数的情况:

N=123

个位出现1的个数为13:1,11,21,…,91,101,111,121

十位出现1的个数为20:10~19,110~119

百位出现1的个数为24:100~123

 我们可以继续分析4位数,5位数,推导出下面一般情况: 

假设N,我们要计算百位上出现1的次数,将由三部分决定:百位上的数字,百位以上的数字,百位一下的数字。

如果百位上的数字为0,则百位上出现1的次数仅由更高位决定,比如12013,百位出现1的情况为100~199,1100~1199,2100~2199,…,11100~11199,共1200个。等于更高位数字乘以当前位数,即12 * 100。

如果百位上的数字大于1,则百位上出现1的次数仅由更高位决定,比如12213,百位出现1的情况为100~199,1100~1199,2100~2199,…,11100~11199,12100~12199共1300个。等于更高位数字加1乘以当前位数,即(12 + 1)*100。

        如果百位上的数字为1,则百位上出现1的次数不仅受更高位影响,还受低位影响。例如12113,受高位影响出现1的情况:100~199,1100~1199,2100~2199,…,11100~11199,共1200个,但它还受低位影响,出现1的情况是12100~12113,共114个,等于低位数字113+1。

综合以上分析,写出如下代码:

public long CountOne2(long n) {
        long count = 0;
        long i = 1;
        long current = 0, after = 0, before = 0;
        while ((n / i) != 0) {
            current = (n / i) % 10;
            before = n / (i * 10);
            after = n - (n / i) * i;

            if (current > 1)
                count = count + (before + 1) * i;
            else if (current == 0)
                count = count + before * i;
            else if (current == 1)
                count = count + before * i + after + 1;

            i = i * 10;
        }
        return count;
}

参考:http://www.cnblogs.com/jy02414216/archive/2011/03/09/1977724.html


  1. #=
    julia统计0到n之间1的个数.jl
    codegay 2016年4月1日 09:29:23
    写个julia版和python对比下时间
    =#
    function ff1(n)
    result=[length(split(string(r),"1"))-1 for r in 1:n]
    result=sum(result)
    println(result)
    return result
    end
    #ff1(99999999)
    #没有找到julia像python count那样直接统计某个字符串数量的方法,吐槽!
    #80000000
    #[Finished in 24.5s] python版是56s

  2. 我最先想到的就这么解:
    /**
    * 题目:给定一个十进制整数N,求出从1到N的所有正数中出现“1”的个数
    * 思路:对一个整数N,先从1开始到N写成一个字符串,然后把字符串整成字符数组,然后比对
    */
    package com.example.review;

    public class review2 {
    public static void main(String[] args){
    System.out.println(sumOf1(12));
    }

    public static int sumOf1(int N){
    String str = “1″;
    char[] arrayChar;
    int result = 0;
    for(int i = 2;i <= N; i++){
    str = str+String.valueOf(i);
    }
    arrayChar = str.toCharArray();
    for(int i = 0; i < arrayChar.length;i++){
    //System.out.println(arrayChar[i]);
    if(arrayChar[i] == '1'){
    result = result +1;
    }
    }
    return result;
    }
    }

  3. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

  4. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }

  5. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count