LeetCode 387. 字符串中的第一个唯一字符

简介: LeetCode 387. 字符串中的第一个唯一字符

题目

给定一个字符串 s ,找到 它的第一个不重复的字符,并返回它的索引 。如果不存在,则返回 -1 。

详见:387. 字符串中的第一个唯一字符

思路

  1. 哈希存储出现次数,第一次遍历字符串,存储每个字符出现的次数,第二次遍历字符串,如果该字符只出现一次,则返回它的索引
  2. find函数,rfind() 从后向前查找字符第一次出现的位置,find() 从前向后查找字符第一次出现的位置,遍历字符串,如果字符的第一个索引和最后一个索引是同一个位置,则返回该索引

队列,也可以借助队列找到第一个不重复的字符,队列具有「先进先出」的性质,因此很适合用来找出第一个满足某个条件的元素。使用一个额外的队列,按照顺序存储每一个字符以及它们第一次出现的位置。对字符串进行遍历时,设当前遍历到的字符为 c,如果 c 不在哈希映射中,我们就将 c

与它的索引作为一个二元组放入队尾,否则我们就需要检查队列中的元素是否都满足「只出现一次」的要求,即我们不断地根据哈希映射中存储的值(是否为−1)选择弹出队首的元素,直到队首元素「真的」只出现了一次或者队列为空。在遍历完成后,如果队列为空,说明没有不重复的字符,返回−1,否则队首的元素即为第一个不重复的字符以及其索引的二元组。在维护队列时,我们使用了「延迟删除」这一技巧。也就是说,即使队列中有一些字符出现了超过一次,但它只要不位于队首,那么就不会对答案造成影响,我们也就可以不用去删除它。只有当它前面的所有字符被移出队列,它成为队首时,我们才需要将它移除。

来源:LeetCode


代码

方法一:哈希存储出现次数

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<int, int>str;
        for(auto ch : s){
            str[ch]++;
        }
        for(int i = 0; i < s.size(); i++){
            if(str[s[i]] == 1){
                return i;
            }
        }
        return -1;
    }
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(∣Σ∣)

方法二: find函数

class Solution {
public:
    int firstUniqChar(string s) {
        for(int i = 0; i < s.size(); i++){
            if(s.find(s[i]) == s.rfind(s[i])){
                return i;
            }
        }
        return -1;
    }
};

方法三:队列

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, int> position;
        queue<pair<char, int>> q;
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            if (!position.count(s[i])) {
                position[s[i]] = i;
                q.emplace(s[i], i);
            }
            else {
                position[s[i]] = -1;
                while (!q.empty() && position[q.front().first] == -1) {
                    q.pop();
                }
            }
        }
        return q.empty() ? -1 : q.front().second;
    }
};


目录
相关文章
|
存储 算法
Leetcode第三题(无重复字符的最长子串)
这篇文章介绍了解决LeetCode第三题“无重复字符的最长子串”的算法,使用滑动窗口技术来找出给定字符串中最长的不含重复字符的子串,并提供了详细的代码实现和解释。
576 0
Leetcode第三题(无重复字符的最长子串)
|
6月前
|
Go 索引
【LeetCode 热题100】394:字符串解码(详细解析)(Go语言版)
本文详细解析了 LeetCode 热题 394:字符串解码。题目要求对编码字符串如 `k[encoded_string]` 进行解码,其中 `encoded_string` 需重复 `k` 次。文章提供了两种解法:使用栈模拟和递归 DFS,并附有 Go 语言实现代码。栈解法通过数字栈与字符串栈记录状态,适合迭代;递归解法则利用函数调用处理嵌套结构,代码更简洁。两者时间复杂度均为 O(n),但递归需注意栈深度问题。文章还总结了解题注意事项及适用场景,帮助读者更好地掌握字符串嵌套解析技巧。
167 6
|
7月前
|
存储 机器学习/深度学习 缓存
🚀 力扣热题 394:字符串解码(详细解析)(Go语言版)
文章提供了两种解法:栈结构和递归解法。栈解法通过维护数字栈与字符串栈,依次处理 `[` 和 `]`,构造解码结果;递归解法则利用函数调用逐层解析嵌套结构。两者时间复杂度均为 $O(n)$,空间复杂度也为 $O(n)$。栈解法直观易懂,适合初学者;递归解法优雅简洁,适合处理深度嵌套规则。掌握这两种方法,可灵活应对类似问题,提升解题能力。
221 11
|
12月前
|
JavaScript
力扣3333.找到初始输入字符串Ⅱ
【10月更文挑战第9天】力扣3333.找到初始输入字符串Ⅱ
125 1
|
C++
Leetcode第43题(字符串相乘)
本篇介绍了一种用C++实现的字符串表示的非负整数相乘的方法,通过逆向编号字符串,将乘法运算转化为二维数组的累加过程,最后处理进位并转换为字符串结果,解决了两个大数相乘的问题。
89 9
|
算法 C++
Leetcode第八题(字符串转换整数(atoi))
这篇文章介绍了LeetCode上第8题“字符串转换整数(atoi)”的解题思路和C++的实现方法,包括处理前导空格、正负号、连续数字字符以及整数溢出的情况。
142 0
【LeetCode 22】459.重复的子字符串
【LeetCode 22】459.重复的子字符串
105 0
【LeetCode 20】151.反转字符串里的单词
【LeetCode 20】151.反转字符串里的单词
101 0
【LeetCode 19】541.反转字符串II
【LeetCode 19】541.反转字符串II
70 0
【LeetCode 18】6.2.反转字符串
【LeetCode 18】6.2.反转字符串
69 0