-
Notifications
You must be signed in to change notification settings - Fork 21
/
_050_First_Not_Repeat_Char.java
95 lines (78 loc) · 2.56 KB
/
_050_First_Not_Repeat_Char.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
package offerV2;
import java.util.BitSet;
import java.util.LinkedHashMap;
import java.util.Map;
/**
* @No v2-050,V1-035
* @problem 第一个只出现一次的字符
* @tag
* @author liyazhou
* @date 2017/5/30
*
* <pre>
* 在字符串中找出第一个只出现一次的字符。
* 如输入"abaccdeff",则输出'b'。
* </pre>
*/
public class _050_First_Not_Repeat_Char {
/**
* Note
*
* Thought
*
* Algorithm
* 1. 使用哈希表统计每一个字符出现的次数
* 2. 遍历哈希表,找出第一个出现次数为 1 的字符(不能使用排序)
*/
private static class Solution {
public int firstNotRepeatingChar2(String str) {
BitSet m1 = new BitSet(256);
BitSet m2 = new BitSet(256);
for (char ch : str.toCharArray()) {
if (!m1.get(ch) && !m2.get(ch)) {
m1.set(ch);
} else if (m1.get(ch) && !m2.get(ch)) {
m2.set(ch);
}
}
for (int i = 0; i < str.length(); i ++) {
char ch = str.charAt(i);
if (m1.get(ch) && !m2.get(ch)) {
return i;
}
}
return -1;
}
/**
* 2017-8-16 20:15:41
*/
public int firstNotRepeatingChar(String str) {
int[] chars = new int[128];
for(int i = 0; i < str.length(); i ++){
chars[str.charAt(i)] += 1;
}
for(int i = 0; i < str.length(); i ++){
if (chars[str.charAt(i)] == 1)
return i;
}
return -1;
}
public static Character firstDistinctChar(char[] chars){
if (chars == null) return null;
Map<Character, Integer> characterIntegerMap = new LinkedHashMap<>();
for (char ch : chars){
if (characterIntegerMap.containsKey(ch)) characterIntegerMap.put(ch, characterIntegerMap.get(ch)+1);
else characterIntegerMap.put(ch, 1);
}
Character result = null;
for (Map.Entry<Character, Integer> entry : characterIntegerMap.entrySet()){
// System.out.println(entry.getKey() + " :: " + entry.getValue());
if (entry.getValue() == 1) {
result = entry.getKey();
break;
}
}
return result;
}
}
}