leetcode习题分类汇总-HashCode篇




### Contains Duplicate-判断数组中是否有重复值

思路:创建hashmap key对应值,然后遍历 时间复杂度O(n),空间复杂度O(n)







### Happy Number-

Example: 19 is a happy number

12 + 92 = 82 82 + 22 = 68
62 + 82 = 100 12 + 02 + 02 = 1

解题思路:一开始直接模拟,循环100次还不是1直接剪掉return false,也能AC,
但是毕竟可能有情况覆盖不到,改用HastSet存放中间数就行了,
如果得到的新结果在中间数集合中出现了,那么一定会陷入循环并且得到的不是1。





### Anagrams-返回string[]中所有回文字符串

思路:
首先简单介绍一下Anagram(回文构词法)。Anagrams是指由颠倒字母顺序组成的单词,比如“dormitory”颠倒字母顺序会变成“dirty room”,“tea”会变成“eat”。

回文构词法有一个特点:单词里的字母的种类和数目没有改变,只是改变了字母的排列顺序。

由此我们可以想到,只要将几个单词按照字母顺序进行排序,就可以通过比较判断他们是否是anagrams。
思路:用map<string, int>记录排序后的字符串以及首次出现的位置。

1. 从strs的第一个元素开始遍历,首先对元素进行排序得到s;

2. 在map里查找s;

3. 若不存在,将s以及该元素的下标存入map<string ,int>;

4. 若存在,首先将第一次出现s时的原始字符串存入结果res,即strs[map[s]],并将map[s]设置为-1(防止下次再存),再将该字符串本身存入结果res;

5. 重复以上1-4步,直到遍历结束。



### Isomorphic Strings-

For example,
Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

思路:hashmap存储对应值,遍历判断

### Longest Substring Without Repeating Characters-返回字符串无重复的字符个数

思路:两个指针确定max,用hashmap存储数据




### Two Sum-数组中寻找两个数之和等于目标值,假设有且只有一个解。

思路:(1)先排序,然后两个指针一个在左一个在右边,时间logN+N;

(2)减少时间复杂度一般采用hashtable,这样可以省去排序的时间,key为target-当前值,value为当前i,如果碰到第二个合适的数就可以根据hash找到前一个数的索引然后存入int[2]里就可以了,时间N,空间N





### Fraction to Recurring Decimal-分数化为小数

思路:
难点:如何识别循环体?

解决方法:用一个HashMap记录每一个余数,当出现重复的余数时,那么将会进入循环,两个重复余数之间的部分就是循环体。

示例:1/13=0.076923076923076923…,当小数部分第二次出现0时,就意味着开始了循环,那么需要把076923用括号括起来,结果为0.(076923)。

涉及技巧:1)在不断相除的过程中,把余数乘以10再进行下一次相除,保证一直是整数相除;2)HashMap的key和value分别是<当前余数, 对应结果下标>,这样获取076923时就可根据value值来找。

注意点1:考虑正负数,先判断符号,然后都转化为正数;

注意点2:考虑溢出,如果输入为Integer.MIN_VALUE,取绝对值后会溢出。

一定要先把 int 转为 long,然后再取绝对值。如果写成 long num = Math.abs(numerator) 就会有问题,因为这句代码在 numerator=Integer.MIN_VALUE 时相当于 long num = Math.abs
(-2147483648),这样得到的 num还是 -2147483648。





总结:重点掌握在什么情况下可能利用,比如在需要索引存储当前值以便以后利用,是否会再次出现等情况采用hashmap,O(1)时间复杂度查找删除元素采用hashset。