第一次笔试。一共4道题，感觉第一题非常难。（顺便请问一下，牛客上面在线笔试，邮箱里说每一题只能提交一次，所以我一直用的自测，后来被第一题搞崩了，我交了以后超时，但是我还可以提交，这是为什么，可以无限提交？？？）
第一道题：给一个数组，打印数组每个元素前面第一个比他更大的元素大小，输出这n个数。
比如 5 4 3 2 1输出-1 5 4 3 2 没有比他大的输出-1。一次测试点有多组数据，每一组的n好像是10w？忘了，反正各种超时。
我开始暴力两趟循环，想都不用想肯定超时。思考了10分钟换dp数组记录数组每一位前面比他更大的第一个数的下标，然后while循环对dp数组往前搜索，果不其然也超时。
第二步优化我用了二分。对DP数组往前检索的途中 二分进行检索 时间复杂度再度优化。然后还是通过0%…………心态炸了
第二道题 以前做过类似的，给两个数组 判断第一个数组的元素经过入栈出栈后能不能变成第二个数组（注意这两个数组的元素也不保证相等）
第三道题 给了你一个递归的公式，照着写就行了。题目大意是求p[n] 然后p[n]又等于p[n-1]做一些计算……以此类推到p[0]
第四道题 真的不会。输入字符串A和字符串B ，比如A是 ABWEJGIR 字符串B是IEG 要求出A里面包含B所有元素的最短子串，也就是输出EJGI，不用保证顺序和B串一样，只用保证包含B里每个字符即可，然后求最短的那个。
有思路的麻烦讲一下这题。每个字符串长度应该是10e6往上，很长，我感觉肯定有什么巧妙的思路来写这题，不过我没想出来。
全部评论
(10) 回帖