刷题笔记6-242.有效的字母异位词 ，349. 两个数组的交集 ，202. 快乐数，1. 两数之和

刷题6-242.有效的字母异位词 ，349. 两个数组的交集 ，202. 快乐数，1. 两数之和

为什么没5呢？因为5休息
哈希表是根据关键码的值而直接进行访问的数据结构。
哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里。

---

---

1.有效的字母异位词

题目链接
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例 1:
输入: s = “anagram”, t = “nagaram”
输出: true

示例 2:
输入: s = “rat”, t = “car”
输出: false

• 有效的字母异位词-判断两个字符串是不是由相同的字母组成，顺序可以不一样

法1

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        record=26*[0]  #建立一个26长的数组
        for i in s:
            record[ord(i)-ord('a')]+=1   #遍历s，对应位置数值+1
        for i in t:
            record[ord(i)-ord('a')]-=1   #遍历t，对应位置数值-1
        for i in range(26):    #遍历数组所有数值，为零则说明为字母异位词
           if record[i]!=0:  #注意!!!
            return False
        return True

---

总结

很巧妙的方法，建立数组，遍历，字符串s中字母出现一次就+1，再出现就再+1。对应字符串t，字母出现一次-1，再出现一次就再-1。最后判断数组是否全为零。
ps：另外两个版本等待补充

---

2.两个数组的交集

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

示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

法1：使用字典和集合

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        dic={}  #字典
        for i in nums1:
            dic[i]=dic.get(i,0)+1  #难点！
        res=set()
        for i in nums2:
            if i in dic:
                res.add(i)   #add()可以给集合添加一个元素
                del dic[i]
        return list(res)    

dic[i]=dic.get(i,0)+1

value在这表示出现次数
使用列表也能过，用append

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        dic={}  #字典
        for i in nums1:
            dic[i]=dic.get(i,0)+1  #难点！
        res=list()
        for i in nums2:
            if i in dic:
                res.append(i)   #append()可以给列表尾部添加元素
                del dic[i]
        return res    

---

总结

还有其他方法有待完善，方法比较灵活，活学活用

---

3.快乐数

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

「快乐数」 定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例：
输入：19
输出：true
解释：
$$\begin{gathered} 1^2+9^2=82 \\ {8}^2+2^2=68 \\ {6}^2+8^2=100 \\ {1}^2+0^2+0^2=1 \end{gathered}$$

• 要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。

class Solution:
    def isHappy(self, n: int) -> bool:
        record=set()
        while True:
            n=self.getsum(n) # 迭代关键
            if n==1:
                return True
            if n in record:
                return False
            else:
                record.add(n)

    def getsum(self, n: int) -> int:
        newsum=0
        while n:
            n,r=divmod(n,10) #n商,r余数
            newsum+=r**2
        return newsum

---

总结

此题有6个版本，后面在一一细看?

---

4.两数之和

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

法1：用字典

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic=dict()
        for index,value in enumerate(nums):  # a+b=c
            if target-value in dic:
                return [dic[target-value],index]   #返回c-a下标，a下标
            else:
                dic[value]=index   #没找到就加入
        return []

• enumerate() 是 python 内置函数（枚举），遍历可迭代对象后，返回序号（索引序列）+元素（对应值）

---

总结

此次题目解法很多，才疏学浅只会了一点，有待加强！