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

联系作者

编写一个程序,用字典顺序列出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] + " ");
}
}
}

联系作者

编写一个程序,用字典顺序列出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] + " ");
}
}
}

联系作者

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

联系作者

编写一个程序,用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);
}
}
}

联系作者

已知一个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));
}
}

联系作者

已知数组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));
}
}

联系作者

假设有一个数组x[ ], 它有n个元素,每一个都大于零,称x[0] + x[1] + … + x[i]为前置和(Prefix Sum),而 x[j] + x[j + 1] + … + x[n - 1]为后置和(Suffix Sum)。试编写一个程序,求出x[ ] 中有多少组相同的前置和与后置和。

说明
如果x[ ] 的元素是3,6,2,1,4,5,2,则x[ ]的前置和有一下7个,即3,9,11,12,16,21,23;后置和则是2,7,11,12,14,20,23;于是11,12,与23这3对就是值相同的前置和与后置和,因为:
11 = 3 + 6 + 2(前置和) = 2 + 5 + 4 (后置和)
12 = 3 + 6 + 2 + 1(前置和) = 2 + 5 + 4 + 1 (后置和)
因为23是整个数组元素的和,因此前置和与后置和一定相同。

可以用变量prefix来表示前置和,用suffix来表示后置和,用i表示前置和累加元素的位置,i从前往后加,用j表示后置和累加元素的位置, j从后往前加。当prefix > suffix时,累加后置和,也就是j向前走;当prefix < suffix时,累加前置和,也就是i往后走;当prefix == suffix时,同时累加前置和与后置和,也就是i往后走,j往前走

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
public class HeadTail {
public static int headTail(int[] nums) {
int i = 0;
int j = nums.length - 1;
int prefix = 0;
int suffix = 0;
int result = 0;
while (i < nums.length && j >= 0) {
System.out.println(prefix + " " + suffix + " " + i + " " + j);
if (prefix == suffix) {
prefix += nums[i++];
suffix += nums[j--];
result++;
} else if (prefix > suffix) {
suffix += nums[j--];
} else {
prefix += nums[i++];
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {3, 6, 2, 1, 4, 5, 2};
System.out.println(headTail(nums));
}
}

联系作者

已知两个元素从小到大排列的数组x[]与y[],请编写一个程序算出两个数组元素彼此之间差的绝对值最小的一个树,此值称为数组的距离。

说明: 如果x[i]与y[i]是两个元素,那么 |x[i] - y[i]| 就是这两个元素之间的距离,所有这些距离的最小值,称为数组的距离。比如说x[]有1,3,5,7,9, y[]有2,6,8,那么最短距离就是1,因为x[0]与y[0]、 x[1]与y[0]、x[2]与y[1]、x[3]与y[1]、还有x[4]与y[2]的距离都是1。

依然是利用数组已经排好序的特性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class MinDist {
public static int minDist(int[] x, int[] y) {
int result = Integer.MAX_VALUE;
int i = 0;
int j = 0;
while (i < x.length && j < y.length) {
if (x[i] >= y[j]) {
result = Math.min(result, x[i] - y[j]);
j++;
} else {
result = Math.min(result, y[j] - x[i]);
i++;
}
}
return result;
}
public static void main(String[] args) {
int[] x = {1, 3, 5, 7, 9};
int[] y = {2, 6, 8};
System.out.println(minDist(x, y));
}
}

联系作者