如何在不使多线程的情况下使速度更快？

Question

我的程序在输出方面工作正常，但对于我的一些测试用例来说，找到答案需要很长时间（有时需要18秒）。我想知道如何改善我的代码的性能。我的代码是： 这是Pebble Solitaire。用户输入n个游戏，然后输入长度为23的字符串，其中只包含'o'（鹅卵石）和' - '（空白空间）的组合。如果有两个相邻的鹅卵石和任何一边有空的空间，即（oo-或-oo），则移除中间的鹅卵石，并将另外两块彼此交换，如果“oo-”变成“ O”。

我目前的做法几乎是一个详尽的方法，它尝试每一个可能的举措，并结果移动设置与剩下的卵石数量最少。

我想知道如何改进这个解决方案，而不使它成为多线程。

以下是我有：

package Pebble; 

import java.util.Scanner; 

public class PebbleSolitaire { 

    public static void main(String[] args){ 

     Scanner input = new Scanner(System.in); 
     int numOfGames = Integer.parseInt(input.nextLine()); 

     while (numOfGames > 0){ 

      char[] values = input.nextLine().toCharArray(); 
      long startTime = System.nanoTime(); 
      System.out.println(solve(values)); 
      System.out.println("Time to finish in ms: " + (System.nanoTime() - startTime)/1000000); 
      numOfGames--; 
     } 
     input.close(); 
    } 

    private static int solve(char[] game){ 

     if(game != null && game.length == 0){ 
      return -1; 
     } 

     int result = 0; 

     for (int i = 0; i < game.length; i++){ 
      if(game[i] == 'o'){ 
       result++; 
      } 
     } 

     //print(game); 

     for (int i = 0; i < game.length; i++){ 

      char[] temp = new char[game.length]; 
      copyArray(temp, game); 

      if (i-2 >= 0 && temp[i] == '-' && temp[i-2] == 'o' && temp[i-1] == 'o'){//move pebble forwards 
       temp[i-1] = temp[i-2] = '-'; 
       temp[i] = 'o'; 
       result = Math.min(result, solve(temp)); 
      } 

      copyArray(temp, game); 

      if(i+2 < temp.length && temp[i] == '-' && temp[i+1] == 'o' && temp[i+2] == 'o'){//move pebble backwards 
       temp[i+1] = temp[i+2] = '-'; 
       temp[i] = 'o'; 
       result = Math.min(result, solve(temp)); 
      } 
     } 
     return result; 
    } 

    private static void copyArray(char[] copy, char[] og){ 
     for(int x = 0; x < copy.length; x++){ 
      copy[x] = og[x]; 
     } 
    } 
    private static void print(char[] c){ 
     for(char ch: c){ 
      System.out.print(ch); 
     } 
     System.out.println(); 
    } 
} 

我的样品输入和输出：

2 
-o----ooo----o----ooo-- 
6 
Time to finish in ms: 0 
oooooooooo-ooooooooooo- 
4 
Time to finish in ms: 18149 

编辑：会使得这种完全迭代大大提高性能？

Answer 1

也许你可以改善这种单方面：

for (int i = 0; i < game.length; i++){ 

     char[] temp = new char[game.length]; 
     copyArray(temp, game); 

     if (i-2 >= 0 && temp[i] == '-' && temp[i-2] == 'o' && temp[i-1] == 'o'){//move pebble forwards 
      temp[i-1] = temp[i-2] = '-'; 
      temp[i] = 'o'; 
      result = Math.min(result, solve(temp)); 
     } 

     copyArray(temp, game); 

     if(i+2 < temp.length && temp[i] == '-' && temp[i+1] == 'o' && temp[i+2] == 'o'){//move pebble backwards 
      temp[i+1] = temp[i+2] = '-'; 
      temp[i] = 'o'; 
      result = Math.min(result, solve(temp)); 
     } 
    } 

到：

for (int i = 0; i < game.length; i++){ 
     char[] temp = null; 

     if (i-2 >= 0 && game[i] == '-' && game[i-2] == 'o' && game[i-1] == 'o'){//move pebble forwards 
      temp = new char[game.length]; 
      copyArray(temp, game); 
      temp[i-1] = temp[i-2] = '-'; 
      temp[i] = 'o'; 
      result = Math.min(result, solve(temp)); 
     } 



     if(i+2 < game.length && game[i] == '-' && game[i+1] == 'o' && game[i+2] == 'o'){//move pebble backwards 

      if(temp == null) temp = new char[game.length];    

      copyArray(temp, game); 
      temp[i+1] = temp[i+2] = '-'; 
      temp[i] = 'o'; 
      result = Math.min(result, solve(temp)); 
     } 
    } 

基本上，只有创建和 “copyArray（温度，游戏）;”当严格需要时。