归零问题 - 出现超时错误

Question

正在尝试解决 hackerrank problem。

你有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)

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)

Answer 2

或者，有一个 O(n*sqrt(n)) 时间和 O(n) space 复杂度的解决方案可以很好地通过所有测试用例。

想法是缓存每个非负整数的最小计数，直到 1,000,000（问题中的最大可能输入数）！！！之前！！！ 运行任意查询。这样做之后，对于每个查询，只需 return 缓存中存储的给定数字的最小计数。因此，检索结果每个查询的时间复杂度为 O(1)。

要找到每个数字的最小计数（我们称之为 down2ZeroCounts），我们应该考虑几种情况：

0 和 1 相应地具有 0 和 1 最小计数。
质数 p 除了 1 和它本身之外没有其他因子。因此，它的最小计数是 1 加上最小计数 p - 1 或更正式的 down2ZeroCounts[p] = down2ZeroCounts[p - 1] + 1。
对于合数 num 有点复杂。对于任何一对 a > 1,b > 1 使得 num = a*b 的最小计数 num 是 down2ZeroCounts[a] + 1 或 down2ZeroCounts[b] + 1 或 down2ZeroCounts[num - 1] + 1。

因此，我们可以逐渐为每个数字按升序构建最小计数。计算每个后续数字的最小计数将基于较低数字的最佳计数，因此最终将构建最佳计数列表。

为了更好地理解该方法，请查看代码：

from __future__ import print_function

import os
import sys

maxNumber = 1000000
down2ZeroCounts = [None] * 1000001

def cacheDown2ZeroCounts():
    down2ZeroCounts[0] = 0
    down2ZeroCounts[1] = 1

    currentNum = 2
    while currentNum <= maxNumber:
        if down2ZeroCounts[currentNum] is None:
            down2ZeroCounts[currentNum] = down2ZeroCounts[currentNum - 1] + 1
        else:
            down2ZeroCounts[currentNum] = min(down2ZeroCounts[currentNum - 1] + 1, down2ZeroCounts[currentNum])

        for i in xrange(2, currentNum + 1):
            product = i * currentNum
            if product > maxNumber:
                break
            elif down2ZeroCounts[product] is not None:
                down2ZeroCounts[product] = min(down2ZeroCounts[product], down2ZeroCounts[currentNum] + 1)
            else:
                down2ZeroCounts[product] = down2ZeroCounts[currentNum] + 1    

        currentNum += 1

def downToZero(n):
    return down2ZeroCounts[n]

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    q = int(raw_input())

    cacheDown2ZeroCounts()
    for q_itr in xrange(q):
        n = int(raw_input())

        result = downToZero(n)

        fptr.write(str(result) + '\n')

    fptr.close()

归零问题 - 出现超时错误

Down to zero problem - getting time exceeded error

python

algorithm

optimization

breadth-first-search

factors

清除数组比清除集合慢

正在执行不必要的循环

更快的代码