LeetCode 233.数字1的个数 - JavaScript
LeetCode 233.数字1的个数 - JavaScript
心谭博客
发布于 2020-04-21 10:39:21
发布于 2020-04-21 10:39:21
题目描述：给定一个整数 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;
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-03-10，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录