查找表类算法精析
介绍
查找，是使用计算机处理问题时的一个最基本的任务，因此也是算法面试中非常常见的一类问题。很多算法问题的本质，就是要能够高效使用查找。LeetCode 中有很多问题都会用到集合和字典（C++ 中为 set 和 map，Python 中为 set 和 dict）这两种数据结构，今天我们将会对 LeetCode 这类问题进行总结，所有代码采用 Python 实现，并可以在 LeetCode 里 AC。
两类查找问题
- 查找有无：元素 ‘a’ 是否存在？可以使用 set 集合这种数据结构
- 查找对应关系（键值对应）：元素 ‘a’ 出现了几次？可以使用 dict 字典这种数据结构
集合 set 的使用
首先，让我们从 set 开始，通过下列的一些问题熟悉它的使用吧！
两个数组的交集
给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]
示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]
说明:
- 输出结果中的每个元素一定是唯一的。
- 我们可以不考虑输出结果的顺序。
解答
方法一：两个 set
幼稚的方法是根据第一个数组 nums1 迭代并检查每个值是否存在在 nums2 内。如果存在将值添加到输出。这样的方法会导致 O(n×m) 的时间复杂性，其中 n 和 m 是数组的长度。
为了在线性时间内解决这个问题，我们使用集合 set，在 O*(1) 时间复杂度实现操作。
其思想是将两个数组转换为集合 set，然后迭代较小的集合检查是否存在在较大集合中。平均情况下，这种方法的时间复杂度为O(n+m)。
class Solution:
def set_intersection(self, set1, set2):
return [x for x in set1 if x in set2]
def intersection(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
set1 = set(nums1)
set2 = set(nums2)
if len(set1) < len(set2):
return self.set_intersection(set1, set2)
else:
return self.set_intersection(set2, set1)
官方解答
由于问题中的元素是唯一的，所以我们只关心元素的有无，那么我们可以使用 set 这个结构。首先将 nums1 的所有数据存入 set 中，再将 nums2 的所有数组也存入 set 中，最后求并集即可。
class Solution:
def intersection(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
a = set(nums1)
b = set(nums2)
c = a & b
return list(c)
快乐数
编写一个算法来判断一个数是不是“快乐数”。
一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。
示例:
输入: 19
输出: true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
解答
递归解法
class Solution:
def isHappy(self, n: int) -> bool:
return self.isHappy(sum(int(i) ** 2 for i in str(n))) if n > 4 else n == 1
- 不是快乐数的数称为不快乐数(unhappy number)，所有不快乐数的数位平方和计算，最后都会进入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 的循环中
-
已知规律： [1 ~ 4] 中只有 1 是快乐数，[5 ~ ∞] 的数字要么回归到 1 要么回归到 4 或 3
- 因此仅需在 n > 4 时调用递归
细节补充
- 尾递归：如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。
集合解法
- 以上解法的规律比较难想到的，正常解法是判断 n 是否会进入循环：
class Solution:
def isHappy(self, n: int) -> bool:
seen = {1}
while n not in seen:
seen.add(n)
n = sum(int(i) ** 2 for i in str(n))
return n == 1
官方解答
判断出现的数之前有没有出现过，出现过就会产生循环，就不是快乐数。可以用集合 set 来记录之前出现的数字。
class Solution:
def isHappy(self, n):
"""
:type n: int
:rtype: bool
"""
ss = set()
while True:
if n == 1:
return True
total = 0
while n:
total += (n % 10) * (n %10)
n = n // 10
if total in ss:
return False
ss.add(total)
n = total
存在重复元素
给定一个整数数组，判断是否存在重复元素。
如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。
示例 1:
输入: [1,2,3,1]
输出: true
示例 2:
输入: [1,2,3,4]
输出: false
示例 3:
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true
解答
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
set1 = set(nums)
if len(set1) != len(nums):
return 'true'
else:
return 'false'
测试通过，但是提交报错。为啥？
因为！不能按题目中的来！！
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
set1 = set(nums)
if len(set1) != len(nums):
return True
else:
return False
解法1：集合法
判断原数组和该数组的长度相不相等，一行解决：
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
return len((set(nums))) != len(nums)
解法2：哈希表
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
dic = {}
for i in nums:
if dic.get(i):
return True
dic[i] = 1
return False
解法3：排序法
排序之后，相等元素必相邻：
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
nums.sort()
for i in range(len(nums)-1):
if nums[i+1] == nums[i]:
return True
return False
官方解答
使用 set 集合存储前面遍历过的元素，对于要每个元素 num[i]，判断是否在前面的 recode 中，如果存在，返回 True。
class Solution:
def containsDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
n = len(nums)
if n <= 1:
return False
recode = set()
recode.add(nums[0])
for i in range(1, n):
if nums[i] in recode:
return True
recode.add(nums[i])
return False
字典 dict 的使用
一些较为典型的字典使用案例。
两个数组的交集 II
给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]
说明：
- 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
- 我们可以不考虑输出结果的顺序。
进阶:
- 如果给定的数组已经排好序呢？你将如何优化你的算法？
- 如果 nums1 的大小比 nums2 小很多，哪种方法更优？
- 如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
解答
思路
- 建立一个哈希表，键为nums1的数，值为这个数出现的次数
- 遍历num2,当num2的数出现在哈希表中，将它添加到答案里，同时更新哈希表，让其出现次数减一。
from collections import defaultdict
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
dic, ans = defaultdict(int), list()
for i in nums1: dic[i] += 1
for i in nums2:
if dic[i] != 0:
ans.append(i)
dic[i] -= 1
return ans
defaultdict(int)项对第一次出现的键会初始化一个0的值- 这题也可以使用
Counter直接统计出字符出现的次数，和手动遍历是一样的。
复杂度分析
假设num1有M项，num2有m项，其中M>m，则
- 时间复杂度O(M+m)
- 空间复杂度O(m)
官方解答
我们对比两个数组的交集，发现在这个问题的基础上，我们多加了记录元素个数的功能，我们可以使用字典 dict实现它。
class Solution:
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
m = len(nums1)
n = len(nums2)
if m == 0 or n == 0:
return []
dicts = {}
for i in nums1:
if i in dicts:
dicts[i] += 1
else:
dicts[i] = 1
ret = []
for j in nums2:
if j in dicts and dicts[j] > 0:
ret.append(j)
dicts[j] -= 1
return ret
有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
说明:
你可以假设字符串只包含小写字母。
进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
解答
from collections import Counter
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
return Counter(s) == Counter(t)
官方解答
只要 t 中和 s 中字符都一样且数目都一样，那么就可以了。Python 实现的话可以采用 collections。Counter 这个函数实现对各个字符出现的次数进行统计。
from collections import Counter
class Solution:
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
c1 = Counter(s)
c2 = Counter(t)
if (c1 == c2):
return True
return False
同构字符串
给定两个字符串 s 和 t，判断它们是否是同构的。
如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。
所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。
示例 1:
输入: s = "egg", t = "add"
输出: true
示例 2:
输入: s = "foo", t = "bar"
输出: false
示例 3:
输入: s = "paper", t = "title"
输出: true
说明:
你可以假设 s 和 t 具有相同的长度。
解答
题解
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
return [*map(s.index, s)] == [*map(t.index, t)]
- 同构代表两个字符串中每个位置上字符在自身第一次出现的索引相同
细节补充
- str 类型数据拥有内置函数 index，输入一个子字符串，可以返回子字符串在 str 中第一次出现的索引，若不存在则报错
-
map(函数，可迭代对象) 将会对（参数2：可迭代对象）中的每个元素运用（参数1：函数）并将结果按顺序储存在一个迭代器中，返回这个迭代器
- 使用
[*……]可对对象解包，本题中[*map……]等效于list(map……)
官方解答
可以使用字典 dict 来记住这些字符对是一个很方便的做法。在这里面我用了两个字典 dict，一个字典 hashmap 用来记 s 的字符到 t 的映射，另一个字典 ismap 用来记录 t 的字符到 s 的映射，用于判断 t 中的两个字符不能由 s 中同一个字符映射而来。
class Solution:
def isIsomorphic(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
hashmap = {}
ismap = {}
for i in range(len(s)):
if s[i] in hashmap:
if hashmap[s[i]] != t[i]:
return False
else:
if t[i] in ismap:
return False
hashmap[s[i]] = t[i]
ismap[t[i]] = True
return True
根据字符出现频率排序
给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
示例 1:
输入:
"tree"
输出:
"eert"
解释:
'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
示例 2:
输入:
"cccaaa"
输出:
"cccaaa"
解释:
'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。
示例 3:
输入:
"Aabb"
输出:
"bbAa"
解释:
此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。
解答
class Solution(object):
def frequencySort(self, s):
"""
:type s: str
:rtype: str
"""
res = ''
map = {}
for i in s :
if i not in map:
map[i] = 1
else :
map[i] += 1
l = sorted(map.items(), key=lambda x: x[1], reverse=True)
for v , k in l:
res += v*k
return res
官方解答
通过一个字典 dict 存储所有字符出现的次数，因为某个字符的出现次数不可能超过 s 的长度，所以我们将每个字符根据其出现次数放入数组中的对应位置，那么最后我们只要从后往前遍历数组所有位置，将不为空的位置的字符串加入结果 ret 中即可。
from collections import Counter
class Solution:
def frequencySort(self, s):
"""
:type s: str
:rtype: str
"""
n = len(s)
sc = dict(Counter(s))
ll = ['' for i in range(0, n+1)]
isvisited = set()
ret = ""
for key,value in sc.items():
ll[value] += key * value
for i in range(n, -1, -1):
if ll[i] != '':
ret += ll[i]
return ret;
查找表与求和问题
章节收录了一些经典的关于查找表相关的求和系列问题。
两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
answer = []
for left_index in range(len(nums)):
right = target - nums[left_index]
if right in nums[left_index+1:]:
nums_right = nums[left_index+1:]
right_index = nums_right.index(right)+left_index+1
answer.extend([left_index, right_index])
break
return answer
官方解答
暴力解法
遍历所有数据对，判断是否等于 target，时间复杂度度 O(n^2)。
双索引对撞
先排序后，后使用双索引对撞，时间复杂度为：O(n log n) + O(n) = O(n log n)， 可以试一试，也是可以 AC 的。
使用查找表
将所有元素放入查找表，之后对于每一个元素 a，查找 target - a 是否存在。
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
n = len(nums)
if n < 2:
return []
dict1 = dict();
for i in range(n):
other = target - nums[i]
if other in dict1:
return [dict1[other], i]
dict1[nums[i]] = i
return []
三数之和
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
解答
class Solution:
def threeSum(self, nums: [int]) -> [[int]]:
nums.sort()
res, k = [], 0
for k in range(len(nums) - 2):
if nums[k] > 0: break # because of j > i > k.
if k > 0 and nums[k] == nums[k - 1]: continue # skip.
i, j = k + 1, len(nums) - 1
while i < j:
s = nums[k] + nums[i] + nums[j]
if s < 0:
i += 1
while i < j and nums[i] == nums[i - 1]: i += 1
elif s > 0:
j -= 1
while i < j and nums[j] == nums[j + 1]: j -= 1
else:
res.append([nums[k], nums[i], nums[j]])
i += 1
j -= 1
while i < j and nums[i] == nums[i - 1]: i += 1
while i < j and nums[j] == nums[j + 1]: j -= 1
return res
官方解答
可以转化成上一题的两数之和的问题，a + b = -c，改动一下两数之和的 twoSum 函数即可实现。
class Solution:
def twoSum(self, nums, target, l, r):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
n = len(nums[l: r+1])
if n < 2:
return set()
start = nums[l - 1]
dict1 = dict()
ret = set()
for i in range(l, r+1):
other = target - nums[i]
if other in dict1:
ret.add((start, other, nums[i]))
dict1[nums[i]] = i
return ret
def threeSum(self, nums):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
n = len(nums)
if n < 3:
return []
nums.sort()
ret = set()
for i in range(n):
# nums[i] 为正数，表示后面不可能有两数之后为负
if nums[i] > 0:
break
if (i >= 1 and nums[i] == nums[i-1]):
continue
ll = self.twoSum(nums, -nums[i], i+1, n-1)
if (ll == set()):
continue
ret = ret | ll
return list(ret)
四数之和
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 *a，**b，c* 和 *d* ，使得 *a* + *b* + *c* + *d* 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
解答
思路：
- 使用两个循环固定两个数，用双指针找到满足题解的另外两个数。
说明：
- 使用双指针法，解法和三数之和类似
- 运用剪枝直接排除重复解
- 合理移动双指针直接排除非正确解
重点：
- 怎样剪除所有重复枝，建议使用list而非set存储结果，去debug分析有哪些重复枝是没处理好的.
- 怎样通过特定条件（一般是边界值）排除非正确解集，减少运算次数
from typing import List
class Solution(object):
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
length = len(nums)
# result = set()
result = []
# 双指针法使用前提：排序
nums.sort()
for i in range(length - 3):
# 去重（剪枝）
if i > 0 and nums[i] == nums[i - 1]:
continue
# 如果固定数与数组三最小数之和大于target, 则后续循环都是不存在解的, 从遍历中跳出
if nums[i] + sum(nums[i + 1:i + 3 + 1]) > target:
break
# 如果固定数与数组三最大数之和小于taget, 则当前遍历不存在解, 进入下一个遍历
if nums[i] + sum(nums[-1:-3 - 1:-1]) < target:
continue
for j in range(i + 1, length - 2):
# 去重（剪枝）
if j - i > 1 and nums[j] == nums[j - 1]:
continue
# 如果固定数与数组两最小数之和大于target, 则后续循环都是不存在解的, 从遍历中跳出
if nums[i] + nums[j] + sum(nums[j + 1:j + 2 + 1]) > target:
break
# 如果固定数与数组两最大数之和小于target, 则当前遍历不存在解, 进入下一个遍历
if nums[i] + nums[j] + sum(nums[-1:-2 - 1:-1]) < target:
continue
# 双指针法
left, right = j + 1, length - 1
while left < right:
tmp_sum = nums[i] + nums[j] + nums[left] + nums[right]
# 如果当前和小于target, 收缩左边界
if tmp_sum < target:
left += 1
# 如果当前和大于target, 收缩左边界
elif tmp_sum > target:
right -= 1
# 如果值相等
else:
# 记录解
# result.add((nums[i], nums[j], nums[left], nums[right], ))
result.append([nums[i], nums[j], nums[left], nums[right]])
# 求得正确解后，去重（剪枝）
while left < right and nums[left] == nums[left + 1]:
left += 1
# 求得正确解后，去重（剪枝）
while left < right and nums[right] == nums[right - 1]:
right -= 1
# 在求得正确解，并且剪枝后，仅收缩移动一个指针，都不会是正确解；
# 因此应收缩移动双指针，直接排除不符合解的情况，减少运算次数
left += 1
right -= 1
return result
官方解答
转化成上一题三数之和问题，a + b + c = -d + target，相应的也需要更改三数之和的 threeSum 函数。
class Solution:
def twoSum(self, nums, target, l, r):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
n = len(nums[l : r+1])
if n < 2:
return list()
start = nums[l - 1]
dict1 = dict()
ret = list()
for i in range(l, r+1):
other = target - nums[i]
if other in dict1:
ret.append([start, other, nums[i]])
dict1[nums[i]] = i
return ret
# nums[l...r] 中返回 a+b+c=target
def threeSum(self, nums, target, l, r):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
n = len(nums[l : r+1])
if n < 3:
return list()
start = nums[l-1]
ret = list()
for i in range(l, r+1):
if nums[i] > 0 and target <= 0:
break
if (i >= l+1 and nums[i] == nums[i-1]):
continue
ll = self.twoSum(nums, target-nums[i], i+1, r)
if (ll == list()):
continue
for i in ll:
i.insert(0, start)
ret.append(i)
return ret
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
n = len(nums)
if n < 4:
return []
nums.sort()
ret = set()
for i in range(n):
ll = self.threeSum(nums, target-nums[i], i+1, n-1)
if ll == list():
continue
for l in ll:
ret.add(tuple(l))
return list(ret)
灵活选择键值
巧用正确的键值，有时可以让您的代码事半功倍。
四数相加 II
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 – 1 之间，最终结果不会超过 231 – 1 。
例如:
输入:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
输出:
2
解释:
两个元组如下:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
解答
class Solution:
def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
dic = collections.Counter(a+b for a in A for b in B)
return sum(dic.get(-c-d,0) for c in C for d in D)
- 记录需要的值
官方解答
- 暴力解法，时间复杂度 O(n^4)
- 将 D 中的元素放入查找表，时间复杂度 O(n^3)
- 将 A + B 的每一种可能放入查找表，然后 两重循环对在查找表中寻找是否存在 -(C[i] + D[i])，时间复杂度为 O(n^2)。两数相加的和作为键值。
我采用第三种方法实现
class Solution:
def fourSumCount(self, A, B, C, D):
"""
:type A: List[int]
:type B: List[int]
:type C: List[int]
:type D: List[int]
:rtype: int
"""
assert(len(A) == len(B) == len(C) == len(D))
memo = dict()
for i in range(len(A)):
for j in range(len(B)):
if A[i] + B[j] in memo:
memo[A[i] + B[j]] += 1
else:
memo[A[i] + B[j]] = 1
ret = 0
for i in range(len(C)):
for j in range(len(D)):
if -C[i] - D[j] in memo:
ret += memo[-C[i]-D[j]]
return ret
字母异位词分组
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明：
- 所有输入均为小写字母。
- 不考虑答案输出的顺序。
解答
方法一：排序数组分类
思路
当且仅当它们的排序字符串相等时，两个字符串是字母异位词。
算法
维护一个映射ans : {String -> List}，其中每个键 K 是一个排序字符串，每个值是初始输入的字符串列表，排序后等于 K。
在 Java 中，我们将键存储为字符串，例如，code。 在 Python 中，我们将键存储为散列化元组，例如，('c', 'o', 'd', 'e')。
class Solution(object):
def groupAnagrams(self, strs):
ans = collections.defaultdict(list)
for s in strs:
ans[tuple(sorted(s))].append(s)
return ans.values()
复杂度分析
- 时间复杂度：O(NKlogK)，其中 N 是
strs的长度，而 K 是strs中字符串的最大长度。当我们遍历每个字符串时，外部循环具有的复杂度为O(N)。然后，我们在 O(KlogK) 的时间内对每个字符串排序。 -
空间复杂度：O(NK)，排序存储在 ans 中的全部信息内容。
官方解答：
对字符串数组中每一个字符串进行排序，之后如果遇到相等的字符串，就说明该字符串对应的排序前的字符串是字母易位词。找字母易位词的过程用哈希表，每当出现一个新的字母易位词，就往 ret 中添加一个 list，同时往哈希表中添加该字母易位词，并将该字母易位词在哈希表中的 value 值存成该 list 的索引值；出现哈希表中已经存在的字母易位词，直接往对应索引的 list 中添加即可。排序后的字符串作为键值。
class Solution:
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
if len(strs) == 0:
return []
ret = []
memo = dict()
k = 0
for one in strs:
lone = list(one)
lone.sort()
tone = "".join(lone)
if tone not in memo:
memo[tone] = k
k += 1
ret.append([])
ret[memo[tone]].append(one)
return ret
回旋镖的数量
给定平面上 n 对不同的点，“回旋镖” 是由点表示的元组 (i, j, k) ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。
找到所有回旋镖的数量。你可以假设 n 最大为 500，所有点的坐标在闭区间 [-10000, 10000] 中。
示例:
输入:
[[0,0],[1,0],[2,0]]
输出:
2
解释:
两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]
解答
- 外层遍历每个点 i，内层遍历并计算其他点 j 到 i 的距离并通过 Map 保存相等距离的频次。
- 计算距离公式不用开根号
- 计算排列组合公式 n * (n – 1)
class Solution:
def dis(self, p1, p2):
return (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1])
def numberOfBoomerangs(self, points: List[List[int]]) -> int:
res = 0
for i in points:
freqMap = {}
for j in points:
if j != i:
d = self.dis(i, j)
freqMap[d] = freqMap[d] + 1 if d in freqMap else 1
for v in freqMap.values():
res += v * (v - 1)
return res
官方解答
暴力解法
三重循环枚举所有的可能性。 时间复杂度为：O(n^3)
使用查找表
观察到 i 是一个 “枢纽”，对于每个点i，遍历其余点到 i 的距离对于每个枢纽 i，计算它到其它点j的距离，并将距离作为键存入字典 dict 中，value 为距离的个数。时间复杂度为：O(n^2)。 距离作为键值。
class Solution:
def numberOfBoomerangs(self, points):
"""
:type points: List[List[int]]
:rtype: int
"""
n = len(points)
if n < 3:
return 0
ret = 0
# i是一个中轴, 计算出所有与i的距离
for i in range(n):
memo = dict()
for j in range(n):
if (i != j):
dict1 = self.dist(points[i], points[j])
if dict1 in memo:
memo[dict1] += 1
else:
memo[dict1] = 1
for key,value in memo.items():
ret += value * (value-1)
return ret
def dist(self, alist, blist):
return (alist[0] - blist[0]) * (alist[0] - blist[0]) + (alist[1] - blist[1]) * (alist[1] - blist[1])
直线上最多的点数
给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。
示例 1:
输入: [[1,1],[2,2],[3,3]]
输出: 3
解释:
^
|
| o
| o
| o
+------------->
0 1 2 3 4
示例 2:
输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出: 4
解释:
^
|
| o
| o o
| o
| o o
+------------------->
0 1 2 3 4 5 6
解答
方法 1：枚举
首先简化这个问题：找出一条通过点 i 的直线，使得经过最多的点。
我们会发现，其实只需要考虑当前点之后出现的点 i + 1 .. N - 1 即可，因为通过点 i-2 的直线已经在搜索点 i-2的过程中考虑过了。
思路非常简单：画一条通过点 i 和之后出现的点的直线，在哈希表中存储这条边并计数为 2 = 当前这条直线上有两个点。
假设现在 i < i + k < i + l 这三个点在同一条直线上，当画出一条通过 i 和 i+l 的直线会发现已经记录过了，因此对更新这条边对应的计数：count++。
如何存储一条边？
如果这条线是水平的，例如 y=c，我们可以利用常数 c 作为水平直线的哈希表的键。
注意到这里所有直线都是通过同一个点 i 的，因此并不需要记录 c 的值而只需要统计水平直线的个数。
剩下的直线可以被表示成 x = slope * y + c，同样 c 也是不需要的，因为所有直线都通过同一个点 i 所以只需要用 slope 作为直线的键。
通过两个点 1 和 2 的直线方程可以 用坐标表示为：
$$
\frac{x-x_{1}}{x_{1}-x_{2}}=\frac{y-y_{1}}{y_{1}-y_{2}}
$$
转换成 $x=s l o p e \times y+c$ 表示为：
$$
\text {slope}=\frac{x_{1}-x_{2}}{y_{1}-y_{2}}
$$
所以，最终的算法如下：
- 初始化最大点数
max_count = 1。 - 迭代所有的点
i从0到N - 2。 - 对于每个点
i找出通过该点直线的最大点数max_count_i：- 初始化通过点
i直线的最大点数：count = 1。 - 迭代下一个顶点
j从i+1到N-1。 - 如果 j 和 i 重合，更新点 i 相同点的个数。
- 否则：
- 保存通过 i 和 j 的直线。
- 每步更新
count。
- 返回结果 max_count_i = count + duplicates。
- 初始化通过点
- 更新结果 max_count = max(max_count, max_count_i)。
class Solution:
def maxPoints(self, points):
"""
:type points: List[Point]
:rtype: int
"""
def max_points_on_a_line_containing_point_i(i):
"""
Compute the max number of points
for a line containing point i.
"""
def add_line(i, j, count, duplicates):
"""
Add a line passing through i and j points.
Update max number of points on a line containing point i.
Update a number of duplicates of i point.
"""
# rewrite points as coordinates
x1 = points[i].x
y1 = points[i].y
x2 = points[j].x
y2 = points[j].y
# add a duplicate point
if x1 == x2 and y1 == y2:
duplicates += 1
# add a horisontal line : y = const
elif y1 == y2:
nonlocal horisontal_lines
horisontal_lines += 1
count = max(horisontal_lines, count)
# add a line : x = slope * y + c
# only slope is needed for a hash-map
# since we always start from the same point
else:
slope = (x1 - x2) / (y1 - y2)
lines[slope] = lines.get(slope, 1) + 1
count = max(lines[slope], count)
return count, duplicates
# init lines passing through point i
lines, horisontal_lines = {}, 1
# One starts with just one point on a line : point i.
count = 1
# There is no duplicates of a point i so far.
duplicates = 0
# Compute lines passing through point i (fixed)
# and point j (interation).
# Update in a loop the number of points on a line
# and the number of duplicates of point i.
for j in range(i + 1, n):
count, duplicates = add_line(i, j, count, duplicates)
return count + duplicates
# If the number of points is less than 3
# they are all on the same line.
n = len(points)
if n < 3:
return n
max_count = 1
# Compute in a loop a max number of points
# on a line containing point i.
for i in range(n - 1):
max_count = max(max_points_on_a_line_containing_point_i(i), max_count)
return max_count
官方解答
两点可以确定一条直线，那么选择固定一个点，求其他点与固定点的斜率，如果斜率相同，那么斜率相同的点在同一条直线上。同时要考虑，斜率可能为无穷大，也有可能两个点为同一个点。键值应该为：斜率。
# Definition for a point.
# class Point:
# def __init__(self, a=0, b=0):
# self.x = a
# self.y = b
from decimal import *
class Solution:
def maxPoints(self, points):
"""
:type points: List[Point]
:rtype: int
"""
n = len(points)
if (n <= 2):
return n
ret = 0
# 对于每一个i,计算它与其他点的斜率
for i in range(n):
memo = {'inf': 0}
same = 0
for j in range(n):
if i != j:
if points[i].x == points[j].x and points[i].y != points[j].y:
memo['inf'] += 1
elif (points[i].x != points[j].x):
slope1 = self.slope(points[i], points[j])
if slope1 in memo:
memo[slope1] += 1
else:
memo[slope1] = 1
else:
same += 1
ret = max(ret, max(memo.values())+same)
return ret + 1
def slope(self, point1, point2):
return Decimal(point2.y - point1.y) / Decimal(point2.x - point1.x)
另:
一句话解释: 固定一点, 找其他点和这个点组成直线, 统计他们的斜率!
这里有一个重点: 求斜率.用两种方法
- 用最大约数方法(gcd), 把他化成最简形式, 3/6 == 2/4 == 1/2
- 除数(不太精确, 速度快!)
class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
from collections import Counter, defaultdict
# 所有点统计
points_dict = Counter(tuple(point) for point in points)
# 把唯一点列举出来
not_repeat_points = list(points_dict.keys())
n = len(not_repeat_points)
if n == 1: return points_dict[not_repeat_points[0]]
res = 0
# 求最大公约数
def gcd(x, y):
if y == 0:
return x
else:
return gcd(y, x % y)
for i in range(n - 1):
# 点1
x1, y1 = not_repeat_points[i][0], not_repeat_points[i][1]
# 斜率
slope = defaultdict(int)
for j in range(i + 1, n):
# 点2
x2, y2 = not_repeat_points[j][0], not_repeat_points[j][1]
dy, dx = y2 - y1, x2 - x1
# 方式一 利用公约数
g = gcd(dy, dx)
if g != 0:
dy //= g
dx //= g
slope["{}/{}".format(dy, dx)] += points_dict[not_repeat_points[j]]
# --------------------
# 方式二, 利用除法(不准确, 速度快)
# if dx == 0:
# tmp = "#"
# else:
# tmp = dy * 1000 / dx * 1000
# slope[tmp] += points_dict[not_repeat_points[j]]
#------------------------------
res = max(res, max(slope.values()) + points_dict[not_repeat_points[i]])
return res
查找表和滑动窗口
结合使用滑动窗口和查找表，不断查找当前滑动窗口内有没有重复的值。
存在重复元素 II
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。
示例 1:
输入: nums = [1,2,3,1], k = 3
输出: true
示例 2:
输入: nums = [1,0,1,1], k = 1
输出: true
示例 3:
输入: nums = [1,2,3,1,2,3], k = 2
输出: false
解答
- 遍历列表，每次都比对最小间隔，并更新哈希表索引，当前位置往左的最小间隔一定是与上一次同数字出现的索引的距离
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
r, d = k + 1, {}
for i, n in enumerate(nums):
r, d[n] = min(r, i - d.get(n, -k - 1)), i
return r <= k
官方解答
结合使用滑动窗口和查找表，不断查找当前滑动窗口内有没有重复值。我们通过建立一个 record 查找表，表中存的是窗口中的数，另外我们要注意的是，当窗口的大小 > k 的时候，我们要移除 record 中最左边的元素（保证我们窗口中有 <= k 个数）。
class Solution:
def containsNearbyDuplicate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
n = len(nums)
if (n <= 1):
return False
recode = set()
for i in range(n):
if nums[i] in recode:
return True
recode.add(nums[i])
if len(recode) > k:
recode.remove(nums[i - k])
return False
存在重复元素 III
给定一个整数数组，判断数组中是否有两个不同的索引 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值最大为 t，并且 i 和 j 之间的差的绝对值最大为 ķ。
示例 1:
输入: nums = [1,2,3,1], k = 3, t = 0
输出: true
示例 2:
输入: nums = [1,0,1,1], k = 1, t = 2
输出: true
示例 3:
输入: nums = [1,5,9,1,5,9], k = 2, t = 3
输出: false
解答
思想类似桶排序算法。假设我们有宽度为(t+1)的连续的桶可以覆盖掉所有的数字范围，那么对于差的绝对值最大为t的两个数，有两种情况：
- （1）这两个数字在同一个桶中
- （2）这两个数字在相邻桶中
def containsNearbyAlmostDuplicate(self, nums, k, t):
if t < 0: return False
n = len(nums)
d = {}
w = t + 1
for i in range(n):
m = nums[i] // w
if m in d:
return True
if m - 1 in d and abs(nums[i] - d[m - 1]) < w:
return True
if m + 1 in d and abs(nums[i] - d[m + 1]) < w:
return True
d[m] = nums[i]
if i >= k: del d[nums[i - k] // w]
return False
官方解答
也是查找表与滑动窗口的思路：维持滑动窗的大小最大为 k，遍历每一个元素 nums[i]，在活动窗口中寻找 |one-nums[i]| < t，即窗口中的元素范围为：[one-t … one+t] 之间。
class Solution:
def containsNearbyAlmostDuplicate(self, nums, k, t):
"""
:type nums: List[int]
:type k: int
:type t: int
:rtype: bool
"""
n = len(nums)
if n <= 1:
return False
recode = set()
for i in range(n):
if t == 0:
if nums[i] in recode:
return True
else:
for one in recode:
if abs(nums[i] - one) <= t:
return True
recode.add(nums[i])
if (len(recode) > k):
recode.remove(nums[i - k])
return False
总结
我们知道在准备面试的时候，刷算法题是一种捷径，特别是刷 LeetCode，但是不能一味的刷题，我们需要总结和思考，对于一些相似的题目我们应该多想想他们的思想，其实很多题的解题思路都是相近的。