Leetcod面试经典150题刷题记录 —— 哈希表篇

发布时间:2023年12月23日

1. 赎金信

题目链接:赎金信 - leetcode
题目描述:
给你两个字符串:ransomNotemagazine ,判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以,返回 true ;否则返回 falsemagazine 中的每个字符只能在 ransomNote 中使用一次。
题目归纳:
统计字符频率并比较即可

解题思路:
(1) 解法: 赎金信 - leetcode官方题解

from collections import Counter

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        # magzine的字符词频绝对 >= ransomNote即可啊
        r_counter = Counter(ransomNote)
        m_counter = Counter(magazine)
        return m_counter >= r_counter

2. 同构字符串(按逻辑完整性,分次书写代码)

题目链接:同构字符串 - leetcode
题目描述:
给定两个字符串 st ,判断它们是否是同构的。如果 s 中的字符可以按某种映射关系替换得到 t ,那么这两个字符串是同构的。每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序。不同字符不能映射到同一个字符上,相同字符只能映射到同一个字符上,字符可以映射到自己本身。
题目归纳:
s[i]t[i]是否互相是一一映射

解题思路:
(1) 解法: 同构字符串 - leetcode官方题解

这里值得说一点的是,写代码不一定是遵守代码完整性,从上到下完整书写,应遵循逻辑完整的原则,这一点也是我写了这么久代码的一点小心得,人做一切事情都是会遵循逻辑和规律,不能是碎片化的,例如这里,应该按这样的顺序写:

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        # 两个字典
        s2t = dict()
        t2s = dict()
        s_len = len(s)

        for i in range(s_len):
            # 先构建映射
            ch_s = s[i]
            ch_t = t[i]          
            s2t[ch_s] = ch_t
            t2s[ch_t] = ch_s

        return True

再添加判断逻辑,将上面的代码块变成下面的

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        # 两个字典
        s2t = dict()
        t2s = dict()
        s_len = len(s)

        for i in range(s_len):
            ch_s = s[i]
            ch_t = t[i]       
            # 再添加映射失败的判断逻辑
            if (ch_s in s2t and s2t[ch_s] != ch_t) or (ch_t in t2s and t2s[ch_t] != ch_s):
                return False     
            s2t[ch_s] = ch_t
            t2s[ch_t] = ch_s

        return True

3. 单词规律

题目链接:单词规律 - leetcode
题目描述:
给定一种规律 pattern 和一个字符串 s ,判断 s 是否遵循相同的规律。这里的 遵循 指完全匹配,例如, pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。
题目归纳:
先把s' '进行split(),得到分词数组S,就回归到了上一题:同构字符串

解题思路:
(1) 解法: 单词规律- leetcode官方题解

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        # 先把s按空格进行split就回归到上一题:同构字符串
        S = s.split()
        S_len = len(S)
        p_len = len(pattern)
        if S_len != p_len:
            return False

        p2S = dict()
        S2p = dict()

        for i in range(p_len):
            ch_p = pattern[i]
            word_S = S[i]
            if (ch_p in p2S and p2S[ch_p] != word_S) or (word_S in S2p and S2p[word_S] != ch_p):
                return False
            
            p2S[ch_p] = word_S
            S2p[word_S] = ch_p
        
        return True

4. 有效的字母异位词

题目链接:有效的字母异位词 - leetcode
题目描述:
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词。
题目归纳:
字符频率相同即可

解题思路:
(1) 解法: 有效的字母异位词 - leetcode官方题解

from collections import Counter

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return Counter(s) == Counter(t) # 字符频率相同即可

4.1 进阶: 输入字符串包含 unicode 字符

5. 字母异位词分组

题目链接:字母异位词分组 - leetcode
题目描述:
给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

题目归纳:
相同字符频率的字符串放一起作为value,那么key就是其对应的字典序母串

解题思路:
(1) 解法: 字母异位词分组 - leetcode官方题解

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # 字符频率一致的放一起
        sortedS_dysWords = dict() # 变量命名法:key_value dystopia n. 异位;非理想化的地方,糟透的社会;地狱般的处境
        n = len(strs)
        
        for S in strs:
            key = "".join(sorted(S))
            if key in sortedS_dysWords: # 该str经排序后,存在于hash表中,说明其字符频率出现过
                sortedS_dysWords[key].append(S)
            else:
                sortedS_dysWords[key] = [S]
        
        ans = []
        for key in sortedS_dysWords:
            value = sortedS_dysWords[key]
            ans.append(value)
        return ans

6. 两数之和

题目链接:两数之和 - leetcode
题目描述:
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。

示例 1:
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

题目归纳:
解题思路:数组的索引方式是由下标index --> 元素值value,可以用一个hash表反向存储,由元素值value --> 下标index

解题思路:
(1) 解法: 两数之和 - leetcode官方题解

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash_table = dict() # key:val = index:nums[index],相当于反向存储数组
        for i, num in enumerate(nums): # 一次遍历即可
            if target - num in hash_table:
                return [i, hash_table[target-num]]
            else: # 数组是key:value = 下标:元素值,这里是key:value=元素值:下标
                hash_table[num] = i 
        return []

7. 快乐数

题目链接:快乐数 - leetcode
题目描述:
编写一个算法来判断一个数 n 是不是快乐数。「快乐数」 定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。如果这个过程 结果为 1,那么这个数就是快乐数。如果 n 是 快乐数 就返回 true ;不是,则返回 false

示例 1:
输入:n = 19
输出:true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
提示
1 <= n <= 231 - 1,即 1 <= n <= 2147483647,换算成十进制,n最高也只有10位数字。

