Số lần xuất hiện của chữ số 'x' trong phạm vi (0, n]

Question

Vì vậy, tôi đang cố gắng viết hàm python có hai đối số, n và num, và đếm số lần xuất hiện của 'n' giữa 0 và num. Ví dụ,

countOccurrences(15,5) nên 2

countOccurrences(100,5) nên 20

tôi đã thực hiện một giải pháp lặp đi lặp lại đơn giản cho vấn đề này:..

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 

Điều này gặp phải các vấn đề rõ ràng nếu tôi cố gắng gọi countOccurrences(100000000000,5). Câu hỏi của tôi là làm thế nào tôi có thể làm cho điều này hiệu quả hơn? Tôi muốn có thể xử lý vấn đề "khá" nhanh chóng, và tránh các lỗi bộ nhớ. Đây là đèo đầu tiên của tôi tại một giải pháp đệ quy cố gắng thực hiện điều này:

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

Tôi đã sửa giải pháp của mình và hy vọng nó phù hợp với thông số kỹ thuật của bạn. Hãy xem qua hàm trợ giúp đầu tiên:

def splitNumber(num): 
    temp = str(number) 
    nums = list(temp) 
    return nums 

Chức năng này tạo danh sách chuỗi tất cả các số riêng lẻ trong đầu vào số. Ví dụ,

splitNumber(100) 

sẽ trở lại:

['1', '0', '0'] 

Từ đây, bạn gọi hàm chính và kiểm tra mỗi số cá nhân với chức năng chính sau:

def countOccurences(num, n): 
    count = 0 
    for x in range(0, (num + 1)): 
     temp = splitNumber(x) 
     for x in range(len(temp)): 
      if (temp[x] == str(n)): 
       count = count + 1 
    return count 

nào nên cho mong muốn đầu ra. Hãy cho tôi biết, nếu việc này giúp ích cho bạn!

Answer 2

Điều này sẽ không ảnh hưởng đến bất kỳ vấn đề nào về bộ nhớ, cho đến khi max_num đủ nhỏ để vừa với C long. Về cơ bản nó vẫn là một thuật toán brute-force, mặc dù được tối ưu hóa đáng kể cho 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))