java高级算法问题 牛人请进

Question

1）N个已经排序好的数组，每个数组有M个数字，给出一个算法把这N个数组合并成一个排好序的大数组，并分析该算法的时间和空间复杂度。

2）写一个Java函数最高效的实现字符串倒序（不能直接使用类库API）。

3）用Java数组实现一个先进先出的Queue。

求解答

Answer 1

第一个，其实类似于 Merge Sort 中的合并一步：
思路是每个小数组进行 select，然后插入大数组：
假设顺序是从小到大：
----------------------------- CODE --------------------------------
import java.util.Random;

public class Sort {
public static void main (String args[]) {
Random rnd = new Random();
final int N=5, M=8;

// Generate random array:
int[][] src = new int[N][M];
for (int i=0; i<N; i++)
src[i][0] = rnd.nextInt(50);
for (int i=0; i<N; i++) {
for (int j=1; j<M; j++)
src[i][j] = src[i][j-1] + rnd.nextInt(20);
}
// Print out the src arrays:
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++)
System.out.print(src[i][j] + " ");
System.out.println();
}

// Sort:
int[] sorted = new int[M*N];
int[] length = new int[N]; //record the length of each array
for (int i=0; i<N; i++)
length[i] = M;

int min = 0;
int j = 0;
for (int i=0; i<sorted.length; i++) {
for (j=0; j<N; j++)
if (length[j] != 0)
break;
if (j==5)
break;
min = j;
for (j=0; j<N; j++) {
if (length[j] == 0)
continue;
if (src[j][0] < src[min][0])
min = j;
}
sorted[i] = src[min][0];
for (j=1; j<length[min]; j++)
src[min][j-1] = src[min][j];
length[min] --;
}

// Print out the result:
System.out.println();
for (int i=0; i<sorted.length; i++)
System.out.print(sorted[i] + " ");
}
}
---------------------------- END CODE -----------------------------
时间复杂度：O(n平方)
空间复杂度：O(n)

****************************************
第二题，这个以前做过，很简单，代码如下：
----------------------------- CODE --------------------------------
public class Reverse {
public static String reverse (String arg0) {
char[] reverse_c = new char[arg0.length()];
for (int i=0; i<reverse_c.length; i++)
reverse_c[i] = arg0.charAt(reverse_c.length-i-1);

return (new String(reverse_c));
}

public static void main (String args[]) {
if (args.length > 0)
System.out.println(reverse(args[0]));
}
}
---------------------------- END CODE -----------------------------
运行：java Reverse "Hello, world!!"
!!dlrow ,olleH

****************************************
第三题：
----------------------------- CODE --------------------------------
public class Queue<E extends Comparable> {
private E[] queue;

@SuppressWarnings("unchecked")
public Queue (int capacity) {
queue = (E[])new Object[capacity];
}

public Queue () {
this(10);
}

public void offer (E element) {
for (int i=queue.length-1; i>0; i--)
queue[i] = queue[i-1];
queue[0] = element;
}

public E peek () {
return queue[queue.length-1];
}

public E poll () {
E head = queue[queue.length-1];
queue[queue.length-1] = null;
return head;
}

public int getCapacity () {
return queue.length;
}
}
---------------------------- END CODE -----------------------------
没有写测试类，但估计是没问题的。可以自己试一下。

Answer 2

1 可以参考我的一篇博文
http://robblog.javaeye.com/admin/blogs/566114
使用堆排序进行多路数组合并。

2

Java代码
1.public static char[] reverseStr(final char[] oriStr) {
2. char[] ret = new char[oriStr.length];
3. for (int i = 0; i < oriStr.length; i++)
4. ret[i] = oriStr[oriStr.length - i - 1];
5. return ret;
6.}
7.
8.public static void main(String[] args) {
9. char[] oriStr = { 'b', 'c', 'd', 'a', 'f' };
10. System.out.println(reverseStr(oriStr));
11.}
public static char[] reverseStr(final char[] oriStr) {
char[] ret = new char[oriStr.length];
for (int i = 0; i < oriStr.length; i++)
ret[i] = oriStr[oriStr.length - i - 1];
return ret;
}

