谷歌笔试题解析：递推公式解算法题

"这篇文本包含了两道谷歌笔试题目及其解答，分别是计算数字中1的个数和寻找集合中满足A+B=C的最大C。" 第一道题目是关于计算一个数字n中1的出现次数。这个问题可以通过递推公式来解决。首先，我们需要确定n的位数L，然后计算出10的L-1次方s。接着，找到n的第一位数字a，即n除以s的结果。递推公式如下： - 当n小于9时，直接返回n的值，如果n大于0则返回1，否则返回0。 - 对于n大于9的情况，1的总数由三部分组成： 1. 所有数中第一位有多少个1，这部分可以用 `(a>1 ? s : n - s*a + 1)` 来计算。 2. 对应a乘以f(s-1)的1的数量，即a后面所有数中1的总数。 3. 对应f(n-s*a)的1的数量，即去掉最高位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中满足A+B=C的最大C。解决这个问题的方法是首先对集合S进行排序，然后使用双指针法遍历集合。具体步骤如下： 1. 将集合S中的所有元素按照升序排列。 2. 初始化两个指针i和j，分别从集合的末尾和开头开始，同时初始化一个k指针指向i-1的位置。 3. 在每次循环中，检查Xj+Xk是否大于Xi，如果是，则减小k；如果小于Xi，则增大j。如果相等，说明找到了满足条件的A、B、C，其中A=Xj，B=Xk，C=Xi，此时可以退出循环。 4. 如果遍历完所有可能的组合都没有找到满足条件的A、B、C，那么说明不存在这样的C。 例如，对于集合S = {1, 4, 7, 10, 11, 13, 15, 18, 34}，我们首先排序得到S = {1, 4, 7, 10, 11, 13, 15, 18, 34}，然后进行双指针遍历，可以找到最大的C=34，对应的A=1，B=33，满足A+B=C。 这两道题目都是典型的算法问题，通过递推和双指针技术，我们可以有效地解决问题。这样的练习对于提升编程思维和解决实际问题的能力有很大帮助，特别是在面试和笔试中。