剑指Offer43题 | 1~n整数中1出现的次数

admin · 2020-02-19

最近在看剑指Offer，因为没学过C++，所以看代码挺别扭，一般都是看完题目自己解决一下再看看作者的思路，收获还是有一些的。虽然感觉这本书题目偏简单，但是面试中能找到最优解且完美实现还是挺有难度的。

今天看的43题是这样描述的：
输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

首先，暴力法就不考虑了，这种题一看就是要找规律的，书中的解法如下：

以21345为例，将其分为1 ~ 1345和1346 ~ 21345两段，

其中1346~21345中1出现的次数分为两种情况

出现在最高位（本例中为万位）的情况：10000~19999一共出现了10000次，但如果万位的数字为1如12345,1只出现在10000 ~ 12345的万位，总共2346次。
出现在除最高位之外其他4位数中的情况：由于最高位为2，可以将1346 ~ 21345分成1346 ~ 11345和11346 ~ 21345两段，每一段剩下4位数字中选1位为1，其余三位0~9中任意选择，根据排列组合1共出现2×4×10³=8000次。

最后递归求解1~1345，代码如下：

func countDigitOne(n int) int {
    strN := strconv.Itoa(n)
    return numberOf1(strN)
}

func numberOf1(strN string) int {
    if len(strN) == 0 {
        return 0
    }
    first := int(strN[0] - '0')
    if len(strN) == 1 && first == 0 {
        return 0
    }
    if len(strN) == 1 && first > 0 {
        return 1
    }
    var numFirstDigit int
    if first > 1 {
        numFirstDigit = int(math.Pow10(len(strN) - 1))
    } else if first == 1 {
        post, _ := strconv.Atoi(strN[1:])
        numFirstDigit = post + 1
    }
    numOtherDigits := first * (len(strN) - 1) * int(math.Pow10(len(strN)-2))
    numRecursive := numberOf1(strN[1:])
    return numFirstDigit + numOtherDigits + numRecursive
}

作者的思路很巧妙，不过我在思考的时候是从另一个角度入手的，即累计个位、十位、百位……的1出现的次数。

为了快速找到规律，我们可以直接分析1 ~ n的十位上1的个数。
十位上的有1的数包括
10,11,12...19,......,
110,111...119,......,
210,211...219......
不难看出，100以内有10个，200以内有20个……，当然，事情要比这稍微复杂一点，

如果n是105，那么1 ~ 109中符合条件的只有10 ~ 19，一共10个；
如果n是115，那么符合条件的有10 ~ 19,110 ~ 115，一共10+6=16个；
如果n是125，那么符合条件的有10 ~ 19,110 ~ 119，一共20个。

1出现的次数折线图

接下来就简单了，可以将情况分为三种：

n%100 < 10 => (n/100) * 10
10 <= n%100 < 20 => (n/100) * 10 + n%100 - 10 + 1
n%100 >= 20 => (n/100) * 10 + 10

而每次统计是以10为倍数的，所以可以定义一个pow变量表示10的N次方，考虑十位上的1时，pow=10，将公式转化为

n/(pow * 10) * pow
n/(pow * 10) * pow + n%(pow * 10) - pow + 1
n/(pow * 10) * pow + pow

上述公式对于个位也是适用的，可以分为n%10 < 1，n%10 >= 2，和n%10 = 1三种情况，后两种结果一样。
循环的结束条件取决于n最多有多少位，每次pow * 10，n小于pow退出。

最后附上代码：

func countDigitOne(n int) int {
    count, pow := 0, 1
    for n >= pow {
        count += n / (pow * 10) * pow
        if incr := n%(pow*10) - pow + 1; incr > pow {
            count += pow
        } else if incr > 0 {
            count += incr
        }
        pow *= 10
    }
    return count
}

性能对比

package interview

import "testing"

var n = 1<<31 - 1

// 循环相加求解
func BenchmarkCountDigitOne1(b *testing.B) {
    for i := 0; i < b.N; i++ {
        countDigitOne1(n)
    }
}

// 书中方法，递归
func BenchmarkCountDigitOne2(b *testing.B) {
    for i := 0; i < b.N; i++ {
        countDigitOne2(n)
    }
}

两种方法benchmark对比