首页 > 编程语言 >搞定leetcode面试经典150题之哈希算法

搞定leetcode面试经典150题之哈希算法

时间：2024-12-03 17:00:54浏览次数：9  
标签：150 return HashMap HashSet int map 哈希 leetcode

系列博客目录

搞定leetcode面试经典150题之哈希算法
搞定leetcode面试经典150题之双指针
搞定leetcode面试经典150题之滑动窗口

文章目录

理论知识

 哈希算法（Hashing）是一种将输入数据映射为固定长度值的技术，通常用于数据查找、加密和数字签名等多个领域。哈希算法的核心思想是将数据通过一个哈希函数映射到一个定长的哈希值（哈希码）上，这个哈希值通常用于在哈希表中查找或存储数据。在 LeetCode 中，哈希算法被广泛应用于解决很多涉及数据查找、去重、计数和映射的问题。

1. 哈希函数（Hash Function）

哈希函数是哈希算法的核心，它将输入的数据（可以是任何类型的，甚至是大的文件或字符串）映射为一个固定大小的输出（通常为一个整数或字符串）。哈希函数的质量直接决定了哈希表性能。

哈希函数的特点：

  • 确定性：相同的输入，哈希函数总是产生相同的输出。
  • 效率：哈希函数应该能够迅速计算出哈希值，适合在实际应用中使用。
  • 均匀性：好的哈希函数能够将输入均匀地映射到哈希表的各个位置，减少碰撞。
  • 避免碰撞：哈希函数应尽量避免将不同的输入映射到相同的哈希值（即碰撞）。虽然在实际中无法完全避免碰撞，但好的哈希函数能够减少碰撞的概率。

2. 哈希表（Hash Table）通过HashMap实现

哈希表是一种基于哈希算法的数据结构，它通过哈希函数将数据存储在固定大小的数组中。在哈希表中，数据的插入、删除和查找操作的平均时间复杂度为 O(1)。

  • 结构：哈希表的基本结构是一个数组，其中每个元素叫做桶（bucket）。每个桶可以存储一个或多个数据项。
  • 哈希冲突：由于哈希表的大小是有限的，不同的输入可能会被哈希到相同的桶位置，导致哈希冲突。哈希冲突需要通过冲突处理机制来解决。

3. 哈希算法的应用

哈希算法在计算机科学和工程中有广泛的应用，主要包括：

  • 哈希表：用于快速查找、插入和删除操作（如在数据库、缓存、编译器等中使用）。
  • 数字签名与数据完整性：用于确保数据的完整性和验证数据是否被篡改（如 MD5、SHA 等哈希算法在加密中广泛使用）。
  • 负载均衡：通过哈希算法将请求均匀分配到多个服务器上（如一致性哈希）。
  • 数据去重：通过计算数据的哈希值判断数据是否已经存在，常用于文件去重、集合去重等。
  • 密码存储：将密码哈希化存储，避免明文存储密码，提高安全性。

4. 哈希算法的时间复杂度

  • 查找操作（查找某个元素）：理想情况下是 O(1)，因为通过哈希值可以直接定位到桶中的位置。
  • 插入操作：通常是 O(1)，但在发生哈希冲突时，可能会退化为 O(n)（如果所有元素都冲突并放入同一个桶中）。
  • 删除操作：通常是 O(1)，但在发生哈希冲突时，可能会退化为 O(n)。
  • 扩容操作：当哈希表需要扩容时，可能会重新计算哈希值并重新分配所有元素，这个操作的时间复杂度是 O(n)。

编程理论

在 Java 中，HashSet 和 HashMap 都是基于哈希表实现的，但它们的用途和内部实现有所不同。我会分别解释这两者的工作原理，特别是关于 HashSet 和哈希函数的计算。

1. HashSet 的工作原理

HashSet 是一个不允许重复元素的集合。内部实际上是基于 HashMap (即哈希表)来实现的，其中元素存储的是 HashMap 中的键（key），而每个键都对应一个 Boolean 值（值可以是固定的，因为 HashSet 只关心键的唯一性）。

