LZ最近翻了翻JAVA版的数据结构与算法，无聊之下将书中的课后题一一给做了一遍，在此给出书中课后题的答案（非标准答案，是LZ的答案，猿友们可以贡献出自己更快的算法）。
1、编写一个程序解决选择问题。令k=N/2，画出表格显示程序对于N种不同的值的运行时间。
分析：选择问题是指从N个数当中，按升序（降序也可以）排列，找出第k个数。LZ的写法是采用书中给出的算法自己实现的，分别采用冒泡排序和分批处理的方式。以下为LZ写出的算法代码。
import java.util.Arrays;
import java.util.Random; //选择问题答案
public class Select { public static final Random RANDOM = new Random(47); //假设N = 10
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
printResult(createArray(RANDOM.nextInt(100000)));
}
} //冒泡排序
public static void sort(int[] values){
for (int i = 1; i < values.length; i++) {
for (int j = 0; j < values.length - i; j++) {
if (values[j] > values[j + 1]) {
int temp = values[j];
values[j] = values[j + 1];
values[j + 1] = temp;
}
}
}
}
//分批处理
public static int select(int[] values){
if (values == null || values.length == 0) {
throw new NullPointerException("values can't be null.");
}
int k = values.length / 2;
int[] temp = Arrays.copyOf(values, k);
sort(temp);
for (int i = k ; i < values.length; i++) {
if (values[i] < temp[k - 1]) {
temp[k - 1] = temp[k - 2];
for (int j = k - 2; j >0; j--) {
if (values[i] > temp[j]) {
temp[j + 1] = values[i];
break;
}else {
temp[j] = temp[j - 1];
}
}
}
}
return temp[k - 1];
}
//创建随即数组
public static int[] createArray(int length){
int[] values = new int[length];
for (int i = 0; i < length; i++) {
values[i] = RANDOM.nextInt(length * 2);
}
return values;
}
//打印结果
public static void printResult(int[] values){
System.out.println("length:" + values.length);
long start = System.currentTimeMillis();
System.out.println("result:" + select(values));
System.out.println("cost:" + (System.currentTimeMillis() - start) + "ms");
System.out.println("--------------------------------");
} }
2、编写一个程序求解字谜游戏问题。
分析：字谜游戏是从一个二维的字符数组中按照标量寻找单词的过程，LZ写的算法就是最直观的算法，有很多嵌套循环，倘若字符表很大的时候，这种方式会很慢。想必书中的后面章节应该会有更简单的方式，只不过LZ还没看到，以后有机会改善这个算法。
import java.util.Random; //字谜问题
public class Character { public static final Random RANDOM = new Random(47); public static final String[] WORDS = new String[]{"ynz","yzgm","oqz","owznt","z"}; public static void main(String[] args) {
char[][] chars = createTable(5);
printTable(chars);
findWord(chars);
}
//按照标量方向寻找满足的单词（或者说字符串）
public static void findWord(char[][] chars){
long start = System.currentTimeMillis();
for (int i = 0; i < chars.length; i++) {
for (int j = 0; j < chars.length; j++) {
for (int k = 0; k < chars.length; k++) {
for (int l = 0; l < chars.length; l++) {
if (i == k && j == l) {
printWord(String.valueOf(chars[i][j]), i, j, k, l);
continue;
}
if (k != i && j != l && (k - i) != (j - l) && (k - i) != (l - j)) {
continue;
}
StringBuffer stringBuffer = new StringBuffer();
if (i == k) {
if (j > l) {
for (int m = j; m >= l; m--) {
stringBuffer.append(chars[i][m]);
}
}else {
for (int m = j; m <= l; m++) {
stringBuffer.append(chars[i][m]);
}
}
}
if (j == l) {
if (i > k) {
for (int m = i; m >= k; m--) {
stringBuffer.append(chars[m][j]);
}
}else {
for (int m = i; m <= k; m++) {
stringBuffer.append(chars[m][j]);
}
}
}
if ((k - i) == (j - l)) {
if (i > k) {
for (int m = i,n = j; m >= k && n <= l; m--,n++) {
stringBuffer.append(chars[m][n]);
}
}else {
for (int m = i,n = j; m <= k && n >= l; m++,n--) {
stringBuffer.append(chars[m][n]);
}
}
}
if ((k - i) == (l - j)) {
if (i > k) {
for (int m = i,n = j; m >= k && n >= l; m--,n--) {
stringBuffer.append(chars[m][n]);
}
}else {
for (int m = i,n = j; m <= k && n <= l; m++,n++) {
stringBuffer.append(chars[m][n]);
}
}
}
printWord(stringBuffer.toString(), i, j, k, l);
}
}
}
}
System.out.println("-------------------------------------------------");
System.out.println("cost time:" + (System.currentTimeMillis() - start) + "ms");
}
//判断是否是既定的一个单词（或字符串）并打印
public static void printWord(String word,int i ,int j,int k,int l){
for (int m = 0; m < WORDS.length; m++) {
if (word.equals(WORDS[m])) {
System.out.println("find word:" + WORDS[m]);
System.out.println("scalar:" + "[" + (i+1) + "," + (j+1) + "]->[" + (k+1) + "," + (l+1) + "]");
}
}
}
//创建随即字符二维数组
public static char[][] createTable(int length){
char[][] chars = new char[length][length];
for (int i = 0; i < chars.length; i++) {
for (int j = 0; j < chars[i].length; j++) {
chars[i][j] = (char)(97 + RANDOM.nextInt(26));
}
}
return chars;
}
//打印二维数组
public static void printTable(char[][] chars){
System.out.println("---------------------------------------------");
for (int i = 0; i < chars.length; i++) {
System.out.print("\t" + (i+1));
}
System.out.println();
for (int i = 0; i < chars.length; i++) {
System.out.print((i+1));
for (int j = 0; j < chars.length; j++) {
System.out.print("\t" + chars[i][j]);
}
System.out.println();
}
System.out.println("---------------------------------------------");
} }
结束语
小算怡情，大算伤身。