数据结构-算法刷题(编程随想录结构、java版本思路)-爱代码爱编程
算法性能分析
数组
链表
哈希表
1、哈希表理论基础
- hash table :哈希表、散列表
- 哈希表是根据关键码的值而直接进行访问的数据结构。
- 常见的三种哈希结构:数组、set(集合)、map(映射)
- c++中std::unordered_set底层实现为哈希表,std::set 和std::multiset 的底层实现是红黑树,红黑树是一种平衡二叉搜索树,所以key值是有序的,但key不可以修改,改动key值会导致整棵树的错乱,所以只能删除和增加。——对应java中 HashSet、TreeSet
- c++中std::unordered_map 底层实现为哈希表,std::map 和std::multimap 的底层实现是红黑树。同理,std::map 和std::multimap 的key也是有序的。——对应java中有 HashMap、TreeMap
- 当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法。
2、有效的字母异位词
- 题目:https://leetcode.cn/problems/valid-anagram/
- 思路:字母只会有26个,使用数组哈希,以出现过的字符与字符’a’的数值差为索引;遍历第一个字符串中每个字符,对应数组哈希位置++,遍历第二个字符串–,最后遍历数组,如果有不为0的位置返回false;否则为true
3、两个数组的交集
- 题目:https://leetcode.cn/problems/intersection-of-two-arrays/
- 思路:输出结果中每个元素是唯一的,不重复、不考虑顺序——HashSet。先遍历数组1,将所有出现过的元素添加到HashSet,再遍历数组2,其中的元素如果在HashSet中出现就添加到结果的集合中,最后记得将结果转为数组返回。
4、快乐数
- 题目:https://leetcode.cn/problems/happy-number/
- 思路:替换过程可能会无限循环——将所有出现过的结果添加到HashSet中,只要结果不是目标1就进行操作,每次替换操作之前判断当前要替换的数是否出现过,出现过直接false;没出现过加到HashSet中,进行替换操作——取余、取模操作。
5、两数之和
- 题目:https://leetcode.cn/problems/two-sum/
- 思路:遍历每个数的时候,判断target和他的差是否出现过,如果出现过要取出那个数的索引——既要判断存不存在,又要取一个对应的值——HashMap。遍历数组中的每个数,判断target和它的差是不是在 HashMap中,存在取出索引和当前值的索引放到数组返回;否则将当前数放进HashMap,用于后面的数的判断。