作者:翟天保Steven
版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处
在一个长为 字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1(需要区分大小写).(从0开始计数)
数据范围:0≤n≤10000,且字符串只有字母组成。
要求:空间复杂度O(n),时间复杂度O(n)
输入:
"google"
返回值:
4
本题考察算法思维。两种解题思路:
1)哈希法
2)位运算
3)队列哈希法
1)哈希法
class Solution {
public:
// 首个不重复字符
int FirstNotRepeatingChar(string str) {
int size = int(str.size());
unordered_map<char, int> mp;
// 统计每个字符出现的次数
for(int i = 0; i < size; i++){
mp[str[i]]++;
}
// 找到第一个只出现一次的字母
for(int i = 0; i < size; i++){
if(mp[str[i]] == 1)
return i;
}
// 没有找到
return -1;
}
};
2)位运算
class Solution {
public:
// 首个不重复字符
int FirstNotRepeatingChar(string str) {
int size = int(str.size());
long long b = 0;
long long flag = 0;
// 统计每个字符出现的次数
for(int i = 0; i < size; i++){
int temp = str[i] - 'a';
if(b & (1 << temp)){
flag |= (1 << temp);
}
b |= (1 << temp);
}
// 找到第一个只出现一次的字母
for(int i = 0; i < size; i++){
int temp = str[i] - 'a';
if((b & (1 << temp)) && !(flag & (1 << temp))){
return i;
}
}
//没有找到
return -1;
}
};
3)队列哈希法
class Solution {
public:
// 首个不重复字符
int FirstNotRepeatingChar(string str) {
int size = int(str.size());
unordered_map<char, int> mp;
queue<pair<char, int> > q;
// 统计字符出现的位置
for(int i = 0; i < size; i++){
// 没有出现过的字符
if(!mp.count(str[i])){
mp[str[i]] = i;
q.push(make_pair(str[i], i));
// 找到重复的字符
}
else{
// 位置置为-1
mp[str[i]] = -1;
// 弹出前面所有的重复过的字符
while(!q.empty() && mp[q.front().first] == -1)
q.pop();
}
}
return q.empty() ? -1 : q.front().second;
}
};
联系客服