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;
};

# 更多资料

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