9.7 携程笔试全A
最后几分钟的时候还在调第4题的边界条件,最后一分钟交卷险过
1、递归+回溯
2、分别统计每行每列中y、o、u的个数,然后枚举每个元素为三角形中直角的情况,用之前统计的数据可在O(1)时间内计算出来
3、先判断数据的总和有没有大于右边界或小于左边界,符合直接输出-1,否则枚举每个数,对小于左边界的数用一个变量记录差值,大于有边界的变量用另一个数记录差值,最后输出两个变量中大的那个
4、使用一个数组next记录每个字符可向右延伸的最远位置,从右到左遍历字符串,设枚举到的索引为i:
1)枚举到1时向右延伸的位置为当前位置,next[j]=j;
2)枚举到0时用一个while循环不断向右判断,设下个位置为j:
下一个数如果是1或大于了最大长度则结束循环, next[i] = j;
下一个数如果为0则将向右延伸的位置改为该数在next中记录的最远位置, j = next[j], j++;
3) 将结果加上 j - i
可以证明每个索引最多只会被访问2次,所以时间复杂度为O(n),注意边界条件的处理,j最大只能为n
1、递归+回溯
2、分别统计每行每列中y、o、u的个数,然后枚举每个元素为三角形中直角的情况,用之前统计的数据可在O(1)时间内计算出来
3、先判断数据的总和有没有大于右边界或小于左边界,符合直接输出-1,否则枚举每个数,对小于左边界的数用一个变量记录差值,大于有边界的变量用另一个数记录差值,最后输出两个变量中大的那个
4、使用一个数组next记录每个字符可向右延伸的最远位置,从右到左遍历字符串,设枚举到的索引为i:
1)枚举到1时向右延伸的位置为当前位置,next[j]=j;
2)枚举到0时用一个while循环不断向右判断,设下个位置为j:
下一个数如果是1或大于了最大长度则结束循环, next[i] = j;
下一个数如果为0则将向右延伸的位置改为该数在next中记录的最远位置, j = next[j], j++;
3) 将结果加上 j - i
可以证明每个索引最多只会被访问2次,所以时间复杂度为O(n),注意边界条件的处理,j最大只能为n
全部评论
能看看第二第三题吗佬
相关推荐


点赞 评论 收藏
分享
点赞 评论 收藏
分享