蔚来 2022 07 27 算法岗笔试算法题

def binary_search(left, right, valid_idx):
     # valid_idx is ascending list 
    
    if left > valid_idx[-1] or right < valid_idx[-1] : return False
    
    l,r = 0, len(valid_idx) -1 
    while l < r:
        mid = (l + r) >> 1
        if valid_idx[mid] < left:
            l = mid + 1
        else:
            r = mid 
    if valid_idx[l] <= right:
        return True
    return False

2.题目：  给定一个数组 对数组里面的数进行操作, 操作是乘一个质数, 要求最少操作多少次, 能够使得数组任何两个元素相乘为完全平方数?（数据范围3*10^5 复杂度应该在nlogn到n2之间，单个数的范围是在10^5到10^9之间）

思路是：将任何一个数拆开为质数相乘，统计每个数的质数个数和种类即可。