网站怎么写,wordpress数据库版本号,亚马逊备案网站建设,注册域名查询网站作者#xff1a;翟天保Steven 版权声明#xff1a;著作权归作者所有#xff0c;商业转载请联系作者获得授权#xff0c;非商业转载请注明出处 题目描述#xff1a;
在一个长为 字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1#xff08;需要区分…作者翟天保Steven 版权声明著作权归作者所有商业转载请联系作者获得授权非商业转载请注明出处 题目描述
在一个长为 字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1需要区分大小写.从0开始计数
数据范围0≤n≤10000且字符串只有字母组成。
要求空间复杂度O(n)时间复杂度O(n) 示例
输入
google返回值
4 解题思路
本题考察算法思维。两种解题思路
1)哈希法
第一次循环用哈希表记录所有字符出现次数。第二次循环找到首个出现次数为1的字符即可。
2)位运算
本质上和哈希法一样。因为字符只有字母数量为26*252。每一位表示一个字符比如字符b就是0010。第一次循环用b记录出现过的字符相应位数设为1如果出现过了则flag对应位数也设为1。第二次循环如果某个字符在b中对应位数为1在flag中为0则说明只出现过一次完毕。
3)队列哈希法
该方法执行一次循环即可。当字符首次出现哈希表存储该字符位置并将其放入队列中。如果出现重复字符则哈希表将该字符位置信息设为-1即无效并依次弹出队列中位置为-1的数据。注意如果重复字符并非首个字符则不进行弹出操作。如abcb则不弹如abcba则将队列abc中的ab弹出只剩下的c也就是答案。 测试代码
1)哈希法
class Solution {
public:// 首个不重复字符int FirstNotRepeatingChar(string str) {int size int(str.size());unordered_mapchar, 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_mapchar, int mp;queuepairchar, 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{// 位置置为-1mp[str[i]] -1;// 弹出前面所有的重复过的字符while(!q.empty() mp[q.front().first] -1)q.pop();}}return q.empty() ? -1 : q.front().second;}
};