过程：

  1. 创建 HashSet：当你 new 一个 HashSet 时，实际上是创建了一个空的集合，可以通过调用 add() 方法向集合中添加元素。

    Set<Integer> set = new HashSet<>();

  2. 添加元素：假设你向 HashSet 中添加元素 1 和 2，下面是具体过程：

    • 当你执行 set.add(1) 时，HashSet 会通过哈希函数计算 1 的哈希值。然后，哈希值会通过哈希表中的位置来决定将 1 放入表的哪个位置。
    • 同样，当你执行 set.add(2) 时，HashSet 会计算 2 的哈希值，并将 2 放入相应的哈希表位置。

    在这两次操作中，HashSet 通过哈希值来确定元素的位置，而哈希表通过哈希值来存储或查找元素。具体地，HashSet 会调用元素的 hashCode() 方法来获得元素的哈希值，然后进行映射。

  3. 处理哈希冲突：如果两个不同的元素（例如 1 和 10）有相同的哈希值（碰撞），那么哈希表会使用链式结构或其他冲突解决策略来处理这类情况。

示例代码：

Set<Integer> set = new HashSet<>();
set.add(1);  // 1的hash值被计算出来，放入HashSet
set.add(2);  // 2的hash值被计算出来，放入HashSet
System.out.println(set);  // 输出: [1, 2]

2. HashMap (哈希表)的工作原理

HashMap 是一个键值对集合，每个元素都有一个键（key）和一个值（value）。当你 put 一个键值对时，哈希表会计算键的哈希值，然后根据这个哈希值来确定值的存储位置。

过程：

  1. 创建 HashMap：

    Map<Integer, Integer> map = new HashMap<>();

  2. 添加键值对：假设你向 HashMap 中添加键值对 (1, 2)，过程如下：

    • map.put(1, 2) 时，哈希表首先计算键 1 的哈希值（通常通过 hashCode() 方法计算），然后根据该哈希值确定在哈希表中的位置，并将 2 存储在这个位置。
    • map.put(2, 3) 时，哈希表计算键 2 的哈希值并将 3 存储在对应位置。

  3. 处理哈希冲突：如果两个键（例如 1 和 2）的哈希值相同，则会发生哈希冲突，HashMap 会使用链式哈希或开放寻址法来处理冲突。

示例代码：

Map<Integer, Integer> map = new HashMap<>();
map.put(1, 2);  // 将键1和对应的值2存入HashMap
map.put(2, 3);  // 将键2和对应的值3存入HashMap
System.out.println(map);  // 输出: {1=2, 2=3}

3. 哈希表中的 hashCode() 和 equals() 方法

Java 中的哈希表使用 hashCode() 方法来计算元素的哈希值，并且在插入和查找时，会用 equals() 方法来判断是否为同一个元素。

  • hashCode()：该方法返回一个整数，表示该对象的哈希值。不同的对象可能具有相同的哈希值（称为哈希冲突）。哈希函数的质量很重要，良好的哈希函数会尽量避免碰撞。

  • equals()：当发生哈希冲突时，哈希表会调用 equals() 方法来判断两个对象是否相等。如果两个对象的 hashCode() 相同，但 equals() 返回 false，它们会被认为是不同的元素。为什么要使用 equals() 判断相等
    如果两个对象的哈希值相同，我们不能简单地认为它们是同一个对象，因为哈希值相同并不意味着对象内容相同。例如，两个不同的字符串 "abc" 和 "abc " 的哈希值可能相同，但它们的内容显然不同。在这种情况下，如果不使用 equals() 来进一步判断，哈希表可能会错误地认为它们是相同的对象。应用：在 HashSet 中，如果两个对象的 hashCode() 相同，但它们的 equals() 方法返回 false，那么它们 可以 被添加到同一个 HashSet 中。

4. 总结

  • HashSet：是一个不允许重复元素的集合，它基于 HashMap 来实现，add() 方法通过计算元素的哈希值来确定存储位置，避免元素重复。
  • HashMap：是一个键值对集合，put() 方法通过计算键的哈希值来确定存储位置，并将对应的值存储到该位置。
  • 哈希函数：哈希表的效率依赖于哈希函数的质量，优秀的哈希函数可以减少哈希冲突，提高操作效率。

小结

当你在 Java 中使用 HashSet 或 HashMap 时，哈希表会使用 hashCode() 方法来计算元素的哈希值，并通过该哈希值来决定元素的存储位置。在插入和查找时，如果发生哈希冲突，HashMap 和 HashSet 会使用 equals() 方法来判断元素是否相等。

leetcode例题

128. 最长连续序列 中等

题目描述
 给定一个未排序的整数数组 nums，找出其中数字连续的最长序列的长度。注意，序列元素不需要在原数组中是连续的。 要求 时间复杂度为 O(n)。

示例 1

输入:

nums = [100, 4, 200, 1, 3, 2]

输出:

4

解释:
最长的连续序列是 [1, 2, 3, 4]，长度为 4。

示例 2

输入:

nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]

输出:

9

解释:

