在一個字串（0 <= 字串長度 <= 10000，全部由字母組成）中找到第一個只出現一次的字符，并回傳它的位置，如果沒有則回傳 -1（需要區分大小寫，從 0 開始計數）
解題思路
利用每個字母的 ASCII 碼做 hash 來作為陣列的下標，首先用一個長度為 58 的陣列來存盤每個字母出現的次數，為什么是 58 呢？是因為 A - Z 對應的 ASCII 碼為 65-90，a - z 對應的 ASCII 碼值為 97 - 122，而每個字母的 index = int(word) - 65，比如 g = 103 - 65 = 38，而陣列中具體記錄的內容是該字母出現的次數，最終遍歷一遍字串，找出第一個陣列內容為 1 的字母就可以了，時間復雜度為 O(n)
public class Solution {
public int FirstNotRepeatingChar(String str) {
if(str == null || str.length() == 0) {
return -1;
}
int[] res = new int[58];
for(int i = 0; i < str.length(); i++) {
res[str.charAt(i) - 65]++;
}
for(int i = 0; i < res.length; i++) {
if(res[str.charAt(i) - 65] == 1) {
return i;
}
}
return -1;
}
}
也可以使用 HashMap 來完成
import java.util.Map;
import java.util.HashMap;
public class Solution {
public int FirstNotRepeatingChar(String str) {
if(str == null || str.length() == 0) {
return -1;
}
Map<Character, Integer> map = new HashMap<>();
for(int i = 0; i < str.length(); i++) {
if(map.containsKey(str.charAt(i))) {
int count = map.get(str.charAt(i));
map.put(str.charAt(i), ++count);
} else {
map.put(str.charAt(i), 1);
}
}
for(int i = 0; i < str.length(); i++) {
if(map.get(str.charAt(i)) == 1) {
return i;
}
}
return -1;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/178071.html
標籤：其他