<LeetCode天梯>Day017 字符串中的第一个唯一字符(哈希表+findrfind) | 初级算法 | Python

wuchangjian2021-11-04 16:40:08编程学习

💖作者简介:大家好,我是车神哥,府学路18号的车神🥇

📝个人主页:应无所住而生其心的博客_府学路18号车神_CSDN博客
🎉点赞评论收藏 == 养成习惯(一键三连)😋
📖本系列主要以刷LeetCode力扣)网站的各类题为标准,实现自我能力的提升为目标⚡
⚡希望大家多多支持🤗~一起加油 😁

  • 专栏《LeetCode天梯》

周四,xdm,北京今天又热起来了还,天气变化太快了,每天抢饭,食堂吃够了呀!疫情依旧反复,大家带好口罩啊~ 继续继续,来,今天和车神哥一起来提升自己的Python编程和面试能力吧,刷天梯~

以下为我的天梯积分规则

每日至少一题:一题积分+10分
若多做了一题(或多一种方法解答),则当日积分+20分(+10+10)
若做了三道以上,则从第三题开始算+20分(如:做了三道题则积分-10+10+20=40;做了四道题则积分–10+10+20+20=60


初始分为100分
若差一天没做题,则扣积分-10分(周六、周日除外注:休息
坚持!!!


初级算法

刷题目录

字符串

在这里插入图片描述

题干

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

示例:

s = “leetcode”
返回 0

s = “loveleetcode”
返回 2

提示:你可以假定该字符串只包含小写字母。


哈希表

分析:

本题找到不重复的字符,很明显的暗示,让我们用字典,哈希表来解题。通过字典确定每个字符的个数,然后再选出只有单次出现的字符,且选出最先出现的,返回其相对应的索引号。

class Solution:
    def firstUniqChar(self, s: str) -> int:
 		# 哈希表
        hashmap = {}
        for i in s:
            if i not in hashmap:
                hashmap.update({i:s.count(i)}) # 将数字各自出现的个数存入哈希表中

        for key,value in hashmap.items():   # 遍历哈希表的键值
            if hashmap[key] == 1:
                return s.index(key)
        return -1

哈希表的速度表现还不错的!~
在这里插入图片描述

索引count

分析:

我们还可以将字符串取为单个字符成list后,通过count计数,看在其中的个数是多少,遍历所有项,删除多余的项,若大于1,则不返回;若仅有一个字符,则返回其对应的索引号。若不存在,则返回-1.

class Solution:
    def firstUniqChar(self, s: str) -> int:
        # 将s中的单个字母取出来为单个字符串
        list1 = list(map(str, s))
        n = len(list1)
 		temp = 0
        list2 = list(map(str, s))
        for i in list1:
            if list1.count(i) > 1:
                list2.remove(i)   # 如果有,则删除list2里的对应值
        # 判断是否存在上述情况
        for j in list1:
            if list1.count(j) == 1:
                temp += 1
        if temp > 0:
            return list1.index(list2[0])   # 查询list2中删除完
        return -1

额,勇气可嘉,超出时间限制了,感觉不应该的啊
在这里插入图片描述
我们再进行优化一下

将temp的判断再细化一下

不遍历所有直接读取list2的参数,看是否删除了相同的值之后还存在值,如果还有则,返回第一个,如果没有,则返回-1。

class Solution:
    def firstUniqChar(self, s: str) -> int:
        # 将s中的单个字母取出来为单个字符串
        list1 = list(map(str, s))
        n = len(list1)
		list2 = list(map(str, s))
        for i in list1:
            if list1.count(i) > 1:
                list2.remove(i)   # 如果有,则删除list2里的对应值
        # 判断是否存在上述情况
        if len(list2) > 0:
            return list1.index(list2[0])   # 查询list2中删除完
        return -1

还是太菜了,超出时间限制了
在这里插入图片描述
不过肯定是能用的。

咱们只用内置函数试试

class Solution:
    def firstUniqChar(self, s: str) -> int:
		for i in range(len(s)):
            if s.count(s[i]) == 1:
                return i
        return -1

在这里插入图片描述
实时证明,确实很慢很慢,不考虑了。

两次遍历

我们可以使用两次遍历来输出,第一次遍历,将每个数字出现的次数保存在一个list中,第二次遍历这个list,如果一遇到值为1,则输出1所在的索引值,否则,返回-1.

class Solution:
    def firstUniqChar(self, s: str) -> int:
		c1 = []
        n = len(s)
        for i in range(n):
            c1.append(s.count(s[i]))
        
        for j in range(n):
            if c1[j] == 1:
                return j
        return -1

勇气可嘉,怎么还是超出时间限制啊o(╥﹏╥)o
在这里插入图片描述

find和rfind

此法骨骼极其清奇,简直不要太妙了。一个从前查找,一个从后查找,如果下标相等,说明只出现了一次

class Solution:
    def firstUniqChar(self, s: str) -> int:
		for x in s:
            if s.find(x) == s.rfind(x):
                return s.find(x)
        return -1

在这里插入图片描述
速度快了很多很多。

综合看来,哈希表法还是速度最快的方法,如果还有更好的方法,可在下面留言哦!~

References

作者:GODEYESCAO
链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn5z8r/?discussion=71JehT
来源:力扣(LeetCode)


今日得分:+10 +10+20
总得分:410

加油!!!

❤坚持读Paper,坚持做笔记,坚持学习,坚持刷力扣LeetCode❤!!!
坚持刷题!!!打天梯!!!
To Be No.1

⚡⚡


创作不易⚡,过路能❤关注收藏点个赞三连就最好不过了

ღ( ´・ᴗ・` )


明明付出远高于回报,却依旧选择硬着头皮做下去。只为了能在还未触及到的未来帮到你。或许这就是傻白甜吧。

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。