遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法。
但是哈希法也是牺牲了空间换取了时间,因为我们要使用额外的数组,set或者是map来存放数据,才能实现快速的查找。
常见三种实现哈希表的数据结构:数组 set集合 map映射
下面是set map的
红黑树是一种平衡二叉搜索树,所以key值是有序的,但key不可以修改,改动key值会导致整棵树的错乱,所以只能删除和增加。
要使用集合来解决哈希问题的时候,优先使用unordered_set,因为它的查询和增删效率是最优的,如果需要集合是有序的,那么就用set,如果要求不仅有序还要有重复数据的话,那么就用multiset。
虽然std::set和std::multiset 的底层实现基于红黑树而非哈希表,它们通过红黑树来索引和存储数据。不过给我们的使用方式,还是哈希法的使用方式,即依靠键(key)来访问值(value)。所以使用这些数据结构来解决映射问题的方法,我们依然称之为哈希法。
题:
242.有效的字母异位词
思路:注意不要看到字符串处理有畏难心理
很简单,创建一个26个字符的数组,遍历s,对应字符-‘a' ++,反过来遍历t, --,如果有非零的则返回false;
49.字母异位词分组
思路1:可以用排序来进行,存储用unordered——map
思路2:计数
用int数组记录每个出现多少,然后输出如 2a3b等字符串来作为key值,再通过key值匹配,有点麻烦
438.找到字符串中所有字母异位词
思路:滑动窗口
首先将slen<plen的进行返回
然后对正常的进行处理
1.计数
2.减去头一个,加上后一个
3.每一次操作完都进行比较,如果正确则加入ans
标签:map,set,哈希,day7,随想录,数组,day1,key,异位 From: https://www.cnblogs.com/wzzz-blogs/p/18523765