散列表 leetcode 哈希算法 Day6--数据结构与算法（Java) 哈希表（数组，Set,Map)

一，242.有效的字母异位词（哈希表，用数组来实现）

力扣题目链接

数组其实就是一个简单哈希表，而且这道题目中字符串只有小写字符，那么就可以定义一个数组，来记录字符串s里字符出现的次数。

需要把字符映射到数组也就是哈希表的索引下标上，因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。

再遍历 字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，并不需要记住字符a的ASCII，只要求出一个相对数值就可以了。 这样就将字符串s中字符出现的次数，统计出来了。

class Solution {

public boolean isAnagram(String s, String t) {

int record[]=new int[26];

for(int i=0;i

{

record[s.charAt(i)-'a']++;

}

for(int i=0;i

{

record[t.charAt(i)-'a']--;

}

for(int i=0;i

{

if(record[i]!=0)

return false;

}

return true;

}

}

其中，最后的for可以采用增强for的写法，简化代码,count就是对record遍历得到的元素

for(int count:record)

{

if(count!=0)

return false;

}

二，349. 两个数组的交集(利用Set下的HashSet来实现）

力扣题目链接

这道题目，主要要学会使用一种哈希数据结构：HashSet，这个数据结构可以解决很多类似的问题,底层是用哈希表实现的。

class Solution {

public int[] intersection(int[] nums1, int[] nums2) {

int []b=new int[0];

if(nums1==null||nums1.length==0||nums2==null||nums2.length==0)

return b;

Set set1=new HashSet<>();

Set resultSet=new HashSet<>();

for(int i:nums1)

{

set1.add(i);

}

for(int i:nums2)

{

if(set1.contains(i))

resultSet.add(i);

}

return resultSet.stream().mapToInt(x->x).toArray();

}

}

 其中，

int []b=new int[0];

if(nums1==null||nums1.length==0||nums2==null||nums2.length==0)

return b;

可以简写为

if(nums1==null||nums1.length==0||nums2==null||nums2.length==0)

return new int[0];

同时，代码中采用了增强for的形式，采用for形式，代码如下：

for(int i=0;i

{

if(set1.contains(nums2[i]))

resultSet.add(nums2[i]);

}

同时将集合转换为数组的代码如下所示：

return resultSet.stream().mapToInt(x->x).toArray();

 // .stream()得到的是一个Stream流对象,而.mapToInt()得到的是一个IntStream流对象

 参见博客：http://t.csdn.cn/GKbxM

 三，第202题. 快乐数

力扣题目链接

题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！

正如：关于哈希表，你该了解这些！ (opens new window)中所说，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。

所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。

class Solution {

public boolean isHappy(int n) {

Set record=new HashSet<>();

while(n!=1&&record.contains(n)==false)

{

record.add(n);

n=getNumber(n);

}

return n==1?true:false;

}

public int getNumber(int n)

{

int sum=0;

while(n>0)

{

int temp=n%10;//得到最后一位

sum+=temp*temp;

n=n/10;//去掉最后一位；

}

return sum;

}

}

while段代码可以简写如下：

while(n!=1&&!record.contains(n))

{

record.add(n);

n=getNumber(n);

}

return n==1;

四，1. 两数之和 

力扣题目链接

这道题 我们需要 给出一个元素，判断这个元素是否出现过，如果出现过，返回这个元素的下标。

那么判断元素是否出现，这个元素就要作为key，所以数组中的元素作为key，有key对应的就是value，value用来存下标。

所以 map中的存储结构为 {key：数据元素，value：数组元素对应的下标}。

在遍历数组的时候，只需要向map去查询是否有和目前遍历元素比配的数值，如果有，就找到的匹配对，如果没有，就把目前遍历的元素放进map中，因为map存放的就是我们访问过的元素。

class Solution {

public int[] twoSum(int[] nums, int target) {

int [] result=new int[2];

if(nums==null||nums.length==0)

{

return result;

}

Map map=new HashMap<>();

for(int i=0;i

{

int temp=target-nums[i];

if(map.containsKey(temp))

{

result[0]=map.get(temp);

result[1]=i;

}

map.put(nums[i],i);

}

return result;

}

}

注意nums==null和nums.length==0的区别，最好两个都写上，防止报错。

http://t.csdn.cn/pdWnm

相关文章