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(234)的情况，有点不太一样：
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的结果是不合适的，这个我会另外再谈的。

---

作者: Cherami
原载: 解惑
版权所有。转载时必须以链接形式注明作者和原始出处及本声明。
分类: Java