CS144-1
本文最后更新于 132 天前,其中的信息可能已经有所发展或是发生改变。

前言

cmake –build build –target check 0来检查你的lab0后就可以开始这部分的实验了

事实上对于这部分实验,在我整个实验中花费的时间是最长的,代码也是最长的,而且即使通过了,后续的实验中,也会由于这部分导致超时,而无法通过。所以参考了其他大佬的思路才通过了这部分的测试

这是我参考的大佬的链接,需要代码的可以去他那边看看https://github.com/Mobuiss

目前大多数对于这一题的思路就是重复子串的合并,我一开始想到的也是用map来实现这个过程,但是后面写得也很长,性能很低。大佬的思路就不一样了,是用一个vector来维护buffer,下面详细讲。

实验开始

这个实验的主体是通过insert这个函数实现的 

它的传参有

uint64_t first_index, string data, bool is_last_substring, Writer& output

first_index是每一个data绝对位置,也就是类似于leetcode中合并区间的区间下标。data就是数据本身,可以调用.size来获取长度,is_last_substring就是问是否是最后一个数据段,output是一个输出接口,调用output.push()就可以把完整的数据段输出。

实现过程:

先是看是否是最后一段数据,如果是就设置保存一下,后面可以用来作为结束的依据。

然后就是判断是否是过于新或者过于旧的片段我们就不要

如果是旧消息(原作者意思是设置左边界)或者新消息(原作者是设置右边界)我们就截取窗口位置

他在实现右边界是比较有意思的,由于之前排除掉就消息,只剩下刚刚好符合的消息,和新消息,通过min函数来判断是否符合容量去实现的。也就是新消息和刚好落在窗口内的消息一起判断了

后面的思路也是让让拍案叫绝,是通过一个vector来维护一串数字,这些数字可以转换成char类型,把符合条件的消息全部转换成int放到vecotr中,然后通过一个随机固定的数字val填充为填充的,原作者用的值,咳咳(笑而不语)。然后如果需要的下标不是val的值(也就是恰好等于我们的需要的下标)则把其后面连续的都放到buffer中

具体实现可以去看原作者是如何做的,接下来我讲另一种思路

也就是我一开始想做的,也是绝大多数人的思路

经历和上面一样的筛选步骤后

存入后由于map会自动排序,会形成如下(实际上维护可能只有两到三个左右的消息段,这里为了演示画多一点)

然后会通过辅助函数来将所有的片段拍在一起,其中涉及到左合并和右合并

然后回放到map中(图中有可能结果有多个不相邻的判断,不一定是只有一个),下次放入判断前重新检查一下是否有新的片段成为了需要的下标,就推送到output里

由于笔者写的这部分代码确实不太好,所以如果想参考的话可以去我上面推荐的作者或者其他博客看看。

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇
Document