题目一:
在一个字符串(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"。
思路:
这道题目的思想是将字符流存储在一个容器中然后再进行处理,需要两个成员变量字符列表和辅助的字符出现次数字典,思路与题目一大致相同,具体如下:
代码实现:
# -*- 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
提交结果:
题目二提交结果
网友评论