题目
给定一个字符串 s ,找到 它的第一个不重复的字符,并返回它的索引 。如果不存在,则返回 -1 。
详见:387. 字符串中的第一个唯一字符
思路
- 哈希存储出现次数,第一次遍历字符串,存储每个字符出现的次数,第二次遍历字符串,如果该字符只出现一次,则返回它的索引
- 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;
}
};
方法二: 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;
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)