前言
哈希原理:牺牲空间换时间
在做这个题目之前,我们先通过通过一些知识回顾一下哈希表
哈希表有三种表现形式:数组,set(集合),map(映射)
数组:数组中内存是连续的,时间效率很高,可以将下标作为键,值作为键值
应用:当题目限制了数值的大小,可以尝试用数组去解决,如果哈希值比较少,特别分散,跨度非常大,就不太能用数组了,容易造成空间极大的浪费。
Hashset:不允许有重复元素的集合 无序的 实现了Set接口
定义:HashMao<key,value>
常用方法:
add() 添加元素
contains() 判断元素是否存在于集合中
remoe() 删除元素
size() 计算大小
for(x:y) 使用for -each来进行迭代
应用:set集合底层有三种形式,分别是hashset,set,multiset。一般直接用hashset,效率高;如果是有序的用set,如果是有序有重复数据,用multiset;
HashMap:存储的内容是键值对的映射 ,实现了Map接口 无序的
常用方法:
put() 添加元素
get() 访问元素
remove() 删除元素
size() 计算大小
for(x:y) 使用for-each来进行迭代
应用:map集合底层有三种形式,分别是hashmap,map,multimap。一般直接用hashmap,效率高
在这里我给出几个相关数组,set,map的力扣练习题,传送门如下:
Leetcide349. 两个数组的交集 set练习
本题讲解的是map练习
题目描述
给你一个字符串数组,请你将字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词,所有源单词中的字母通常恰好只用一次。
示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
示例 2:
输入: strs = [“”]
输出: [[“”]]
示例3:
输入: strs = [“a”]
输出: [[“a”]]
提示:
1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母
一、思路
字母异位词就是由相同字符组成的不同顺序的词,整体流程就是;定义HashMao<key,value>,将字符串作为key,相同的字母异位词作为值,用一个列表来收集,通过遍历字符串,对于每个字符进行排序,然后组成一个新的字符串,map映射反映的是键值对的匹配,我们把字符串作为键,所以我们可以判断此时map映射中是否有新生成字符串的键,没有的话就创造并把原字符串加入,有的话就将这个加入就行,最后返回一个带有map键值的list列表。
二、参考代码
哈希表HashMap
class Solution { public List<List<String>> groupAnagrams(String[] strs) { HashMap<String,ArrayList> map = new HashMap<String,ArrayList>(); for(String str:strs){ char [] c =str.toCharArray(); Arrays.sort(c); String key = new String(c); if(map.get(key) == null){ map.put(key,new ArrayList<String>()); } map.get(key).add(str); } return new ArrayList(map.values()); } }
以上分析,希望对您有所帮助,您的支持是我最大的动力,感谢一键三连!!