Leetcode Answers 387

接着刷,第二道题是一道easy的题,就当舒缓心情了。

题目:
Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

Examples:

1
2
3
4
5
s = "leetcode"
return 0.
s = "loveleetcode",
return 2.

Note: You may assume the string contain only lowercase letters.

思路:
Easy问题嘛,要找unique还得index最小,那么首先想到的就是如何mark unique,其次要按顺序mark,最后遍历map找mark的最小index,如此直观地看就可以了。那么先是一个Dictionary 来保存每个char出现的最小index,一旦出现了重复就把index换成范围外的数字,比如s.Length,接着第二遍遍历从头找第一个合法的index,没有就是-1。结束。

Answer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
public int FirstUniqChar(string s) {
var dict = new Dictionary<char, int>();
var len = s.Length;
for(int i = 0; i< len; i++){
if(dict.ContainsKey(s[i])){
dict[s[i]] = len;
}else{
dict[s[i]] = i;
}
}
int min = len;
for(int i=0;i<len;i++){
if(dict[s[i]] < min){
min = dict[s[i]];
break;
}
}
return min == len ? -1 : min;
}
}

考察:应该是有更快的方法,但是我觉得这个已经是所想即所得了,就放这了。

以上。

17-04-27
@Sturbridge