题解 虾皮笔试 9/3

T1 题意 给定长度为n的子串，找出所有长度为k的子串中频率最高的，如果相同频率选择字典序最小的。

n<=100,0<=k<=n

怀疑数据有锅，map<string,int>，或者随便怎么样暴力计数就行了

复杂度((n-k)*k*log(n-k)) 按照比较一次复杂度为k来算,暴力复杂度顶满也就是100*100*6+100*100(这段是暴力切割字符串)肯定不会t的，应该是数据有问题了。

T2, 给定数组，求最大的k个数的和，这个直接sort 加k次就行了

语法题复杂度O(nlogn+k)

T3 ,给一个花园，里面本来有一些花，用数组表示，0表示没有花，1表示有花，规则，不能在花的边上种花，注意给定的数组本身是可以违反规则的。求能不能再种n朵花

解法1 dp，状态表示上一个位置有花，最多能种多少花，没有花能种多少花，

转移方程dp[i][1]=dp[i-1][0]+1

如果当前位置本来有花：dp[i][0]=-1e9(设定不可选取的值)

否则dp[i-1][0]=max(dp[i-1][0],dp[i-1][1]),实际上max可以用不到，因为dp[i][1]>=dp[i][0]是恒成立的

需要注意的是他自己可能会违反规则，也就是初始花园1相邻，这个时候我们可以在当前位置本来有花，下一个位置也是花的情况，使得dp[i][0]=dp[i][1]

由于计算了原本的花，碰到原本有花就对n+1，若最大花数>=n就是可以

解法 2 贪心，发现一段长度为len的空地，能种(len+1)/2朵花，那么扫描所有连续的0计算长度，注意如果第一个0左边是1，或者最后一个0右边是1，长度-2.

复杂度O(n)

编程题目本身比较简单，都是语法题，不过前面的选择感觉还挺新的，起码和其他很多公司的选择比起来基本没啥重复的点。不过这个T1我不清楚是什么原因只能过90%，估计数据有锅或者怎么样，不排除数据范围描述不正确。