LeetCode算法(哈希)
今天的算法内容是哈希相关的题目,难度比数组和链表大,但是可能我习惯了python的字典,hash的理解更容易一些,大家如果不知道hash的概念,请自行搜一下大佬们的讲解,我叙述的没他们好,那么下面就开始今天的练习
1.有效字母异位词
链接:有效字母异位词
简述一下目标,比如说有 abc ,cab
字母abc 和 字母cab 的字母个数是一样的
都是 a:1 b:1 c:1
这样的词称为异位词,我们需要写出一个算法来判断两个字母是否为异位词
思路:
(1)建立一张hash表,key为字母,value为字母出现的次数
(2)遍历任意一个字符串,将遍历到的字母,对应的value值+1,证明该字母出现过一次
(3)遍历另一个字符串,将遍历到的字母,对应的value值-1
(4)遍历hash表,查看所有的value值是否存在为0的,如果都为0则证明是异位词,反之不是
注意:
这里hash表中的key,其实并不是真正的字母,而是通过映射来对应字母,因为hash表的本质还是一个数组,所以我们通过字母与索引的映射来一一对应。每个字母有自己的 ASCII 。通过ASCII来进行映射关系,而hash也是通过数组来体现。
举例:
字母a - 字母a = 0
字母b - 字母a = 1
字母c - 字母a = 2......以此类推
所以,索引0-25,对应的就是26个字母。代码如下:
public class LetterEctopicWords {/*** 字母异位词*/public boolean isAnagram(String s, String t) {int[] record = new int[26];for (int i = 0; i < s.length(); i++) {int num = s.charAt(i) - 'a';record[num]++;}for (int i = 0; i < t.length(); i++) {int num = s.charAt(i) - 'a';record[num]--;}for (int j : record) {if (j != 0) {return false;}}return true;}}
2.两个数组的交集
链接:两个数组的交集
这里需要新知道一个hash的数据结构,hashSet,Set简单一句话总结就是无序不重复的集合,主要的作用就是去重,知道这个概念就可以继续往下进行了
比如两个数组:[1221],[22],它们的交集就是[2]
思路:引入set后,可以将一个数组进行第一波去重处理,然后遍历第二个数组,和去重后的第一个数组进行比较,如果相同,则添加到结果集set中,不相同则跳过,最后遍历set结果集,添加到数组进行返回即可
import java.util.HashSet;
import java.util.Set;public class IntersectionOfTwoArrays {/*两个数组的交集*/public int[] intersection(int[] nums1, int[] nums2) {//首先是创建一个set集合用于存放唯一元素//遍历第二个数组,在set集合取值进行判断,如果存在,则放入数组,如果不存在则不做操作Set<Integer> set1 = new HashSet<>();Set<Integer> set2 = new HashSet<>();for (int num : nums1) {set1.add(num);}for (int num : nums2){if (set1.contains(num)){set2.add(num);}}int[] result = new int[set2.size()];int index = 0;for (int i : set2) {result[index] = i;index++;}return result;}
}
3.两数之和
链接:两数之和
这道题就正式的需要hashMap了,也就是键值对,在使用之前需要说一下,该如何判断什么时候使用hashmap。
首先就是,既需要目标的数据,还需要目标的索引,或者是其他的两个条件,这种时候就要使用hashmap了。
简单说一下题目
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
这里发现,既需要获取数组的元素,又需要获取元素的索引,所以考虑使用hashmap
当我们拿到一个元素,例如2时,我们需要找到 9 - 2 也就是 7 ,去配对,那么就可以写代码了
思路:
(1)首先需要一个hashmap,key为元素的值,value为对应的索引
(2)遍历数组,并计算当前元素与目标结果的差值
(3)判断map中是否含有该差值,如果有则获取其索引和当前元素索引,返回
(4)如果没有,则把当前元素放入到map表中。
代码如下:
import java.util.HashMap;
import java.util.Map;public class SumOfTwoNumbers {/*两数之和*///使用哈希表public int[] twoSum(int[] nums, int target) {//首先定义一个返回值,为两个长度的数组,存储两个数的下标//定义一个hashmap,key为数,value为该数的下标//遍历数组,并计算当前数值与target的差值,如果差值已经在hashmap里了,直接返回//如果不在,则将当前数值及索引放入hashmapint[] result = new int[2];HashMap<Integer,Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++){int complement = target - nums[i];if (map.containsKey(complement)){result[0] = map.get(complement);result[1] = i;return result;}map.put(nums[i],i);}return null;}
}
4.字母异位词分组
链接:字母异位词分组
异位词还是和第一道题一样
例子:
输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
输出:
[
[“ate”,“eat”,“tea”],
[“nat”,“tan”],
[“bat”]
]
从示例发现,每个异位词其实只有一种分类,比如说e,a,t这三个字母,排序过后就是aet,其他有这三个字母的字符串,经过排序后,都会变成aet,那么只需要将所有的字符串排序,并找到自己对应排序后的异位词就可以了。
思路:
(1)构建一个map,key为排序后的字符串,value为对应异位词的集合
(2)遍历数组,取每个字符串
(3)将字符串进行排序,并在map中进行匹配
(4)如果没有,例如第一个字符串进入时,map一定是空的,则将排序后的字符串放入,并将自己放入到其对应的value中,而有的情况直接放入就好,所以先判断是否存在,不存在直接放入,然后再把自己添加进去
(5)返回map中所有的value
代码如下:
import java.util.*;public class AlphabetHeterotopicWordGrouping {/*字母异位词分组*/public List<List<String>> groupAnagrams(String[] strs) {//思路://首先新建一个hashmap,key值为排序后的字符串,value为对应的集合//然后遍历字符串数组,将字符串进行排序//判断hashmap中是否有对应排序后的字符串,如果没有,则以当前排序后的字符串为key,新建一个集合为value//然后获取hashmap的对应键的value集合,将当前字符串添加进去HashMap<String,List<String>> hashMap = new HashMap<>();for (String str : strs){char[] chars = str.toCharArray();Arrays.sort(chars);String sortStr = new String(chars);if (!hashMap.containsKey(sortStr)){hashMap.put(sortStr,new ArrayList<String>());}//自己也需要添加到排序后的集合中hashMap.get(sortStr).add(str);}return new ArrayList<>(hashMap.values());}}
5.最长连续序列
链接:最长连续序列
例子:
输入:nums = [100,4,200,1,3,2]
输出:4
解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
看到这题,第一个想法就是,先排序,其次是去重,因为连续序列一定是从小到大的,且唯一
第二就是连续的条件, 后者 - 1 = 前者。
第三就是 全局最大值 和 一部分数的最大值的变化,记录一部分的最大值,并更新全局最大值
思路:
(1)使用Hashset,先对数组进行去重,然后排序
(2)将HashSet转变为list,方便后续遍历
(3)设置最大连续值 = 0,和部分最大连续值变量 = 1(因为一个数字也算)
(4)设置条件,如果,后者 - 1 = 前者。认为是连续,将部分最大连续值+1
(5)如果不是连续,将更新全局最大值,并将部分最大连续值重置
(6)最后更新全局最大值,返回
代码如下:
import java.util.*;public class LongestContinuousSequence {/*最长连续序列*/public int longestConsecutive(int[] nums) {//使用Hashset,先对数组进行去重,然后排序//使用变量来记录当前最长序列,和当前序列长度,如果当前值减去前一个值为1,则为连续,变量自增//如果不为1,则证明不是连续,当前序列长度变为1,最后比较最长序列和当前序列长度Set<Integer> integerSet = new HashSet<>();for (int num : nums) {integerSet.add(num);}// 将 HashSet 转换为 List 并排序List<Integer> sortList = new ArrayList<>(integerSet);Collections.sort(sortList);// 如果列表为空,返回 0if (sortList.size() == 0) {return 0;}// 变量声明int longSequence = 0;int nowSequence = 1;// 计算最长连续序列for (int i = 1; i < sortList.size(); i++) {if (sortList.get(i) == sortList.get(i - 1) + 1) {nowSequence++;} else {longSequence = Math.max(longSequence, nowSequence);nowSequence = 1;}}// 更新最长连续序列longSequence = Math.max(longSequence, nowSequence);return longSequence;}}
今天有关hash的差不多就到这里了,有不对不理解的地方请指出!谢谢大家