【剑指Offer】34第一个只出现一次的字符

本是古典何须时尚 2022-05-04 09:57 68阅读 0赞

## 题目描述 ##

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

时间限制：1秒；空间限制：32768K；本题知识点：字符串

## 解题思路 ##

### 思路一 ###

利用python内置函数list.count()和list.index()。

# -*- coding:utf-8 -*-
    class Solution:
        def FirstNotRepeatingChar(self, s):
            # write code here
            s = list(s)
            a = set(s) #集合
            loc = len(s)
            for i in a:
                if s.count(i)==1 and s.index(i)<loc:
                    loc = s.index(i)
            if loc == len(s):
                return -1
            return loc

### 思路二 ###

用一个足够大的数组来存储所有字符的出现次数，初始化全为0，先遍历字符串一次来记录每个字符的出现次数，再遍历一次找到第一个出现次数为1的字符。

注意，python里将字符转化为ASCII码用到ord()函数，而不是int()函数。

# -*- coding:utf-8 -*-
    class Solution:
        def FirstNotRepeatingChar(self, s):
            # write code here
            # 初始化一个全为0的list用于记录字符
            l = [0]*256
            # 记录每个字符出现次数
            i = 0
            while i < len(s):
                l[ord(s[i])] += 1 #字符转换为ASCII码
                i += 1
            # 找到出现1次的字符
            i = 0
            while i < len(s):
                if l[ord(s[i])] == 1:
                    return i
                i += 1
            return -1