当前位置 博文首页 > 中流击水,浪遏飞舟:哈希&&队列&&剑指 Offer 5

    中流击水,浪遏飞舟:哈希&&队列&&剑指 Offer 5

    作者:[db:作者] 时间:2021-08-26 12:44

    简单题:返回字符串s第一次出现且只出现一次的字符。

    1.数组的菜鸡解答(不是考察的目标

    class Solution {
    public:
        char firstUniqChar(string s) {
            vector<int>counts(26,0);
            char ans;
            bool t=true;
            for(auto x:s){
                counts[x-'a']++;
            }
            for(auto y:s){
                if(counts[y-'a']==1){
                    ans=y;
                    t=false;
                    break;
                }
            }
            return t?ans=' ':ans;
        }
    };
    

    2.哈希表(这才是考察的目标

    跟数组原理差不多,只不过用到了和哈希表的数据结构。
    参考大佬的力扣题解:
    面试题50. 第一个只出现一次的字符(哈希表 / 有序哈希表,清晰图解)

    class Solution {
    public:
        char firstUniqChar(string s) {
            unordered_map<char,int>counts;
            for(auto x:s){
                counts[x]++;
            }
            for(auto x:s){
                if(counts[x]==1){
                    return x;
                }
            }
            return ' ';
        }
    };
    

    3.有序哈希表(当字符串s较长时,在解法2的基础上,可以用一个vector< char >数组只记录第一次出现的字符,省去遍历长字符串的时间

    4.queue队列(使得队首一直是第一次出现的字符

    cs