华为德科OD笔试
素数之积
给定一个整数
,求该数是否为两素数之积。
一开始我试图用筛选法打表把所有素数打出来,因为我觉得直接暴力枚举并检测素数肯定会超时。结果发现光是打出来的表就直接爆内存了(
因为两个因子必定一个是小于等于 ,另一个大于等于
, 于是就把打表范围降到
,表长度
。
然后在表中枚举小于等于 的因子,判断另一个因子是否素数。
判断另外一个因子是否素数时也可以利用打表信息,当该因子小于等于 是可以利用二分法直接查找是否在表中。
大于 时,记该因子为
,因为
,所以
,因此可枚举表中
判断是否包含
的因子,没有则为素数。
因此最坏时间复杂度为 。
其实后来想了想,枚举 的因子需要
,检测该因子是否素数需要
,整体时间其实也是
。
实际测试 时打表大概 2ms,枚举 10ms,完全不会超时。
n = int(input()) #### 打表 #### import bisect primes = [...] #表略 sqrt = n ** 0.5 for p in primes: if p > sqrt: print(-1, -1) break if n % p == 0: div = n // p if div <= primes[-1]: if primes[bisect.bisect_left(primes, div)] == div: print(p, div) break else: is_prime = True sqrt2 = div ** 0.5 for p2 in primes: if p2 > sqrt2: break if div % p2 == 0: is_prime = False break if is_prime: print(p, div) break else: print(-1, -1) #### 枚举 #### def is_prime(n): if n == 1: return False for i in range(2, int(n ** 0.5) + 1): if n % i == 0: return False return True for i in range(2, int(n ** 0.5) + 1): if n % i == 0: if is_prime(i) and is_prime(n // i): print(i, n // i) break else: print(-1, -1)
工厂流水线
给定
条流水线与
个作业,每个作业的作业时间
。流水线总是优先选取作业时间最短的作业进行工作。求总工作时长。
堆就完事了。不过输入数据巨坑, 的数量会多于
,卡了我半天。
import heapq m, n = map(int, input().split()) t = list(map(int, input().split()))[:n] t.sort() h = t[:m] heapq.heapify(h) for i in range(m, n): heapq.heapreplace(h, h[0] + t[i]) print(max(h))
完全波形信号
给定一个由 0 和 1 组成的字符串。一个信号定义为由 0 开头和结尾,中间不会有连续两个 0 的一个子串。求输入中最长的 0、1 交替的波形信号。
直接正则替换,能一行解决的绝对不写第二行(
import re s = '0' + input() + '0' waves = re.sub(r'0{2,}', '0|0', s).split('|')[1:-1] ans = '' for w in waves: if all(w[i] != w[i + 1] for i in range(len(w) - 1)): ans = max(ans, w, key=len) print(ans or -1)#华为笔试##外企德科人力资源服务##华为OD#