有时候真的很郁闷，想要对Solr和Elasticsearch进行二次开发，结果在Eclipse和Intellij上，都不知道怎么启动，官网也没有说，只能上网找或者自己摸索。上网找也是很耗时间的，这些人就不能在官网上记一下吗？这里记下遇到的问题，目前使用Intellij进行Java开发，所以只纪录Intellij的情况。

下载源码

官网没有提供源码的下载，所以只好到github仓库上下载，尝试用git clone -b 2.3 https://github.com/elastic/elasticsearch.git, 但下载到的是2.3.1的，于是纠结要怎么样才能得到2.3.0的，最后求助于之前的搜索同事，知道在https://github.com/elastic/elasticsearch/releases里可以下载。

主程序入口

查看elasticsearch脚本，发现程序入口是org.elasticsearch.bootstrap.ElasticSearch

path.home is not configured

参考elasticsearch2.0源码在开发环境eclipse中启动的问题及解决方案

查看执行./elasticsearch脚本启动时添加的参数，设置VM options为

1

-Xms256m -Xmx1g -Djava.awt.headless=true -XX:+UseParNewGC -XX:+UseConcMarkSweepGC -XX:CMSInitiatingOccupancyFraction=75 -XX:+UseCMSInitiatingOccupancyOnly -XX:+HeapDumpOnOutOfMemoryError -XX:+DisableExplicitGC -Dfile.encoding=UTF-8 -Djna.nosys=true -Des.path.home=/Users/long/elasticsearch

其中主要是设置es.path.home,目录位置并没有限制。设置Program arguments为start

“java.lang.IllegalStateException” jar hell!

参考https://github.com/elastic/elasticsearch/pull/13465

1
2
3
4
5
6
7
8

I stripped the SDK classpath in IntelliJ down to the default sun.boot.class.path and I am not seeing jar hell failures anymore. Specifically:

jre/lib/charsets.jar
jre/lib/jce.jar
jre/lib/jfr.jar
jre/lib/jsse.jar
jre/lib/resources.jar
jre/lib/rt.jar

到这里才想起来Intellij在导入jdk时，将许多的jar包加入到Classpath中了，进入File->Other Settings->Default Project Structure,修改jdk的Classpath为

1
2
3
4
5
6

jre/lib/charsets.jar
jre/lib/jce.jar
jre/lib/jfr.jar
jre/lib/jsse.jar
jre/lib/resources.jar
jre/lib/rt.jar

提示找不到config目录

在/Users/long/program/java/elasticsearch-2.3.0/core目录下新建config目录，将官方发布的Elasticsearch可执行包里的config目录拷贝到这里。

之后启动org.elasticsearch.bootstrap.Elasticsearch, 成功。

在搜索引擎中，要得到第一页的结果，可以使用堆这个数据结构来实现。在最小的K个数有这样的例子，这里需要将最小的K个数，改成最大的K个数实现。也就是说，建立一个大小为K的小顶堆，对于之后的元素，每个与堆顶比较，如果小于堆顶，则它不可能是最大的K个数之一，如果大于堆顶，则将堆顶替换，并重建小顶堆。之后剩下的K个元素就是最大的K个数，而堆顶是这K个元素中最小的。之后取出堆顶，得到这K个元素中最小的，然后重建小顶堆，再取出堆顶，得到这K个元素中第二小的，一直到堆中没有元素。

要得到第二页的结果，其实也是类似的。假设每页是K个元素，则先建立一个大小为2K的小顶堆。之后按照最大K个数的做法得到最大的2K个数。然后取出这2K个元素中的后面K个元素即是第二页的结果。

在Solr的QueryCompent.java中，mergeIds函数里就是这样做的。

在Django后台添加markdown编辑器中说过如何在Django后台添加markdown编辑器,后来发现这里添加的pagedown有一个问题，也就是换行问题。在markdown中，单个换行会用空格代替，但pagedown中并没有这么做。经过跟踪，发现问题是在pagedown-extra中,解决的办法是在pagedown/Markdown.Converter.js的_FormParagraphs函数1168行//if this is an HTML marker, copy it前添加str = str.replace(/\n/g, " ");即可.

如此，在后台添加markdown编辑器就完成了。之后还需要前台现实时也用markdown渲染,通过自定义filter,添加markdown渲染可以实现这个功能。

• pip install markdown安装markdown

