印刷支撑

Question

问题是这样的：

input: 1
output:
{}

input: 2
output:
{}{}
{{}}

input: 3
output:
{}{}{}
{{}}{}
{}{{}}

这是我的节目：

public class PrintBraces {
    int n;
    char []braces;

    void readData()
    {
        java.util.Scanner scn=new java.util.Scanner(System.in);
        System.out.print("Please enter the value of n : ");
        n=scn.nextInt();
    }

    void manipulate()
    {
        braces=new char[n*2];

        for(int i=0;i<2*n;i+=2)
        {
            braces[i]='{';
            braces[i+1]='}';
        }

        for(int i=0;i<n;i++)
        {
            int oddNo=2*i-1;
            if(oddNo>0)
            {
                char temp=braces[oddNo];
                braces[oddNo]=braces[oddNo+1];
                braces[oddNo+1]=temp;

                print();

                temp=braces[oddNo];
                braces[oddNo]=braces[oddNo+1];
                braces[oddNo+1]=temp;
            }
            else
            {
                print();
            }
        }
    }

    void print()
    {
        for(int i=0;i<2*n;i++)
        {
            System.out.print(braces[i]);
        }
        System.out.println();
    }
}

class PrintMain
{
    public static void main(String args[])
    {
        PrintBraces pb=new PrintBraces();
        pb.readData();
        pb.manipulate();
    }
}

正如所料，我得到了正确的答案。

我已经把它解决了，但我认为它不够有效。有人能优化它吗？我也希望看到其他其他方法来解决同样的问题。可能是递归的？此外，我愿意接受任何改进我的编程风格的建议。在我的代码中有什么好的做法吗？

Answer 1

public class Solution{

    public static void par(int n, int open, int closed, String str) {

        if (closed == n) {
            System.out.println(str);
            return;
        }

        if (open < n) {
            par(n, open+1, closed, str + "{");
        }

        if (closed < open) {
            par(n, open, closed+1, str + "}");
        }
    }

    public static void main(String[] args) throws Exception {

        par(Integer.parseInt(args[0]), 0, 0, "");

    }
}

测试用例3的输出：

{{{}}}
{{}{}}
{{}}{}
{}{{}}
{}{}{}

如果您需要额外的速度-您应该使用缓冲输出。就像这样：

import java.io.*;
import java.util.*;

public class Solution{

    static BufferedWriter out; 

    public static void par(int n, int open, int closed, String str)  throws IOException {

        if (closed == n) {
            out.write(str + "\n");
            return;
        }

        if (open < n) {
            par(n, open+1, closed, str + "{");
        }

        if (closed < open) {
            par(n, open, closed+1, str + "}");
        }
    }

    public static void main(String[] args) throws IOException  {
        out = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(java.io.FileDescriptor.out), "ASCII"), 4096);
        par(Integer.parseInt(args[0]), 0, 0, "");
        out.flush();
    }
}

例如，13的第一个版本需要17秒钟：

timethis %JAVA_HOME%/bin/java -server Solution 13 >13.txt

缓冲输出版本~ 0.4秒！

PS。有趣的是，jdk1.7.0_04 ~比那个c版本快5倍：

#include<stdio.h>
#include<string.h>

unsigned long pairs_count;
unsigned long *brackets;
unsigned long found = 0;

void print_result()
{
    unsigned long i, j;

    for (i = 0; i < pairs_count; i++) {
    printf("(");

    for (j = 0; j < pairs_count; j++)
        if (brackets[j] == i)
        printf(")");
    }

    printf("n");
    found++;
}

void step(unsigned long start_val, unsigned long pos)
{
    unsigned long k, i;

    if (start_val > pos)
    k = start_val;
    else
    k = pos;

    for (i = k; i < pairs_count; i++) {
    brackets[pos] = i;

    if (pos == pairs_count - 1)
        print_result();
    else
        step(i, pos + 1);
    }
}

int main()
{

    scanf("%d", &pairs_count);

    brackets = new unsigned long[pairs_count];

    if (!brackets) {
    printf("Unsufficient memory.n");
    return (0);
    }

    step(0, 0);

    delete brackets;

    printf("Found: %d.n", found);

    return (0);
}

Answer 2

可以用稍微不同的方式尝试给定的问题。可以看到，配对对应于二进制数字，{代表1s，}代表0。

例如，与4 {}'s的最大值成对是11110000，所以我们所要做的就是生成从1到11110000的每一个数字，剔除所有不符合我们要求的数字--也就是说，在计算数字中左数的时候，1的数目不能小于0的数，而且1和0的总数必须相等。

可以进行一些优化，例如，可以消除所有奇数。数字的总数必须是偶数，等等。

如果大括号的个数为n，则该算法具有O(2^n)复杂度。因此，它不是一种有效的算法。我想知道你的算法有多复杂，你如何才能证明你的算法是正确的。

关于更多的想法，参考:加泰罗尼亚数字。

Answer 3

这是我的努力。有点像@cat_baxter的那种。我在这里要指出的一点是，如果您在代码中添加了大量注释，有时仅仅是这样做的努力就会使代码更好。

我认为这是最优的，也就是说，它从未开始向无效的位置增长序列，但我不想试图证明这一点。

public class PrintBraces {
  public static void main(String[] args) {
    // Do a number of them.
    for (int i = 1; i < 10; i++) {
      System.out.println("Print Braces: " + i);
      printBraces(i);
    }
  }

  private static void printBraces(int n) {
    // There will always be n*2 characters in the brace array.
    char[] braces = new char[n * 2];
    // Start at position 0 with 0 opened.
    printBraces(braces, 0, 0);
  }

  private static void printBraces(char[] braces, int opened, int offset) {
    // How much space is left in the array?
    int space = braces.length - offset;
    // Are we at the end of the array?
    if (space > 0) {
      // We can open or close so try both.
      // We can only open if there is enough room to close all opened and at least one more.
      if (space > opened) {
        printBraces(braces, opened, offset, true);
      }
      // We can only close if we are opened more than once.
      if (opened > 0) {
        printBraces(braces, opened, offset, false);
      }
    } else {
      // Array is full! Is it legal?
      if (opened == 0) {
        System.out.println(braces);
      } else {
        // Here just for my sanity. Code never gets here - proving we are correct.
        System.out.println("?-" + braces);
      }
    }
  }

  private static void printBraces(char[] braces, int opened, int offset, boolean open) {
    // Add that kind of brace and recurse.
    braces[offset] = open ? '{' : '}';
    printBraces(braces, opened + (open ? 1 : -1), offset + 1);
  }
}