My code:
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<String> generateParenthesis(int n) {
ArrayList<String> result = new ArrayList<String>();
if (n <= 0)
return result;
String s = "(";
generateParenthesis(1, 0, n, result, s);
return result;
}
private void generateParenthesis(int left, int right, int total, ArrayList<String> result, String s) {
if (left == right && left + right == 2 * total) {
result.add(s);
return;
}
if (left < total) {
generateParenthesis(left + 1, right, total, result, s + '(');
}
if (right < left)
generateParenthesis(left, right + 1, total, result, s + ')');
}
public static void main(String[] args) {
Solution test = new Solution();
System.out.println(test.generateParenthesis(3));
}
}
My test result:
这次作业其实挺简单的，不知道自己为什么会卡住，其实看了答案，自己已经很接近了。。。可能分心了吧，肚子又有点疼，很那做下去了。一般分心了之后，就再也难重新集中注意力做这道题目了。
说说之前花了大量的时间研究的问题吧。
String 到底他妈是什么东西，存在了哪里。
他的本质，源码里规定的很清楚。
final char[]. 是常量型的字符数组。一旦初始化就不能再被改变了。所以一般是存储在常量池中。
那么，常量池又是什么东西呢？
常量池(constant pool)指的是在编译期被确定，并被保存在已编译的.class文件中的一些数据。它包括了关于类、方法、接口等中的常量，也包括字符串常量。
好像有些废话。但的确是这个意思。string存在于常量池中，而常量池是否存在于堆中，我不清楚。
string一般有两种初始化方式。
String s = new String("myString");
String s = "myString";
第一个初始化出来的不是字符串常量，不能在编译期就确定，所以new String() 创建的字符串不放入常量池中，它们有自己的地址空间。
而第二个初始化出来的是字符串常量，存在了常量池中。
第一种方式通过关键字new定义过程：在程序编译期，编译程序先去字符串常量池检查，是否存在“myString”,如果不存在，则在常量池中开辟一个内存空间存放“myString”；如果存在的话，则不用重新开辟空间，保证常量池中只有一个“myString”常量，节省内存空间。然后在内存堆中开辟一块空间存放new出来的String实例，在栈中开辟一块空间，命名为“s1”，存放的值为堆中String实例的内存地址，这个过程就是将引用s1指向new出来的String实例。
第二种方式直接定义过程：在程序编译期，编译程序先去字符串常量池检查，是否存在“myString”，如果不存在，则在常量池中开辟一个内存空间存放“myString”；如果存在的话，则不用重新开辟空间。然后在栈中开辟一块空间，命名为“s1”，存放的值为常量池中“myString”的内存地址。
这是摘抄自网上的一段话。讲的还有些道理。
然后说说，
StringBuilder 和 StringBuffer
他们和string的最大不同是，
他们都是 char[]. 即初始化后可变的，
String、StringBuffer和StringBuilder在本质上都是字符数组，不同的是，在进行连接操作时，String每次返回一个新的String实例，而StringBuffer和StringBuilder的append方法直接返回this，所以这就是为什么在进行大量字符串连接运算时，不推荐使用String，而推荐StringBuffer和StringBuilder。
StringBuffer在方法前加了一个synchronized修饰，起到同步的作用，可以在多线程环境使用。为此付出的代价就是降低了执行效率。因此，如果在多线程环境可以使用StringBuffer进行字符串连接操作，单线程环境使用StringBuilder，它的效率更高。
下面给两个链接，文章写得不错。
http://my.oschina.net/xiaohui249/blog/170013
http://blog.csdn.net/ithomer/article/details/7300948
**
总结： string, 常量池，初始化， StringBuilder, StringBuffer
**
Anyway, Good luck, Richardo!
My code
public class Solution {
public List<String> generateParenthesis(int n) {
ArrayList<String> ret = new ArrayList<String>();
if (n <= 0)
return ret;
dfs(n, n, "", ret);
return ret;
}
private void dfs(int left, int right, String s, ArrayList<String> ret) {
if (left > right)
return;
else if (left == 0 && right == 0) {
ret.add(s);
return;
}
if (left > 0) {
dfs(left - 1, right, s + "(", ret);
}
if (right > 0) {
dfs(left, right - 1, s + ")", ret);
}
}
}
这道题木没有做出来。奇怪的是，第一次竟然也没有做出来。
为什么呢？因为典型的backtracking，
是用一个 for 循环，然后探索过的，会删掉。
但是这边的左括号，删掉一次后，第二次还会再加去，也可以看出，他根本没有用for循环，所以我思维定式了，导致用for循环来思考问题而得不出答案。
String s = "abc";
s += "d";
此时 s的内存地址已经发生了改变。
StringBuilder s = new StringBuilder("abc");
s.append("d");
s的内存地址并未改变。stringbuilder 是 Mutable的。加上"d"后，将自己的地址返回。
Anyway, Good luck, Richardo!
My code:
public class Solution {
public List<String> generateParenthesis(int n) {
List<String> ret = new ArrayList<String>();
if (n <= 0) {
return ret;
}
helper(0, 0, n, "", ret);
return ret;
}
private void helper(int left, int right, int n, String s, List<String> ret) {
if (left < right) {
return;
}
if (left == n && right < n) {
helper(left, right + 1, n, s + ")", ret);
return;
}
else if (right == n) {
ret.add(s);
return;
}
else if (left == right) {
helper(left + 1, right, n, s + "(", ret);
}
else {
helper(left + 1, right, n, s + "(", ret);
helper(left, right + 1, n, s + ")", ret);
}
}
}
差不多的想法。思想起源于， 一个 valid parenthesis, 只有 left 始终 >= right, 并且，最终时刻， left == right
可以根据这个想法，来构造 valid parenthesis,保证 left 始终 >= right, 并且在最后， left = right = n
Anyway, Good luck, Richardo! -- 09/17/2016