题目归纳:
看上去可以用仿真法,但是由于图灵停机问题:“给定一段算法和输入组成程序A,你找不到一段通用程序B,去判断程序A是否会陷入无限循环”,所以这道题你没有一个通用的判定方法,来判断是否会无限循环,除非你能找到那些会陷入无限循环的数字,官方题解在之后就给出了这样的一个无限循环,在 1 <= n <= 231 - 1 的情况下,这样的循环有且只有一个。

解题思路:
解法: 快乐数 - leetcode官方题解
(1) 用hash集合检测循环。
(2) 隐式链表+快慢指针(又称为弗洛伊德循环查找算法)检测循环。
(3) 数学法确定循环数字 + 仿真。
这道题的关键点在于死循环数字的检测上

开端循环赵今麦

hash集合检测循环

def get_next(n):
    total = 0
    while n > 0:
        digit = n%10
        total += digit**2
        n = int(n/10)
    return total

class Solution:
    def isHappy(self, n: int) -> bool:
        seen = set()
        while n != 1 and n not in seen: # 不在seen集合中,就是不在循环中
            seen.add(n)
            n = get_next(n)
        return n == 1

隐式链表+快慢指针(弗洛伊德循环查找算法)

def get_next(n):
    total = 0
    while n > 0:
        digit = n%10
        total += digit**2
        n = int(n/10)
    return total

class Solution:
    def isHappy(self, n: int) -> bool:
        slow_p = n
        fast_p = get_next(n)
        while fast_p != 1 and slow_p != fast_p : # fast指针没到终点,并且slow没追上fast,游戏就没结束
            slow_p = get_next(slow_p) # 1 step 
            fast_p = get_next(get_next(fast_p)) # 2 step
        return fast_p == 1 # 走到了终点吗?

数学+仿真(待完成)

class Solution:
    # 在没有确定循环数字前,模拟的思路是错误的
    def squareSum(self, num: int) -> int:
        ans = 0
        while num != 0:
            x = num % 10
            ans += x**2
            num = int(num/10)
        return ans

    def isHappy(self, n: int) -> bool:
        while n != 1:
            n = self.squareSum(n)
        return True

8. 存在重复元素 II

题目链接:存在重复元素 II - leetcode
题目描述:
给你一个整数数组 nums 和一个整数 k ,判断数组中是否存在两个 不同的索引 ij ,满足 nums[i] == nums[j]abs(i - j) <= k 。如果存在,返回 true ;否则,返回 false
题目归纳:
(1)我一开始的解法是遍历数组+遍历hash表
(2)最大下标解法。
(3)滑动窗口法。

解题思路:
解法: 存在重复元素 II - leetcode官方题解

8.1 我的原始解法(遍历数组+遍历hash表)

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        # 相同value,其下标index_i添加到hash表中
        # 建立hash表 key:val = value:[index_1, ...]
        # 遍历hash表的下标数组,查找是否存在 abs(i-j) <= k
        hash_table = dict()
        
        # (1)遍历数组,并添加元素至hash表中
        for i,num in enumerate(nums):
            if num in hash_table:
                hash_table[num].append(i)
            else: # 建立数组
                hash_table[num] = [i]

        print(hash_table)
        # (2)遍历hash表,查找是否有index满足 abs(i-j) <= k
        for value in hash_table:
            indices = hash_table[value]
            for i in indices:
                for j in indices:
                    if i != j and abs(i-j)<=k: # 必须是不同的索引
                        return True

        return False

8.2 记录最大下标解法

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        pos = dict()
        for i,num in enumerate(nums):
            if num in pos and i - pos[num] <= k: # i 一直比当前的pos[num]大
                return True
            pos[num] = i # 记录最大的下标
        return False

8.3 滑动窗口法

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        # 滑动窗口法
        # (1)nums中,每个长度不超过k+1的滑动窗口,其任意两个下标i,j,一定满足abs(i-j)<=k
        # (2)若存在一个滑动窗口,其中有重复元素,则一定存在两个不同的下标i,j,满足nums[i] = nums[j] and abs(i-j) <= k
        # (3)若该滑动窗口没有重复元素,则不符合要求,继续遍历滑动窗口
        # (4)若一个滑动窗口的结束下标是i,则开始下标是max(0,i-k)
        # (5)使用哈希集合,存储滑动窗口中的元素,从左至右遍历数组nums
        # (6)若 i > k,则i-(k+1)处的元素被移出滑动窗口,即s.remove(nums[i-k-1])
        # (7)若nums[i]在哈希集合中,则在同一个滑动窗口中有重复元素,不在哈希集合中则将其加入集合。

        window = set()
        for i, num in enumerate(nums):
            if i > k: # (1)维持窗口大小
                window.remove(nums[i-(k+1)])
            if num in window: # (2)判断窗口是否出现相同元素
                return True
            window.add(num)
        return False

9. 最长连续序列(有个语法问题,待解决)

题目链接:最长连续序列 - leetcode
题目描述:
给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
题目归纳:

解题思路:
解法: 最长连续序列 - leetcode官方题解

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        longest_streak = 0
        num_set = set(nums) #去重,时间复杂度O(n),想到用set()是非常关键的

        for num in num_set:
            if num - 1 not in num_set: # 若存在前驱数,则跳过。判断的时间复杂度是O(1)
                current_num = num
                current_streak = 1

                # next_num = num + 1 # ???不能用next_num? 离大谱了!!
                # while next_num in num_set: # 这行搭配上面这行会超时,实在离谱
                while current_num+1 in num_set: # 判断的时间复杂度是O(1)
                    current_num += 1
                    current_streak += 1

                longest_streak = max(longest_streak, current_streak)

        return longest_streak
文章来源:https://blog.csdn.net/weixin_44327736/article/details/135150789
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。