python - 归零问题 - 获取时间超出错误

Question

尝试解决 hackerrank problem .

您收到了 Q 个查询。每个查询由一个数字 N 组成。每次移动可以对 N 执行 2 次操作。如果N=a×b(a≠1,b≠1)，我们可以改变N=max(a,b)或者将N的值减少1。 确定将 N 的值减小到 0 所需的最小移动次数。

我使用BFS方法来解决这个问题。

a.使用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)

Answer 1

这段代码速度缓慢有两个主要原因。

清除数组比清除集合慢

第一个问题是这一行:

memoize= [-1 for i in range(1000000)]

这会准备 100 万个整数，并针对 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)