网站首页 > java教程 正文
描述
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从字符流中只读出前两个字符 "go" 时,第一个只出现一次的字符是 "g" 。当从该字符流中读出前六个字符 “google" 时,第一个只出现一次的字符是"l"。
数据范围:字符串长度满足 ,字符串中出现的字符一定在 ASCII 码内。进阶:空间复杂度 ,时间复杂度
后台会用以下方式调用 Insert 和 FirstAppearingOnce 函数
string caseout = "";
1.读入测试用例字符串casein
2.如果对应语言有Init()函数的话,执行Init() 函数
3.循环遍历字符串里的每一个字符ch {
Insert(ch);
caseout += FirstAppearingOnce()
}
2. 输出caseout,进行比较。
返回值描述:
如果当前字符流没有存在出现一次的字符,返回#字符。
示例1
输入:"google"
返回值:"ggg#ll"
示例2
输入:"abcdee"
返回值:"aaaaaa"
第一种方式
利用一个map来存储,字符作为key,出现次数作为value即可,每次取第一个value为1的key即可,代码如下
Map<Character,Integer> map = new LinkedHashMap<>();
public void firstInsert(char ch) {
if(map.get(ch) != null){
map.put(ch,2);
}else{
map.put(ch,1);
}
}
public char firstFirstAppearingOnce() {
if(null != map){
Iterator<Character> iterator = map.keySet().iterator();
while (iterator.hasNext()){
Character next = iterator.next();
if (map.get(next) == 1){
return next;
}
}
}
return '#';
}
第二种方式
不利用map,利用一个数组来标识每个字符,由于 ASCII 码一共128个,所以定义一个长度为128的数组即可,再定义一个队列(因为队列是先进先出),每次循环判断,如果发现当前出队列的值在数组中的值不是1,则直接抛弃,直到找到队列中第一个char,在数组中的值为1,代码如下
int[] ints = new int[128];
Queue<Character> queue = new LinkedList<>();
public void secondInsert(char ch) {
if(ints[ch]++ == 0){
queue.add(ch);
}
}
public char secondFirstAppearingOnce() {
while (!queue.isEmpty()){
Character peek = queue.peek();
if(ints[peek] == 1){
return peek;
}else {
queue.poll();
}
}
return '#';
}
猜你喜欢
- 2024-11-24 Java基础刷题,一篇入门
- 2024-11-24 LeetCode题解|1047.删除字符串中的所有相邻重复项
- 2024-11-24 java集合框架-Collection与List集合
- 2024-11-24 悟空云课堂 | 第三期:路径遍历漏洞的防范与检测
- 2024-11-24 LeetCode-043-字符串相乘
- 2024-11-24 Java面试:给你15到20分钟,你把这道编程题写下
- 2024-11-24 一个简单的字符串,为什么 Redis 要设计的如此特别
- 2024-11-24 Go&Java算法之至少有K个重复字符的最长子串
- 2024-11-24 2021-06-25:只由小写字母(a~z)组成的一批字符串,都放在字符
- 2024-11-24 剑指offer(二十七)-字符串的排列(Java版)
你 发表评论:
欢迎- 最近发表
-
- 五,网络安全IDA Pro反汇编工具初识及逆向工程解密实战
- 「JAVA8」- Lambda 表达式(java lambda表达式原理)
- 深入探讨Java代码保护:虚拟机保护技术的新时代
- Nginx反向代理原理详解(图文全面总结)
- 逆向拆解日本IT,哪些Java技术栈薪资溢价高
- mybatis 逆向工程使用姿势不对,把表清空了,心里慌的一比
- Spring Boot集成ProGuard轻松实现Java 代码混淆, Java 应用固若金汤
- 从 Java 代码逆向工程生成 UML 类图和序列图
- 人与人相处:尊重是标配,靠谱是高配,厚道是顶配
- Windows系统安装日期如何修改(windows10怎么修改安装日期)
- 标签列表
-
- java反编译工具 (77)
- java反射 (57)
- java接口 (61)
- java随机数 (63)
- java7下载 (59)
- java数据结构 (61)
- java 三目运算符 (65)
- java对象转map (63)
- Java继承 (69)
- java字符串替换 (60)
- 快速排序java (59)
- java并发编程 (58)
- java api文档 (60)
- centos安装java (57)
- java调用webservice接口 (61)
- java深拷贝 (61)
- 工厂模式java (59)
- java代理模式 (59)
- java.lang (57)
- java连接mysql数据库 (67)
- java重载 (68)
- java 循环语句 (66)
- java反序列化 (58)
- java时间函数 (60)
- java是值传递还是引用传递 (62)
本文暂时没有评论,来添加一个吧(●'◡'●)