hackerearth 练习超过时间限制

Question

我正在尝试在 HackerEarth 中解决 this exercise。但是我有time limit exceeded的错误。这是我写的代码：

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class TestClass {
    //gcd 
    public static long gcd(long num1, long num2) {
        if (num2 != 0) {
            return gcd(num2, num1 % num2);
        } else {
            return num1;
        }
    }

    public static void main(String args[] ) throws Exception {
        //BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); // Reading input from STDIN
        while (T-- > 0) {
            StringTokenizer st1 = new StringTokenizer(br.readLine());
            long a = Long.parseLong(st1.nextToken());
            long b = Long.parseLong(st1.nextToken());
            long A = a/gcd(a,b);
            long B = b/gcd(a,b);
            System.out.printf("%d%1s%d%n",B,"",A);
        }
    }
}

Answer 1

由于实施不当，您的解决方案有点慢。我使用与您的解决方案相同的逻辑和时间复杂度重写了您的解决方案以更好地实现，并获得 Accepted 和 none 的测试用例超出 .8 秒

import java.util.*;
 
class TestClass {
    // Same gcd function but it's better code :)
    public static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);   
    }
 
    public static void main(String args[] ) throws Exception {
        Scanner s = new Scanner(System.in);
        int t = s.nextInt();  // this way of reading input is faster alot.
        while(t-- > 0) {
            int a = s.nextInt();  
            int b = s.nextInt();  // No need to use long it's  just 1e9

            int tmp = gcd(a, b);  // It's better to save the value of the gcd(a, b) instead of calculate it twice. 

            int A = a/tmp;
            int B = b/tmp;
            System.out.println(B+" "+A);
        }
    }
}

hackerearth 练习超过时间限制

Time limit exceeded in hackerearth exercise

java

algorithm