网站cms企业,公司网页制作html代码,保世基官方网站建设,东莞企业黄页资料目录
前言
哈希表
1. 两数之和 - 力扣#xff08;LeetCode#xff09;
算法分析
算法代码
面试题 01.02. 判定是否互为字符重排
编辑算法分析
算法代码
217. 存在重复元素
算法分析
算法代码 219. 存在重复元素 II
算法分析
算法代码
解法二
算法代码
算法…
目录
前言
哈希表
1. 两数之和 - 力扣LeetCode
算法分析
算法代码
面试题 01.02. 判定是否互为字符重排
编辑算法分析
算法代码
217. 存在重复元素
算法分析
算法代码 219. 存在重复元素 II
算法分析
算法代码
解法二
算法代码
算法分析
算法代码
49. 字母异位词分组 算法分析
算法代码 前言
当我们想要快速查找某个值是否存在或者想要对数据进行去重的时候我们有没有方法可以解决上面这些问题我们可以用哈希表。
哈希表
哈希表Hash Table是一种通过哈希函数将键key映射到表中位置来访问记录的数据结构它具有高效的数据查找、插入和删除能力。
我们什么时候可以使用哈希表 在快速查找、频繁统计、快速映射、去重的情景下都可以使用哈希表。 我们来通过算法题目来更好的了解哈希算法。
1. 两数之和 - 力扣LeetCode 算法分析
本道题要求我们从数组中找两个数并且两数之和为target。这道题可以采用暴力枚举时间复杂度为O(n^2)如果在大量数据的情况下是会超时的那么我们可以采用哈希算法来解决这道题。
我们可以在hash表中存储元素以及其下标的映射。在遍历数组的过程每次判断target-当前元素是否在hash表中存在如果不存在那就将
当前元素以及其下标存到hash表中反之如果找到那么就取出下标返回。
为什么不将所有元素都放进去hash表再进行判断这样的话就无法解决元素重复的问题。假设目标值为2那么现在有1我们如果将1先放进了hash表那么我们在遍历的时候可以找到1但实际上这两个1是同一个。而如果我们先判断hash表中是否存在target-当前元素的元素则可以避免出现重复的情况。
算法代码
/*** 解决方案找出数组中两个数之和等于目标值的数对索引* 方法使用哈希表实现* 时间复杂度O(n)其中n是数组的长度* 空间复杂度O(n)需要额外的空间来存储哈希表* * param nums 输入的整数数组* param target 目标值寻找两数之和等于此值* return 返回一个长度为2的整数数组包含满足条件的两个数的索引如果不存在这样的数对则返回{-1, -1}*/
public int[] twoSum(int[] nums, int target) {// 利用哈希表来存储已经遍历过的数字及其索引以便快速检查目标值与当前值的差值是否已经出现过HashMapInteger,Integer mapnew HashMap();for(int i0;inums.length;i){// 检查当前数字与目标值的差值是否已经在哈希表中if(map.containsKey(target-nums[i])){// 如果差值存在则找到了满足条件的两个数返回它们的索引return new int[]{map.get(target-nums[i]),i};}else{// 如果差值不存在将当前数字及其索引放入哈希表中以供后续查找使用map.put(nums[i],i);}}// 如果遍历完整个数组后仍未找到满足条件的数对返回{-1, -1}return new int[]{-1,-1};
}时间复杂度为O(n),空间复杂度为O(n).
面试题 01.02. 判定是否互为字符重排
算法分析
本道题其实就是要判断两个字符串是否是一样那么我们就可以两个hash表来存储每次字符出现的次数如果两个hash表对应的值都相等那就说明两个字符串是一样的。
算法代码 /*** 检查两个字符串是否互为字符重排* * param s1 第一个字符串* param s2 第二个字符串* return 如果两个字符串互为字符重排则返回true否则返回false*/public boolean CheckPermutation(String s1, String s2) {// 如果两个字符串长度不同则它们不可能互为字符重排if (s1.length() ! s2.length()) {return false;}// 如果任一字符串为空则它们不可能互为字符重排if (s1.length() 0 || s2.length() 0) {return false;}// 创建一个哈希表来存储字符出现的次数ASCII码共有128个字符额外留一个位置给可能的空字符int hash[] new int[129];// 遍历第一个字符串统计每个字符出现的次数for (int i 0; i s1.length(); i) {char ch s1.charAt(i);hash[ch];}// 遍历第二个字符串检查每个字符是否在哈希表中出现过并减少相应字符的计数for (int i 0; i s2.length(); i) {char ch s2.charAt(i);// 如果字符在哈希表中的计数为0则说明两个字符串的字符组成不同if (hash[ch] 0) {return false;}hash[ch]--;}// 如果所有字符都能一一对应且没有多余的字符则两个字符串互为字符重排return true;}
217. 存在重复元素 算法分析
这道题就是要求在数组中有没有一个元素是出现超过两次的我们可以用哈希算法来解决这道题利用HashSet如果set里面没有存在当前元素就将当前元素存到set中反之如果有则返回true。
算法代码 public boolean containsDuplicate(int[] nums) {HashSetInteger hashSetnew HashSet();for(int i0;inums.length;i){if(hashSet.contains(nums[i])){return true;}hashSet.add(nums[i]);}return false;} 219. 存在重复元素 II 算法分析
跟上一道题类似不过这里还需要将下标进行存储需要利用HashMap在遍历的过程中如果当前元素在hashmap中已经存在那么就判断这两个元素之间的距离如果小于k则返回true否则将当前元素以及其下标存储到hashmap中。
算法代码
/*** 检查数组中是否存在两个相同的数字且它们的索引之差的绝对值最大为k* 这个方法通过使用HashMap来跟踪数字及其最后出现的索引来实现* 如果发现重复数字并且它们的索引之差不超过k则返回true* 如果不满足这些条件则在遍历完整个数组后返回false* * param nums 输入的整数数组* param k 索引之差的绝对值的最大允许值* return 如果找到至少一对索引之差的绝对值不超过k的相同数字则返回true否则返回false*/public boolean containsNearbyDuplicate2(int[] nums, int k) {// 使用HashMap来存储数字及其对应的索引HashMapInteger, Integer map new HashMap();for(int i0;inums.length;i){// 检查当前数字是否已经在HashMap中存在if(map.containsKey(nums[i])){// 如果当前数字已存在并且当前索引与之前索引之差不超过k则返回trueif(i-map.get(nums[i])k){return true;}}// 更新或添加当前数字及其索引到HashMap中map.put(nums[i],i);}// 如果没有找到满足条件的数字对则返回falsereturn false;}
时间复杂度为O(n),空间复杂度为O(n)
解法二
对于这道题我们还可以通过滑动窗口的思想来解决题目要求在数组中找两个相同的元素并且他们下标的距离要小于等于k那么我们就可以通过维护一个长度为k的窗口。如果当窗口小于k的时候那么我们就将元素添加到窗口中如果窗口中存在和当前元素相同的元素那么就直接返回true反之则将元素添加到窗口中当元素的个数等于窗口的长度的时候那就将左边第一个元素进行移除。这里我们借助HashSet来判断窗口中是否有重复的元素。
算法代码 /*** 检查数组中是否存在重复的元素且它们的索引之差的绝对值最大为k* 这个方法用于识别在一定索引范围内是否存在重复的数字** param nums 一个整数数组其中可能包含重复元素* param k 索引之差的绝对值的最大允许值* return 如果找到至少一对索引之差的绝对值不超过k的重复元素则返回true否则返回false*/public boolean containsNearbyDuplicate(int[] nums, int k) {// 使用HashSet存储当前窗口内的元素以便快速检查重复SetInteger set new HashSet();for (int i 0; i nums.length; i) {// 当窗口大小超过k时移除窗口最左侧的元素以保持窗口大小不超过kif (i k) {set.remove(nums[i - k - 1]);}// 尝试将当前元素添加到HashSet中如果添加失败说明存在重复元素且索引之差不超过kif (!set.add(nums[i])) {return true;}}// 遍历完成后如果没有返回true说明没有找到满足条件的重复元素return false;}
算法分析
这道题相对于前面两道题来说要难上一些。但是以及依旧可以借鉴上面题目的思想利用滑动窗口有序集合。
根据题意假设任意位置为i值为u。我们希望在下标范围为[max(0,i-k,i)的范围内找到值范围在[u-t,ut]范围内的数。如果我们每次遍历到任意位置的时候都往前检查k个元素这样时间负责度会达到O(nk)会超时所以我们需要对检索后面k个元素进行优化在java中有一个TreeSet数据结构能够帮助我们在有序集合内快速找到值小于等于u或者大于等于u的值。
算法代码
/*** 检查数组中是否存在两个索引之差不超过indexDiff且值之差不超过valueDiff的元素* * param nums 包含整数的数组* param indexDiff 索引之间的最大差值* param valueDiff 值之间的最大差值* return 如果找到满足条件的元素对则返回true否则返回false*/public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {int n nums.length;TreeSetInteger set new TreeSet();for(int i0;in;i){int unums[i];//如果set不为空从set中找到大于等于u的最小值最接近u的数Integer ceil set.ceiling(u);//如果set不为空且小于等于u的最大值最接近u的数Integer floor set.floor(u);//检查是否存在满足条件的元素if(ceil!nullceil-uvalueDiff) return true;if(floor!nullu-floorvalueDiff) return true;//将当前元素加入setset.add(u);//如果当前索引大于等于indexDiff则从set中移除滑动窗口最左侧的元素if(iindexDiff) set.remove(nums[i-indexDiff]);}//遍历后仍未找到满足条件的元素返回falsereturn false;}
49. 字母异位词分组 算法分析
这道题要我们找字符串的字符个数都相同的字符串并将这些字符串都放在同一个列表中那么我们可以采用哈希算法这里借助HashMap键key为字符串值为一个存储着字符串的列表。在遍历字符串数组的时候我们每次将字符串进行排序再判断hashmap是否存储当前字符串如果存在则将当前元素添加到列表中反之则创建一个列表并将当前元素添加到列表中。最后再将map中的值存储放到ans中。
算法代码
/*** 对字符串数组进行遍历将其中的字符串转换为字符数组并排序然后转换回字符串* 使用HashMap来存储这些转换后的字符串作为键以及它们在原始数组中的出现情况作为值* 最后将HashMap中的所有值收集到一个二维列表中并返回* * param strs 字符串数组包含待处理的字符串* return 返回一个二维列表其中包含按照字母异位词分组的字符串列表*/
public ListListString groupAnagrams(String[] strs) {// 初始化答案列表ListListString ansnew ArrayList();// 初始化哈希图用于存储排序后的字符串作为键以及它们的出现情况作为值HashMapString,ListString mapnew HashMap();// 遍历输入的字符串数组for(int i0;istrs.length;i){// 获取当前遍历到的字符串String sstrs[i];// 将字符串转换为字符数组char[] charss.toCharArray();// 对字符数组进行排序Arrays.sort(chars);// 将排序后的字符数组转换回字符串snew String(chars);// 如果排序后的字符串已经在哈希图中存在if(map.containsKey(s)){// 将当前字符串添加到该键对应的列表中map.get(s).add(strs[i]);}else{// 否则创建一个新的字符串列表ListString listnew ArrayList();// 将当前字符串添加到列表中list.add(strs[i]);// 将排序后的字符串和对应的字符串列表作为键值对存入哈希图map.put(s,list);}}// 遍历哈希图的所有键for(String key:map.keySet()){// 将每个键对应的值字符串列表添加到答案列表中ans.add(map.get(key));}// 返回答案列表return ans;
}以上就是哈希算法篇的所有内容啦~
若有不足欢迎指正~
