Java排列挑戰是緩慢的

Question

我一直在研究GeeksforGeeks的排列問題。這裏是挑戰的鏈接：http://www.practice.geeksforgeeks.org/problem-page.php?pid=702

挑戰是採取一系列的數字和這些數字的每個可能的順序在2或3的組中，檢查數字的總和是否可以被3整除。的節目的結束打印出一個例子是，通過3

整除組的數量... INT []數組= {1，2，3}應該打印出8.

以下是我用於這個挑戰的代碼。代碼有效，但速度很慢。運行時需要低於1.272s，所以我怎樣才能使這個代碼更快？或者保存它執行很多行？

public static void PG2(int[] array, int l, int r, Counter count){ 
     int newR = r - 1; 
     int i; 
     if(l == 2){ 
      String number = String.valueOf(array[0]); 
      String number2 = String.valueOf(array[1]); 
      number = number.concat(number2); 
      int aNumber = Integer.parseInt(number); 
      count.divBy3(aNumber); 
     } else { 
      int temp; 
      int temp2; 
      for(i = l; i < r; i++){ 
       temp = array[l]; 
       array[l] = array[i]; 
       array[i] = temp; 
       PG2(array, l+1, r, count); 
       temp2 = array[l]; 
       array[l] = array[i]; 
       array[i] = temp2; 
      } 
     } 
    } 

    public static void PG3(int[] array, int l, int r, Counter count){ 
     int newR = r - 1; 
     int i; 
     if(l == 3){ 
      String number = String.valueOf(array[0]); 
      String number2 = String.valueOf(array[1]); 
      String number3 = String.valueOf(array[2]); 
      number = number.concat(number2); 
      number = number.concat(number3); 
      int aNumber = Integer.parseInt(number); 
      count.divBy3(aNumber); 
     } else { 
      int temp; 
      int temp2; 
      for(i = l; i < r; i++){ 
       temp = array[l]; 
       array[l] = array[i]; 
       array[i] = temp; 
       PG3(array, l+1, r, count); 
       temp2 = array[l]; 
       array[l] = array[i]; 
       array[i] = temp2; 
      } 
     } 
    } 




    public static void main(String[] args) throws Exception { 
     BufferedReader input = new BufferedReader(new InputStreamReader(System.in)); 

     String t = input.readLine(); 
     int T = Integer.parseInt(t); 

     while(T > 0){ 
      String arrayS = input.readLine(); 
      int ArrayS = Integer.parseInt(arrayS); 

      int[] newArray = new int[ArrayS]; 

      String arrayElements = input.readLine(); 
      String[] ArrayElements = arrayElements.trim().split("\\s+"); 
      for(int i = 0; i < ArrayS; i++){ 
       int num = Integer.parseInt(ArrayElements[i]); 
       newArray[i] = num; 
      } 
      int total = 0; 
      Counter count = new Counter(); 
      PG2(newArray, 0, ArrayS, count); 
      PG3(newArray, 0, ArrayS, count); 

      System.out.println(count.counter); 
      T--; 
     } 
    } 

這裏是計數器類：

public class Counter { 
    public int counter; 

    public void divBy3(int number){ 
     int total = 0; 
     while(number > 0){ 
      total += number % 10; 
      number = number/10; 
     } 

     if(total % 3 == 0){ 
      this.counter++; 
     } 
    } 


} 

Answer 1

您的代碼創建了很多不必要的對象。

首先，計數器類是不需要的，你可以很容易地保持一個int計數器的符合要求的組數。

當計算，如果總和是被3整除你不需要去通過數字，只需檢查（類型爲int的n）：if (n % 3 == 0) { ...

你正在創建的字符串，然後轉換到整數字符串和回再次不必要。只需從命令行讀入int，並將其用於int數組。

// a main method that reads in ints and then keeps them as such 
Scanner in = new Scanner(System.in); 
int t = in.nextInt(); 
while (t > 0) { 
    int n = in.nextInt(); 
    int[] arr = new int[n]; 
    for (int i = 0; i < n; i++) { 
     arr[i] = in.nextInt(); 
    } 
    int count = countGroupsOfTwo(arr); 
    count += countGroupsOfThree(arr); 
    System.out.println(count); 
    t--; 
} 

最後，遞歸會比簡單的循環迭代慢。我個人認爲遞歸也使得解決方案更清潔。

我把這些建議扔進了一個快速天真的解決方案，它只需要大約1/2秒的時間來運行。