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

题目

输入一个整数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时的组合个数

---

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

---

举例3：当n=2220时，计算其百位上为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种

若n的十位为1： 组合数为220种

若n的百位为1： 组合数为200+35=255种

若n的千位为1： 组合数为1000种

共计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~