python - 计算范围 (0,n] 中数字 'x' 的出现次数

Question

所以我正在尝试编写一个 python 函数，它接受两个参数 n 和 num，并计算 0 和 num 之间“n”的出现次数。例如，

countOccurrences(15,5) 应该是 2。

countOccurrences(100,5) 应该是 20。

我针对这个问题做了一个简单的迭代解决方案:

def countOccurrences(num,n):
  count=0
  for x in range(0,num+1):
    count += countHelper(str(x),n)
  return count

def countHelper(number,n):
  count=0
  for digit in number:
    if digit==n:
      count += 1
  return count

如果我尝试调用 countOccurrences(100000000000,5)，就会遇到明显的问题。我的问题是如何提高效率？我希望能够“相当”快速地处理问题，并避免出现内存不足错误。这是我尝试执行此操作的递归解决方案的第一次传递:

def countOccurence(num, n):
  if num[0]==n:
    return 1
  else:
    if len(num) > 1:
      return countOccurence(num[1:],n) + countOccurence(str((int(num)-1)),n)
    else:
      return 0

Answer 1

这不会遇到任何内存问题，直到 max_num 足够小以适应 C long。基本上它仍然是一种蛮力算法，尽管针对 Python 进行了显着优化。

def count_digit(max_num, digit):
    str_digit = str(digit)
    return sum(str(num).count(str_digit) for num in xrange(max_num+1))