2022.07.16 蔚来算法提前批笔试题

第一道题根据奇偶性，先求出所有的元素的质因数集合，则所有元素均是有这些质因数构成，计算所有质因数在元素中构成的数量，任意两个元素为完全平方数，则此质因数在所有的元素中出现的数量必须同为奇数或者偶数，假设K个偶数，那么就有N-K个奇数，K个偶数+1即为全部奇数，或者N-K个奇数-1为偶数，那么比较该质因数的min(K,N-K),然后对所有的质因数集求和即为最小操作数

楼主进面试了吗

我今天和你同一套题，第一题选客栈应该怎么写啊

楼主图像算法岗吗？

第一题的，根据楼上大哥的思路写出来的，大家看看有没有问题😑，还有感觉会超时。。。 def t1(ls):     dt = [{} for _ in range(len(ls))]     haset = set()     for i in range(len(ls)):         num = ls[i]         while num % 2 == 0:             dt[i][2] = dt[i].get(2, 0) + 1             num //= 2             haset.add(2)         j = 3         while j <= num**0.5:             if num % j == 0:                 dt[i][j] = dt[i].get(j, 0) + 1                 num //= j                 haset.add(j)             else:                 j += 2         if num > 3:             dt[i][num] = dt[i].get(num, 0) + 1             haset.add(num)     ans = 0     for num in haset:         odd, even = 0, 0         for dtt in dt:             if dtt.get(num, 0) % 2 == 0:                 even += 1             else:                 odd += 1         ans += min(even, odd)     return dt, ans if __name__ == '__main__&(688)#39;:     print(t1([1002, 98, 14, 68]))

一套题哎，想问下选择客栈那个题的优化思路，我只通过了60%，剩下超时了想看看更好的方法

第二题不就是计算一下快排移动的次数吗

第一题没想到 第二题可以抽象成求数组里的最长非递减子序列