LeetCode答题记录233. 数字1的个数

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
输入: 13
输出: 6
解释: 数字 1 出现在以下数字中: 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位数相同 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、计算最高位出现数字1的次数；if:最高位大于1 次数为 10的k次方，k是最高位的位数，等于1：次数为 n-k+1。
2、计算次高位：去掉最高位，计算剩余部分出现数字1的次数。计算方式见下详解
3、当入参位数为1位即 n < 10 时返回1。
这个过程递归，即可求出最终结果

第二步详解：例子n = 2345. 相当于计算0_{999的百位出现1的次数+1000}1999百位出现1的次数+2000~2345百位出现1的次数
也就是0~999百位为1的次数 * 2 + 0~345百位为1的次数