LeetCode每日一题：字符串中的第一个唯一字符

法1：hash

思路

很简单的思路，用一个hash表，键为字符，值为一个pair，pair的first成员存字符的出现次数，second成员为该字符的下标，维护一个下标最小值为答案即可。

代码

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, pair<int, int>> mp;

        for(int i = 0; i < s.size(); i++) {
            mp[s[i]].first++;
            mp[s[i]].second = i;
        }

        int pos = INT_MAX;
        for(auto el: mp) {
            if((el.second).first == 1) {
                pos = min(pos, (el.second).second);
            }
        }

        return pos == INT_MAX ? -1 : pos;
    }
};

法2：延长字符串

思路

把整个s串延长一倍，接在原串尾部。遍历串的前半截，如果当前字符在该下标往后的片段里第一次出现的位置为当前位置+N，那么可以判断它确实只出现了一次，即s.find(ch, i+1) = i + n

代码

class Solution {
public:
    int firstUniqChar(string s) {
        int n = s.size();
        s = s + s;

        for(int i = 0; i < n; i++) {
            char ch = s[i];
            //cout << s.find(ch, i + 1) << endl;
            if(s.find(ch, i + 1) == i + n) return i;
        }

        return -1;
    }
};