阿里笔试419 45minAK题解

写了大概45min 感觉挺水的~
第一题写了20min 第二题写了10min 第三题写了15min 
T1 给定一个序列，问有多少个区间的众数次数>=k
sol:考虑two-pointer。枚举左端点，寻找最小的右端点是的众数次数>=k
推导后发现需要支持以下功能
1.增加某一个数的出现次数
2.减少某一个数的出现次数
3.查询众数的出现次数（即出现次数最多的数字的出现次数）
这些功能可以抽象化可以理解为维护一个集合，支持单点修改，支持查询最大值
因此考虑使用堆来实现，具体实现过程类似dijkstra找最短节点的过程。
T2 题意大概就是模拟一个消消乐的过程
sol:bfs暴力模拟消除的过程，而下落的过程可以逐行维护每一列的高度来模拟实现。
T3 求所有长度为n的字符串有多少个长度为3的回文子串
考虑动态规划
考虑一个字符串的最后两个字符的形式，要么是"aa"，要么是“ab”。
不妨记
"aa"结尾的字符串的数量为x[n]，记这些字符串的权值和为fx[n]。
记"ab"结尾的字符串的数量为y[n]，记这些字符串的权值和为fy[n]。

"aa"有两种转移方式——>"aaa"，“aab”
其中"aaa"有1种方式。
其中"aab"有25种方式，指的是填与"a"不同的25个字符。

"ab"有三种转移方式——>"aba"，“abb”，"abc"
其中"aba"有1种方式。
其中"abb"有1种方式。
其中"abc"有24种方式，指的是填与"a"不同的25个字符。

这里简单写一下dp的转移方程
x[n]=x[n-1]+y[n-1]
fx[n]=x[n-1]+fx[n-1]+y[n-1]
y[n]=25x[n-1]+25y[n-1]
fy[n]=25fx[n-1]+y[n-1]+25fy[n-1]
直接暴力dp复杂度为O(n)
考虑使用矩阵快速幂优化（类似快速求斐波那契数列）
即可做到O(logn)