剑指offer31:整数中1出现的次数(从1到n整数中1…
2019-08-27 07:07:38来源:博客园 阅读 ()
剑指offer31:整数中1出现的次数(从1到n整数中1出现的次数)
1 题目描述
求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数?为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数(从1 到 n 中1出现的次数)。2 思路和方法
统计整数n中的每个十进制位中1出现的次数,再累加起来。 对于每一位来说可以把一个数拆分为 前面( begin)+中间( middle)+后面(end )。 1234的百位 = 1+2+34
3 C++核心代码
简洁版:https://blog.csdn.net/typantk/article/details/88386888(讲解的太好了)
1 class Solution { 2 public: 3 int NumberOf1Between1AndN_Solution(int n) 4 { 5 int ones = 0; 6 for (long m = 1; m <= n; m *= 10) 7 ones += (n/m + 8) / 10 * m + (n/m % 10 == 1 ? n%m + 1 : 0); 8 return ones; 9 } 10 };View Code
代码较多
1 class Solution { 2 public: 3 int NumberOf1Between1AndN_Solution(int n) 4 { 5 int temp = n; 6 int last; 7 int result = 0; 8 int base = 1; 9 while(temp){ 10 last = temp%10; //个位数是否为1 11 temp = temp/10; //去掉个位数 12 result += temp*base; 13 if (last==1){ 14 result += n%base + 1; 15 } 16 else if(last>1){ 17 result += base; 18 } 19 base *= 10; 20 } 21 return result; 22 } 23 };View Code
4. C++完整代码
1 #include <iostream> 2 3 using namespace std; 4 5 long long fun(long long n) 6 { 7 if (n < 1) 8 return 0; 9 long long count = 10, num = 0, begin, middle, end, m; 10 begin = n; 11 middle = 0; 12 end = 0; 13 while (begin) 14 { 15 begin = n / count; 16 m = n%count; 17 middle = m / (count / 10); 18 end = m % (count / 10); 19 if (middle > 1) 20 num = num + (count / 10) * (begin + 1); 21 else if (middle == 1) 22 num = num + (count / 10) * begin + (end + 1); 23 else 24 num = num + (count / 10) * begin; 25 count = count * 10; 26 } 27 return num; 28 } 29 30 int main() 31 { 32 long long n, m; 33 while (scanf("%lld %lld", &n, &m) != EOF) 34 { 35 if (n>m) 36 printf("%lld\n", fun(n) - fun(m - 1)); 37 else 38 printf("%lld\n", fun(m) - fun(n - 1)); 39 } 40 printf("%\n"); 41 42 system("pause"); 43 return 0; 44 }View Code
https://blog.csdn.net/zhoubin1992/article/details/47361969
参考资料
https://blog.csdn.net/typantk/article/details/88386888(讲解的太好了)
https://blog.csdn.net/u012477435/article/details/83351659#_873
原文链接:https://www.cnblogs.com/wxwhnu/p/11415964.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- [题记]字符串转换整数-leetcode 2020-04-03
- L1-008 求整数段和 (10分) 2020-03-22
- 整数去重 2020-02-23
- 剑指offer笔记面试题1----赋值运算符函数 2019-10-18
- 又是a+b 2019-09-08
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash