如果我正在以一种有效的方式找到一个大数的阶乘,而我却得到了一个tle,我该怎么办?

vsikbqxv  于 2021-06-30  发布在  Java
关注(0)|答案(3)|浏览(309)

问题:超长阶乘(https://www.hackerrank.com/challenges/extra-long-factorials/problem)约束:1<n<=100
我在做一个有效的方式,加上它的解决方案在网上仍然可用,当我提交代码,它的tle。下面是我的代码

  1. public static void multiply(ArrayList<Integer> prod,int i)
  2. {
  3. int carry=0;
  4. for(int j=0;j<prod.size();j++)
  5. {
  6. int currp=prod.get(j)*i+carry;
  7. prod.add(j,currp%10);
  8. carry=currp/10;
  9. }
  10. while(carry>0)
  11. {
  12. prod.add(carry%10);
  13. carry/=10;
  14. }
  15. }
  16. // Complete the extraLongFactorials function below.
  17. static void extraLongFactorials(int n) {
  18. ArrayList<Integer> prod= new ArrayList<>();
  19. prod.add(1);
  20. for(int i=2;i<n;i++)
  21. multiply(prod,i);
  22. for(int i=prod.size()-1;i>=0;i--)
  23. System.out.print(prod.get(i));
  24. System.out.println();
  25. }
gr8qqesn

gr8qqesn1#

所以我在代码中犯了两个错误。现在我的代码被提交了。下面是正确的代码-

  1. public static void multiply(ArrayList<Integer> prod,int i)
  2. {
  3. int carry=0;
  4. for(int j=0;j<prod.size();j++)
  5. {
  6. int currp=prod.get(j)*i+carry;
  7. prod.set(j,currp%10);
  8. carry=currp/10;
  9. }
  10. while(carry>0)
  11. {
  12. prod.add(carry%10);
  13. carry/=10;
  14. }
  15. }
  16. // Complete the extraLongFactorials function below.
  17. static void extraLongFactorials(int n) {
  18. ArrayList<Integer> prod= new ArrayList<>();
  19. prod.add(1);
  20. for(int i=1;i<=n;i++)
  21. multiply(prod,i);
  22. for(int i=prod.size()-1;i>=0;i--)
  23. System.out.print(prod.get(i));
  24. System.out.println();
  25. }
展开查看全部
jvlzgdj9

jvlzgdj92#

java有提供任意精度的内置类。使用 BigInteger.valueOf(long) 以及 BigInteger.multiply(BigInteger) 喜欢

  1. static void extraLongFactorials(int n) {
  2. BigInteger v = BigInteger.valueOf(n);
  3. while (--n > 0) {
  4. v = v.multiply(BigInteger.valueOf(n));
  5. }
  6. System.out.println(v);
  7. }
d4so4syb

d4so4syb3#

你的代码有一些严重的错误。
我测试了将其粘贴到类中并添加一个main方法:

  1. public static void main(String[] args) {
  2. for (int i = 1; i <= 10; i++) {
  3. extraLongFactorials(i);
  4. }
  5. }

您的代码将为 1 .
您的代码返回“1”作为 2 ,这是错误的(应该是“2”)
您的代码无法计算 3 -它从不停止
我故意不纠正你的错误-试着自己去发现并修复它们(使用调试器)。
好消息是:代码中有两个bug。修正这些,你的代码就会通过测试。

相关问题