• 按照自定义模版标签和过滤器, 在所在的app目录下新建templatetags目录，在templatetags目录里新建__init__.py文件，之后编写my_markdown.py文件，内容如下：

  1 2 3 4 5 6

  from django import template from markdown import markdown register = template.Library() @register.filter(name='mark') def mark(value): return markdown(value, extensions=['markdown.extensions.extra', 'markdown.extensions.codehilite'])

• 在模版中使用

  1 2	{% load my_markdown %} <p>{{ post.content|mark|safe}}</p>

在有些应用中，需要针对应用的特征编写Analyzer，这里以Lucene5.0为例。在许多中文搜索应用，往往需要对文本进行分词，而用单字分词不能满足条件，所以需要使用其它分词，而MMSEG是其中一种。

从网上找到了chenbl写的mmseg4j，学会如何使用mmseg4j后，开始编写Analyzer。查看Analysis包的介绍后，发现主要是实现一个Tokenizer，然后在Analyzer中调用即可。于是编写了如下MMSegAnalyzer,

1
2
3
4
5
6
7
8
9

public class MMSegAnalyzer extends Analyzer {
    public MMSegAnalyzer() {
    }
    @Override
    protected TokenStreamComponents createComponents(String fieldName) {
        // TODO Auto-generated method stub
        return new TokenStreamComponents(new MMSegTokenizer());
    }
}

之后编写MMSegTokenizer,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

public class MMSegTokenizer extends Tokenizer {
    private final CharTermAttribute termAtt = addAttribute(CharTermAttribute.class);
    private final OffsetAttribute offsetAtt = addAttribute(OffsetAttribute.class);
    Dictionary dic;
    Seg seg;
    MMSeg mmSeg;

    public MMSegTokenizer() {
        dic = Dictionary.getInstance();
        seg = new ComplexSeg(dic);
        mmSeg = new MMSeg(input, seg);
    }

    @Override
    public boolean incrementToken() throws IOException {
        clearAttributes();
        // TODO Auto-generated method stub
        Word word = null;
        while((word = mmSeg.next())!=null) {
            termAtt.copyBuffer(word.getSen(), word.getWordOffset(), word.getLength());
            offsetAtt.setOffset(word.getStartOffset(), word.getEndOffset());
            return true;
        }
        return false;
    }
    @Override
    public void close() throws IOException {
        super.close();
    }

    @Override
    public void reset() throws IOException {
        super.reset();
    }
}

其中

1
2

private final CharTermAttribute termAtt = addAttribute(CharTermAttribute.class);
private final OffsetAttribute offsetAtt = addAttribute(OffsetAttribute.class);

这两个属性是用来设置Token的内容和文本的偏移位置。
然后使用《Lucene in Action2》第四章中提到的AnalyzerDemo.java来进行测试，发现抛出异常java.lang.IllegalStateException: TokenStream contract violation，
查看TokenStream类后,知道reset函数是在incrementToken函数之前调用，主要是完成一些初始化工作。猜测是MMSeg有一些初始化工作没有完成，然后查看MMSeg类，发现有个reset函数，正是完成一些初始化工作。
于是修改修改MMSegTokenizer的reset函数，如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

public class MMSegTokenizer extends Tokenizer {
    private final CharTermAttribute termAtt = addAttribute(CharTermAttribute.class);
    private final OffsetAttribute offsetAtt = addAttribute(OffsetAttribute.class);
    Dictionary dic;
    Seg seg;
    MMSeg mmSeg;

    public MMSegTokenizer() {
        dic = Dictionary.getInstance();
        seg = new ComplexSeg(dic);
        mmSeg = new MMSeg(input, seg);
    }

    @Override
    public boolean incrementToken() throws IOException {
        clearAttributes();
        // TODO Auto-generated method stub
        Word word = null;
        while((word = mmSeg.next())!=null) {
            termAtt.copyBuffer(word.getSen(), word.getWordOffset(), word.getLength());
            offsetAtt.setOffset(word.getStartOffset(), word.getEndOffset());
            return true;
        }
        return false;
    }
    @Override
    public void close() throws IOException {
        super.close();
    }

    @Override
    public void reset() throws IOException {
        super.reset();
        mmSeg.reset(input);
    }
}

MMSegAnalyzer可以进行分词了。之后看mmseg4j的实现，才发现要实现一个高效的MMSEG分词并不是一件容易的事。

在Java中创建线程有两中方法，一种是实现Runnable接口，一种是继承Thread类

实现Runnable接口

1. 将任务代码迁移到实现Runnable接口的类的run方法中

   1 2 3 4 5

   class MyRunnable implements Runnable { public void run() { task code } }

