美文网首页剑指offer- python实现
面试题50:第一个只出现一次的字符

面试题50:第一个只出现一次的字符

作者: 不会编程的程序猿甲 | 来源:发表于2020-03-28 21:14 被阅读0次

    题目一:
    在一个字符串(0<=字符串长度<=10000,全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1(需要区分大小写)。

    思路一:
    利用python的特性,可以用count()函数计算出某字符出现的次数,当出现的次数为1时,返回这个字符的索引即可,否则遍历完成之后返回-1.

    代码实现一:

    # -*- coding:utf-8 -*-
    class Solution:
        def FirstNotRepeatingChar(self, s):
            # write code here
            #利用python特性
            if not s or len(s)==0:
                return -1
            for i in s:
                if s.count(i)==1:
                    return s.index(i)
            return -1
    

    思路二:
    自建一个字典,保存字符出现的次数。然后再按照列表的字符顺序读取字典中相应键值出现的次数,如果为1则返回。这种方法的时间复杂度为O(n)。

    代码实现二:

    # -*- coding:utf-8 -*-
    class Solution:
        def FirstNotRepeatingChar(self, s):
            # write code here
            if not s or len(s) == 0:
                return -1
            #储存字符次数的字典
            numberDic = {}
            #建立字典
            for char in s:
                if char in numberDic:
                    numberDic[char]+=1
                else:
                    numberDic[char] =1
    
            #再次遍历列表查找字符
            for i, cha in enumerate(s):
                if numberDic[cha] == 1:
                    return i
            return -1  #如果没找到则返回-1
    

    提交结果:

    思路一结果 思路二结果

    题目二:字符流中第一个只出现一次的字符
    请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从字符流中只读出前两个字符"go"时,第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时,第一个只出现一次的字符是"l"。

    思路:
    这道题目的思想是将字符流存储在一个容器中然后再进行处理,需要两个成员变量字符列表和辅助的字符出现次数字典,思路与题目一大致相同,具体如下:

    50 字符流中第一个只出现一次的字符.png

    代码实现:

    # -*- coding:utf-8 -*-
    class Solution:
        # 返回对应char
        def __init__(self):
            self.alist = []   #容纳字符流的容器
            self.NumDic = {}  #保存次数的字典
        def FirstAppearingOnce(self):
            # write code here
            while len(self.alist)>0 and self.NumDic[self.alist[0]] !=1:
                self.alist.pop(0)   #将元素删除
            if len(self.alist)>0:
                return self.alist[0]
            else:
                return '#'
        def Insert(self, char):
            # write code here
            if char not in self.NumDic:
                self.alist.append(char)
                self.NumDic[char] = 1
            else:
                self.NumDic[char] +=1
    

    提交结果:

    题目二提交结果

    相关文章

      网友评论

        本文标题:面试题50:第一个只出现一次的字符

        本文链接:https://www.haomeiwen.com/subject/cuosuhtx.html