cmatrixprobe

发呆业务爱好者

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

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


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


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

以21345为例,将其分为1 ~ 13451346 ~ 21345两段,

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

  1. 出现在最高位(本例中为万位)的情况:10000~19999一共出现了10000次,但如果万位的数字为1如12345,1只出现在10000 ~ 12345的万位,总共2346次。

  2. 出现在除最高位之外其他4位数中的情况:由于最高位为2,可以将1346 ~ 21345分成1346 ~ 1134511346 ~ 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个……,当然,事情要比这稍微复杂一点,

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

1出现的次数折线图

  • 接下来就简单了,可以将情况分为三种:
  1. n%100 < 10 => (n/100) * 10
  2. 10 <= n%100 < 20 => (n/100) * 10 + n%100 - 10 + 1
  3. n%100 >= 20 => (n/100) * 10 + 10
  • 而每次统计是以10为倍数的,所以可以定义一个pow变量表示10的N次方,考虑十位上的1时,pow=10,将公式转化为
  1. n/(pow * 10) * pow
  2. n/(pow * 10) * pow + n%(pow * 10) - pow + 1
  3. 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对比

Goroutine调度(本地执行队列顺序)

上一篇

二叉树的递归遍历与recover

下一篇
评论
头像 发表评论 说点什么
还没有评论
1623
2