題干
輸入一個(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);
