題干

輸入一個(gè)整數(shù)n，求1～n這n個(gè)整數(shù)的十進(jìn)制表示中1出現(xiàn)的次數(shù)。例如，輸入12，1～12這些整數(shù)中包含1的數(shù)字有1，10，11和12，1一共出現(xiàn)了5次。

解題思路

舉例分析，例如數(shù)字21345，可以將1～21345分成兩段，1～1345和1346～21345。

先看1346～21345中1出現(xiàn)的次數(shù)。分為兩種情況，先分析1出現(xiàn)在最高位的情況，在1346～21345中1出現(xiàn)在10000～19999這10000個(gè)數(shù)字的萬(wàn)位中，一共出現(xiàn)了10000次。而對(duì)于最高位是1的情況下，1出現(xiàn)的次數(shù)就是剩余位數(shù)的數(shù)字+1次。

除去最高位之外的4位數(shù)中，1出現(xiàn)的次數(shù)可以通過(guò)排列組合計(jì)算，等于最高位的數(shù)字*(剩余位數(shù)) * 10^(剩余位數(shù)-1)。

對(duì)于1～1345中1出現(xiàn)的次數(shù)可以通過(guò)遞歸的方式計(jì)算。

代碼實(shí)現(xiàn)

<?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);