题目描述

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

示例

输入：n = 13
输出：6

思路

  1. 既然是1~n整数中1出现的次数，可以拆解为整数n各个位置上所以可能出现1的个数。
  • 例如一个整数n为4位数，那么结果便是第一位、第二位、第三位以及第四位上可能出现1的次数之和。
  1. 每位上出现1的个数依赖于三个位置。

  • 高于该位的数字

  • 该位的数字

  • 低于该位的数字

  • 可以拿401、411以及412的十位做例子。

// 401
// 010 011 012 013 014 015 016 017 018 019
// 110 111 112 113 114 115 116 117 118 119
// 210 211 212 213 214 215 216 217 218 219
// 310 311 312 313 314 315 316 317 318 319

// 411
// 010 011 012 013 014 015 016 017 018 019
// 110 111 112 113 114 115 116 117 118 119
// 210 211 212 213 214 215 216 217 218 219
// 310 311 312 313 314 315 316 317 318 319
// 410 411

// 421
// 010 011 012 013 014 015 016 017 018 019
// 110 111 112 113 114 115 116 117 118 119
// 210 211 212 213 214 215 216 217 218 219
// 310 311 312 313 314 315 316 317 318 319
// 410 411 412 413 414 415 416 417 418 419
  1. 从上面的例子中，设置当前位为current，高位为high，低位为low；
    可以总结出某位上出现1的次数的相关公式(i为10，因为当前位是十位)：
  • 如果current=0；则count = high * i
  • 如果current=1；则count = high * i + low + 1
  • 如果current>1；则count = (high+1) * i
  1. 可以根据得出的公式，从个位开始累加1出现的次数，一直到最高位累加完成为止。

Java代码实现

class Solution {
    public int countDigitOne(int n) {
        int i = 1;
        int res = 0,high = n,current=0,low=0;

        while(high > 0){
            high = high/10;
            current = (n/i)%10;
            low = n - (n/i)*i;

            if(current == 0){
                res = res + high* i;
            }else if(current == 1){
                res = res + high * i + low + 1;
            }else{
                res = res + (high+1)*i;
            }

            i = i * 10;
        }

        return res;
    }
}

Golang代码实现

func countDigitOne(n int) int {
    i := 1
    high,current,low,res := n,0,0,0

    for high > 0  {
        high /= 10
        current = (n/i)%10
        low = n - n/i*i

        if current == 0{
            res = res + high * i;
        }else if current == 1{
            res = res + high *i + low + 1
        }else{
            res = res + (high+1) * i
        }
        i *= 10
    }
    return res
}