最长的连续序列是 [0, 1, 2, 3, 4, 5, 6, 7, 8]，长度为 9。

提示

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

题解：
我自己先是没有用哈希，想到了先排序。然后如果一个数比他的下一个数小1，那长度就加1。如果不满足比下一个数小1，则到这里，当前序列结束，为了加上当前数字所占的长度1，需要判断当前数字是否和前面一个数是连续的，也就是比前面一个数大1。
但是忘记了以下两点。

  • 注意即使longOfSub>longest不满足也要把longOfSub置成零，不然longOfSub 会一直叠加
  • 还要注意测试用例数组中可能存在重复数值，需要去除。此时就可以用到HashSet

31ms击败47.81%

class Solution {
    public int longestConsecutive(int[] nums) {
        Arrays.sort(nums);
        HashSet<Integer> hashSet = new HashSet<>();
        for(int num:nums){
            hashSet.add(num);
        }
        int[] result = new int[hashSet.size()];
        int i =0;
        for(int num: hashSet){
            result[i++] = num;
        }
        Arrays.sort(result);
        int longest = 0;
        int longOfSub = 0;
        if(result.length == 1) return 1;
        if(result.length == 0) return 0;
        int n = 0;
        while(n < result.length){
            if(n<result.length-1&&result[n]==result[n+1]-1){
                longOfSub++;
            } else if (n>1 && result[n] == result[n-1]+1) {
                longOfSub++;
                if(longOfSub>longest){
                    longest = longOfSub;
                    longOfSub = 0;
                }else {
                    longOfSub = 0;
                }
            }else {
                longOfSub++;
                if(longOfSub>longest){
                    longest = longOfSub;
                    longOfSub = 0;
                }else {
                    longOfSub = 0;
                }
            }
            n++;
        }
        return  longest;
    }
}

用哈希，所有序列分为头，中，尾，通过哈希找到所有头，再判断每个序列何时结束。此时和自己之前的思路不同：之前是判断了这个数是不是序列中的，把这个数的1个长度给加上，现在是先加上头的1，再判断这个数的后面有没有，有再把下个数的长度1加上，后者编写更加简单。
44ms击败38.11%

class Solution {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> hashSet = new HashSet<>();
        for(int num : nums){
            hashSet.add(num);
        }
        int[] newArray = new int[hashSet.size()];
        int index = 0;
        for(int set : hashSet){
            newArray[index++] = set;
        }
        int longest = 0;
        int longbuffer = 0;
        Arrays.sort(newArray);
        for(int num : newArray){
            int newnum = num;

            if(!hashSet.contains(num-1)){
                longbuffer++;
                while(hashSet.contains(newnum+1)) {
                    longbuffer++;
                    newnum ++;
                }
                longest = Math.max(longest,longbuffer);
            }
            longbuffer = 0;
        }
        return  longest;
    }
}

