例1 给定一个数n, 求不超过n的所有的能被3或者5整除的数的和。例如: n = 9，答案3 + 6 + 5 + 9 = 23。

分析 ： 数学问题

被3整除的数， 3,6,9,…[n / 3] * 3

被5整除的数， 5,10,15, [n / 5] * 5

重复的数同时是3和5的倍数 15, 30, …[n / 15] * 15

需要注意n的取值范围

方案

等差数列求和公式

x是首项，y是项数, d是公差

(x + x + d * (y – 1)) * y / 2, 注意y = 0也适用

关键是项数!

加 x = 3, d = 3, y = n / 3

加 x = 5, d = 5, y = n / 5

减 x = 15, d = 15, y = n / 15

例2 字符串只有可能有A、B、C三个字母组成，如果任何紧邻的三个字母相同，就非法。求长度为n的合法字符串有多少个？比如： ABBBCA是非法，ACCBCCA是合法的。

分析 ： 动态规划的思路——真的要枚举么？

dp[i][0] : 长度为i的、最后两位不同的合法串的个数

dp[i][1]: 长度为 i的、最后两位相同的合法串的个数

递推: dp[i][0] = (dp[i-1][0] * 2 + dp[i-1][1] * 2)

dp[i][1] = dp[i-1][0]

方案 ：

初值：dp[1][0] = 3, dp[1][1] = 0

结果：dp[n][0] + dp[n][1]

空间优化：dp[i][0,1]只与dp[i-1][0,1]相关，可以省掉高维

时间复杂度：O(n)

例3 一个整数组里包含0-(n-1)的排列 (0到(n-1)恰好只出现一次），如果每次只允许把任意数和0交换，求排好顺序至少交换多少次。 （PAT 1067）

分析 ： 组合数学里的圈。

例如0占了1的位置，1占了2的位置，2占了0的位置。

一个排列，总可以划分为若干个不相交的圈

上例我们交换0和1，再交换0和2，则排好顺序了

方案

一个长度为m的圈，如果包含0，则交换(m -1)次可以恢复所有的数到原位

如果一个长度为m的圈不包含0，则交换(m+ 1) 次可以恢复所有的数到原位

例如1在2的位置，2在3的位置，3在1的位置

我们先交换0和任意一个数，例如交换0和1

则变成1在0的位置，0在2的位置，2在3的位置，3在1的位置。

代码

例4 给定一个字典，找到两个单词，它们不包含相同的字母，且乘积尽可能大，允许预处理字典。

分析 ：

开放问题——没有标准答案

需要和面试官交流、探讨

打开思路

方法1

枚举， 至少O(n2), 如何判断不包含相同字母？

细节 ： 如何判断包含相同字母？

每个单词出现的字母适用bitmap？

每个单词“签名”， 表示出现哪些字母 2的26次方

两个单词签名是x和y

如果x & y （按位与）非0，则包含相同的字母

n多大可以接受

方法2

预处理字典？如果空间足够大!

如何表示每个单词？ 仍然签名x =[0..2的26次方-1]

如何表示字母集合？

给定状态s在[0..2的26次方-1]中，表示可以出现哪些字母，我们想找到满足条件的最长单词， dp[s]

可以的含义？ 可以出现，可以不出现。即s中为1的位(bit)表示的字母可以在这个单词中出现，也可以不在这个单词中出现，但s中为0的那些位一定不允许在单词中出现的最长单词的长度

换言之，单词中出现的字母是状态s为1的位表示的字母集合的子集

如何计算dp[s]?

初值：全0

对每个单词的签名x, 计算dp[x] = max(dp[x], length(word))

更新？

for s = 1 to 2的26次方 – 1

对每一个比s少一个二进制1(bit)的状态s’

dp[s] = max(dp[s], dp[s’])

对dp[s]的更新的理解

s’ < s

s’已经计算好了

例如我们想计算状态11010，

状态01010, 10010, 11000已经计算好了

子集的最优解

要么是上面某个状态的子集的最优解（已经计算好了）

要么是这个集合本身 （预处理过）

最终答案

对每个单词签名x， 我们可选的字母集合是(~x)的子集——因为不能优相同的位

所以求 max(length(x) * dp[(~x) & ((1 << 26) – 1))]即可

时间复杂度：

每个单词签名 O(length * n)

计算dp[s] O(2的26次方 * 26)

最终求解 O(n)

空间复杂度 O(2的26次方)

难点

理解位运算

理解dp

当前集合的子集包括

比当前集合少一个元素的全部子集

当前集合本身

我们可以把dp的整数换为实际单词，可以得到解

一定要和面试官交流

不要把面试当成笔试

给面试官积极的情绪

没有标准答案——开放问题

多提假设

函数头部要自己写出

无固定套路

多总结、思考、归纳

Goode luck