[数据结构与算法] leetcode2021年度刷题分类型总结（十）哈希表（python）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> leetcode2021年度刷题分类型总结（十）哈希表（python） -> 正文阅读

[数据结构与算法]leetcode2021年度刷题分类型总结（十）哈希表（python）

例一：202. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。
如果这个过程结果为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

class Solution(object):
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """
        # 如果中间结果重复出现，说明陷入死循环了，该数不是快乐数
        res=0
        record=set()

        while n!=1:
            while n//10:
                x=n%10
                res+=x*x
                n//=10
            res+=n*n
            if res in record:
                return False
            record.add(res)
            # print(res)
            n=res
            res=0
        return True

##################暴力解法
#########把每个数直接拆开成str，循环99次如果还到不了1，直接false
        s=n
        for i in range(99):
            s = list(str(s))
            temp = [int(i) ** 2 for i in s]
            s = sum(temp)
            if s == 1:
                return True
        return False

例二.242. 有效的字母异位词

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

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

输入: s = “anagram”, t = “nagaram”
输出: true

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        #方法一：用字典
        s=list(s)
        t=list(t)
        sdict=dict.fromkeys(s,0) #字典所有val初始化为0
        for si in s:
            sdict[si]+=1
        tdict=dict.fromkeys(t,0)
        for ti in t:
            tdict[ti]+=1

        if sdict==tdict:
            return True
        else:
            return False

        #方法二
        #一个数组叫做record用来上记录字符串s里字符出现的次数
        #因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。

        record=[0]*26

        for i in range(len(s)):
            record[ord(s[i])-ord("a")] +=1#ord字符转数字，chr数字转字符

        for i in range(len(t)):
            record[ord(t[i])-ord("a")]-=1

        for i in range(26):
            if record[i]!=0:
                return False
        return True

例三.349. 两个数组的交集

给定两个数组 nums1 和 nums2 ，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

class Solution(object):
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        ##方法一：哈希
        return list(set(nums1) & set(nums2))    # 两个数组先变成集合，求交集后还原为数组

        ##方法二：指针
        nums1.sort()
        nums2.sort()
        res=[]

        left,right=0,0

        while left<len(nums1) and right<len(nums2):
            # print(left)
            if nums1[left]<nums2[right]:            
                left+=1
            elif nums1[left]>nums2[right]:
                right+=1
            else:
                res.append(nums1[left])
                left+=1
                right+=1

        return list(set(res))

例四.1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

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

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        ##方法一：先排序再双指针法
        n=len(nums)
        tmp=[]
        for i,num in enumerate(nums):
            tmp.append([num,i])
        tmp.sort()

        left,right=0,n-1

        while left<right:
            if tmp[left][0]+tmp[right][0]>target:
                right-=1
            elif tmp[left][0]+tmp[right][0]<target:
                left+=1
            else:
                return [tmp[left][1],tmp[right][1]]

        ## 方法二：简化版思路，在该数组中找出 和为目标值 target 的两个整数
        #相当于在数组中找target - val（设当前值为val，如果target - val不在记录records当中
        #把当前值val作为键记录在records中，其索引作为值也记录，直到找到target - val in records
        records = dict()

        # 用枚举更方便，就不需要通过索引再去取当前位置的值
        for idx, val in enumerate(nums):
            if target - val not in records:
                records[val] = idx
            else:
                return [records[target - val], idx] # 如果存在就返回字典记录索引和当前索引

例五.454. 四数相加 II

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：

(0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
(1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

class Solution(object):
    def fourSumCount(self, nums1, nums2, nums3, nums4):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :type nums3: List[int]
        :type nums4: List[int]
        :rtype: int
        """
        ##拆分成两步
        #1. # use a dict to store the elements in nums1 and nums2 and their sum
        #2.if the -(a+b) exists in nums3 and nums4, we shall add the count
        #要注意每个数的出现次数很重要
        hashmap=dict()
        res=0
        for num1 in nums1:
            for num2 in nums2:
                if num1+num2 in hashmap:
                    hashmap[num1+num2]+=1
                else:
                    hashmap[num1+num2]=1

        for num3 in nums3:
            for num4 in nums4: #注意：不能if判断时直接写hashmap[-(num3+num4)]，因为不知道有无-(num3+num4)这个key
                if -(num3+num4) in hashmap:
                    res+=hashmap[-(num3+num4)]
        return res

例六.383. 赎金信

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

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

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

输入：ransomNote = “a”, magazine = “b”
输出：false

