解惑

解己之惑,解人之惑

Google面试题解说性能之六:数学显神威

其实很多问题一旦涉及到数学问题或者数据处理密集型问题,那么最终显现神威的就是数学公式,这个面试题也是这类问题,所以如果我们能够推导出一个数学公式就是最理想的,在前面的例子中,我们进行了一些深入的分析,根据前面的例子,你可能会尝试把步长从100扩展到1000或者10000,但是实际上这个方法遇到了瓶颈,因为循环嵌套的层次太多,计算公式太复杂也会导致问题。如果我们最开始尝试的时候把全部的f(n)的结果打印出来,你会发现这样的内容:

  1. f(9) = 1
  2. f(99) = 20
  3. f(999) = 300
  4. f(9999) = 4000
  5. ……

这个是我们的第一个规律:位数乘以((位数-1)的10的次方)。
根据这个f(n)的说明,我们定义另外一个方法x(n),它的定义就是n这个数包含的1的个数,例如x(1)=1,x(2)=0,x(11)=2,那么我们可以把f(n)展开为:
f(n)=x(0)+x(1)+……+x(n)
同时我们可以把x(n)也展开,假设n=XYZ,那么x(n)的展开式为:
x(n)= x(X)+x(Y)+x(Z)
也等于:
x(n)= x(X)+x(YZ)
再结合上面的规律我们就可以推导出一个规律了,先用例子来说明,以106为例:
f(106) = x(0)+…+x(99)+x(100)+…+x(106) = f(99) + x(100)+…+x(106)
f(99)我们使用上面的第一个规律很容易计算得到,那么后面的这7个数包含多少个1呢,其实也很简单,应用可能小学就学过的公因子概念,当然这里不是真正的公因子,而是这些数里面包含的1的个数相同的部分,结合x(n)的展开式,我们进一步推演出:
f(106) = f(99) + x(1)+ x(00)+x(1)+x(01)+…+x(1)+x(06) = f(99) + x(1) * (6+1) + x(00) + .. x(06) = f(99) + x(1) * (6+1) + f(6)
这样计算就很简单了,不是吗?
好,再看看f(345)的情况,有点不太一样:
f(345) = x(0)+…x(99)+x(100)+…+x(199)+x(200)+..+x(299)+x(300)+…+x(345)= f(99) + x(1) * (99+1) + f(99)+ x(2)*(99+1)+f(99)+x(3)*(45+1)+f(45)
这个例子足够典型了吗?看到规律了吗?
给定一个数n,假设最高位为x,除去最高位的数字为y,位数为z,那么
如果x=1,那么f(n)等于f(pow(10,z-1)-1)+(y+1)+f(y)
如果x>1,那么f(n)等于f(pow(10,z-1)-1)*x+pow(10,z-1)+f(y)

转换为代码就是:

private static int fn(int number) {
if (number < 10) {
return number > 0 ? 1 : 0;
}
String s = number + “”;
int length = s.length();
int end = Integer.parseInt(s.substring(1, length));
int x = s.charAt(0) – ‘0’;
int result = 0;
if (x == 1) {
result = (length – 1) * (int) Math.pow(10, length – 1 – 1) + fn(end)
+ (end + 1);
} else {
result = (length – 1) * (int) Math.pow(10, length – 1 – 1) * x
+ (int) Math.pow(10, length – 1) + fn(end);
}
return result;
}

你可以运行试试这个公式是否准确。
最后需要强调一下的是,这个方法可以快速的计算给定的一个数的f(n)的结果,但是如果用一个简单的循环来查找符合f(n)=n的结果是不合适的,这个我会另外再谈的。

  1. Google面试题解说性能之一:字符串运算VS数字运算

  2. Google面试题解说性能之二:分析问题

  3. Google面试题解说性能之三:不要小看循环中的任何一个语句

  4. Google面试题解说性能之四:优化无止境

  5. Google面试题解说性能之五:人比电脑聪明

  6. Google面试题解说性能之六:数学显神威

  7. Google面试题解说性能之七:缓存中间结果

  8. Google面试题解说性能之八:工欲善其事必先利其器

  9. Google面试题解说性能之总结

(Visited 70 times, 1 visits today)

1 Comment

  1. 这个规律真不错
    可惜只能看看了
    自己没这个精力和时间来搞呀

发表评论

电子邮件地址不会被公开。 必填项已用*标注

© 2019 解惑

本主题由Anders Noren提供向上 ↑