给定一个字符串s,找到它的第一个不重复的字符,并返回它的索引。如果不存在,返回-1.
方法一:(python) 超时
找到所有只出现一次的字符,并记录它们的索引。如果索引存在,返回索引集合中的最小值。如果这样的索引集合为空,返回-1
方法二:(超时)
按顺序记录每一个字符出现的频率。找到第一个频率值为1的字符。 返回它的索引。如果所有的频率值都不为1,返回值为-1.
方法三:hashmap
使用字典。 定义一个字典,以s的字符作为“key”, 每个字符出现的个数作为“value”。遍历s, 如果字典已经存在一个“key”和s中的字符相同,就不必计算此字符在s中的个数;如果s中的字符不在字典的"key"中,计算此字符的个数,同时,如果这个字符的个数为1, 直接返回这个字符在s中的索引。
遍历完s, 没有找到值为1的key,那么就返回-1.
注意,使用字典,因为字典的key是不能重复的。那么以原始字符串中的字符作为key,就会减少重复运算的次数。不会导致“超时”。
方法四:
将字符串临时保存,遍历每一个字符,如果此字符的个数不为1, 那么就在临时字符串中删除此字符;如果此字符的个数为1, 那么在原始字符串中找到这个字符的索引, 并返回。如果遍历完字符串,没有找到个数为1的字符,返回-1.
注意:使用临时字符串的目的是,可以不断的删除不满足条件的字符,这样临时字符串的长度越来越小,不会导致“超时”,同时也不会影响原始字符串的查找功能。
方法五:定义一个固定长度的list,用来存字符串中每个字符的个数。
遍历s,计算每个字符出现的次数, 存到list; 遍历s,以s中字符作为索引的list中最先遍历到的“1”对应的字符就是所求,并返回这个字符在s中的索引。
注意:“以s中的字符为list的相对索引”: s中的每个字符都有对应的整数(unicode转换)。一共26个字母。这样就可以
或者:
注意:可以遍历s。但是,不能储存len(s)个字符出现的个数,因为会“超时”。所以,存储s中出现字符个数的list的长度需要限制。一共有26个字母。这里list的长度就是26。
领取专属 10元无门槛券
私享最新 技术干货