Careercup-Google面接問題-6253551042953216

2014-05-06 01:49
タイトルリンク
原題:

Modify the following code to add a row number for each line is printed







public class Test {

    public static void main(String [] args){

        printParenthesis(3);

    }

    public static void printParenthesis(int n){

        char buffer[] = new char[n*2];

        printP(buffer,0,n,0,0);

    }

    public static void printP(char buffer[], int index, int n, int open, int close){

        if(close == n){

            System.out.println(new String(buffer));

        }else{

            if(open > close){

                buffer[index] = ']';

                printP(buffer, index+1, n, open, close+1);

            }

            if(open < n ){

                buffer[index] = '[';

                printP(buffer,index+1,n,open+1,close);

            }

        }

    }

}



Expected Output:







1.[][][]

2.[][[]]

3.[[]][]

4.[[][]]

5.[[[]]]



What changes needs to be done to accomplish the output expected?

タイトル:次のコードにいくつかの修正を加えて、出力の結果にサンプルのフォーマットのようなシーケンス番号を付けることができます.
解法:コードはまだ明らかではないかもしれませんが、結果からN対括弧マッチングのすべての組合せが出力され、カタラン数H(3)=5であり、条件にも合致していることがわかります.グローバルなcounterを追加し、出力文の近くにcounterに1を追加すれば、シーケンス番号で出力できます.
コード:

 1 // http://www.careercup.com/question?id=6253551042953216

 2 public class Test {

 3     static int res_count = 0;

 4     

 5     public static void main(String [] args) {

 6         printParenthesis(3);

 7     }

 8     

 9     public static void printParenthesis(int n) {

10         char buffer[] = new char[n * 2];

11         res_count = 0;

12         printP(buffer, 0, n, 0, 0);

13     }

14     

15     public static void printP(char buffer[], int index, int n, int open, int close) {

16         if(close == n) {

17             System.out.print((++res_count) + ".");

18             System.out.println(new String(buffer));

19         } else {

20             if (open > close) {

21                 buffer[index] = ']';

22                 printP(buffer, index+1, n, open, close + 1);

23             }

24             if (open < n) {

25                 buffer[index] = '[';

26                 printP(buffer, index + 1, n, open + 1, close);

27             }

28         }

29     }

30 }