试图解决hackerrank问题。
您将获得Q查询。每个查询由单个数字N组成。您可以在每个移动中对N执行2个操作。如果N = a×b(a≠1,b≠1),我们可以更改N = max(a,b)或将N的值减小1。确定将N的值减小到的最小移动次数。 0。
我已经使用BFS方法来解决此问题。
一种。使用seive生成所有素数
b。使用质数,我可以避免计算因子
C。我将-1和所有因素都排队入零。
d。我还使用了先前的结果来不使遇到的数据入队。
这仍然给了我时间。任何的想法?在代码中也添加了注释。
import math
#find out all the prime numbers
primes = [1]*(1000000+1)
primes[0] = 0
primes[1] = 0
for i in range(2, 1000000+1):
if primes[i] == 1:
j = 2
while i*j < 1000000:
primes[i*j] = 0
j += 1
n = int(input())
for i in range(n):
memoize= [-1 for i in range(1000000)]
count = 0
n = int(input())
queue = []
queue.append((n, count))
while len(queue):
data, count = queue.pop(0)
if data <= 1:
count += 1
break
#if it is a prime number then just enqueue -1
if primes[data] == 1 and memoize[data-1] == -1:
queue.append((data-1, count+1))
memoize[data-1] = 1
continue
#enqueue -1 along with all the factors
queue.append((data-1, count+1))
sqr = int(math.sqrt(data))
for i in range(sqr, 1, -1):
if data%i == 0:
div = max(int(data/i), i)
if memoize[div] == -1:
memoize[div] = 1
queue.append((div, count+1))
print(count)
此代码有两个导致速度缓慢的主要原因。
第一个问题是这一行:
memoize= [-1 for i in range(1000000)]
这将准备一百万个整数,并针对您的1000个测试用例中的每一个执行。一种更快的方法是简单地使用Python集来指示已经访问了哪些值。
第二个问题是这一行:
if primes[data] == 1 and memoize[data-1] == -1:
如果您有素数,并且已经访问过该数字,则实际上是在慢循环中搜索素数因数,因为它永远找不到任何解(因为它是素数)。
实际上,由于使用了集合而带来的改进是如此之大,以至于您甚至不需要您的主要测试代码,并且以下代码在时限内通过了所有测试:
import math
n = int(input())
for i in range(n):
memoize = set()
count = 0
n = int(input())
queue = []
queue.append((n, count))
while len(queue):
data, count = queue.pop(0)
if data <= 1:
if data==1:
count += 1
break
if data-1 not in memoize:
memoize.add(data-1)
queue.append((data-1, count+1))
sqr = int(math.sqrt(data))
for i in range(sqr, 1, -1):
if data%i == 0:
div = max(int(data/i), i)
if div not in memoize:
memoize.add(div)
queue.append((div, count+1))
print(count)
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句