• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

队列具有“先进先出”的性质 所以非常适合寻找满足某个条件的第一个元素


Recommended Posts

https://leet code-cn.com/problems/first-unique-character-in-a-string/solution/zi-fu-chuan-zhong-de-di-yi-ge-Wei-yi-zi-x9rok/

想法和算法

我们还可以借助队列找到第一个不重复的字符。Queue具有“先进先出”的性质,因此非常适合寻找满足某个条件的第一个元素。

具体来说,我们使用与第二种方法相同的哈希映射,并使用一个额外的队列来存储每个字符及其在序列中的第一个出现位置。当我们遍历一个字符串时,让当前遍历的字符为cc。如果cc不在哈希表中,我们将把cc和它的索引作为二进制组放在队列的末尾。否则,我们需要检查队列中的所有元素是否满足“只出现一次”的要求,即我们不断地根据hash map中存储的值(无论是否为-11)选择在队列头部弹出的元素,直到队列头部的元素“真正”只出现。

遍历完成后,如果队列为空,说明没有不重复的字符,返回-11;否则,队列头的元素是第一个不重复的字符及其二进制索引。

技巧

在维护队列时,我们使用了“延迟删除”技术。也就是说,即使队列中的某些字符出现不止一次,只要不在队列的最前面,也不会影响回答,所以我们不必删除。我们只需要在它前面的所有字符都从队列中删除,它成为队列的头时,再删除它。

作者:LeetCode-Solution

链接:3359 leet code-cn.com/problems/first-unique-character-in-a-string/solution/zi-fu-chuan-zhong-de-di-yi-ge-Wei-yi-zi-x9rok/

资料来源:LeetCode

版权归作者所有。商业转载请联系作者授权,非商业转载请注明出处。

Link to comment
Share on other sites