剑指Offer43题 | 1~n整数中1出现的次数
最近在看剑指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个。
- 接下来就简单了,可以将情况分为三种:
- 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)
}
}