官方题解如下 更快 26ms击败85.89%

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> num_set = new HashSet<Integer>();
        for (int num : nums) {
            num_set.add(num);
        }

        int longestStreak = 0;

        for (int num : num_set) {
            if (!num_set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (num_set.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
}

49.字母异位词分组 中等难度

题目描述

给定一个字符串数组 strs，将字母异位词（Anagrams）组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的新单词。

示例 1

输入:

strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出:

[["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]

示例 2

输入:

strs = [""]

输出:

[[""]]

示例 3

输入:

strs = ["a"]

输出:

[["a"]]

提示

  • 1 <= strs.length <= 10^4
  • 0 <= strs[i].length <= 100
  • strs[i] 仅包含小写字母。

解答
 是看了蜜糖之后自己写的，蜜糖的思路就是首先把字符串数组中所有字符串中的字符进行排序，就可以知道哪些是字母异位词了。
 出了一个代码编写方面的问题，有一个小错误，Arrays.sort(buffer) 排序字符数组后，使用 buffer.toString() 获取的字符串并不是我们期望的排序结果字符串，而是字符数组的内存地址的字符串表示。因此，需要将字符数组转换成字符串，使用 String.valueOf(buffer) 来正确获取排序后的字符串。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> hashMap = new HashMap<>();
        for(String str : strs){
            final char[] buffer = str.toCharArray();
            Arrays.sort(buffer);
            String result = buffer.toString();//错误代码 应该为String result = Arrays.toString(buffer);
            if(hashMap.containsKey(result)){
                hashMap.get(result).add(str);
            }else{
                List<String> s = new ArrayList<>();
                s.add(str);
                hashMap.put(result, s);
            }
        }
        return new ArrayList<>(hashMap.values());//注意代码
    }
}

205 .同构字符串 简单

题目描述

给定两个字符串 s 和 t，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t，那么这两个字符串是同构的。

  • 每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。
  • 不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1

输入:

s = "egg", t = "add"

输出:

true

示例 2

输入:

s = "foo", t = "bar"

输出:

false

示例 3

输入:

s = "paper", t = "title"

输出:

true

提示

  • 1 <= s.length <= 5 * 10^4
  • t.length == s.length
  • s 和 t 由任意有效的 ASCII 字符组成。

题解
自己一看到这个题的时候，感觉不像简单题，以为是要找到一种方法，比如a来替代s，那么b(a后面的字母)就要替代t(s后面的字母)，是有对应关系的。后来一看官方题解，不是的。看了官方题解后自己想，感觉只需要一个HashMap即可，得到如下代码：

class Solution {
    public boolean isIsomorphic(String s, String t) {
        char[] sArray = s.toCharArray();
        char[] tArray = t.toCharArray();
        HashMap<Character,Character> shashMap = new HashMap<>();
        for (int i = 0; i < sArray.length; i++) {
            if((shashMap.containsKey(sArray[i]) && shashMap.get(sArray[i])!=tArray[i])){
                return false;
            }else {
                shashMap.put(sArray[i],tArray[i]);
            }
        }
        return true;
    }
}

犯了一个错误，比如 String s是ab，String t是cc。上面代码会在HashMap中加入两个关键字不同，但是值相同的对。这显然是错误的，所以还是需要两个HashMap才可以。思路就是：已知两个给定的字符串是等长的，然后同位置进行扫描的时候，每扫描到一个位置，就判断其是否在HashMap中有映射值，有的话，不光要有s映射到t的，还要保证t映射到s的与s映射到t的相同，即保证一对一映射。没有的话，就在两个HashMap中加入，保证一对一映射。

class Solution {
    public boolean isIsomorphic(String s, String t) {
        char[] sArray = s.toCharArray();
        char[] tArray = t.toCharArray();
        HashMap<Character,Character> shashMap = new HashMap<>();
        HashMap<Character,Character> thashMap = new HashMap<>();
        for (int i = 0; i < sArray.length; i++) {
            if((shashMap.containsKey(sArray[i]) && shashMap.get(sArray[i])!=tArray[i])||(thashMap.containsKey(tArray[i])&& thashMap.get(tArray[i])!=sArray[i])){
                return false;
            }else {
                shashMap.put(sArray[i],tArray[i]);
                thashMap.put(tArray[i],sArray[i]);
            }
        }
        return true;
    }
}

383 赎金信 简单

链接
题解
以下是自己的代码，18ms击败7.86%

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        char[] magazineArray = magazine.toCharArray();
        HashMap<Character,Integer> buffer = new HashMap<>();
        for(char str : magazineArray){
            if(buffer.containsKey(str)){
                buffer.put(str,buffer.get(str)+1);
            }else {
                buffer.put(str,1);
            }
        }
        char[] ransomNotearray = ransomNote.toCharArray();
        for(char str: ransomNotearray){
            if(buffer.containsKey(str)){
                if(buffer.get(str)>1){
                    buffer.put(str,buffer.get(str)-1);
                }else{
                    buffer.remove(str);
                }
            }else {
                return false;
            }
        }
        return true;
    }
}

