打开APP
userphoto
未登录

开通VIP,畅享免费电子书等14项超值服

开通VIP
剑指offer(C++)-JZ50:第一个只出现一次的字符(算法-其他)

作者:翟天保Steven
版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处

题目描述:

在一个长为 字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1(需要区分大小写).(从0开始计数)

数据范围:0≤n≤10000,且字符串只有字母组成。

要求:空间复杂度O(n),时间复杂度O(n)

示例:

输入:

"google"

返回值:

4

解题思路:

本题考察算法思维。两种解题思路:

1)哈希法

  1. 第一次循环用哈希表记录所有字符出现次数。
  2. 第二次循环找到首个出现次数为1的字符即可。

2)位运算

  1. 本质上和哈希法一样。因为字符只有字母,数量为26*2=52。每一位表示一个字符,比如字符b就是0010。
  2. 第一次循环用b记录出现过的字符,相应位数设为1,如果出现过了则flag对应位数也设为1。
  3. 第二次循环如果某个字符在b中对应位数为1,在flag中为0,则说明只出现过一次,完毕。

3)队列哈希法

  1. 该方法执行一次循环即可。
  2. 当字符首次出现,哈希表存储该字符位置,并将其放入队列中。
  3. 如果出现重复字符,则哈希表将该字符位置信息设为-1,即无效,并依次弹出队列中位置为-1的数据。注意,如果重复字符并非首个字符,则不进行弹出操作。如abcb,则不弹;如abcba,则将队列abc中的ab弹出,只剩下的c也就是答案。

测试代码:

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;
    }
};
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请点击举报
打开APP,阅读全文并永久保存 查看更多类似文章
猜你喜欢
类似文章
【热】打开小程序,算一算2024你的财运
剑指offer之字符串的全排列
数据结构——数据结构的查找与排序 (折半查找 、哈希查找 、直接插入排序 、冒泡排序 、快速排序)
C语言字符串压缩算法代码演示
​LeetCode刷题实战290:单词规律
c#中各种数据类型的转化
C语言编程 有一篇文章,共有3行文字,每行80个字符。要求分别统计出其中英文字母,数字,空...
更多类似文章 >>
生活服务
热点新闻
分享 收藏 导长图 关注 下载文章
绑定账号成功
后续可登录账号畅享VIP特权!
如果VIP功能使用有故障,
可点击这里联系客服!

联系客服