华为德科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#
全部评论
这要是不知道素数是啥,咋办
1
送花
回复 分享
发布于 2022-06-27 20:25
楼主yyds,借楼谢谢! 深圳急聘华为OD:10+2起步(211以上+2),一本以上私聊。拿到offer的同学帮点赞。 另资源互换捞人私聊。
点赞
送花
回复 分享
发布于 2022-07-22 16:52
京东
校招火热招聘中
官网直投

相关推荐

5 27 评论
分享
牛客网
牛客企业服务