题目

描述

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
后台会用以下方式调用Insert 和 FirstAppearingOnce 函数
string caseout = "";
1.读入测试用例字符串casein
2.如果对应语言有Init()函数的话，执行Init() 函数
3.循环遍历字符串里的每一个字符ch {
Insert(ch);
caseout += FirstAppearingOnce()
}
2. 输出caseout，进行比较。

返回值描述：

如果当前字符流没有存在出现一次的字符，返回#字符。

解题思路

Insert()为字符的输入，我们可以在输入字符的时候直接使用HashMap记录字符出现的次数，并且记录所有的字符，时间复杂度为O(1),空间复杂度为O(n)

FirstAppearingOnce()查找字符出现次数为1的，可以设置偏移量下标，在HashMap中查找出现为1的字符，时间复杂度为O(n)

import java.util.HashMap;
public class Solution {
  //Insert one char from stringstream
  //保存字符以及字符出现的次数
  HashMap<Character,Integer> map = new HashMap<>();
  //保存出现的所有字符
  StringBuffer charString = new StringBuffer();
  //保存偏移量
  Integer index = 0;
  public void Insert(char ch)
  {
      charString.append(ch);
      // 默认次数为1
      Integer count = 1;
      // 如果字符出现过，就可以将其设置2
      if (map.containsKey(ch)){
          map.put(ch, count+1);
      }else {
      // 如果没有出现过则为1
          map.put(ch, count);
      }
  }
  //return the first appearence once char in current stringstream
  public char FirstAppearingOnce()
  {
  // 从偏移量开始查找
      for ( ; index < charString.length(); index++ ){
          Integer count = map.get(charString.charAt(index));
          // 如果字符出现的次数为1，则表示查找到了
          if (count == 1){
              return charString.charAt(index);
          }
      }
      // 所有的字符出现次数都不为1，返回'#'
      return '#';
  }
}

题解 | #字符流中第一个不重复的字符#

题目

描述

返回值描述：

解题思路