242.有效的字母异位词
242. 有效的字母异位词 - 力扣（LeetCode）
给定两个字符串 _s_ 和 _t_ ，编写一个函数来判断 _t_ 是否是 _s_ 的字母异位词。
注意： 若 _s_ 和 _t_ 中每个字符出现的次数都相同，则称 _s_ 和 _t_ 互为字母异位词。
- 示例 1:
- 输入: s = "anagram", t_= "nagaram"
- 输出: true
- 示例 2:
- 输入:_ = "rat", t = "car"
- 输出: false
解题思路：
1. 排序法：sort两个字符串，直接判断是否相等
2. 哈希表-字典：两个dict，分别存储两个字符串中的不同字母数量，判断dict是否相等
3. 哈希表-列表：一个长度为26, 元素值全为0的list，先通过ASCII码对一个字符串元素，在列表对应位置元素的数值累加，再对另一个字符串元素在该列表中数值累减
class Solution():
def isAnagram(s,t): # 排序法
new_s = sorted(s)
new_t = sorted(t)
if new_s == new_t:
return True
return False
def isAnagram(s,t): # 哈希表-字典
dict_s = {}
dict_t = {}
for w in s:
if w in dict_s:
dict_s[w]+=1
else:
dict_s[w]=1
for w in t:
if w in dict_t:
dict_t[w]+=1
else:
dict_t[w]=1
if dict_s == dict_t:
return True
return False
def isAnagram(s,t): # 哈希别-列表
res = [0]*26
for w in s:
res[ord(w)-ord('a')]+=1
for w in t:
res[ord(w)-ord('a')]-=1
for i in res:
if i!=0:
return False
return True
349.两个数组的交集
349. 两个数组的交集 - 力扣（LeetCode）
给定两个数组 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] or [4,9]
解题思路：
1. 暴力求解：遍历nums2，判断每个元素是否在nums1中
2. 哈希表-集合：使用set()，求交集
3. 哈希表-字典/列表+集合：先创建nums1哈希表，再遍历nums2判断元素是否在哈希表
class Solution():
def intersection(nums1,nums2): # 暴力求解
res = []
for n in nums2:
if n in nums1 and n not in res:
res.append(n)
return res
def intersection(nums1,nums2): # 哈希表-集合求交集
return list(set(nums1)&set(nums2))
def intesection(nums1,nums2): # 哈希表-字典+集合
table = {} # 字典查询似乎更快？
for n in nums1:
table[n] = table.get(n,0) + 1
res = set()
for n in nums2:
if n in table:
res.add(n)
return list(res)
202.快乐数
202. 快乐数 - 力扣（LeetCode）
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果n是 快乐数 就返回true；不是，则返回false。 - 示例 1：
- 输入：n = 19
- 输出：true
- 解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
- 示例 2：
- 输入：n=2
- 输出：false
解题思路：
无限循环条件：计算过程，必然会出现相同的数
class Solution():
def isHappy(n):
table = {}
while n!=1:
if n in table:
return False
table[n] = 1
n = sum([int(i)**2 for i in str(n)])
return True
1.两数之和
1. 两数之和 - 力扣（LeetCode）
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
- 示例 1：
- 输入：nums = [2,7,11,15], target = 9
- 输出：[0,1]
- 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
- 示例 2：
- 输入：nums = [3,2,4], target = 6
- 输出：[1,2]
- 示例 3：
- 输入：nums = [3,3], target = 6
- 输出：[0,1]
解题思路：
1. 暴力求解：双循环，两数相加==target
2. 哈希表：判断target-num是否在table出现过，若出现返回table[target-num]和当前id；否则，table[num]=id
class Solution():
def twoSum(nums,target): # 暴力求解
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if nums[i]+nums[j]==target:
return [i,j]
return None
def twoSum(nums,target): # 哈希表
table = {}
for id,num in enumerate(nums):
if target-num in table:
return [table[target-num],id]
table[num]=id
return None