搜索第二页实现

發表於 2016-03-16

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

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

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

联系作者

Django添加markdown

By robinjia

發表於 2016-02-10

在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文件，内容如下：

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>

联系作者

Lucene编写Analyzer

By robinjia

發表於 2015-12-23

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

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

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

之后编写MMSegTokenizer,

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函数，如下:

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创建线程

By robinjia

發表於 2015-12-21

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

实现Runnable接口

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

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

创建一个类对象:
Runnable r = new MyRunnable()
由Runnable创建一个Thread对象
Thread t = new Thread(r)

启动线程
t.start()
完整例子如下:

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方法，因为这样不会创建新的线程:

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类

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

完整例子如下:

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()，因为这样不会创建新的线程

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类的源码就会发现问题的所在.

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方法中，则没有创建线程相关的代码

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

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

联系作者

安装jdk源码

By robinjia

發表於 2015-12-21

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

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

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

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

联系作者

寻找极小值

By robinjia

發表於 2015-12-12

题目

一个数组是以循环顺序排列的，也就是说在数组中有某个元素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，会出现以下两中情况

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

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

代码

写成代码如下：

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));
    }
}

联系作者

vps上部署Hexo

By robinjia

發表於 2015-12-11

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脚本,添加如下内容

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遇到的问题

By robinjia

發表於 2015-12-11

因为在这个学习笔记里要贴一些代码，可是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, 增加一个函数

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

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中再添加一个函数.

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中这些标签就不需要了，需要对它进行替换。添加一个函数

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);，解决问题

联系作者

产生匹配括号的字符串

By robinjia

發表於 2015-12-07

请写一个程序，输入一个正整数的值，然后列出所有有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程序如下：

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);
        }
    }
}

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

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);
        }
    }
}

联系作者

产生所有排列--字典顺序(非递归解)

By robinjia

發表於 2015-11-02

编写一个程序，用字典顺序列出n个元素的所有排列(Permutation).
说明:
下面是一个n = 4，用字典顺序列出来的所有排列，一共为4! = 24个。
1234 2134 3124 4123
1243 2143 3142 4132
1324 2314 3214 4213
1342 2341 3241 4231
1423 2413 3412 4312
1432 2431 3421 4321

在产生所有排列–字典顺序中，用了递归的方法求解字典排列，这里使用非递归的方法。据Hall和Knuth的考证，200多年前(1812年)Fischer和Kruse在一本书中就提到了这个方法.

step 1: 从右往左找，找到第一个i使得nums[i] < nums[i + 1]
step 2: 从右往左找，找到第一个j使得nums[i] < nums[j]
step 3: 交换nums[i]与nums[j]
step 4: 将nums[i + 1],…nums[n]反转
在step 1时，如果找不到满足条件的i, 则结束程序。

例如153642,
从右往左找，找到第一个 i = 2 使得nums[i] < nums[i + 1] 即3 < 6
从右往左找，找到第一个 j = 3 使得nums[i] < nums[j] 即 3 < 4
交换nums[i]和nums[j], 得到154632
将nums[i + ],..nums[n]反转，即将632反转，得到154236
所以154236就是153642的下一个排列。

如此从要求12…n的字典排列，可以从12,…n开始，一直用求下一个排列的方法列出所有排列。

package chapter3;

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

public class Permutation {
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums.length == 0)
            return result;
        while (true) {
            List<Integer> temp = new ArrayList<Integer>();
            for (int t: nums) {
                temp.add(t);        
            }
            result.add(temp);
            int i = nums.length - 2;
            while (i >= 0 && nums[i] > nums[i + 1]) 
                i--;
            if (i < 0)
                break;

            int j = nums.length - 1;
            while (j > i && nums[i] > nums[j])
                j--;
            swap(nums, i, j);
            reverse(nums, i + 1, nums.length - 1);
        }
        reverse(nums, 0, nums.length - 1);
        return result;
    }
    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public static void reverse(int[] nums, int begin, int end) {
        while (begin < end) {
            swap(nums, begin, end);
            begin++;
            end--;
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        List<List<Integer>> result = permute(nums);
        for (List<Integer> list: result) {
            for (Integer i: list) {
                System.out.print(i);
            }
            System.out.println("");
        }
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }    
    }
}

阿龙的学习笔记

兼济天下则达,独善其身则穷

搜索第二页实现

联系作者

Django添加markdown

联系作者

Lucene编写Analyzer

联系作者

Java创建线程

实现Runnable接口

继承Thread类

联系作者

安装jdk源码

联系作者

寻找极小值

题目

说明

解法

代码

联系作者

vps上部署Hexo

设置ssh密钥登陆vps失败

git push时无法通过

Hexo生成的css文件没有更新

在git仓库里添加hooks

联系作者

Wordpress迁移到Hexo遇到的问题

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

Template render error: unexpected token: /

文件名问题

HTML实体问题

代码标签问题

联系作者

产生匹配括号的字符串

联系作者

产生所有排列--字典顺序(非递归解)

联系作者