官方题解 没有用哈希，但是速度很快。有很多可以学习借鉴的地方，比如for (char c : magazine.toCharArray())非常简约。char 应该用 c 来表示变量，而不是str

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        int[] cnt = new int[26];
        for (char c : magazine.toCharArray()) {
            cnt[c - 'a']++;
        }
        for (char c : ransomNote.toCharArray()) {
            cnt[c - 'a']--;
            if(cnt[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}

290 单词规律 简单

以下是自己的代码，1ms击败93.49%。思路和205题一样。

class Solution {
    public boolean wordPattern(String pattern, String s) {
        char[] chars = pattern.toCharArray();
        int i = 0;
        if(chars.length!= s.split(" ").length){
            return false;
        }
        Map<Character,String> map = new HashMap<>();
        Map<String,Character> charmap = new HashMap<>();
        for(String str : s.split(" ")){
            if(charmap.containsKey(str)&&charmap.get(str)!=chars[i]||map.containsKey(chars[i])&& !Objects.equals(map.get(chars[i]), str)){
                return false;
            }else{
                map.put(chars[i],str);
                charmap.put(str,chars[i]);
            }
            i++;
        }
        return  true;
    }
}

242.有效的字母异位词

链接
不要忘记了可能s比t长的情况。 17ms击败12.59%

class Solution {
    public boolean isAnagram(String s, String t) {
        Map<Character,Integer> map = new HashMap<>();
        for(char c : s.toCharArray()){
            if(map.containsKey(c)) map.put(c,map.get(c)+1);
            else{
                map.put(c,1);
            }
        }
        for(char c: t.toCharArray()){
            if(map.containsKey(c)&&map.get(c)>=1) {
                map.put(c,map.get(c)-1);
                if(map.get(c)==0){
                    map.remove(c);
                }
            }
            else{
                return false;
            }
        }
        if(!map.isEmpty()){//这个一开始忘记了
            return  false;
        }
        
        return true;
    }
}

官方题解 非常神奇

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();
        Arrays.sort(str1);
        Arrays.sort(str2);
        return Arrays.equals(str1, str2);
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/valid-anagram/solutions/493231/you-xiao-de-zi-mu-yi-wei-ci-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

标签：150,return,HashMap,HashSet,int,map,哈希,leetcode
From： https://blog.csdn.net/buyaotutou/article/details/144180327

相关文章

  • 2024/12/2【链表】LeetCode 142 环形链表 II 【X】
    题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/description/题解链接：https://www.programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC没做出来......
  • LeetCode题练习与总结：字典序的第 K 小数字--440
    一、题目描述给定整数 n 和 k，返回  [1,n] 中字典序第 k 小的数字。示例1:输入:n=13,k=2输出:10解释:字典序的排列是[1,10,11,12,13,2,3,4,5,6,7,8,9]，所以第二小的数字是10。示例2:输入:n=1,k=1输出:1提示:1<=k<=n<......
  • LeetCode题练习与总结：排列硬币--441
    一、题目描述你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。给你一个数字 n ，计算并返回可形成 完整阶梯行 的总行数。示例1：输入：n=5输出：2解释：因为第三行不完......
  • 哈希的刷题奇遇记2
    [USACO09OCT]BarnEchoesG题目入口题目描述Thecowsenjoymooingatthebarnbecausetheirmoosechoback,althoughsometimesnotcompletely.Bessie,evertheexcellentsecretary,hasbeenrecordingtheexactwordingofthemooasitgoesoutandret......
  • leetcode 1652. 拆炸弹 未解决
    1652.拆炸弹原本是简单题，但是k<0的情况由于选用的方法不好，浪费太多时间了。代码也有很多冗余classSolution{public:vector<int>decrypt(vector<int>&code,intk){intsize=code.size();vector<int>res(size,0);if(k==0)ret......
  • leetcode757 设置交集大小至少为2
    给定n个闭区间，求一个集合使得每个区间都至少有两个整数在其中，问集合至少包含多少个元素？1<=n<=3000;0<=start[i]<end[i]<=1E8分析：将区间按end升序、start降序排序，维护集合的最大和次大值，分情况讨论，贪心选择靠右边的点。classSolution{public:intintersectionSizeTwo(v......
  • LeetCode 2413[最小偶倍数]
    题目链接LeetCode2413[最小偶倍数]详情实例提示题解思路判断奇偶性奇数乘以2并返回偶数直接返回代码classSolution{public:intsmallestEvenMultiple(intn){if(0==(n%2))returnn;return2*n;}};......
  • leetcode 1423. 可获得的最大点数
    1423.可获得的最大点数首先，前k个数和后k个数的较大者并不是正确答案，比如 100  40  17  9  73  75，正确解是248。其次，想到了前或者后拿了一个数之后，就是求剩下序列拿k-1个数，可以转换成子问题，所以想到了递归。但是k比较大的时候就超时了：classSolution......
  • 代码随想录算法训练营第三十一天|leetcode56. 合并区间、leetcode738.单调递增的数字
    1leetcode56.合并区间题目链接：56.合并区间-力扣（LeetCode）文章链接：代码随想录视频链接：贪心算法，合并区间有细节！LeetCode：56.合并区间哔哩哔哩bilibili思路：其实很清楚，跟之前的方法差不多，但是自己写的时候就是有地方不会了，会不知道接下来的思路是什么1.1视频后的思路卡壳......
  • leetcode 2841. 几乎唯一子数组的最大和
    2841.几乎唯一子数组的最大和使用unordered_map；unordered_multiset可能也可以，但是不如前者方便classSolution{public:longlongmaxSum(vector<int>&nums,intm,intk){intsize=nums.size();longlongnow=0;unordered_map<int,......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99