LeetCode 233.数字1的个数 - JavaScript

题目描述:给定一个整数 n,计算所有小于等于 n 的非负整数中数字 1 出现的个数。

题目分析

当输入为 13 的时候,结果是 6。因为 1 在以下数字中:1、10、11、12、13,一共出现了 6 次。

直接想到暴力法从 1 遍历到 n,并且通过取模运算计算每个数字中 1 的数目,最后统计总数。这种方法可以得到结果,但是会 TLE。

解法:观察规律

正确的解法是:观察规律,按位计算。

为了方便说明,对于一个数字 n,位数从右到左增加,最右边位数是 1。规定当前位是 bit,那么高位数字指的是:从 bit+1 位到最高位;低位数字指的是:从 bit-1 位到最低位。例如对于 213,如果 bit 是 2(从右到左第 2 位),那么高位数字是 2,低位数字是 3,当前位数字 x 是 1。

若计算在所有小于等于 n 的数字中,第 bit 位上为 1 的数字的数目,应该分 3 种情况讨论:

  • x === 1,那么第 bit 位数上包含的 1 的数目为:高位数字 * 10 ^ (bit-1) + (1 + 低位数字)
  • x < 1,那么第 bit 位数上包含的 1 的数目为:高位数字 * 10 ^ (bit-1)
  • x > 1 ,那么第 bit 位数上包含的 1 的数目为:(高位数字 + 1)* 10^(bit-1)

代码实现如下:

// ac地址:https://leetcode-cn.com/problems/number-of-digit-one/
// 原文地址:https://xxoo521.com/2020-03-10-times-of-one/
/**
 * @param {number} n
 * @return {number}
 */
var countDigitOne = function(n) {
    if (n < 0) {
        return 0;
    }

    let bit = 1;
    let res = 0;
    let high = n;
    while (high) {
        // 高位数字:从第bit+1位到最高位
        high = Math.floor(n / Math.pow(10, bit));
        // 从bit位到最高位
        let tmp = Math.floor(n / Math.pow(10, bit - 1));
        // 当前位
        let current = tmp % 10;
        // 低位数字:从bit-1位到最低位
        let low = n - tmp * Math.pow(10, bit - 1);

        // 以数字213,第2位为例,很好理解
        if (current === 1) {
            res = res + (low + 1) + high * Math.pow(10, bit - 1);
        } else if (current > 1) {
            res = res + (high + 1) * Math.pow(10, bit - 1);
        } else {
            res = res + high * Math.pow(10, bit - 1);
        }
        ++bit;
    }

    return res;
};

更多资料

整理不易,若对您有帮助,请给个「关注+点赞」,您的支持是我更新的动力 👇

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×