Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.
Solution:
For example '8192':
1-999 -> countDigitOne(999)
1000-1999 -> 1000 of 1s + countDigitOne(999)
2000-2999 -> countDigitOne(999)
.
.
7000-7999 -> countDigitOne(999)
8000-8192 -> countDigitOne(192)
Count of 1s : countDigitOne(999)*8 + 1000 + countDigitOne(192)
Noticed that, if the target is '1192':
Count of 1s : countDigitOne(999)*1 + (1192 - 1000 + 1) + countDigitOne(192)
(1192 - 1000 + 1) is the 1s in thousands from 1000 to 1192.
public int countDigitOne(int n) { if(n <= 0) return 0; if(n < 10) return 1; int base = (int)Math.pow(10, (n+"").length() - 1); int k = n / base; return countDigitOne(base - 1) * k + (k == 1 ? (n-base+1) : base) + countDigitOne(n % base); }
非递归的解法:
int countDigitOne(int n) { int result = 0; int digit = 1, num = n; while (num) { int mod = num % 10; int sign = mod > 0 ? 1 : 0; num /= 10; int a = num * digit; int b = sign * (mod == 1 ? n % digit + 1: digit); result += a + b; digit *= 10; } return result; }
相关推荐
大佬的leetcode刷题笔记(c++版本)
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
LeetCode题解 - Java语言实现-181页.pdf
leetcode 答案Leetcode---数据库 我对 Leetcode 数据库问题的回答
彩色版本 正版 pdf 精讲数据结构 + 算法 链表 树 图表 贪心算法 指针 动态规划 查找算法
leetcode1-300.docx
leetcode 答案leetcode--python Leetcode 的答案
leetcode 回文LeetCode-回文数
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
500195422331430LeetCode题解 - Java语言实现.zip
leetcode 答案LeetCode--哈希表 以上是我对“哈希表”问题的回答,都被leetcode的判断所接受。
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
leetcode 接口 该项目可帮助您使用首选的 IDE 或带有命令行界面 (CLI) 的编辑器来执行 leetcode。 入门 先决条件 Windows 10、MacOS、Linux Chrome版 >=90.0.4430 安装 # Prepare your virtual environment conda ...
leetcode 1 -200题所有源码 有问题私聊我
leetcode1-240题中文题解,md格式,java版本 有题目有题解有代码 需要使用markdown打开
本书包含了 LeetCode Online Judge所有题目的答案,所有代码经过精心编写,编码规范良好,适合读者反复揣摩,模仿,甚至在纸上默写