242. 有效的字母异位词
- 思路
- example
- hash: 数组, size: 26
- ord('a)
- 遍历完t后, 再检查一遍table_s,全部为0说明匹配。
- 复杂度. 时间：O(m+n), 空间: O(1) = O(26)
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
table_s = [0] * 26
for ch in s:
table_s[ord(ch)-ord('a')] += 1
for ch in t:
table_s[ord(ch)-ord('a')] -= 1
for i in range(26):
if table_s[i] != 0:
return False
return True
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
table = collections.defaultdict(int)
for ch in s:
table[ch] += 1
for ch in t:
table[ch] -= 1
if table[ch] < 0:
return False
for key, val in table.items():
if table[key] != 0:
return False
return True
- Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?
- 对于进阶问题，Unicode 是为了解决传统字符编码的局限性而产生的方案，它为每个语言中的字符规定了一个唯一的二进制编码。而 Unicode 中可能存在一个字符对应多个字节的问题，为了让计算机知道多少字节表示一个字符，面向传输的编码方式的 UTF−8 和 UTF−16 也随之诞生逐渐广泛使用，具体相关的知识读者可以继续查阅相关资料拓展视野，这里不再展开。
回到本题，进阶问题的核心点在于「字符是离散未知的」，因此我们用哈希表维护对应字符的频次即可。同时读者需要注意 Unicode 一个字符可能对应多个字节的问题，不同语言对于字符串读取处理的方式是不同的。 - hash: 字典
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
table_s = collections.defaultdict(int)
table_t = collections.defaultdict(int)
for ch in s:
table_s[ch] += 1
for ch in t:
table_t[ch] += 1
return table_s == table_t
349. 两个数组的交集
- 思路
- example
- hash: set （两个）
- set1
- result set
- 复杂度. 时间：O(m+n), 空间: O(m+n)
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
set1 = set()
for num in nums1:
set1.add(num)
res = set()
for num in nums2:
if num in set1 and num not in res:
res.add(num)
return list(res)
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
set1 = set(nums1)
set2 = set(nums2)
res = set()
for num in nums1:
if num in set1 and num in set2:
res.add(num)
return list(res)
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
set1 = set()
for num in nums1:
set1.add(num)
set2 = set()
for num in nums2:
if num in set1:
set2.add(num)
return list(set2)
202. 快乐数
- 思路
- example
- hash: set
用set来处理cycle
- 复杂度.
class Solution:
def isHappy(self, n: int) -> bool:
def compute_sum(num):
sum_ = 0
while num:
rem = num % 10
sum_ += rem ** 2
num //= 10
return sum_
used = set()
while True:
n = compute_sum(n)
if n == 1:
return True
if n in used:
return False
used.add(n)
class Solution:
def isHappy(self, n: int) -> bool:
def sumOfSquare(n):
res = 0
while n:
res += (n % 10) ** 2
n //= 10
return res
if n == 1:
return True
path = set()
path.add(n)
while n != 1:
n = sumOfSquare(n)
if n in path:
return False
else:
path.add(n)
return True
1. 两数之和
- 思路
- example
- hash: dict
- record[nums[i]] = i
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
n = len(nums)
hash_map = collections.defaultdict(int)
for i in range(n):
if target - nums[i] in hash_map:
return [hash_map[target-nums[i]], i]
hash_map[nums[i]] = i
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
n = len(nums)
record = collections.defaultdict(int)
for i in range(n):
if nums[i] in record:
return [record[nums[i]], i]
record[target-nums[i]] = i
