专栏首页前端小书童【一天一大 lee】字符串中的第一个唯一字符 (难度:简单) - Day20201223

【一天一大 lee】字符串中的第一个唯一字符 (难度:简单) - Day20201223

20201223

题目:

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

示例:

s = "leetcode"
返回 0

s = "loveleetcode"
返回 2

提示:

你可以假定该字符串只包含小写字母

抛砖引玉

抛砖引玉

遍历-哈希

两次遍历:

  1. 统计每个字符的数量
  2. 返回第一次遇到的数量只有 1 的字符索引

如果没有遇到数量为 1 的字符返回-1

/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function(s) {
    const map = new Map()
    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
}

遍历-Unicode

提示中提到字符串只包含小写字母,则说明字符的 Unicode 是可以使用的

那么参照上面的遍历思路,声明一个长 26 的数组,按照字符的 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
}

队列

队列(queue):先进先出

遇到新字符第一次出现直接进入队列中,且标记其索引

遇到已经出现过的字符则将其出现的索引位置标记为-1,且将其从队列中的移除

var firstUniqChar = function(s) {
    const queue = [],
        // 标记字符出现的次数
        map = new Map()
    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)
            // 注意此时s[i]不一定在队列头部,需要遍历队列找出要移除的字符
            while (queue.length && map.get(queue[0][0]) === -1) queue.shift()
        }
    }
    return queue.length ? queue[0][1] : -1
}

博客: 前端小书童

每天的每日一题,写的题解会同步更新到公众号一天一大 lee 栏目 欢迎关注留言

公众号:前端小书童

本文分享自微信公众号 - 前端小书童(gaowenju_web),作者:前端小书童

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-12-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【一天一大 lee】反转字符串 (难度:简单) - Day20201008

    编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

    前端小书童
  • 一天一大 lee(反转字符串中的单词 III)难度:简单-Day20200830

    给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。

    前端小书童
  • 字符串中的第一个唯一字符

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

    WindrunnerMax
  • 【一天一大 lee】上升下降字符串 (难度:简单) - Day20201125

    在任何一步中,如果最小或者最大字符不止一个,你可以选择其中任意一个,并将其添加到结果字符串。

    前端小书童
  • 每天一道leetcode387-字符串中第一个唯一的字符

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

    乔戈里
  • 【一天一大 lee】重构字符串 (难度:中等) - Day20201130

    将所有字符规制到哈希表中,且记录每个字符出现的次数,然后当字符单个字符的间隔填充。

    前端小书童
  • 387 字符串中的第一个唯一字符

    给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。 (s只包含小写字母)

    木瓜煲鸡脚
  • LeetCode95|字符串中的第一个唯一字符

    本题使用键值对集合LinkedHashMap进行解决,使用LinkedHashMap的好处是因为链表的有序性,这样就可以找到第一个不重复的字符了,使用HashM...

    码农王同学
  • 387. 字符串中的第一个唯一字符

    CaesarChang张旭
  • 【一天一大 lee】比较含退格的字符串 (难度:简单) - Day20201019

    给定 S 和 T 两个字符串,当它们分别被输入到空白的文本编辑器后,判断二者是否相等,并返回结果。# 代表退格字符。

    前端小书童
  • LeetCode 387. 字符串中的第一个唯一字符

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

    freesan44
  • LeetCode 387: 字符串中的第一个唯一字符

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

    爱写bug
  • Leetcode 387:字符串中的第一个唯一字符

    和出现次数有关的,不要犹豫,hash 具体思路:首先用字典统计每个字符出现的频率,然后顺序遍历字符串,并在字典中进行查找,出现频率为1,返回。 时间复杂度O(n...

    故事尾音
  • Swift 字符串中的第一个唯一字符 - LeetCode

    1、将字符串转为数组 2、循环字符串数组,将字符作为键,索引作为值存入字典 3、存入字典时先判断是否已经存在,已存在则将值置位-1 4、循环字典,拿到所有...

    韦弦zhy
  • 漫画:字符串中的第一个唯一字符

    今天大多公司都开工了!疫情之下,应该是在家里办公吧~反正出不了家门,想偷懒的话就刷道算法题学习学习吧。

    程序员小浩
  • 【一天一大 lee】查找常用字符 (难度:简单) - Day20201014

    给定仅有小写字母组成的字符串数组 A,返回列表中的每个字符串中都显示的全部字符(包括重复字符)组成的列表。例如,如果一个字符在每个字符串中出现 3 次,但不是 ...

    前端小书童
  • 一天一大 leet(字符串相加)难度:简单-Day20200803

    上面方法为了完成逐位相加的逻辑对字符串进行了补位 可以使用记录索引即位置来避免真实操作字符串

    前端小书童
  • 一天一大 lee(表示数值的字符串)难度:中等-Day20200902

    例如,字符串"+100"、"5e2"、"-123"、"3.1416"、"-1E-16"、"0123"都表示数值,但"12e"、"1a3.14"、"1.2.3"、...

    前端小书童
  • leecode刷题(13) -- 字符串中的第一个唯一字符

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

    希希里之海

扫码关注云+社区

领取腾讯云代金券