Topic:

Given a string, find its first non-repeating character and return its index. If none exists, -1 is returned.

Example:

S = "leetcode" returns 0. S = "loveleetcode" returns 2Copy the code

Tip:

You can assume that the string contains only lowercase letters

The topic

Traversal – hash

Double traversal:

  1. Count the number of characters
  2. Returns the first encountered character index of only 1

Returns -1 if no character of 1 is encountered

/ * * *@param {string} s
 * @return {number}* /
var firstUniqChar = function(s) {
    const map = new Map(a)for (const c of s) {
        map.set(c, (map.get(c) || 0) + 1)}for (let i = 0; i < s.length; i++) {
        if (map.get(s[i]) === 1) return i
    }
    return -1
}
Copy the code

Traverse – Unicode

The prompt mentions that strings contain only lowercase characters, indicating that Unicode for characters is available

Declare an array of 26 characters, and fill the array with characters of Unicode-97

var firstUniqChar = function(s) {
    const list = Array(26).fill(0)
    for (const c of s) {
        list[c.charCodeAt() - 97] + +}for (let i = 0; i < s.length; i++) {
        if (list[s[i].charCodeAt() - 97= = =1) return i
    }
    return -1
}
Copy the code

The queue

Queue: First in, first out

The first occurrence of a new character directly enters the queue and marks its index

An already occurring character is marked as -1 and removed from the queue

var firstUniqChar = function(s) {
    const queue = [],
        // Marks the number of occurrences of characters
        map = new Map(a)for (let i = 0; i < s.length; i++) {
        if(! map.has(s[i])) { map.set(s[i], i) queue.push([s[i], i]) }else {
            map.set(s[i], -1)
            // Note that s[I] is not necessarily at the head of the queue, so you need to traverse the queue to find the character to remove
            while (queue.length && map.get(queue[0] [0= = = -])1) queue.shift()
        }
    }
    return queue.length ? queue[0] [1] : -1
}
Copy the code

Blog: Front end little bookboy

Every day a daily problem, write the solution of the problem will be updated to the public account one day a big Lee column welcome to pay attention to the message

Public number: front end little bookboy