代码随想录算法训练营Day 5| 242.有效的字母异位词, 242.有效的字母异位词,202. 快乐数,1. 两数之和

题目简介

242.有效的字母异位词 https://leetcode.cn/problems/valid-anagram/description/
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

349. 两个数组的交集 https://leetcode.cn/problems/intersection-of-two-arrays/description/
给定两个数组 nums1 和 nums2 ，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。

202. 快乐数 https://leetcode.cn/problems/happy-number/description/
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。
如果这个过程结果为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。

1. 两数之和 https://leetcode.cn/problems/two-sum/description/
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

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

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

初见思路

242: 可以用Python原生Counter乱杀, Python可导包先整Counter，dict的区别仅在于性能

from collections import Counter
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return Counter(s) == Counter(t)

349: 再上一个原生包乱杀解法

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set(nums1) & set(nums2))

202: 这道题本身更偏数学规律而不是哈希表，以下是我以前的解：

class Solution:
    def isHappy(self, n: int) -> bool:
        def get_power_sum(num) -> int:
            total_sum = 0
            while num > 0:
                num,digit = divmod(num, 10)
                total_sum += digit ** 2
            return total_sum
        
        slow_run = n
        fast_run = get_power_sum(n)
        while slow_run!=fast_run and fast_run != 1:
            slow_run = get_power_sum(slow_run)
            fast_run = get_power_sum(get_power_sum(fast_run))
        return fast_run == 1

注意题眼，可能会死循环，那么需要检测循环的方法：要么记录历史平方和，看是否重复；要么遵循链表一样的快慢指针法逻辑，有环跳出。另一个核心是Python自带的divmod方法，可以方便的返回商和余数精简代码。
1: 这道题已经做过太多遍，就不废话了，已经是代码界的abandon了。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            residual = target - nums[i]
            if residual in nums[i+1:]:
                return [i,nums[i+1:].index(residual)+i+1]
        return [-1,-1]

这个是Python的一种解，可能不算很直观，但是很简练；以下是标准的哈希表的解法：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        records = dict()

        for index, value in enumerate(nums):  
            if target - value in records:   
                return [records[target- value], index]
            records[value] = index    
        return [-1,-1]