剑指 Offer 43 - 1~n 整数中 1 出现的次数
# 📃 题目描述
题目链接:剑指 Offer 43. 1~n 整数中 1 出现的次数 (opens new window)
注意这里是十进制,而不是二进制!
# 🔔 解题思路
直接看 LeetCode 官方题解 (opens new window) 就行
我们可以从小到大枚举 k。如果 n≥10^k,说明 n 包含 10^k 对应的数位,我们就可以计算这一数位 1 的个数并累加,否则退出枚举(比如 n>=10^2(100),说明 n 是有百位的,我们就可以计算从 1 ~ n 百位上 1 的个数)。
class Solution {
public int countDigitOne(int n) {
int count = 0;
// k = 0 表示个位,k = 10 表示十位......
for (int k = 0; n >= Math.pow(10, k); k ++) {
long mulk = (long) Math.pow(10, k);
count += (n / (mulk * 10)) * mulk;
// 剩下数的最高位有多少个 1
long rest = n % (mulk * 10);
// if (rest < mulk) {
// count += 0;
// }
if (rest >= mulk && rest < mulk + mulk) {
count += rest - mulk + 1;
}
else if (rest >= mulk + mulk) {
count += mulk;
}
}
return count;
}
}
# 💥 复杂度分析
- 空间复杂度:O(1)
- 时间复杂度:O(LogN)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10