2017-05-23 42 views
0

任務:查找包含N個開放括號和N個右括號的常規括號表達式的數量。 N是從鍵盤輸入的。無法理解「括號對組合」算法?

我發現這個算法解決並試圖理解它。

public static void addParen(ArrayList<String> list, int leftRem, int rightRem, char[] str, int count) { 
    if (leftRem < 0 || rightRem < leftRem) return; // some state 

    if (leftRem == 0 && rightRem == 0) { /* no additional left parentheses */ 
     String s = String.copyValueOf(str); 
     list.add(s); 
    } else { 
     /* Add left parenthesis if there are parentheses of any kind */ 
     if (leftRem > 0) { 
      str[count] = '('; 
      addParen(list, leftRem - 1, rightRem, str, count + 1); 
     } 

     /* Add a right parenthesis if the expression is true */ 
     if (rightRem > leftRem) { 
      str[count] = ')'; 
      addParen(list, leftRem, rightRem - 1, str, count + 1); 
     } 
    } 
} 
public static ArrayList<String> generateParens(int count) { 
    char[] str = new char[count * 2]; 
    ArrayList<String> list = new ArrayList<String>(); 
    addParen(list, count, count, str, 0); 
    return list; 
} 

但它能做只有第一個結果字符串: ((()))

它是如何工作的延續?我們如何得到其他括號? 也許你可以提出編程這個任務的其他版本?

如果count = 3,結果:

((())) 
(()()) 
(())() 
()(()) 
()()() 
+0

請讓我們知道什麼樣的結果的算法,預計將產生。 – dasblinkenlight

+1

什麼是*任務*? – SHG

+0

iuliq我也迷失在方括號內;(:D – strash

回答

0

請注意,你的任務是計算括號內的有效序列,而不是將它們輸出。因此,讓我們覺得有多少變種,使長度N(對)的有效序列(表示其S(N)):

You can get any valid sequence of length N-1 and add() pair after it 
You can get any valid sequence of length N-2 and add opening parenthesis, 
valid sequence of length 1, and closing parenthesis 
... 
You can get any valid sequence of length N-1-M and add opening parenthesis, 
any valid sequence of length M, and closing parenthesis 
... 
You can make opening parenthesis, add any valid sequence of length N-1, 
and closing parenthesis 

所以,總體來說配方:

S(N) = Sum[S(N-M-1)*S(M)] for M=0..N-1 (with S(0)=1) 

只需填寫陣列/列表從較小的值到較大的值。

例子:

S(3) = S(2)*S(0)+S(1)*S(1)+S(0)*S(2)=2+1+2=5 

需要注意的是簡潔的公式確實存在,但我認爲你的老師希望有一些合乎邏輯的結論的解決方案

+0

謝謝你明確的答案! –

0

嗯,肯定的一個流行的任務編程類:)你會發現很多的解決方案在網絡上的多語言,如the one below。其實這個很醜。也許你挖掘到它,並拿出一些愛撫編碼器的心臟在更大程度上:)

public static List<String> generateParenthesis(int n) { 
    ArrayList<String> result = new ArrayList<>(); 
    ArrayList<Integer> diff = new ArrayList<>(); 
    result.add(""); 
    diff.add(0); 
    for (int i = 0; i < 2 * n; i++) { 
     ArrayList<String> temp1 = new ArrayList<>(); 
     ArrayList<Integer> temp2 = new ArrayList<>(); 
     for (int j = 0; j < result.size(); j++) { 
      String s = result.get(j); 
      int k = diff.get(j); 

      if (i < 2 * n - 1) { 
       temp1.add(s + "("); 
       temp2.add(k + 1); 
      } 

      if (k > 0 && i < 2 * n - 1 || k == 1 && i == 2 * n - 1) { 
       temp1.add(s + ")"); 
       temp2.add(k - 1); 
      } 
     } 
     result = new ArrayList<>(temp1); 
     diff = new ArrayList<>(temp2); 
    } 
    return result; 
} 
+0

謝謝!! 你的解決方案比較好...但是對我來說也太難了!:D –