class Solution(object):
    def canConstruct(self, ransomNote, magazine):
        """
        :type ransomNote: str
        :type magazine: str
        :rtype: bool
        """
        #参考：最简版
        #一个个数ransomNote，把它在magazine中的对应字符一个个删除，直到最后出现ransomNote中有，magazine中没有的字符，return False；否则return True
        for c in ransomNote:
            if c in magazine:
                magazine=magazine.replace(c,'',1)
            else:
                return False
        return True

        #方法一、双指针版
        ransomNote=list(ransomNote)
        magazine=list(magazine)
        ransomNote.sort()
        magazine.sort()
        left,right=0,0
        m=len(ransomNote)
        cnt=0
        while left<len(ransomNote) and right<len(magazine):
            if ransomNote[left]>magazine[right]:
                right+=1
            elif ransomNote[left]<magazine[right]:
                left+=1
            else:
                left+=1
                right+=1
                cnt+=1
        if cnt==m:
            return True
        return False


        #方法二、根据ransomNote 和 magazine 由小写英文字母组成的线索
        tmp=[0]*26 #使用数组作为哈希表
        ransomNote=list(ransomNote)
        magazine=list(magazine)
        for ran in ransomNote:
            tmp[ord(ran)-ord("a")]+=1
        
        for maga in magazine:
            tmp[ord(maga)-ord("a")]-=1

        for i in tmp:
            if i>0:
                return False

        return True

        #方法三：方法二简化版
        ##方法二虽然通，但是过程想错了，应该先数magazine，如果ransomNote中有magazine中没有的字符，直接False
        arr = [0] * 26

        for x in magazine:
            arr[ord(x) - ord('a')] += 1

        for x in ransomNote:
            if arr[ord(x) - ord('a')] == 0:
                return False
            else:
                arr[ord(x) - ord('a')] -= 1
        
        return True

例七.15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

三数之和的求解思想是：首先遍历质数数组，下标为i。在每次遍历中（即 i 固定），设定left,right=i+1,len(nums)-1，然后如果 nums[i]+nums[left]+nums[right]<0，那么left+=1;如果nums[i]+nums[left]+nums[right]>0，那么right-=1；如果相等，除了要保存[nums[i],nums[left],nums[right]]还需要left+=1，right-=1，因为在同样的 i 下，可能还存在nums[i]+nums[left]+nums[right]==0的组合，要直到right<=left才能停下来，继续for循环。

这里去除重复解是难点。
采取的方法是

if(i>0 and nums[i]==nums[i-1]): #当出现已经处理过的相同的nums[i]，跳过
continue
while left<right and nums[left]==nums[left+1]: #判断左界和右界是否和下一位置重复，去重复解
left+=1
while left<right and nums[right]==nums[right-1]:
right-=1

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        res=[]

        for i in range(len(nums)):
            if nums[i]>0:
                return res
            if(i>0 and nums[i]==nums[i-1]): #去重复解
                continue
            left,right=i+1,len(nums)-1
            while left<right:
                if nums[i]+nums[left]+nums[right]<0:
                    left+=1
                elif nums[i]+nums[left]+nums[right]>0:
                    right-=1
                else:
                    res.append([nums[i],nums[left],nums[right]])
                    while left<right and nums[left]==nums[left+1]: #去重复解
                        left+=1
                    while left<right and nums[right]==nums[right-1]:
                        right-=1
                    left+=1
                    right-=1

        ##还有答案中不可包含重复三元组，需要去重          

        return res

例八：18. 四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按任意顺序返回答案。

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums.sort()
        n=len(nums)
        res=[]

        for i in range(n):
            if i>0 and nums[i]==nums[i-1]: #去重复解
                continue
            # print(i)
            for j in range(i+1,n):
                if j>i+1 and nums[j]==nums[j-1]:
                    continue
                
                left,right=j+1,n-1
                while left<right:
                    if nums[i]+nums[j]+nums[left]+nums[right]<target:
                        left+=1
                    elif nums[i]+nums[j]+nums[left]+nums[right]>target:
                        right-=1
                    else:
                        res.append([nums[i],nums[j],nums[left],nums[right]])
                        # print(res)
                        while left<right and nums[left]==nums[left+1]:
                            left+=1
                        while left<right and nums[right]==nums[right-1]:
                            right-=1
                        left+=1
                        right-=1

        return res

提示：
1.例八四数之和是例七的延续，一样的道理，五数之和、六数之和等等都采用这种解法。
2. 例五和例八都是四数之和，但是一个用两次双重循环，一个用双指针的理由：因为三数之和和四数之和这两道题目使用哈希法在不超时的情况下做到对结果去重是很困难的，很有多细节需要处理。而例五是四个独立的数组，只要找到A[i]+ B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况。