脚本宝典收集整理的这篇文章主要介绍了LeetCode 233 : Number of Digit One (java),脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
题目:
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,求从1到n所有数中数字1在各个位上出现的总次数。
解法:
可以做循环从1到n挨个找。慢。
更好的是用归纳法总结出1出现的次数的规律。
假设n=abcde五位数字的时候,我们分析百位c,有三种情况:
1)c == 0的时候,比如12013,此时百位出现1的是:00 100 ~ 00 199, 01 100~01 199,……,11 100~ 11 199,共1200个,显然这个有高位数字决定,并且受当前位数影响; 个数就是 ab*100
2)c == 1的时候,比如12113,此时百位出现1的肯定包括c=0的情况,另外还需要考虑低位的情况即:00100 ~ 00113共14个; 个数等于ab*100+ de + 1
3)c >= 2的时候,比如12213,此时百位出现1的是:00 100 ~ 00 199, 01 100~01 199,……,11 100~ 11 199,12 100 ~ 12 199,共1300个,这个有高位数字决定,其实是加一,并且乘以当前位数; 个数就是 (ab+1)*100
总结起来,对于一个 n = abcde 来说,百位出现1的个数计算方法为 :
if(c==0) ans = ab*100;
if(c==1) ans = ab*100+cd+1
if(c>1) ans = (ab+1)*100
代码:
public class Solution { public int countDigitOne(int n) { if(n <= 0) return 0; int q = n; int x = 1; int ans = 0; int temp = 0; do{ temp = q%10; q/=10; if(temp == 0) ans+=q*x; else if(temp == 1) ans+=q*x + n%x + 1; else ans+=(q+1)*x; x*=10; } while (q > 0); return ans; } }
Ref:
以上是脚本宝典为你收集整理的LeetCode 233 : Number of Digit One (java)全部内容,希望文章能够帮你解决LeetCode 233 : Number of Digit One (java)所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。