9.23 网易算法笔试

做过最难的笔试了，4道编程题 100，100，10，10

1. 查询区间内长度为3，且相等的连续子串数量

前缀和，qzh[i] = qzh[i-1] + (s[i] == s[i+1] && s[i+1] == s[i+2]) ? 1 : 0
这样可以O(1) 时间查询区间满足要求的子串数量

2. 构造长度为n的数组，相邻位置不超过1，且都为正整数。数组和为m，求指定位置p的最大值。

二分查找，假设p位置为x ....
可参考
https:/****************blems/maximum-value-at-a-given-index-in-a-bounded-array/description/

3. 定义树的路径权值为所有节点权值按位与计算的值，计算所有路径的权值之和
暴力 dfs

4. f(1) = a, f(2) = b, f(i) = f(i-1) * f(i-2) * c^d
求 f(n) 因子数量
1 <= a, b, c, d < 10^12

f(n) 可以写成 a^x1 * b ^x2 * c ^ (x3 * d)
找规律可以发现系数和斐波那契数列有关

如果 任意数Z = z1^3 * z2^5 * z3 ^8, 其中z1,z2,z3是质数，那么 Z的因子数量为 (3+1) * (5+1) * (8+1)

把f(n) 也就是a,b,c质因数分解，然后算最后的因子数量

n太大了，推导斐波那契数列时候会超时，但总体上应该是这个思路