2. 创建一个类对象:
   Runnable r = new MyRunnable()

3. 由Runnable创建一个Thread对象
   Thread t = new Thread(r)
4. 启动线程
   t.start()
   完整例子如下:

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

   public class MyRunnable implements Runnable { @Override public void run() { System.out.println("Child: " + Thread.currentThread().getId()); } public static void main(String[] arg) { for (int i = 0; i < 5; i++) { Runnable r = new MyRunnable(); Thread t = new Thread(r); t.start(); } System.out.println("Parent: " + Thread.currentThread().getId()); } }

输出结果如下：
Child: 8
Child: 9
Child: 10
Child: 11
Parent: 1
Child: 12
这里不能直接调用run方法，因为这样不会创建新的线程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public class MyRunnable implements Runnable {
    @Override
    public void run() {
        System.out.println("Child: " + Thread.currentThread().getId());
    }
    public static void main(String[] arg) {
        for (int i = 0; i < 5; i++) {
            Runnable r = new MyRunnable();
//          Thread t = new Thread(r);
//          t.start();
            r.run();
        }
        System.out.println("Parent: " + Thread.currentThread().getId());
    }
}

输出结果如下：
Child: 1
Child: 1
Child: 1
Child: 1
Child: 1
Parent: 1
可以看到id都是一样的,也就是这里没有创建新的线程.

继承Thread类

1
2
3
4
5

class MyThread extends Thread {
    public void run() {
        task code
    }
}

完整例子如下:

1
2
3
4
5
6
7
8
9
10
11
12
13

public class MyThread extends Thread {
    @Override
    public void run() {
        System.out.println("Child: " + Thread.currentThread().getId()); 
    }
    public static void main(String[] arg) {
        for (int i = 0; i < 5; i++) {
            Thread t = new MyThread();
            t.start();
        }
        System.out.println("Parent: " + Thread.currentThread().getId());
    }
}

输出结果如下：
Child: 8
Child: 9
Child: 10
Child: 11
Parent: 1
Child: 12
这里不能直接调用t.run()，因为这样不会创建新的线程

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public class MyThread extends Thread {
    @Override
    public void run() {
        System.out.println("Child: " + Thread.currentThread().getId()); 
    }
    public static void main(String[] arg) {
        for (int i = 0; i < 5; i++) {
            Thread t = new MyThread();
//          t.start();
            t.run();
        }
        System.out.println("Parent: " + Thread.currentThread().getId());
    }
}

结果如下：
Child: 1
Child: 1
Child: 1
Child: 1
Child: 1
Parent: 1
可以看到id都是一样的。
查看Thread类的源码就会发现问题的所在.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public synchronized void start() {
    /**
     * This method is not invoked for the main method thread or "system"
     * group threads created/set up by the VM. Any new functionality added
     * to this method in the future may have to also be added to the VM.
     *
     * A zero status value corresponds to state "NEW".
     */
    if (threadStatus != 0)
        throw new IllegalThreadStateException();

    /* Notify the group that this thread is about to be started
     * so that it can be added to the group's list of threads
     * and the group's unstarted count can be decremented. */
    group.add(this);

    boolean started = false;
    try {
        start0();
        started = true;
    } finally {
        try {
            if (!started) {
                group.threadStartFailed(this);
            }
        } catch (Throwable ignore) {
            /* do nothing. If start0 threw a Throwable then
              it will be passed up the call stack */
        }
    }
}

private native void start0();

在start方法中调用native方法start0()，虽然看不到它的具体实现，但可以推测这里创建了新的线程，然后调用run方法。而run方法中，则没有创建线程相关的代码

1
2
3
4
5

public void run() {
    if (target != null) {
        target.run();
    }
}

关于两种方法的区别，可以看http://stackoverflow.com/questions/541487/implements-runnable-vs-extends-thread, 推荐使用实现Runnable接口的方法。

要想提高Java水平，阅读jdk源码是很有必要的，所以要安装jdk源码。所幸安装过程很简单。

在jdk目录下，如(/home/long/jdk1.7.0_80)，有src.zip文件，这里保存了jdk源码。安装过程如下:

1. 进入jdk目录
   cd /home/long/jdk1.7.0_80
2. 新建src子目录
   mkdir src
3. 进入src子目录
   cd src
4. 解压jdk源码
   unzip ../src.zip

这样，在Eclipse中，按住ctrl键，单击类名，就可以看到源码了。

