java演算法難題

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