leetcode

一，题目大意：

找到字符串中没有重复的字符，并且这个字符是第一个出现的。

二、字符串题目条件：

输入的字符全部是小写，所以大小写区分这些问题就不用考虑了。

三、分析这类题目：

1，解题的方式有很多：可以用数组计数（最常用，也很快），集合的思想，特定的题目还可以用异或、减法做。

2，这里我们采用数组计数的方法解决。

3，其他题目举例： 不定顺序判断是否模式（数组计数） 找出两个字符串的唯一不同（数组计数，异或）

四、java解决这类题目：数组计数，但是这道题目有两个方向：

1，找第一个出现一次的字符时候，从计数数组出发，找到计数为1的。定义一个变量记录位置最小值，最后返回。（这种方向适合字符串大的）。

public static int firstUniqChar(String s) { int[] num = new int[26]; boolean flag = true; int min = s.length(); for(int i=0;i<s.length();i++) { num[s.charAt(i) - 'a']++; } for(int i = 0;i<num.length;i++) {//从计数数组出发 int now = s.indexOf(i+'a'); if(num[i] == 1 && now < min) { flag = false; min = now; } } if(flag) return -1; return min; }

2，找第一个出现一次的字符时候，从字符串出发。找到第一个计数为1的就可以返回了。（适合字符串小的，leetcode的测试数据都较小，用这个更快）

public static int firstUniqChar2(String s) { if(null == s || 0 == s.length() ) return -1; int[] hash = new int[26]; char[] array = s.toCharArray(); for(int i = 0; i < array.length; i++){ int num = array[i] - 'a'; hash[num]++; } for(int i = 0; i < array.length; i++){//从字符串出发 int num = array[i] - 'a'; if(hash[num] == 1){ return i; } } return -1; }

五、python解决这道题。

1，python的collections库：代码写起来很清爽，但是集合操作相对慢。

class Solution(object): def firstUniqChar(self, s): """ :type s: str :rtype: int """ d = collections.Counter(s) ans = -1 for x,c in enumerate(s): if d[c] == 1: ans = x break return ans

2，数组计数

class Solution(object): def firstUniqChar(self, s): """ :type s: str :rtype: int """ if len(s) == 0: return -1 hash = [0]*26 for i in s: hash[ord(i) - 97] += 1 for i in s: if hash[ord(i) -97] == 1: return s.index(i) return -1