387. 字符串中的第一个唯一字符


387. 字符串中的第一个唯一字符

    public int firstUniqChar(String s) {
        Map<Character, Integer> frequency = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); ++i) &#123;
            char ch = s.charAt(i);
            frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);
        &#125;
        for (int i = 0; i < s.length(); ++i) &#123;
            if (frequency.get(s.charAt(i)) == 1) &#123;
                return i;
            &#125;
        &#125;
        return -1;
    &#125;

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/first-unique-character-in-a-string/solution/zi-fu-chuan-zhong-de-di-yi-ge-wei-yi-zi-x9rok/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
public int firstUniqChar(String s) &#123;
        Map<Character, Integer> position = new HashMap<Character, Integer>();
        Queue<Pair> queue = new LinkedList<Pair>();
        int n = s.length();
        for (int i = 0; i < n; ++i) &#123;
            char ch = s.charAt(i);
            if (!position.containsKey(ch)) &#123;
                position.put(ch, i);
                queue.offer(new Pair(ch, i));
            &#125; else &#123;
                position.put(ch, -1);//将队列头部重复的数据移除
                while (!queue.isEmpty() && position.get(queue.peek().ch) == -1) &#123;
                    queue.poll();
                &#125;
            &#125;
        &#125;
        return queue.isEmpty() ? -1 : queue.poll().pos;
    &#125;

    class Pair &#123;
        char ch;
        int pos;

        Pair(char ch, int pos) &#123;
            this.ch = ch;
            this.pos = pos;
        &#125;
    &#125;

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/first-unique-character-in-a-string/solution/zi-fu-chuan-zhong-de-di-yi-ge-wei-yi-zi-x9rok/

解析
小贴士

在维护队列时,我们使用了「延迟删除」这一技巧。也就是说,即使队列中有一些字符出现了超过一次,但它只要不位于队首,那么就不会对答案造成影响,我们也就可以不用去删除它。只有当它前面的所有字符被移出队列,它成为队首时,我们才需要将它移除。
链接:https://leetcode-cn.com/problems/first-unique-character-in-a-string/solution/zi-fu-chuan-zhong-de-di-yi-ge-wei-yi-zi-x9rok/


文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
  目录