我一直在研究 GeeksforGeeks 的排列问题。这是挑战的链接:http://www.practice.geeksforgeeks.org/problem-page.php?pid=702
挑战是获取一组数字,并针对这些数字以 2 或 3 为一组的每种可能顺序,检查数字之和是否能被 3 整除。在程序结束时打印出能被 3 整除的组数。
一个例子是... int[] array = {1, 2, 3} 应该打印出 8。
下面是我用于此挑战的代码。该代码可以工作,但速度很慢。运行时间需要低于 1.272 秒,那么我怎样才能使这段代码更快呢?或者避免执行这么多行?
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++;
}
}
}
最佳答案
您的代码创建了许多不必要的对象。
首先,不需要计数器类,您可以轻松地保留符合要求的组数的 int 计数器。
计算总和是否可以被 3 整除时,您不需要遍历数字,只需检查(对于 int n
):if (n % 3 == 0) { ...
您正在创建字符串,然后将整数转换为字符串,然后再返回,这是不必要的。只需将命令行中的整数读入一个 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--;
}
最后,递归将比简单的 for 循环迭代慢。我个人也不认为递归会使解决方案更清晰。
我将这些建议组合成了一个快速简单的解决方案,运行只需要大约 1/2 秒。
关于Java 排列挑战很慢,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39239047/