Skip to content

Latest commit

 

History

History
75 lines (67 loc) · 4.25 KB

countDigitOne.md

File metadata and controls

75 lines (67 loc) · 4.25 KB
Raw

面试题43. 1～n整数中1出现的次数

原题

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

示例 1： 输入：n = 12 输出：5

示例 2： 输入：n = 13 输出：6

限制： 1 <= n < 2^31 注意：本题与主站 233 题相同：https://leetcode-cn.com/problems/number-of-digit-one/

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof

解法

class Solution {
    private static int[] count = {0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000};
    public int countDigitOne(int n) {
        int res = 0;
        int index = 0, pow = 1, pre = 0;
        while (n != 0) {
            int num = n % 10;
            if (num == 1) {
                res += pre + 1 + count[index];
            } else if (num > 1) {
                res += pow + num * count[index];
            }
            pre = pre + num * pow;
            pow *= 10;
            index++;
            n /= 10;
        }
        return res;
    }
}

思路分析：

  • 用暴力法肯定会超时，所以这个题得找规律。
  • 1-9这几个一位数中，只有1个1。
  • 1-99这些数字，如果分为1-9，10-19，20-29……90-99，不看十位刚好是十组1-9，有10*1个1，但是10-19这一组是特殊的，每个数字的十位都是1，又贡献了10个1。所以1-99这些数字一共有$1 * 10 + 10 ^ 1 = 20$个1。
  • 对于1-999，同样拆分为1-99，100-199，……900-999，不看百位刚好是十组1-99，有10*20个1，但是100-199这一组是特殊的，每个数字百位都是1，又贡献了100个1，所以这些数字一个有$10 * 20 + 10^2 = 300$个1。
  • 以此类推1-9999有$10 * 300 + 10^3 = 4000$个1，1-99999有50000个1……观察n的范围最多有十位，所以我们枚举到900000000即可。为什么要进行这样的计算呢？其实从上面的计算过程发现，拆分很重要，更大的数字范围是通过拆分为小的范围计算的。
  • 尝试一下拆分：比如数字1-439。
    • 可以将其拆分为1-9，（01-09，10-19，20-29），（001-099，100-199，200-299，300-399）.
    • 这样就可以视为1组1-9，三组1-9加上一组十位均为1的数字，四组1-99加上一组百位均为1的数字。
    • 其结果为$1 + 1 * 3 + 10^1 + 20 * 4 + 10^2 = 194$。
  • 再来举一个例子：比如数字2359。
    • 拆分为1-9，（01-09，10-19，20-29，30-39，40-49），（001-099，100-199，200-299），（0001-999，1000-1999）。
    • 所以计算结果为$1 + 5 * 1 + 10 ^ 1 + 3 * 20 + 10 ^ 2 + 2 * 300 + 10 ^ 3 = 1776$。
  • 所以刚才先枚举出来1-9，1-99，1-999……1-999999999一共多少个1，就是为了方便计算的时候直接使用。通过刚才的例子可以发现：
    • 拆分的过程，其实就是每一位的数字去查看需要拆分为多少个组合。既然需要知道n的每一位数字，就需要使用while循环，每次num = n % 10，进行当前位的拆分与计算贡献了多少个1之后，需要移位n /= 10。
    • 计算每一位贡献多少时，需要知道10^k次，比如个位对应k=0，十位对应k=1……。为了不重复计算幂次，使用pow来存放10的k次，一开始处理个位，所以初始pow = 1时，在当前位计算完毕后pow *= 10;。
    • 计算每一位贡献多少时，还需要知道这次拆分的组合，能贡献多少个1（最高位为1的组合由最高位贡献的已经在上一个tip中计算过了），这个就需要使用count[]了，我们使用变量index表示该取count的哪个元素。对于个位拆分得到的组合，这一项的计算取0，对于十位拆分出来的组合，这一项计算取1……，所以初始时候index = 0，在当前位计算完毕后index++。
    • 然后整个计算过程对每一位的结果pow + num * count[index];进行累加。（num * count[index]，第一个因子表示拆分出来的组合数目）
  • 这么看好像是对了，但是忘记考虑某一位特殊的数字0与1，
    • 如果是0，那么这一位拆分不出来任何数字，当然不能按刚才的计算式计算，跳过计算，只更新其他变量。
    • 但是如果是1，最高位为1的组合的数字就不完整，它的数量不是pow，这个组合的数字数量取决于前置位共有多少个数字。比如1000-1421，共有421 + 1个数字，由最高位只能贡献422个1。所以在我们的循环过程中还需要记录前置位共有多少个数字，使用变量pre，所以当num == 1时，应该是这样计算res += pre + 1 + count[index];。计算完后，要更新pre = pre + num * pow;。
  • 时间复杂度为$O(1)$，因为数字最大才2^31，十次while循环的执行就结束了。空间复杂度，只使用了常数大小的数组及几个辅助变量，为$O(1)$。

运行结果：

  • 执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗 :36.6 MB, 在所有 Java 提交中击败了100.00%的用户