The title

Title link: leetcode-cn.com/leetbook/re…

Answer key


1. Methods of violence

The first thought is directly two layers of loop up, although simple, but useful, on the code;

/ * * *@param {string} s
 * @return {number}* /
var firstUniqChar = function(s) {

    let isReapet = false;
    let len =  s.length;

    for(let i = 0; i < len; i++) { isReapet =false;

        for(let j = 0; j<len; j++) {if( i ! == j && s[i] === s[j]) { isReapet =true;
                break; }}if(isReapet === false) {
            returni; }}return -1;

};

Copy the code


2, improvement: space for time

The time complexity of the violent method is O(Nlog2n)O(Nlog_2n)O(nlog2n), so we must want to reduce the time complexity of the violent method. According to the theory of space for time, we can see whether it can be completed within the time complexity of O(n)O(n)O(n). Use an object (or Map) to record whether a character is repeated, and then find the position of the first non-repeating character.

Using Object records

/ * * *@param {string} s
 * @return {number}* /
var firstUniqChar = function(s) {

    let len =  s.length;
    let isRepeat = {};

    for(let item of s) {
        if( isRepeat[item] === undefined) {
            isRepeat[item] = false;
        }else {
            isRepeat[item] = true; }}for(let i = 0; i < len; i++) {if(isRepeat[s[i]] === false) {
            returni; }}return -1;

};
Copy the code


Using Map Records

/ * * *@param {string} s
 * @return {number}* /
var firstUniqChar = function(s) {

    let len =  s.length;
    let map = new Map(a);// Use a Map to record whether characters are repeated, true if they are repeated, false if they are not
    for(let item of s) {

        if( map.get(item) === undefined) {
            map.set(item,false);
        }else {
            map.set(item,true); }}for(let i = 0; i < len; i++) {if(map.get(s[i]) === false) {
            returni; }}return -1;

};
Copy the code

Since both Object and Map can be used, what is the difference between them? From MDN

  • Object inherits all the key names in the prototype chain, so it may conflict with its own key names. By default, a Map contains only its own key name;

  • The key of Object must be a String or Symbol; Map keys can be of any type;

  • The keys of Object are unordered, and the order of keys in Map is the same as that of insertion.

  • The number of key/value pairs of Object can only be calculated manually and can be obtained by size in Map.

  • Object is not iterable, Map is iterable;

  • Map performs better when key pairs are frequently added or deleted.


3, improvement: use JS string method

Str.indexof () and str.lastIndexof () determine the position of the first and last occurrence of characters in the string;

/ * * *@param {string} s
 * @return {number}* /
var firstUniqChar = function(s) {

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

};
Copy the code


If you have a better way of thinking and reconciliation, welcome to discuss ah ~

This is a summary and implementation of each problem in LeetCode’s “Elementary Algorithms” using JavaScript. The summary is here:

Juejin. Cn/post / 700669…