Google笔试题解析：递推公式解数字1出现次数

"这篇资源主要包含了两道Google的笔试题，一道是要求编写一个函数，计算从1到给定整数n之间1出现的次数，另一道是寻找集合S中最大的C，使得A+B=C，其中A、B、C都在集合S中。资源提供了部分解法，包括递推公式实现的Java代码以及原创的解答思路。" 在这篇资源中，首先讨论的题目是关于计算1出现次数的问题。给定一个正整数n，我们需要找出从1到n的所有数中数字1出现的总数。一种常见的解决方法是通过递推公式来实现。递推公式如下： - 当n < 9时，直接返回n的值，因为此时n本身就是一个一位数，所以1的个数就是n（如果n > 0）或0（如果n = 0）。 - 对于更大的n，我们可以将其拆分为首位数字a和其余部分n-s*a，其中s是10的n位数减1次方。递推公式为： - (a>1?s:n-s*a+1)：表示所有数中第一位为1的个数。 - a * f(s-1)：表示首位数字a乘以去掉首位后的数字1的个数。 - f(n-s*a)：表示去掉首位数字a后的数字1的个数。 提供的Java代码实现如下： ```java long f(long n) { if (n < 9) return n > 0 ? 1 : 0; int L = (int) (Math.log10(n) + 1); // 求n的位数 long s = (long) Math.pow(10, L - 1); // 求10的L-1次方 long a = (long) (n / s); // 求n的第一位数字 return (a > 1 ? s : n - s * a + 1) + a * f(s - 1) + f(n - s * a); } ``` 第二道题目是寻找集合S中的最大C。这个问题可以通过排序集合S，然后使用两个指针j和k从两端向中间遍历，比较Xj + Xk与Xi的关系来解决。如果Xj + Xk > Xi，则减小k；如果Xj + Xk < Xi，则增加j。一旦找到满足条件的A、B、C，就可以结束遍历。以下是一个简单的示例： ```markdown 例子： 集合S: 1, 4, 7, 10 - i = 4, j = 0, k = 3 -> Xj + Xk = 1 + 7 > Xi = 10, k-- -> k = 2 - i = 4, j = 0, k = 2 -> Xj + Xk = 1 + 7 = Xi = 10, A = 1, B = 7, C = 10 ``` 这个资源对于准备Google笔试或面试的IT从业者来说非常有价值，它不仅提供了具体的题目，还包含了解题思路和代码实现，有助于提升算法和问题解决能力。