题目

一个数组是以循环顺序排列的，也就是说在数组中有某个元素i，从x[i]开始有这样的关系，即x[0] < x[1] < x[2] < … < x[i - 1]，x[i] < x[i + 1] < … < x[n] < x[0]。例如8，10，14，15，2，6这7个元素就是循环顺序排列的，因为从2开始为递增，到了最后一个元素就转化为第1个元素，再一次顺序递增。换句话说，如果把x[i]，x[i + 1]，…，x[n]取出，并且接到数组开头，于是就是一个从小到大的顺序(这不是个旋转的工作吗？)。编写一个程序，接收一个以循环顺序排列的数组，把它的极小值找出来，以上面的数据为例，程序应该会输出2.

说明

因为从x[0]起顺序是递增的，一直到极小值出现，马上就会出现相反的顺序，于是很多人马上就会想出这个做法：
for (i = 1; i < n && x[i] >= x[i - 1]; i++)
一旦这个循环停下来了，如果i等于n那就表示每一个元素都大于在它前面的哪一个，因而极小值为x[0]；但若i < n，且x[i] < x[i - 1]，因此极小值为x[i]。
这是个正确的做法，但效率却不够高，因为在最坏的情况下可能要做n - 1次的比较。不过，这个数组严格说还是有顺序性的，根据这一特性应该可以找出更好、更快的方法，不妨试试看。

解法

解决的办法是用二分查找。也许会质疑这个数组并没有完全依顺序排列，所以不能用二分查找法。其实只要能够把问题分成两部分，而有办法判断解答在其中一部分的话，这就是个二分查找。

现在处理x[L]与x[R]之间的元素(包含两个端点)，去中间元素x[M], M = (R - L) / 2 + L，会出现以下两中情况

1. x[M] < x[R]，因为从左到右是递增的，直到极小值开始才下降，之后又开始递增。而第一个递增部分的任意一个元素大于第二个递增部分的任意元素。所以极小值一定不会在M的右边。所以下一个R = M。
2. x[M] >= x[R]，会出现这种情况，说明M在第一个递增部分，R在第二个递增部分，所以极小值一定在M的右边。所以下一个L = M + 1。

就这样一直反复下去，等到L=R的时候， x[L]就是极小值。

代码

