Leetcode 233. 数字 1 的个数

  • Leetcode 233. 数字 1 的个数
  • 题目
    • 给定一个整数 n,计算所有小于等于 n 的非负整数中数字 1 出现的个数。
    • 0 <= n <= 10 ^ 9
  • 解法
    • 计算 1 在每一位出现的次数,分为 最低位、中间位(非最低、最高)、最高位 1 出现的次数,假设数字为 abcd,如下
      • 最低位:则最低位出现的次数为 [0,abc)每次都出现,且仅有 d 大于 0 则还加上 abc1
      • 中间位:第二位分为左边 [0,ab]、右边 [0,9],[0,ab)均会出现 [0,9],接下来就看 [ab10,ab19] 出现的次数,使用 n-ab09 小于 0 则为 0,大于 10 则为 10,第三位类似
      • 最高位:首先只要大于 1 位就有最高位,然后最高位没有左边,接着仅需要看 [1000,1999] 有哪些包含即可,使用 n-999 小于 0 则为 0,大于 10 则为 10
    • 时间复杂度:O(logn),空间复杂度:O(1)
  • 代码
    /**
     * 计算 1 在每一位出现的次数,分为 最低位、中间位(非最低、最高)、最高位 1 出现的次数,假设数字为 abcd,如下
     *     最低位:则最低位出现的次数为 [0,abc)每次都出现,且仅有 d 大于 0 则还加上 abc1
     *     中间位:第二位分为左边 [0,ab]、右边 [0,9],[0,ab)均会出现 [0,9],接下来就看 [ab10,ab19] 出现的次数,使用 n-ab09 小于 0 则为 0,大于 10 则为 10,第三位类似
     *     最高位:首先只要大于 1 位就有最高位,然后最高位没有左边,接着仅需要看 [1000,1999] 有哪些包含即可,使用 n-999 小于 0 则为 0,大于 10 则为 10
     * 时间复杂度:O(logn),空间复杂度:O(1)
     */
    private int solution(int n) {
        // 最低位 1 出现的次数:假设 abcd,最低位出现的次数为 [0,abc)每次都出现,且仅有 d 大于 0 则还加上 abc1
        int lowestDigitOne = n / 10 + Math.min(n % 10, 1);

        // 中间位 1 出现的次数(非最低、最高)
        int middleDigitOne = 0;

        // abcd/100=ab 求第二位,abcd/1000=a 求第三位
        long nowDivTen = 100;
        for (; nowDivTen <= n; nowDivTen *= 10) {

            // 第二位分为左边 [0,ab]、右边 [0,9]
            long leftAllDigit = n / nowDivTen + 1;
            long rightAllDigit = nowDivTen / 10;
            // [0,ab)均会出现 [0,9]
            middleDigitOne += (leftAllDigit - 1) * rightAllDigit;

            // [ab10,ab19] 出现的次数,使用 n-ab09 小于 0 则为 0,大于 10 则为 10
            long highestAllDigit = (n / nowDivTen * nowDivTen) + (nowDivTen / 10 - 1);
            middleDigitOne += Math.min(Math.max(n - highestAllDigit, 0), rightAllDigit);
        }

        // 最高位 1 出现的次数
        int highestDigitOne = 0;
        if (n > 9) {
            // 假设 abcd,仅需要看 [1000,1999] 有哪些包含即可,使用 n-999 小于 0 则为 0,大于 1000 则为 1000
            long rightAllDigit = nowDivTen / 10;
            long highestAllDigit = nowDivTen / 10 - 1;
            highestDigitOne += Math.min(Math.max(n - highestAllDigit, 0), rightAllDigit);
        }

//        System.out.println(lowestDigitOne + ":" + middleDigitOne + ":" + highestDigitOne);
        return lowestDigitOne + middleDigitOne + highestDigitOne;
    }

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>