Markdown在线编辑器 - www.MdEditor.com
欢迎使用 Markdown在线编辑器 MdEditor
题目
求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
解题思路
核心想法： 求每个位上出现1的次数
如求出现在十位上1的次数
十位出现1的所有组合情况 共10个
10
11 只算十位出现的1 算1个
……
19
关键就是有多少种情况见下图
代码
int NumberOf1Between1AndN_Solution(int n) { int count = 0; int weight; // 个位对应1 十位对应2 百位对应3 int max_weight = 0; // 最高位数 //求最高位数 int tmp = n; while (tmp != 0){ max_weight++; tmp /= 10; } //依次不同位出现次数累加 int front = 0, current =0,behind = 0; int uint = 1; // 第i位对应1后i-1个0 for (int i = 1; i <= max_weight; i++) { uint = 1; for (int j = 1; j <= i - 1; j++) { uint *= 10; } front = n/(uint*10); // 去掉后i位 current = (n / (uint)) % 10; //得到第i位 behind = n % (uint); // 只剩后i-1位 if(current == 0){ count += front * uint; } else if(current == 1){ count += front * uint + behind + 1; } else if (current > 1) { count += front * uint + uint; } } return count; }
End
