[LeetCode]Number of Digit One,解题报告
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了[LeetCode]Number of Digit One,解题报告,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1880字,纯文字阅读大概需要3分钟。
内容图文
![[LeetCode]Number of Digit One,解题报告](/upload/InfoBanner/zyjiaocheng/1122/28d85c1863b244a0a675f8ad4ff8ca8e.jpg)
题目
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.
解题思路
题目理解:
题目的意思是给定一个数n,计算[0, n]的区间中1出现的次数。
具体思路:
在面试过程中如果被问到类似的题目,一定不要着急,因为这肯定是一道找规律的题目。最好的办法是在白纸上写一个差不多大的数,然后分析如何计算每一位1出现的次数。
以24071为例,如果我们想计算百位上1出现的次数,具体思路如下:
- 获取百位的高位为24,获取百位的低位为71,当前百位数字为0。
- 从高位出发来分析,百位出现的次数有:00100~00190,01100~01190,02100~02190,…,23100~23190。总共有(24*100)个1出现。
这是百位为0的情况,如果百位为1的时候,那除了上述的(24*100)个1之外,还包括:24100~24171,共(71 + 1)个1,即总共:24 * 100 + 71 + 1。
如果百位大于1例如为6的时候,那除了最开始的(24*100)个1之外,还包括了:24100~24199,共100个1,即总共:(24 + 1)*100。
总结规律
其实通过上面的分析,我们就可以归纳出一个规律如下。
要求第i位1出现的次数,并且i的高位数为highN,低位数为lowN,当前第i位的数字为cdigit,则当前i位1出现的次数分三种情况:
- cdigit == 0, count = highN * factor.
- cdigit == 1, count = highN * factor + lowN + 1.
- cdigit > 1, count = (highN + 1) * factor.
其中,factor为当前的乘积因子,例如百位的factor为100,十位的乘积因子为10。
有了规律,代码只要按照规律写出来即可。
AC代码
public
class
NumberofDigitOne {
public
int
countDigitOne(int n) {
int count = 0;
long factor = 1;
long cdigit = 0;
long highN = 0;
int lowN = 0;
while (n / factor > 0) {
cdigit = (n % (factor * 10)) / factor;
highN = n / (factor * 10);
if (cdigit == 0) {
count += highN * factor;
} elseif (cdigit == 1) {
count += highN * factor + lowN + 1;
} else {
count += (highN + 1) * factor;
}
lowN += cdigit * factor;
factor *= 10;
}
return count;
}
publicstaticvoidmain(String[] args) {
int n = 1410065408;
NumberofDigitOne ndo = new NumberofDigitOne();
int count = ndo.countDigitOne(n);
System.out.println(count);
}
}
版权声明:本文为博主原创文章,未经博主允许不得转载。
原文:http://blog.csdn.net/wzy_1988/article/details/47148263
内容总结
以上是互联网集市为您收集整理的[LeetCode]Number of Digit One,解题报告全部内容,希望文章能够帮你解决[LeetCode]Number of Digit One,解题报告所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。