題目描述
請實作一個函式用來找出字符流中第一個只出現一次的字符，
例如，當從字符流中只讀出前兩個字符"go"時，第一個只出現一次的字符是"g"，
當從該字符流中讀出前六個字符“google"時，第一個只出現一次的字符是"l"，
如果當前字符流沒有存在出現一次的字符，回傳#字符，
思路
設定一個陣列，記錄每個字符的三種狀態：未出現（0），出現一次（1），多次出現（-1）， 設定一個佇列，記錄每次從字符流中讀取時，尚未出現過的字符， 查詢當前已讀取的字符流中第一個只出現一次的字符，需要判斷隊首字符狀態，執行出列操作直至隊首元素只出現過一次，時間復雜度O(1)，空間復雜度O(1)，
代碼
import java.util.Queue;
import java.util.LinkedList;
public class Solution {
private int[] map = new int[256];
private Queue<Character> queue = new LinkedList<Character>();
//Insert one char from stringstream
public void Insert(char ch) {
if(map[ch] == 0) {
map[ch] = 1;
queue.offer(ch);
} else if(map[ch] == 1) {
map[ch] = -1;
}
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce() {
while(!queue.isEmpty() && map[queue.peek()] == -1) {
queue.poll();
}
if(!queue.isEmpty()) {
return queue.peek();
}
return '#';
}
}
筆記
無
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/79566.html
標籤：其他
下一篇：簡單實用演算法—陣列亂序