整数中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 位为 ni

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

LoQLdJHPyd.png!large

参考 可知如下规律:

  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;
    }
}

本文章首发在 LearnKu.com 网站上。

上一篇 下一篇
讨论数量: 0
发起讨论 只看当前版本


暂无话题~