题目描述
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.
使用hashmap(该方法并不好，当数据量很多的时候，内存占用特别大)：
// 基本方法，并非最优，但是大多数人都是这个方法
import java.util.HashMap;
public class Solution {
public int FirstNotRepeatingChar(String str) {
if (str == null || str.length() == 0) return -1;
HashMap<Character, Integer> map = new HashMap<>();
int len = str.length();
char c;
for (int i = 0; i < len; ++i) {
c = str.charAt(i);
if (map.containsKey(c)) {
map.put(c, map.get(c) + 1);
} else {
map.put(c, 1);
}
}
for (int i = 0; i < len; ++i) {
if (map.get(str.charAt(i)) == 1) {
return i;
}
}
return -1;
}
} 使用位图方法：
关于位图基本理解可以随便上网搜，比如https://blog.csdn.net/yangquanhui1991/article/details/52172340这一篇，或者找其他的也行。
也可以查看BitSet源码，源码的<<循环移位很巧妙，不用求余运算，不过只是处理数据是否存在，而不是处理存在了一次或者多次的，所以不能直接用BitSet。
public class Solution {
final int ARRAYNUM = 10001 >> 4;//10001 * 2 / 32
final int[] arr = new int[ARRAYNUM];
public int FirstNotRepeatingChar(String str) {
char[] charArray = str.toCharArray();
int len = charArray.length;
for (int i = 0; i < len; ++i) {
set(charArray[i]);
}
for (int i = 0; i < len; ++i) {
if (get(charArray[i]) == 1) {
return i;
}
}
return -1;
}
private int get(char bitIndex) {
int wordIndex = bitIndex >> 4; // 数据项，bitIndex / 16,每个int元素可以表示16个字符，每个字符三种状态00未出现，01一次，10多次，2个bit位即可
int pos = (bitIndex & 31) << 1; // 偏移量，除以32的余数，每个数据项占2bit位，所以乘以2
int temp = (arr[wordIndex] >> pos) & 0x03;
return temp;
}
private void set(char bitIndex) {
int wordIndex = bitIndex >> 4; // 数据项，bitIndex / 16,每个int元素可以表示16个字符，每个字符三种状态00未出现，01一次，10多次，2个bit位即可
int pos = (bitIndex & 31) << 1; // 偏移量，除以32的余数，每个数据项占2bit位，所以乘以2
int temp = (arr[wordIndex] >> pos) & 0x03;
++temp;
if (temp >= 2) temp = 2;
if (temp == 2) { // 为2说明已经出现过一次，本次是重复的
arr[wordIndex] &= ~(0x03 << pos); // 先清空
}
// 为1说明字符未出现过，本次为第一次
arr[wordIndex] |= temp << pos; // 赋值
}
} ==============Talk is cheap, show me the code==============
京公网安备 11010502036488号