By

题目

一个数组是以循环顺序排列的，也就是说在数组中有某个元素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));
    }
}

联系作者

By

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来发布页面，很有意思。

联系作者

By

因为在这个学习笔记里要贴一些代码，可是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);，解决问题

联系作者

By

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

联系作者

By

编写一个程序，用字典顺序列出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开始，一直用求下一个排列的方法列出所有排列。

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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] + " ");
        }    
    }
}

联系作者

By

编写一个程序，用字典顺序列出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

这里是一个递归的做法。看上面4! = 24个排列的第一列，它们的第一个元素都是1，第一列的最后一个是以1开头，用字典顺序排出来的最后，自然是1432.事实上，如果是n个元素的排列，以1开头的最后一个应该是1n(n-1)…432。下一列是2开头，把n(n-1)…432中最小的一个与第一个互换，也就是把倒数第一个与第一个互换，得到2n(n-1)..431，但这不是1n(n-1)…432的下一个，但是如果把后面的n - 1个元素反过来，就会得到2134…(n-1)n，是正确的顺序，于是进入第二列。

第二列的最后一个应该是2n(n-1)…431,把 n(n-1)…431中最小的与第一个互换，但因为1已经出现过了，所以把倒数第二个元素(自然是3)与第一个互换，得到3n(n-1)…421，再把后面的n - 1个元素反过来，得到3124…(n-1)n，就得到第三列的第一个。

第三列的最后一个是3n(n-1)…421, 把n(n-1)…421中最小的与第一个互换，但因为1，2已经出现过了，所以把倒数第3个元素(自然是4)与第一个互换，得到4n(n-1)…321，再将后面n - 1个反过来排，得到4123…(n - 1)n，正好是第4列的第一个元素。

于是我们可以得到一个递归的做法，从1234…n起，用一个递归的程序
1. i = n
2. 对后面n - 1个进行排列(递归的)
3. 把第i位与第1位互换
4. i减去1
5. 把后面的n - 1位反过来排
6. 回到第2步
当i到第一位时程序结束。

需要注意的一点是，排序结束后，数组元素的位置是逆置的，要保证不改变数组元素，我们需要将数组进行一个逆置。

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
package chapter3;

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

public class Permutions {
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums.length == 0)
            return result;
        permute(nums, 0, result);
        reverse(nums, 0, nums.length - 1); //after permutation, we need to reverse array
        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 permute(int[] nums, int start, List<List<Integer>> result) {
        if (start == nums.length - 1) {
            List<Integer> temp = new ArrayList<Integer>();
            for (int i = 0; i < nums.length; i++) {
                temp.add(nums[i]);
            }
            result.add(temp);
            return;
        }
        int i = nums.length;
        while (i > start) {
            permute(nums, start + 1, result);
            swap(nums, start, i - 1);
            i--;
            if (i <= start)
                break;
            reverse(nums, start + 1, nums.length - 1);    
        }
    }
    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] + " ");
        }
    }
}

联系作者

By

8后问题(Eight Queen Problem)是指在一个8 8的西洋棋盘上要如何放置8个皇后棋且不会互相吃到对方；皇后棋可以吃掉任何它所在的那一列、那一行，以及那两个对角线(米字形)上的任何棋子。请写一个程序，读入一个值n表示棋盘的大小，然后求出n n格棋盘上放n个皇后棋且不会相互吃掉对方的所有解答。

说明。这是广义的N后问题，因为所要求的是“所有”解答，而不单是其中的一组，对大多数会运用递归的人来说，这个题目反而容易做些。这一类型题目的揭发通常要用到回溯(Backtrack)的技巧–不管用递归还是不用递归都是如此，虽然会浪费时间，但多半会找到答案。

依据题意，写了一个递归的方法，判断是否能放置皇后时有点麻烦，应该有更简便的方法。

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
 import java.util.Arrays;

public class NQueens {
    public static int totalNQueens(int n) {
        boolean[][] board = new boolean[n][n];
        return totalNQueens(0, n, board);
    }
    //check if queen can put on board[row][col]
    private static boolean canPutCheck(int row, int col, int n, boolean[][] board) {
        for (int i = 0; i < n; i++) {
            if (board[row][i]) //row
                return false;
            if (board[i][col]) //col
                return false;
        }
        //diagonal
        int i = 0;
        while (row + i < n && col + i < n) {
            if (board[row + i][col +i])
                return false;
            i++;
        }
        i = 0;
        while (row - i >= 0 && col - i >= 0) {
            if (board[row - i][col - i])
                return false;
            i++;
        }
        //back diagonal
        i = 0;
        while (row + i < n && col - i >= 0) {
            if (board[row + i][col - i])
                return false;
            i++;
        }
        i = 0;
        while (row - i >= 0 && col + i < n) {
            if (board[row - i][col + i])
                return false;
            i++;
        }
        return true;

    }
    private static int totalNQueens(int row, int n, boolean[][] board) {
        if (row == n) { 
            return 1;
        }
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (canPutCheck(row, j, n, board)) {
                board[row][j] = true;
                count += totalNQueens(row + 1, n, board);
                board[row][j] = false; //backtrack
            }
        }
        return count;

    }
    public static void main(String[] args) {
        for (int i = 4; i < 10; i++)
            System.out.println(i + " " + totalNQueens(i));
    }
}

联系作者

By

