数据结构1059.恢复古诗题解

10165102128 edited 4 年前

1059.恢复古诗

题目大意是给你一些字符串,分为许多组,然后你只要根据每组字符串的第一个和最后一个字符串的值,将组与组之间连接起来就好了。

这道题的难点可能就是在于需要比较的是字符串,如果将题目中的字符串都替换成不同的数字,那么就会更加简单,你只要比较每个序列的第一个数字和最后一个数字就好。

这个道理也同样适用于字符串,使用一个两重的循环,分别将每一组字符串的第一个字符串与其他组的最后一个字符串比较,如果相同,那么就找到这组字符串的前面的那组字符串,将这个顺序记录下来,最后按序输出就好。

上面这个应该是一个简单的做法,花费的时间比较多,但是由于 jxtxzzw 的数据较弱,所以你这样也是可以AC的。下面讲一下 jxtxzzw 希望你用的方法。

这道题最正确的做法其实应该使用 hash 将每组字符串的第一个字符串 hash 函数将其映射到数字,然后可以利用数组寻址将对应的组号存储到相应的位置,之后再用相同的 hash 函数将每组最后一个字符串同样映射到数字,当然相同的字符串,使用相同的 hash 函数可以得到相同的数字,这样就可以将最后一个字符串找到与其相等的字符串,则可以将组与组之间连接起来。

重点就是你找的 hash 函数要好,否则有可能将不同的字符串映射到同一个数字上,就会十分尴尬了。当然如果你使用 c++ 你可以直接用 map ,更加快捷方便。

Past Versions

Comments