数据结构-哈希表（一）

时间：2024-03-20 14:31:17

哈希表（Hash Table），也称为散列表，是一种常见的数据结构，用于存储键值对。它通过将键映射到一个特定的索引位置来实现高效的数据访问和查找。

下面是哈希表的基本原理和操作：

  1. 哈希函数（Hash Function）：哈希表使用哈希函数将键映射到索引位置。哈希函数将任意大小的输入映射为固定大小的输出，通常是一个整数。优秀的哈希函数应该将不同的键均匀地映射到不同的索引位置，以减少冲突。

  2. 数组存储桶：哈希表内部使用一个固定大小的数组作为存储桶。每个桶可以存储一个或多个键值对，通常使用链表或者更高效的数据结构如红黑树来处理桶中的冲突。

  3. 插入操作：当要向哈希表中插入一个键值对时，首先通过哈希函数计算键的索引位置。然后，将键值对存储在对应的桶中。如果存在冲突（即多个键映射到同一个索引位置），通常会使用链表或其他方法处理冲突，将键值对添加到冲突的桶中。

  4. 查找操作：要查找哈希表中的一个键，首先通过哈希函数计算键的索引位置。然后，检查对应的桶中是否存在该键。如果存在冲突，需要在冲突的桶中进行搜索。

  5. 删除操作：要删除哈希表中的一个键值对，首先通过哈希函数计算键的索引位置。然后，找到对应的桶，删除包含该键的节点。

哈希表的优点是可以在平均情况下实现快速的插入、查找和删除操作，时间复杂度通常为 O(1)。然而，在最坏情况下，哈希表的性能可能下降到 O(n)，其中 n 是哈希表中的键值对数量。此外，哈希表的空间复杂度也比实际存储的键值对数量要高，因为需要预留足够的桶空间以减少冲突。

在实际应用中，哈希表广泛用于缓存、索引和唯一标识等场景。编程语言和标准库通常提供了哈希表的实现，可以直接使用或进行扩展。

1.有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

第一种方法我们使用字典哈希来解决 

from collection import defaultdict
def isAnagram(s,t):
    hashMap=defaultdict(int)
    if len(t)!=len(s):   # 如果长度不相等则二者不可能为异位
        return False
    for i in s:
        hashMap[i]+=1    # 先将s中字符存到hash表中
    for i in t:
        hash[i]-=1
    for i in t:          # 判断t中字母是否在hash表中
        if hashMap!=0:
            return False
    return True

第二种我们利用数组来解决

def isAnagram(s,t):
    nums=[0] * 26
    for i in t:
        nums[ord(i)-ord(a)]+=1
    for i  in s:
        nums[ord(i)-ord(a)]-=1
    for i in range(26):
        if nums[i]!=0:
               return False
    return True

2.赎金信

这一题与上一题的不同之处就是在于最后遍历，第1题中我们需要判断二者是否相同所以我们需要将数组全部遍历，而本题则是判断ransomNote是否可以由magazine构成，因此最后遍历时，我们遍历包含ransomNote的数组，如果其值大于0则说明magazine中并没有对应字符

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：

输入：ransomNote = "a", magazine = "b"
输出：false
class Solution:
    def canConstruct(ransomNote, magazine):
        nums=[0] * 26
        for i in ransomNote:
            nums[ord(i)-ord("a")]+=1
        for i in magazine:
            nums[ord(i)-ord("a")]-=1
        for i in ransomNote:
            if nums[ord(i)-ord("a")]>0:
                return False
        return True

3.字母异位词分组

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

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

示例 1:

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

输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
def Group(strs):
     hashMap=collections.defaultdict(list)
     for i in range(0,len(strs)):
             key="".join(sorted(strs[i]))
             hashMap.append(strs[i])
     return lsit(hashMap.values())

 4.找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
class Solution:
    def findAnagrams(s, p):
        n,m=len(s),len(p)
        res=[]
        s_cnt=[0]*26
        p_cnt=[0] *26
        if n<m:return res
        for i in range(m):
            p_cnt[ord(p[i])-ord("a")]+=1
            s_cnt[ord(s[i])-ord("a")]+=1
        if p_cnt==s_cnt:
            res.append(0)
        for i in range(m,n):
            s_cnt[ord(s[i-m])-ord("a")]-=1
            s_cnt[ord(s[i])-ord("a")]+=1
            if s_cnt==p_cnt:
                res.append(i-m+1)
        return res

 

相关文章