编写一个程序，用Gray码(Gray Code)的顺序列出一个集合的所有子集。

什么是Gray码? nbit的Gray码是一连串共有2的n次方个元素的数列，每一个元素都有nbit,而且任何相邻的两个元素之间都只有1bit的值不同。例如，
两个bit的Gray码:
00 01 11 10 是一组Gray码
3个bit的Gray码:
000 001 011 010 110 111 101 100 是一组Gray码
但是Gray码并不是惟一的，把他循环排列或是用反过来的顺序写，也会得到一组Gray码；比如说，如果把3bitGray码的最后3个元素放在前面去，就会得到:
111 101 100 000 001 011 010 110 也是一组Gray码

产生Gray码的方法很多，这里这介绍其中一种。
将2bit Gray码列出
00
01
11
10
将3bit Gray码列出
000
001
011
010
110
111
101
100
观察3bit Gray码可以发现，它可以由2bit Gray码来得到。
3bit Gray码的前四个由2bit Gray码从第一个到最后一个在最前面的加上0得到
3bit Gray码的后四个 可以将2bit Gray从最后一个到第一个在最前面加上1得到
写成代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class GrayCode {
    public static List<Integer> grayCode(int n) {
         List<Integer> result = new ArrayList<Integer>();
         if (n == 0) {
             result.add(0);
         } else {
             List<Integer> temp = grayCode(n-1);
             for (Integer i: temp) {
                 result.add(i);
             }
             for (int i = temp.size() - 1; i >= 0; i--) {
                 result.add(temp.get(i) + (1 << (n - 1)));
             }
         }
         return result;
    }
    public static void main(String[] args) {
        List<Integer> result = grayCode(1);
        for (Integer i: result) {
            System.out.println(i);
        }
    }
}

联系作者

By

已知一个m行n列的矩阵M,它的元素满足一个很特殊的性质，即任一元素M[i][j]都小于它右边与下方的元素(如果存在的话),换言之，M[i][j] < M[i][j + 1]且M[i][j] < M[i + 1][j]。如int[ ][ ] nums = { {1, 4, 7, 11, 15},{2, 5, 8, 12, 19},{3, 6, 9, 16, 22},{10, 13, 14, 17, 24},{18, 21, 23, 26, 30}};

现在有一个值K，编写一个程序，检查矩阵M中是否有K。

对于矩阵M，可以将它划分成两部分区域，一部分是小于等于K的区域，一部分是大于K的区域。沿着两部分区域的边界线查找K即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class SearchaMatrix {
    public static boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int i = 0;
        int j = n - 1;
        while (i < m && j >= 0) {
            if (matrix[i][j] > target) {
                j--;
            } else if (matrix[i][j] < target) {
                i++;
            } else {
                return true;
            }       
        }
        return false;
    }
    public static void main(String[] args) {
        int[][] nums = { {1, 4, 7, 11, 15},{2, 5, 8, 12, 19},{3, 6, 9, 16, 22},{10, 13, 14, 17, 24},{18, 21, 23, 26, 30}};
        System.out.println(searchMatrix(nums, 17));
    }
}

联系作者

By

已知数组x[ ]储存了一组整数，请写一个程序，找出在数组中连续元素的和中最大的一个。举例而言，如果有数组1，2，-6，3，-2，4，-1，3，2，-4，那么连续的元素和有1 + 2 = 3，1 + 2 + (-6) = -3，2 + (-6) = -4，。。。，但最大的就是3 + (-2) + 4 + (-1) + 3 + 2这一段，值为9。这个题目通常叫做最大连续元素和问题，或者叫做最大连续子数组。

一个自然的办法是使用双重循环，但是性能不好。这个问题要求O(n)解法，需要动点脑筋。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class MaximumSubarray {
    public static int maxSubArray(int[] nums) {
        int result = nums[0];
        int sum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (sum < 0) {
                sum = 0;
            }
            sum += nums[i];
            result = Math.max(result, sum);
        }
        return result;      
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, -6, 3, -2, 4, -1, 3, 2, -4};
        System.out.println(maxSubArray(nums));
    }
}

还有一种是分治的方法，效率慢一些

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 MaximumSubarray {
    public static int maxSubArray(int[] nums) {
        return maxSubArray(nums, 0, nums.length - 1);    
    }
    public static int maxSubArray(int[] nums, int left, int right) {
        if (left > right) {
            return Integer.MIN_VALUE;
        } else if (left == right) {
            return nums[left];
        } else {
            int middle = (right - left) / 2 + left;
            int leftMax = maxSubArray(nums, left, middle);
            int rightMax = maxSubArray(nums, middle + 1, right);
            int sum = 0;
            int maxToLeft = Integer.MIN_VALUE;
            for (int i = middle; i >= left; i--) {
                sum += nums[i];
                maxToLeft = Math.max(maxToLeft, sum);
            }
            sum = 0;
            int maxToRight = Integer.MIN_VALUE;
            for (int i = middle + 1; i <= right; i++) {
                sum += nums[i];
                maxToRight = Math.max(maxToRight, sum);
            }
            int result = maxToLeft + maxToRight;
            result = Math.max(result, leftMax);
            result = Math.max(result, rightMax);
            return result;
        }
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, -6, 3, -2, 4, -1, 3, 2, -4};
        System.out.println(maxSubArray(nums));
    }
}

联系作者