Leetcode 242 有效的字母异位词
题目链接: 有效的字母异位词
给定两个字符串，判断其中一个字符串是否为另一个字符串的字母异位词（即字母种类和个数均能一一对应，仅位置不同）
例如anagram和nagaram互为彼此的字母异位词
思路: 统计一个字符串中所有字符，再遍历另一个字符串，若发现字母种类或者个数无法对应，则不是有效的字母异位词，否则是有效的字母异位词
具体代码实现:
class Solution:def isAnagram(self, s: str, t: str) -> bool:# 用字典记录每个字母出现的频率if len(s) != len(t):return Falsemymap = dict()for ch in s:mymap[ch] = mymap.get(ch, 0) + 1for ch in t:mymap[ch] = mymap.get(ch, 0) - 1for val in mymap.values():if val != 0:return Falsereturn True
class Solution:def isAnagram(self, s: str, t: str) -> bool:# 利用计数器类进行判断from collections import Counterreturn Counter(s) == Counter(t)
时间复杂度: O(n)
Leetcode 349 两个数组的交集
题目链接: 两个数组的交集
思路: 分别记录在数组1和数组2中出现过的数字，若一个数字在两个数组中均出现过，则将其加入到集合中
具体代码实现:
class Solution:def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:# 利用数组作为哈希表进行处理count1 = [0] * 1001count2 = [0] * 1001for num in nums1:count1[num] += 1for num in nums2:count2[num] += 1result = []for num in range(1001):if count1[num] * count2[num] > 0:result.append(num)return result
class Solution:def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:# 直接用集合进行去重，随后取并集即可return list(set(nums1) & set(nums2))
Leetcode 202 快乐数
题目链接: 快乐数
给定一个数，计算该数上各位数的平方之和，重复这一操作，若最终得到的结果为1，则判断该数为快乐数，若计算过程中出现无限循环无法凑出1，则说明该数不是快乐数
思路: 维护一个集合，记录在计算过程中得到的结果，若当前计算结果已经出现在过往的结果集中，则说明当前出现了循环，给定的数字不是快乐数
具体代码实现
class Solution:def isHappy(self, n: int) -> bool:past_sum = set()while n != 1:n = self.getHappySum(n)if n in past_sum:return Falsepast_sum.add(n)return Truedef getHappySum(self, num: int) -> int:"""给定一个数，返回其各个位置上数的平方和"""sum = 0while num:cur = num % 10sum += cur ** 2num = num // 10return sum
Leetcode 1 两数之和
题目链接: 两数之和
给定一个数组nums和一个目标和target，要求从数组中找出两个数字，使这两个数字之和等于目标值，并返回这两个数字的下标。题目保证一定存在符合条件的两个数。
思路: 有两种解法，既可以通过暴力解法，利用两层循环遍历数组找出符合条件的两个元素，并返回其下标。也可以遍历一遍数组，在遍历过程中，维护一个字典，其中记录元素值-数组下标键值对。每遍历一个元素num时，检查target-num是否已经存在于元素值中，若已经存在，则返回当前num对应的下标和target-num元素在数组中对应的下标即可。
具体代码实现
class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:# 暴力解法for i in range(len(nums)):for j in range(i+1, len(nums)):if nums[i] + nums[j] == target:return [i, j]
class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:# 哈希表法mydict = dict()for idx in range(len(nums)):if (target-nums[idx]) in mydict:return [mydict[target-nums[idx]], idx]mydict[nums[idx]] = idxreturn []
时间复杂度: O(n^2)(暴力解法), O(n)(哈希表法)