代码随想录算法训练营 Day 5
Published:
Q1. LeetCode 242
解法1: 使用哈希表存储每个字母在s中出现的次数，然后再判断t中的字母是否出现相同次数。需要判断最后哈希表是否还有值，若还有，则表明s中有多余字符
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
hashmap = {}
for c in s:
hashmap[c] = hashmap.get(c, 0) + 1
for c in t:
if c not in hashmap:
return False
hashmap[c] = hashmap[c] - 1
if hashmap[c] == 0:
del hashmap[c]
if hashmap:
return False
return True
解法2: 用列表存储s中每个字母出现的次数，然后再遍历t，每次将出现的字符对应位置减1，若某个位置出现负数则返回False
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
freq = [0] * 26
for c in s:
freq[ord(c) - ord('a')] += 1
for c in t:
if freq[ord(c) - ord('a')] == 0:
return False
freq[ord(c) - ord('a')] -= 1
return sum(freq) == 0
复杂度分析
时间复杂度：O($n$) 空间复杂度：O(1)
Q2. LeetCode 349
解法1: 利用哈希表统计数组1中的各个数字出现次数，然后遍历数组2，如果当前数字在哈希表中，则将其加入结果数组中
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
hashmap = {}
for num in nums1:
hashmap[num] = hashmap.get(num, 0) + 1
res = []
for num in nums2:
if num in hashmap and num not in res:
res.append(num)
return res
解法2: 因为数字范围为[0,1000]，所以可以用数组替代
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
c1 = [0] * 1001
c2 = [0] * 1001
for num in nums1:
c1[num] += 1
for num in nums2:
c2[num] += 1
res = []
for i in range(len(c1)):
if c1[i] * c2[i] > 0:
res.append(i)
return res
复杂度分析
时间复杂度：O($n+m$) 空间复杂度：O($n$)
Q3. LeetCode 202
思路：存储出现的和，假如出现重复的结果，说明进入循环，则立刻返回False
class Solution:
def isHappy(self, n: int) -> bool:
record = set()
while n not in record:
record.add(n)
new_sum = 0
n_str = str(n)
for i in n_str:
new_sum += int(i) ** 2
if new_sum == 1:
return True
n = new_sum
return False
复杂度分析
时间复杂度：O($logn$) 空间复杂度：O($logn$)
Q4. LeetCode 1
思路：利用哈希表存储数字以及所对应的索引，其中key为数字，value为索引
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashmap = {}
for i in range(len(nums)):
diff = target - nums[i]
if diff in hashmap:
return [i, hashmap[diff]]
hashmap[nums[i]] = i
return []
复杂度分析
时间复杂度：O($n$) 空间复杂度：O($n$)