亚马逊笔试补测20210831

1. 定义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].

2. 定义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

3. 根据依赖关系构建树，进行广度优先搜索（层序遍历），找出和最大的那一层，输出该和。