為什么在查找數字階乘的遞回解決方案中存在堆疊溢位錯誤？-有解無憂

我正在解決LeetCode #172：

給定一個整數 n，回傳 n 中尾隨零的數量！

約束：

0 <= n <= 10⁴

我的代碼找到了n的答案！首先，然后計算尾隨零的數量。但是，運行代碼會引發堆疊溢位例外，我一生都無法弄清楚原因。

這是代碼：

class Solution {
    public int trailingZeroes(int n){ 
        int fact = findFactorial(n);   // 120
        int ans = 0;
        
        // how many zeroes does fact have? 
        String ansString = Integer.toString(fact);
    
        // edge - if string is only one character long
        if (ansString.length()==1) {
          return 0;  
        } 
        
        // loop from the end counting the continuous zeroes
        for (int i= ansString.length()-1 ; i > 0; i--){
            Character cha = ansString.charAt(i);
            
            if (cha.equals('0')) {
                ans  ;
            }
            else {
                break;
            }
        }
        
        return ans;
    }
    
    public int findFactorial(int n){
        // base case
        if (n==1) return 1;
        
        // reduct towards base case
        else {
            int f = n * findFactorial(n-1);
            return f;
        }
    }

}

uj5u.com熱心網友回復：

你說：

給定一個整數 n，回傳 n 中尾隨零的數量！

約束：

0 <= n <= 10 ⁴

首先，您的解決方案將不起作用，因為int無法容納那么大的數字。您需要BigInteger按如下所示使用。

下面的遞回形式將計算10 ⁴ ! 沒有太多明顯的延遲。

public static BigInteger factorial(int n) {
     if (n == 1 || n == 0) {
         return BigInteger.ONE;
     }
     return factorial(n-1).multiply(BigInteger.valueOf(n));
}
String fact = factorial(1000).toString();
System.out.println(fact.replaceAll("\\d ?(0*)$", "$1").length());

印刷

但是您不需要計算階乘來解決實際問題。考慮以下。

所有數字的乘積1 to N必須有 10 的除數（即 2 和 5）。5 將出現的次數最少，因此這是您需要關注的地方。尾隨零的數量等于的次數10 divides N。并且由于5可能將給定項除以多次（例如 25 和 125），因此您還需要更新除數。

int n = 1000; // factorial candidate
int sum = 0;
int k;
for (int d = 5; (k = n/d) > 0; d*=5) {
       sum  = k;
}
System.out.printf("%d! has %d trailing zeros", n, sum);

印刷

1000! has 249 trailing zeros

這是遞回解決方案（雖然效率不高）。

public static int trailingZeros (int n) {
    if (n > 0) {
        return trailingZeros(n/5)   n/5;
    }
    return 0;
}

uj5u.com熱心網友回復：

出現堆疊溢位錯誤的原因是在使用計算階乘時使用了遞回findFactorial。將其更改為使用回圈而不是遞回，如下所示Find factorial of large numbers in Java。因此你的方法findFactorial變成：

BigInteger findFactorial(int n) {
    BigInteger fact = BigInteger.valueOf(1);
    for (int i = 2; i <= n; i  )
        fact = fact.multiply(BigInteger.valueOf(i));
    return fact;
}

然后在您呼叫的方法中findFactorial更改行：

int fact = findFactorial(n);
String ansString = Integer.toString(fact);

到

BigInteger fact = findFactorial(n);
String ansString = BigInteger.toString(fact);

uj5u.com熱心網友回復：

這是使用 for 回圈的簡單方法，

your_number在運行此代碼之前將的值更改為任何數字。

public static void main(String[] args) {
            String factorial = findFactorial(new BigInteger("your_number")).toString();
            char[] factorialArray = factorial.toCharArray();
            int numberOfZeros = 0;
    
            for (int i = factorialArray.length - 1; i >= 0; i--) {
                if(factorialArray[i] == '0') {
                    numberOfZeros  ;
                }
                else {
                    break;
                }
            }
    
            System.out.println(numberOfZeros);
        }
    
        static BigInteger fact = new BigInteger("1");
    
        static BigInteger findFactorial(BigInteger integer) {
            for (int i = 1; i <= integer.intValueExact(); i  ) {
                fact = fact.multiply(BigInteger.valueOf(i));
            }
    
            return fact;
        }

uj5u.com熱心網友回復：

使用我機器上 JVM 的默認堆疊大小正確構造的遞回實作將至少作業到 9000！（好像到了9119！）之前有一個堆疊溢位。所以 10000 限制可能是明確選擇來觸發這個問題的，所以你會想到一個非遞回實作。

在這里，我實作了回圈和遞回。

import java.math.BigInteger;

public class BigFactorial {
    public static void main(String[] args) {
        printResult(120, factorialLoop(120));
        printResult(120, factorialRecursive(120));
    }

    static BigInteger factorialLoop(int n) {
        BigInteger f = BigInteger.ONE;
        for (int i = 2; i <= n; i  ) {
            f = f.multiply(BigInteger.valueOf(i));
        }
        return f;
    }
    
     static BigInteger factorialRecursive(int n) {
        if (n == 1)
            return BigInteger.ONE;
        return BigInteger.valueOf(n).multiply(factorialRecursive(n-1));
    }

    static void printResult(int n, BigInteger f) {
        System.out.println(n   "! = "   f);
        String fStr = f.toString();
        int len = fStr.length();
        for (int i = len - 1; i >= 0; i--) {
            if (fStr.charAt(i) != '0') {
                System.out.println("There are "   (len - 1 - i)   " trailing zeros.");
                break;
            }
        }

    }
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/403068.html

標籤：

上一篇：Python：找到最短的數字串列，添加時將是特定數字

下一篇：如何跟蹤遞回函式被呼叫的次數