题解 虾皮笔试 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%，估计数据有锅或者怎么样，不排除数据范围描述不正确。
#虾皮##虾皮笔试##笔试##题解#
查看1道真题和解析