給定一個整數(shù) n烦绳，計算所有小于等于 n 的非負整數(shù)中數(shù)字 1 出現(xiàn)的個數(shù)犯戏。
輸入: 13
輸出: 6
解釋: 數(shù)字 1 出現(xiàn)在以下數(shù)字中: 1, 10, 11, 12, 13 仲智。
func countDigitOne(_ n: Int) -> Int {
var inN = n
var k = 1;
while inN >= 10 {
inN = inN / 10
k *= 10;
}
return self.calculate(n, k)
}
func calculate(_ n: Int, _ k: Int) -> Int {
//保證k與n位數(shù)相同 k = "1","10","100"...
if n < 1 {
return 0
}
if n < 10 {
return 1
}
var inK = k;
while n / inK < 1 {
inK /= 10
}
var c = 0;
c = n / inK;
if c == 1 {
return (n - inK + 1) + self.calculate(n-inK, inK/10) + self.calculate(inK-1,inK/10)
}else {
return inK + calculate(n-c*inK,inK/10) + c * self.calculate(inK-1,inK/10)
}
}
解法：遞歸求解。
1锈死、計算最高位出現(xiàn)數(shù)字1的次數(shù)贫堰；if:最高位大于1 次數(shù)為 10的k次方，k是最高位的位數(shù)待牵，等于1：次數(shù)為 n-k+1其屏。
2、計算次高位：去掉最高位缨该，計算剩余部分出現(xiàn)數(shù)字1的次數(shù)偎行。計算方式見下詳解
3、當入?yún)⑽粩?shù)為1位即 n < 10 時返回1贰拿。
這個過程遞歸蛤袒，即可求出最終結(jié)果
第二步詳解：例子n = 2345. 相當于計算0999的百位出現(xiàn)1的次數(shù)+10001999百位出現(xiàn)1的次數(shù)+2000~2345百位出現(xiàn)1的次數(shù)
也就是0~999百位為1的次數(shù) * 2 + 0~345百位為1的次數(shù)
