题目描述
求出 1~13 的整数中 1 出现的次数, 并算出 100~1300 的整数中 1 出现的次数? 为此他特别数了一下 1~13 中包含 1 的数字有 1,10,11,12,13 因此共出现 6 次, 但是对于后面问题他就没辙了. ACMer 希望你们帮帮他, 并把问题更加普遍化, 可以很快的求出任意非负整数区间中 1 出现的次数(从 1 到 n 中 1 出现的次数).
解题思路:
分析每一位出现等于 0, 等于 1, 大于 1 的情况.
case1 : 为 0 的情况:
对于 250 这个数字, 个位为 0 时, 个位可能出现 1 的情况是 25 种, 如 1, 11, 21 ... 101, 111,121 ... 201,211... 241 , 其实可以看出是 0 前面的 25*1 的结果.
对于 205 这个数字, 十位为 0 时, 那么十位可能出现 1 的情况为 20 种, 如 10, 11, 12 ...110,111,112..119 , 其实可以看出是 0 前面的 2*10 的结果.
case2: 大于 1 的情况:
对于 22 这个数字, 个位大于 1 时, 个位可能出现 1 的情况有 3 种, 如 1, 11, 21, 其实可以看出是前面的 2*1+1 的结果.
对于 224 这个数字, 十位大于 1 时, 十位可能出现 1 的情况有 30 种, 如 10,11,12...19,110,111,112... 119,210,211,212...219, 其实可以看出是前面的(2+1)*10 的结果.
case3: 等于 1 的情况:
对于 21 这个数字, 个位等于 1 时, 个位出现 1 的情况有 3 种, 如 1,11,21, 其实可以看做是 2*1+(0+1)
对于 212 这个数字, 十位等于 1 时, 十位出现 1 的情况有 23 种, 如 10,11,12...19,110,111,112...119,210,211,212, 其实可以看做 2*10+(2+1)的结果. 2*10 的 2 表示 212 在百位上可以取值 0-1, 而 (2+1) 中则表示当百位为 2, 十位为 1 时, 后面的个位可取的范围为 0-2 一共 3 个数字.
- class Solution {
- public:
- int NumberOf1Between1AndN_Solution(int n)
- {
- int vsum = 0;
- int nn = n;
- int Md = 1;
- while(n != 0){
- int pv = n%10;
- int prev = n/10;
- Md *= 10;
- n /= 10;
- if(pv == 0){
- vsum += (nn/Md) * Md/10;
- }else if(pv == 1){
- if(Md == 10){
- // 特判当个位为 1 的情况
- vsum += (nn/Md)* Md/10 + 1;
- }else{
- vsum += (nn/Md)* Md/10 + (nn%(Md/10)+1);
- }
- }else{
- vsum += ((nn/Md) + 1) * Md/10;
- }
- }
- return vsum;
- }
- };
整数中 1 出现的次数(从 1 到 n 整数中 1 出现的次数)
来源: http://www.bubuko.com/infodetail-3015799.html