阿里云笔试0914题解
开发卷 T1 组建团队T2 区间子串数量T3 矩阵路径最大和,详细题解见评论,有帮助欢迎点赞评论交流哦
全部评论
T3 矩阵路径最大和
如果题目没有乘2的条件,我们用dp计算一遍,记录左上角到当前元素的最大和,然后取最后一个元素即可。现在有了乘2的条件,如果动了一个元素,那么答案有两种情况:一种是经过这个元素,一种是不经过。为了快速求出经过这个元素的情况,我们从右下角再计算一遍,记录右上角到当前元素的最大和,与前面的左上角到当前的最大和相加即可。而如果不经过该元素还能最大,那就是之前的情况了,二者取大者即可。
时间复杂度O(m*n),空间复杂度O(m*n)
T1 组建团队
贪心。我们按照每个人要求的最小成员数排序,然后依次组队。具体地,按照要求的成员数划分集合,集合内部组队,其余人扔到下一个集合继续组队。
时间复杂度O(n),空间复杂度O(n)
T2 区间子串数量
刚看到题还以为是KMP吓一跳,一看范围那没事了。据样例可知问的是连续子串,还可以重叠,那么直接用前缀和处理即可,记录截止到当前字符串的子串数量,每次查询只需要将左右边缘前缀和相减。
注意左边缘不是l-1, 而是l-1+(m-1)。比如abcabc匹配abc的前缀数组是0001112,l=1, r=6(即bcabc)时,答案计算是2-1而不是2-0(第一个abc不是整个在区间内的)。
时间复杂度O(m*n),空间复杂度O(n)
第三题终点dp也太巧妙了
佬,第二题的左区间太坑了吧
到底是什么人在A啊
好像卷子还不一样?我第三题是小红对数组做操作使得数组里的值相等,有无大佬和我一套题,蹲个复盘
我第一题用的动态规划(背包),但是只过了3.33%。也不能到IDE调试,完全懵。请问这个思路的问题在哪里呀?
第3题和你思路一样,但是用的java超时了,只过了27%,哭死
太牛了
mark
相关推荐