leetcode算法- 字符串中的第一个唯一字符

说明

案例:

s = "leetcode"
返回 0.

s = "loveleetcode",
返回 2.

注意事项：您可以假定该字符串只包含小写字母。

come from https://leetcode-cn.com/problems/first-unique-character-in-a-string/

这一题苦思冥想了很久，才想到一个解题思路：
具体思路：

循环遍历每一个字符，通过match方法获取重复字符的数量，为了性能的提升，如果重复字符量大于1 ，则剔除与该字符相同的所有字符。如果重复字符的数量为1，则直接返回。其中做了很多特殊情况的处理。

var firstUniqChar = function (s) {
    if (!s) {
        return -1
    }
    if (s.length === 1) {
        return 0
    }
    let scopy = s
    for (let i = 0; i < s.length; i++) {
        const regStr = `${s[i]}`
        const reg = new RegExp(regStr, 'g')
        const numArr = scopy.match(reg)
        if (!numArr) {
            continue
        }
        const num = numArr.length
        if (num > 1) {
            scopy = scopy.replace(reg, '')
        }
        if (!scopy) {
            return -1
        }
        if (num === 1) {
            return i
        }
    }
    return -1
}

自评： 此算法的执行效率很低，并且做了很多特殊处理，仅仅是实现了，使用match大大降低了执行效率。

相同的实现思路，通过while 优化了一版

var firstUniqChar = function (s) {
    let cps = s
    while (cps.length > 0) {
        const r = new RegExp(cps[0], 'g')
        const numArr = cps.match(r)
        if (numArr.length === 1) {
            return s.indexOf(cps[0])
        } else {
            cps = cps.replace(r, '')
        }
    }
    return -1
}

自评：代码虽然进行了优化，但是实现思路跟上面是一样的，所有执行效率并没有显著的提升。

通过艰苦的思考，又想出一个方案，周五的夜晚就这么度过了
解题思路：
通过第一次循环，以对象的方式记录每一个字符的数量。第二次 for in 获取只有字符数量是1的，然后获取下标。

var firstUniqChar = function (s) {
    let i = 0
    const obj = {}
    while (i < s.length) {
        const key = s[i]
        if (key in obj) {
            obj[s[i]]++
        } else {
            obj[s[i]] = 1
        }
        i++
    }
    for (const key in obj) {
        if (obj[key] === 1) {
            return s.indexOf(key)
        }
    }
    return -1
}

果然通过努力的思考，解题效率进一步提升。

然后再上一版，leetcode 上高效率的实现：

var firstUniqChar = function (s) {
    // 26个小写字母
    const chars = 'abcdefghijklmnopqrstuvwxyz'

    // 初始化设置为一个较大的不可能的值，index最大为s.length-1,但是这里设置为s.length
    let index = s.length
    // 遍历所有字符
    for (const c of chars) {
        // 找到有且只出现一次的字符
        const start = s.indexOf(c)
        const last = s.lastIndexOf(c)
        if (start !== -1 && start === last) {
            // 获取index, start的最小值，并赋值于index，经过循环以后，如果有更小的值，则继续更新index,最终index的值一定是其中最小的
            index = Math.min(index, start)
        }
        if (index === 0) break
    }
    return index === s.length ? -1 : index
}

可以看出，执行效率提升了几倍