30 整数中1出现的次数（从1到n整数中1出现的次数）这题很难要多看*
题目描述
设N = abcde ,其中abcde分别为十进制中各位上的数字。
如果要计算百位上1出现的次数，它要受到3方面的影响：百位上的数字，百位一下（低位）上的数字，百位一上（高位）上的数字。
如果百位上数字为0，百位上可能出现1的次数由更高位决定。比如：12013，则可以知道百位出现1的情况可能是：100~199，1100~1199,2100~2199，，.........，11100~11199，一共1200个。可以看出是由更高位数字（12）决定，并且等于更高位数字（12）乘以 当前位数（100）。
如果百位上数字为1，百位上可能出现1的次数不仅受更高位影响还受低位影响。比如：12113，则可以知道百位受高位影响出现的情况是：100~199，1100~1199,2100~2199，，.........，11100~11199，一共1200个。和上面情况一样，并且等于更高位数字（12）乘以 当前位数（100）。但同时它还受低位影响，百位出现1的情况是：12100~12113,一共114个，等于低位数字（113）+1。
如果百位上数字大于1（2~9），则百位上出现1的情况仅由更高位决定，比如12213，则百位出现1的情况是：100~199,1100~1199，2100~2199，...........，11100~11199,12100~12199,一共有1300个，并且等于更高位数字+1（12+1）乘以当前位数（100）。
/*N = abcde 百位上数字是c
仅以求百位上出现1的情况为例。
*/
int count = ;
//百位上数字为0,百位上可能出现1的次数由更高位决定
if(c == ){
//等于更高位数字（ab）* 当前位数（100）
count += ab*;
}
//百位上数字为1,百位上可能出现1的次数不仅受更高位影响还受低位影响
else if(c == ){
//更高位数字（ab） * 当前位数（100） + 低位数字（de）+1
count += ab* + de + ;
}
//百位上数字大于1（2~9）,百位上出现1的情况仅由更高位决定
else{
//（更高位数字+1（ab+1））* 当前位数（100）
count += (ab + ) * ;
}
这里得到high,cur,low的方法一定要掌握，得到高位需要当前base * 10,得到低位就是利用除法去掉地位的方法，得到当前位的方法就是除法去掉低位后再除以10.举例方法进行解决。
记住n /factor得到的是以factor对应的位结束的高位整数。
long long int Count(long long int n){
//1的个数
long long int count = ;
//当前位
long long int Factor = ;
//低位数字
long long int LowerNum = ;
//当前位数字
long long int CurrNum = ;
//高位数字
long long int HigherNum = ;
if(n <= ){
return ;
}
while(n / Factor != ){
//低位数字
LowerNum = n - (n / Factor) * Factor;
//当前位数字
CurrNum = (n / Factor) % ;
//高位数字
HigherNum = n / (Factor * );
//如果为0,出现1的次数由高位决定
if(CurrNum == ){
//等于高位数字 * 当前位数
count += HigherNum * Factor;
}
//如果为1,出现1的次数由高位和低位决定
else if(CurrNum == ){
//高位数字 * 当前位数 + 低位数字 + 1
count += HigherNum * Factor + LowerNum + ;
}
//如果大于1,出现1的次数由高位决定
else{
//（高位数字+1）* 当前位数
count += (HigherNum + ) * Factor;
}
//前移一位
Factor *= ;
}
return count;
}
leetcode上面这道题必须写成long类型才能通过，写成int不能通过。
public:
int NumberOf1Between1AndN_Solution(int n){
if(n <= ){
return ;
}
unsigned long long base = ;
unsigned long long low = ;
unsigned long long cur = ;
unsigned long long high = ;
unsigned long long cnt = ;
while((n / base) != ){
low = n - (n / base) * base;
cur = (n / base) % ;
high = n / (base * );
if(cur == ){
cnt += high * base;
}
else if(cur == ){
cnt += high * base + low + ;
}
else if(cur > ){
cnt += (high + ) * base;
}
base *= ;
}
return cnt;
}
};
最新文章
- iOS 中自定义 cell，点击cell的时候文字不出现的原因
- Powershell 十个常见任务
- 事务隔离级别（IsolationLevel）
- CodeForces Round#313
- jQuery fullPage.js 全屏滚动
- 1kkk
- [ZOJ 3662] Math Magic (动态规划+状态压缩)
- 图的最短路算法 Dijkstra及其优化
- 转: html5 history api详解~很好的文章
- 【c语言】推断一个数是不是2的n次方
- mysql主键设置成auto_increment时，进行并发性能測试出现主键反复Duplicate entry &#39;xxx&#39; for key &#39;PRIMARY&#39;
- 【Machine Learning in Action --4】朴素贝叶斯从个人广告中获取区域倾向
- ZooKeeper源码分析-Jute-第一部分
- DBoW2算法原理介绍
- React native 中 SectionList用法
- npm -S -D -g i 有什么区别
- sql leetcode -Duplicate Emails
- 定义 java 基本数据类型
- mysql学习之路_外键
- OpenGL教程(25) skybox