第一个只出现一次的字符(使用hashmap和使用位图)
发布日期:2021-06-30 19:56:32
浏览次数:3
分类:技术文章
本文共 2224 字,大约阅读时间需要 7 分钟。
题目描述
在一个字符串(0<=字符串长度<=10000,全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1(需要区分大小写).
题目链接:
使用hashmap(该方法并不好,当数据量很多的时候,内存占用特别大):
// 基本方法,并非最优,但是大多数人都是这个方法import java.util.HashMap;public class Solution { public int FirstNotRepeatingChar(String str) { if (str == null || str.length() == 0) return -1; HashMapmap = 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; }}
使用位图方法:
关于位图基本理解可以随便上网搜,比如这一篇,或者找其他的也行。
也可以查看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==============
转载地址:https://liuchenyang0515.blog.csdn.net/article/details/86688125 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月17日 03时22分38秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
solr修改schema文件(solr修改配置文件)
2019-04-30
Bootstrap datetimepicker日期时间插件使用方法(日期时间选择器)
2019-04-30
字体图标库(Font Awesome)的使用--绝佳的图标字体库和CSS框架
2019-04-30
select下拉框分组展示插件的使用--(select-mania插件的使用)
2019-04-30
Java 8新特性之--lambda表达式的使用和应用
2019-04-30
Java Lambda表达式的应用--Stream API操作集合框架
2019-04-30
省市区三级联动插件Distpicker--前端实现地区三级联动
2019-04-30
solr的使用详解
2019-04-30
Myslq连接(JDBC)url属性的参数的设置
2019-04-30
关于Java继承,重载及运行的顺序的总结
2019-04-30
关于Spring MVC与前端的交互
2019-04-30
Mybatis逆向工程的使用
2019-04-30
关于Hibernate的优缺点
2019-04-30
常用的 Maven 命令
2019-04-30
常用的20个正则表达式
2019-04-30
数据结构之顺序表的实现
2019-04-30
数据结构之线性链表
2019-04-30
JQuery使用validate插件完成校验
2019-04-30
关于java的继承
2019-04-30