欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

《剑指Offer》计算从1到n整数中1出现的次数

程序员文章站 2022-07-10 13:35:04
...

题目

输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。例如输入12,从1到12这些整数中包含1的数字有1,10,11和12,1一共出现了5次

PS:牛客链接LeetCode链接


方法一(Brute Force)

思路: 直接遍历1~n之间的每个数字,每次循环使用先取余(%10)后自除以10的方式,统计每个数字的各个数位上1出现的次数,并累加,然后返回总和

复杂度分析: 时间复杂度:O(n*logn),空间复杂度:O(1)

代码:


方法二

思路: 将n的各个数位的值看做是能够在0~9之间任意变换的数,则题目的要求可以理解为求解组合值小于n的组合中数字1出现的次数。

举例1:当n=2020时,计算其百位上为1时的组合个数

《剑指Offer》计算从1到n整数中1出现的次数


举例2:当n=2120时,计算其百位上为1时的组合个数

《剑指Offer》计算从1到n整数中1出现的次数


举例3:当n=2220时,计算其百位上为1时的组合个数

《剑指Offer》计算从1到n整数中1出现的次数


规律总结:

x为数n的右边起第i(i>=0)个数位上的数值,left为n中第i位左侧数字组成的值,right为n中第i位的右侧数字组成的值,则:

1. 当x==0时: 当前数位上值为1的组合值个数为left*10^i

2. 当x==1时: 当前数位上值为1的组合值个数为left*10^i+right+1

3. 当x>1时: 当前数位上值为1的组合值个数为(left+1)*10^i


举例4:当n=2134时,计算1~n中数字1出现的次数

若n的个位为1: 组合数为214

《剑指Offer》计算从1到n整数中1出现的次数

若n的十位为1: 组合数为220

《剑指Offer》计算从1到n整数中1出现的次数

若n的百位为1: 组合数为200+35=255
《剑指Offer》计算从1到n整数中1出现的次数

若n的千位为1: 组合数为1000
《剑指Offer》计算从1到n整数中1出现的次数

共计1669种组合,即在1~2134范围内的整数中,1出现的次数为1669次


本人代码(Java):

public class Solution {
    public int countDigitOne(int n) {
        // 左侧数值,当前数位的数值,右侧数值
        long leftNum,curNum,rightNum;
        // 当前数位,数字1出现的次数
        long k = 1,count = 0;
        while(k<=n){
            leftNum = n/k/10;
            curNum = n/k%10;
            rightNum = n%k;
            if(curNum == 1) count += leftNum*k+rightNum+1;
            else if(curNum > 1) count += (leftNum+1)*k;
            else count += leftNum*k;
            k*=10;
        }
        return count;
    }
}

复杂度分析: 时间复杂度:O(logn),空间复杂度:O(1)


大神代码(Java):

public int countDigitOne(int n) {
  int count = 0;
    
  for (long k = 1; k <= n; k *= 10) {
    long r = n / k, m = n % k;
    // sum up the count of ones on every place k
    count += (r + 8) / 10 * k + (r % 10 == 1 ? m + 1 : 0);
  }
    
  return count;
}

End~