[LeetCode387.字符串中的第一个唯一字符] | 刷题打卡

题目描述

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

示例：

s = "leetcode"
返回 0

s = "loveleetcode"
返回 2

提示：你可以假定该字符串只包含小写字母。

思路

最最最容易想到的就是双层循环，但是算法追求的是最优解法，即较低的空间和时间复杂度，所以我们这里不对这种解法做举例。

方案一：【hashMap】

遍历这个字符串，建立一个key为当前字符串，value为该字符串索引的hashMap。当key是第一次存储在hashMap中时，value存为-1。以后每次出现更新value为当前索引。遍历完成后，遍历hashMap，找到第一个不为-1的索引，即是满足题目要求的结果。

var firstUniqChar = function(s) {
    const position = new Map();
    const length = s.length;
    for (let [i, ch] of Array.from(s).entries()) {
        if (position.has(ch)) {
            position.set(ch ,-1)
        } else {
            position.set(ch, i);
        }
    }

    let first = length;
    for (let pos of position.values()) {
        if (pos !== -1 && pos < first) {
            first = pos;
        }
    }

    if (first === length) {
        return -1;
    }
    return first;
};

方案二：【队列】

利用队列的先进先出的特性，map表中某一字符没有就入队，有则弹出该字符。如果

var firstUniqChar = function(s) {
    const position = new Map();
    const q = [];
    for (let [i, ch] of Array.from(s).entries()) {
        if (!position.has(ch)) {
            position.set(ch, i);
            q.push([s[i], i]);
        } else {
            position.set(ch, -1);
            while (q.length && position.get(q[0][0]) === -1) {
                q.shift();
            }
        }
    }
    return q.length ? q[0][1] : -1;
};

方案三：【查询字符串的索引】

真奇淫技巧啊~

var firstUniqChar = function(s) {
    for(let i = 0; i<s.length;i++) {
        if (s.indexOf(s[i]) === s.lastIndexOf(s[i])) {
            return i
        }
    }
    return -1;
};

总结

数组类的题目可以多考虑hashMap以及队和列的特性。

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情：juejin.cn/post/693314…