public static void main(String[] args) {
char[] oriStr = { 'b', 'c', 'd', 'a', 'f' };
System.out.println(reverseStr(oriStr));
}

3 说下思路
使用一个数组保存进入队列的值，分别用两个变量保存队头和队尾，需要考虑：
- 入队： 在队尾插入元素，队尾加1
- 出队： 返回队头，队头加1
- 空队列： 队头索引和队尾索引相同
- 数组扩张和缩小： 由于数组定义时必须指定长度，可以先指定一个长度，当队列中的元素个数将要大于这个长度是，扩张数组，队列长度过小时缩小数组。如果扩张数组： 可以参考ArrayList中的实现。

Answer 3

第一个，其实类似于
Merge
Sort
中的合并一步：
思路是每个小数组进行
select，然后插入大数组：
假设顺序是从小到大：
-----------------------------
CODE
--------------------------------
import
java.util.Random;
public
class
Sort
{
public
static
void
main
(String
args[])
{
Random
rnd
=
new
Random();
final
int
N=5,
M=8;
//
Generate
random
array:
int[][]
src
=
new
int[N][M];
for
(int
i=0;
i<N;
i++)
src[i][0]
=
rnd.nextInt(50);
for
(int
i=0;
i<N;
i++)
{
for
(int
j=1;
j<M;
j++)
src[i][j]
=
src[i][j-1]
+
rnd.nextInt(20);
}
//
Print
out
the
src
arrays:
for
(int
i=0;
i<N;
i++)
{
for
(int
j=0;
j<M;
j++)
System.out.print(src[i][j]
+
"
");
System.out.println();
}
//
Sort:
int[]
sorted
=
new
int[M*N];
int[]
length
=
new
int[N];
//record
the
length
of
each
array
for
(int
i=0;
i<N;
i++)
length[i]
=
M;
int
min
=
0;
int
j
=
0;
for
(int
i=0;
i<sorted.length;
i++)
{
for
(j=0;
j<N;
j++)
if
(length[j]
!=
0)
break;
if
(j==5)
break;
min
=
j;
for
(j=0;
j<N;
j++)
{
if
(length[j]
==
0)
continue;
if
(src[j][0]
<
src[min][0])
min
=
j;
}
sorted[i]
=
src[min][0];
for
(j=1;
j<length[min];
j++)
src[min][j-1]
=
src[min][j];
length[min]
--;
}
//
Print
out
the
result:
System.out.println();
for
(int
i=0;
i<sorted.length;
i++)
System.out.print(sorted[i]
+
"
");
}
}
----------------------------
END
CODE
-----------------------------
时间复杂度：O(n平方)
空间复杂度：O(n)
****************************************
第二题，这个以前做过，很简单，代码如下：
-----------------------------
CODE
--------------------------------
public
class
Reverse
{
public
static
String
reverse
(String
arg0)
{
char[]
reverse_c
=
new
char[arg0.length()];
for
(int
i=0;
i<reverse_c.length;
i++)
reverse_c[i]
=
arg0.charAt(reverse_c.length-i-1);
return
(new
String(reverse_c));
}
public
static
void
main
(String
args[])
{
if
(args.length
>
0)
System.out.println(reverse(args[0]));
}
}
----------------------------
END
CODE
-----------------------------
运行：java
Reverse
"Hello,
world!!"
!!dlrow
,olleH
****************************************
第三题：
-----------------------------
CODE
--------------------------------
public
class
Queue<E
extends
Comparable>
{
private
E[]
queue;
@SuppressWarnings("unchecked")
public
Queue
(int
capacity)
{
queue
=
(E[])new
Object[capacity];
}
public
Queue
()
{
this(10);
}
public
void
offer
(E
element)
{
for
(int
i=queue.length-1;
i>0;
i--)
queue[i]
=
queue[i-1];
queue[0]
=
element;
}
public
E
peek
()
{
return
queue[queue.length-1];
}
public
E
poll
()
{
E
head
=
queue[queue.length-1];
queue[queue.length-1]
=
null;
return
head;
}
public
int
getCapacity
()
{
return
queue.length;
}
}
----------------------------
END
CODE
-----------------------------
没有写测试类，但估计是没问题的。可以自己试一下。