Topic describes

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

Example:

s = "leetcode"return0

s = "loveleetcode"return2
Copy the code

Tip: You can assume that the string contains only lowercase letters.

Train of thought

The most obvious thing to think of is a two-layer loop, but the algorithm is looking for the optimal solution, which is the lower space and time complexity, so we won’t give examples of this solution here.

Option 1: [hashMap]

Iterate over the string to create a hashMap with key as the current string and value as the string index. When the key is stored in the hashMap for the first time, value is stored as -1. Each subsequent occurrence updates value to the current index. When the loop is complete, iterate over the hashMap and find the first index that is not -1, which is the result of the problem.

var firstUniqChar = function(s) {
    const position = new Map(a);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;
};
Copy the code

Scheme 2: [Queue]

Using the first-in, first-out (FIFO) feature of queues, if a character in the map table does not enter the queue, the character will be displayed if it does. if

var firstUniqChar = function(s) {
    const position = new Map(a);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;
};
Copy the code

[Query string index]

What a strange skill

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;
};
Copy the code

conclusion

Array class topics can consider hashMaps and the team and column features.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to view the details of the campaign: juejin.cn/post/693314…