《剑指Offer》-43.1~n整数中1出现的次数

题干

输入一个整数n，求1～n这n个整数的十进制表示中1出现的次数。例如，输入12，1～12这些整数中包含1的数字有1，10，11和12，1一共出现了5次。

解题思路

举例分析，例如数字21345，可以将1～21345分成两段，1～1345和1346～21345。

先看1346～21345中1出现的次数。分为两种情况，先分析1出现在最高位的情况，在1346～21345中1出现在10000～19999这10000个数字的万位中，一共出现了10000次。而对于最高位是1的情况下，1出现的次数就是剩余位数的数字+1次。

除去最高位之外的4位数中，1出现的次数可以通过排列组合计算，等于最高位的数字*(剩余位数) * 10^(剩余位数-1)。

对于1～1345中1出现的次数可以通过递归的方式计算。

代码实现

<?php
function numberOf1Between1AndN($n)
{
    if ($n <= 0) {
        return 0;
    }

    return numberOf1($n);
}

function numberOf1($n)
{
    if (empty($n) || !is_numeric($n)) {
        return 0;
    }

    $n = (string)$n;

    $first = $n[0];
    $len = strlen($n);
    if ($len == 1 && $first == 0) {
        return 0;
    }
    if ($len == 1 && $first > 0) {
        return 1;
    }

    $numFirstDigit = 0;
    if ($first > 1) {
        $numFirstDigit = pow(10, $len - 1);
    } elseif ($first == 1) {
        $numFirstDigit = intval(substr($n, 1)) + 1;
    }
    $numOtherDigits = $first * ($len - 1) * pow(10, $len - 2);
    $numRecursive = numberOf1(substr($n, 1));

    return $numFirstDigit + $numOtherDigits + $numRecursive;
}

echo numberOf1Between1AndN(999);