亚马逊笔试补测20210831
亚马逊笔试补测20210831
定义
sum_free集合为：集合内任意两数之和不存在集合中（包括自身+自身）。给定整数N，代表集合S = {1,2,3,...,N}. 找出集合S中所有的sum_free_set，并把长度最长的sum_free_set的元素加在一起，作为输出。# 例 N = 3 S = {1,2,3} 子集：{}，{1}，{2}，{3}, {1,2}, {2,3}, {1,3}, {1,2,3} sum_free_set: {}，{1}，{2}，{3}, {2,3} {1,2}: 1+1=2 所以不是 sum_free_set {1,2,3}: 1+2=3 所以不是 sum_free_set 输出：{2,3} + {1,3} = 9思路：使用深度优先搜索（集合里每个数选或不选）。使用字典 d，key 为某个 sum_free_set 的长度，value 为长度为 x 的所有 sum_free_set 的和。在 dfs 的过程中，记录最大长度 maxx，搜索结束后返回 d[maxx].
定义
magic number: n为：某个product可以整除n^2。给定集合S={2,3,6}，计算集合的乘积product = 36，找出针对product的最小magic number: 2.
# 思路：构建字典 d，键为某个质因数，值为该质因数出现次数。对集合 S 里的每个数进行质因数分解，统计到字典 d 中。统计结束后，对 l = d.keys() 进行排序，然后遍历d[l[i]]，若次数>1，则输出l[i].
def find_prime_factors(n):
i = 2
prime_factors = []
while i * i <= n:
if n % i:
i += 1
else:
n //= i
prime_factors.append(i)
if n > 1:
prime_factors.append(n)
return prime_factors
def find_least_magic(nums):
from collections import defaultdict
d = defaultdict(int)
for n in nums:
for pf in find_prime_factors(n):
d[pf] += 1
keys = sorted(d.keys())
for k in keys:
if d[k] > 1:
return k- 根据依赖关系构建树，进行广度优先搜索（层序遍历），找出和最大的那一层，输出该和。
