Ⅰ java高级算法问题 牛人请进
第一个，其实类似于 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 -----------------------------
没有写测试类，但估计是没问题的。可以自己试一下。
Ⅱ java经典算法题——猴子吃桃
public class Monkey
{
public static void main(String[] args)
{
int sum=0,remain=1;
//每天吃剩的桃子加一个正好是前一天桃子的一半，每天桃子的总数就回是前一天剩下桃子的数量答
for(int day=9;day>=1;day--)
{
sum=(remain+1)*2;
remain=sum;
System.out.println("第"+day+"天还剩"+remain+"个桃子");
}
System.out.println(sum);
}
}