写成代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public class MinimumInRotatedSortedArray {
    public static int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;
        while (left < right) {
            mid = (right - left) / 2 + left;
            if (nums[mid] < nums[right]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return nums[left];
    }
    
    public static void main(String[] args) {
        int[] temp = {6, 7, 1, 2, 3, 4};
        System.out.println(findMin(temp));
    }
}

Hexo一般都是部署到github上去，只是我有vps，干吗不用。

对于部署到vps上，本来是想使用Hexo server，然后用Nginx做反向代理。后来想想，这样耗费资源，于是在网上找到在VPS上部署hexo，直接将生成的页面给Nginx服务器，既节省资源，访问速度又更快。只是我还是想通过git管理Hexo代码，就像以前写MV小站那样。可是对于git不熟悉，上次也没有做笔记。于是在网上找到VPS上(debian8 jessie)部署hexo(Nginx代理+git部署)，正是我想要的。具体可以参考这篇，这里只记录遇到的问题。

设置ssh密钥登陆vps失败

用ssh-keygen生成密钥之后，将公钥id_rsa.pub的内容复制到vps上的authorized_keys里，一直无法登陆。最后在linux ssh 使用深度解析（key登录详解）中找到了解答，原来是authorized_keys文件权限的缘故，这个文件必须设置为600，ssh key登陆才会通过。查看日志文件/var/log/secure可以得道一些帮助。

git push时无法通过

在master上执行git config receive.denyCurrentBranch ignore即可。

Hexo生成的css文件没有更新

不知道什么情况，有时候有更新，有时候又没有更新。所以干脆先执行hexo clean后再执行hexo g。另外，git hooks很实用。

在git仓库里添加hooks

在.git/hooks目录里，参考post-receive脚本,添加如下内容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

GIT_REPO=/home/dengsl/program/nodejs/blog
 DEPLOY_DIR=/home/dengsl/program/html/blog/note

 # Get the latest commit subject
 SUBJECT=$(git log -1 --pretty=format:"%s")

 cd $GIT_REPO
 env -i git reset --hard

 #update or deploy
 IF_DEPLOY=$( echo $SUBJECT | grep 'deploy')
 if [ -z "$IF_DEPLOY" ]; then
     echo >&2 "Success. Repo update only"
     exit 0;
 fi

 # Check the deploy dir whether it exists
 if [ ! -d $DEPLOY_DIR ] ; then
 echo >&2 "fatal: post-receive: DEPLOY_DIR_NOT_EXIST: \"$DEPLOY_DIR\""
 exit 1
 fi

 #deploy static site
 hexo clean
 hexo g
 cp -r public/* $DEPLOY_DIR

现在就可以通过git来发布页面，很有意思。

因为在这个学习笔记里要贴一些代码，可是Wordpress的编辑器对于代码支持不够好，会改变代码格式，于是决定迁移到对代码支持更好的Hexo.Hexo是用Node.js写的博客系统，类似与Octpress，台湾人写的，很不错。

对于如何搭建Hexo，以及如何迁移Wordpress,可以看官方文档。这里主要说说迁移过程遇到的问题。

npm和hexo命令安装后在新开的终端中不能使用

使用nvm安装npm后，在新开的终端中npm命令不能使用，执行nvm install 4后又可以使用。考虑过之后，发现是没有将npm命令所在的bin目录加到PATH中。执行which npm, 找到npm所在的bin目录, 在用户的.bashrc文件中,将它就加入PATH中即可。如下
export PATH=/home/long/.nvm/versions/node/v4.2.3/bin:$PATH

Template render error: unexpected token: /

在https://github.com/hexojs/hexo/issues/1439也有类似的问题，原来hexo变量是用两个{和两个}包含起来, 而在一些编程语言中，二维数组会出现用两个{和两个}的情况，所以冲突了。于是修改hexo-migrator-wordpress插件,到存放hexo-migrator-wordpress插件的目录(从博客的根目录进入到node_modules/hexo-migrator-wordpress)下,打开index.js, 增加一个函数

1
2
3
4

function replaceTwoBrace(str){
    str = str.replace(/{{/g, '{ {');
    return str;
};

之后在content = tomd(content).replace(/\r\n/g, '\n');前面增加一行content = replaceTwoBrace(content);,解决问题。

文件名问题

生成的文件名如下例子
e8-af-ad-e8-a8-80-e7-89-b9-e6-80-a7-e8-bf-98-e6-98-af-e6-9c-89-e5-bf-85-e8-a6-81-e5-ad-a6-e4-b9-a0-e7-9a-84.md
e8-bd-af-e8-bf-9e-e6-8e-a5-e5-92-8c-e7-a1-ac-e8-bf-9e-e6-8e-a5.md
e8-bf-bd-e8-b8-aaquery-too-complex-not-enough-stack-e9-94-99-e8-af-af.md
我想这是将URL转化过来的结果，因为URL中，中文是UTF-8编码。这里之所以有问题是因为这样的文件名生成的URL和以前在Wordpress中不一样，这样之前在搜索引擎索引的文章就不能访问了，因为URL变了。想通过修改hexo-migrator-wordpress插件来解决,打开index.js, 在128行附近的post.create(data, next);, 之后看到post = hexo.post;, 然后进入node_modules/hexo/lib/hexo目录，在post.js里看到fs.writeFile(path, content)，想通过改这里来解决。后来想想，写个Python脚本,从内容的第一行，也就是title字段抽取出标题也可以解决。于是写了个Python脚本, changePostURL.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import os,sys

def getTitle(firstLine):
    strs = ':'.join(firstLine.split(':')[1:])
    strs = strs.replace("'", '') 
    strs = strs.strip()
    title = '-'.join(strs.split(' '))
    return title
if __name__ == "__main__":
    dirName = sys.argv[1]
    for root,dirs,fileNames in os.walk(dirName):
        for fileName in fileNames:
            print fileName 
            print root
            fileName = os.path.join(root, fileName)
            f = open(fileName)
            firstLine = f.readline()
            title = getTitle(firstLine)
            print title
            content = firstLine + f.read()
            f.close()
            newname = title + '.md'
            print newname
            os.rename(fileName, os.path.join(root,newname))

执行python changePostURL.py source/_posts/搞定

Update: 该问题有了更好的解决办法，参看Wordpress迁移Hexo文件名问题

HTML实体问题

在转化出来的文件内容中，有>和<等实体，我想是因为Wordpress编辑器进行了转化。虽然最后的显示结果没有问题，但在Markdown中，我还是希望看到>和<等,于是在hexo-migrator-wordpress中再添加一个函数.

1
2
3
4
5
6
7
8
9

function replaceHTMLEntity(str){
    str = str.replace(/amp;/g, '');
    str = str.replace(/&lt;/g, '<');
    str = str.replace(/&gt;/g, '>');
    str = str.replace(/&quot;/g, '"');
    str = str.replace(/&#92;/g, '\\');
    str = str.replace(/&#48;/g, '0');
    return str;
};

之后在content = tomd(content).replace(/\r\n/g, '\n');前面添加一行,content = replaceHTMLEntity(content);，解决问题

代码标签问题

在Wordpress中，我使用Syntax Highlighter进行代码高亮时，在代码块的前后需要添加相应的标签来高亮，如Java程序需要添加[java],[/java], 而在Markdown中这些标签就不需要了，需要对它进行替换。添加一个函数

1
2
3
4
5
6
7
8
9
10
11

function replaceCodeTag(str){
    str = str.replace(/\[python\]/gi, '```');
    str = str.replace(/\[\/python\]/gi, '```');
    str = str.replace(/\[java\]/gi, '```');
    str = str.replace(/\[\/java\]/gi, '```');
    str = str.replace(/\[php\]/gi, '```');
    str = str.replace(/\[\/php\]/gi, '```');
    str = str.replace(/\[c\]/gi, '```');
    str = str.replace(/\[\/c\]/gi, '```');
    return str;
};

之后在content = tomd(content).replace(/\r\n/g, '\n');前面添加一行,content = replaceCodeTag(content);，解决问题

请写一个程序，输入一个正整数的值，然后列出所有有n个做括号与n个右括号正确地组成的字符串；当然，正确的左、右括号一定个数一样多。

说明：
所谓由括号正确地组成的字符串，指的是如果有一个左括号，那么在它的右边就一定有一个与它相匹配的右括号。(())、()(),就是仅有的两个由两个左括号和两个右括号正确地组成的字符串；((()))、(()())、(())()、()(())、()()()是仅有的5个由3个左括号和3个右括号正确地组成的字符串。

如何产生这样的字符串呢？下面就是一个有用的想法：如果在产生的过程中已经产生了若干左、右括号，为了要把产生的行为完成，还欠R个左括号、L个右括号，那么有没有办法找出产生下一个括号时L与R的关系呢？记住，递归是一个不容忽视的利器。
解法：
假设还有left个左括号和right个右括号等待匹配，根据left与right的大小可以分三种情况
1.当 left == right 时，此时只能继续放左括号
2.当 left < right时，可以有两个选择， 继续放一个左括号或者继续放一个有括号。
放左括号时需要判断left是否大于0，只有left大于0时,才能继续放左括号。
放右括号时则不需要判断。
3.当left > right时，此时没有意义。

写成Java程序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class GenerateParenthesis {
    public static List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<String>();
        generateParenthesis(n, n , n, "", result);
        return result;
    }
    private static void generateParenthesis(int left, int right, int n, 
            String s, List<String> result) {

        if (s.length() == n * 2) {
            result.add(s);
        } else {
            if (left == right) {
                generateParenthesis(left - 1, right, n , s + "(", result);
            } else if (left < right) {
                if (left > 0) {
                    generateParenthesis(left - 1, right, n , s + "(", result);
                }
                generateParenthesis(left, right - 1, n, s + ")", result);
            } 
        }    
    }
    public static void main(String[] args) {
        List<String> result = generateParenthesis(3);
        for (String s: result) {
            System.out.println(s);
        }
    }
}

还可以对程序进行优化，因为递归过程会产生许多字符串，可以用数组来解决这个问题。修改程序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class GenerateParenthesis {
    public static List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<String>();
        char[] str = new char[n * 2];
        generateParenthesis(n, n , str, 0, result);
        return result;
    }
    private static void generateParenthesis(int left, int right, char[] str, 
            int length, List<String> result) {

        if (length == str.length) {
            result.add(String.valueOf(str));
        } else {
            if (left == right) {
                str[length] = '(';
                generateParenthesis(left - 1, right, str, length + 1, result);
            } else if (left < right) {
                if (left > 0) {
                    str[length] = '(';
                    generateParenthesis(left - 1, right, str, length + 1, result);
                }
                str[length] = ')';
                generateParenthesis(left, right - 1, str, length + 1, result);
            } 
        }    
    }
    public static void main(String[] args) {
        List<String> result = generateParenthesis(3);
        for (String s: result) {
            System.out.println(s);
        }
    }
}