整数中1出现的次数（从1到n整数中1出现的次数）

题目描述

求出1-13的整数中1出现的次数,并算出100-1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

分析

设数字 n 是个 x 位数，记 n 的第 i 位为 n_i

• n _i 为当前位，记为 cur
• n _i 的左边为低位，记为 low
• n _i 的右边为高位，记为 high
• 10 ^ i 为位因子，记为位因子，记为 digit

由 参考 可知如下规律：

1. 当cur = 0时： 此位 1 的出现次数只由高位 high 决定，计算公式为：high × digit
2. 当cur = 1时： 此位 1 的出现次数由 high 和 low 决定，计算公式为：high × digit + low + 1
3. 当cur > 1时： 此位 1 的出现次数只由高位 high 决定，计算公式为：high × digit + digit

代码

<?php

namespace app\index\controller;

class Test
{
    // 测试
    public function test()
    {
        $n   = 2031;
        $res = $this->NumberOf1Between1AndN_Solution($n);
    }

    function NumberOf1Between1AndN_Solution($n)
    {
        $high  = floor($n / 10);        // 高位
        $cur   = $n % 10;               // 当前位
        $low   = 0;                     // 低位
        $res   = 0;                     // 结果
        $digit = 1;                     // 位因子

        while ($high != 0 || $cur != 0) {          // 最高位不为0，或当前不为0
            if ($cur == 0)
                $res += $high * $digit;            // 当前数字为0，则由高位数决定
            elseif ($cur == 1)
                $res += $high * $digit + $low + 1; // 当前数为1，则由高位和低位决定
            else
                $res += ($high + 1) * $digit;      // 当前数大于1，则由高位数决定

            $low   = $low + $cur * $digit;
            $cur   = $high % 10;
            $high  = floor($high / 10);
            $digit = $digit * 10;
        }
        return $res;
    }
}