java面试题

其中的实现是我自己做的，如果有错误忘大家指正：转载请注明出处http://www.cnblogs.com/yixiwenwen/archive/2012/10/18/2729394.html

1．现在输入n个数字，以逗号，分开；然后可选择升或者降序排序；按提交键就在另一页面显示按什么排序，结果为，，提供reset

import java.awt.Button;

import java.awt.FlowLayout;

import java.awt.Frame;

import java.awt.Label;

import java.awt.TextField;

import java.awt.event.MouseAdapter;

import java.awt.event.MouseEvent;

import java.awt.event.WindowAdapter;

import java.awt.event.WindowEvent;

import java.util.Arrays;

public class Test1 extends Frame{

private TextField field = null;

private TextField xianshi = null;

private Button sheng = null;

private Button jiang = null;

private Button reset = null;

public Test1(){

super();

this.setBounds(200, 300, 400, 100);

field = new TextField(20);

xianshi = new TextField(20);

xianshi.setEditable(false);

sheng = new Button("升序");

jiang = new Button("降序");

reset = new Button("reset");

this.setLayout(new FlowLayout());

this.add(new Label("请输入数字于\",\"号分隔："));

this.add(field);

this.add(new Label("排序后为："));

this.add(xianshi);

this.add(sheng);

this.add(jiang);

this.add(reset);

this.addWindowListener(new WindowAdapter() {

@Override

public void windowClosing(WindowEvent e) {

System.exit(1);

super.windowClosing(e);

}

});

sheng.addMouseListener(new MouseAdapter() {

@Override

public void mouseClicked(MouseEvent e) {

super.mouseClicked(e);

int[] list = getValue();

StringBuffer xs = new StringBuffer();

for (int i=0;i<list.length;i++) {

xs.append(" " + list[i]);

}

xianshi.setText(xs.toString());

}

});

jiang.addMouseListener(new MouseAdapter() {

@Override

public void mouseClicked(MouseEvent e) {

super.mouseClicked(e);

int[] list = getValue();

StringBuffer xs = new StringBuffer();

for (int i=list.length-1;i>=0;i--) {

xs.append(" " + list[i]);

}

xianshi.setText(xs.toString());

}

});

reset.addMouseListener(new MouseAdapter() {

@Override

public void mouseClicked(MouseEvent e) {

super.mouseClicked(e);

field.setText("");

xianshi.setText("");

}

});

this.setVisible(true);

}

private int[] getValue() {

String str = field.getText();

int[] list = null;

if(str!= null && str.trim().length()>0){

String[] strs = str.split(",");

list = new int[strs.length];

for (int i = 0; i < strs.length; i++) {

list[i] = Integer.parseInt(strs[i]);

}

Arrays.sort(list);

return list;

}

public void spilt(String values){

String[] strs = values.split(",");

for (int i = 0; i < strs.length; i++) {

System.out.print(strs[i] + " ");

}

public static void main(String[] args) {

new Test1();

}

2．金额转换，阿拉伯数字的金额转换成中国传统的形式如：（￥1011）－>（一千零一拾一元整）输出。

import java.util.HashMap;

import java.util.Map;

public class Test2 {

Map<Integer, String> map = new HashMap<Integer, String>();

private static StringBuffer str = new StringBuffer();

public Test2() {

super();

map.put(0, "零");

map.put(1, "一");

map.put(2, "二");

map.put(3, "三");

map.put(4, "四");

map.put(5, "五");

map.put(6, "六");

map.put(7, "七");

map.put(8, "八");

map.put(9, "九");

map.put(10, "十");

map.put(100, "百");

map.put(1000, "千");

map.put(10000, "万");

map.put(100000000, "亿");

}

public void getString(int monery) {

if(monery / 1000 >= 100000){

getString(monery/100000000);

str.append(map.get(100000000));

monery = monery % 100000000;

}

if(monery / 1000 >= 10){

getString(monery/10000);

str.append(map.get(10000));

monery = monery % 10000;

}

int q = monery / 1000;

int b = (monery % 1000) / 100;

int s = (monery % 100)/ 10;

int g = monery % 10 ;

if(q > 0){

str.append(map.get(q)+map.get(1000));

}

if(b > 0 ){

str.append(map.get(b)+map.get(100));

}

if(s > 0 && b == 0 && q>0){

str.append(map.get(0) +map.get(s)+map.get(10));

}else if(s > 0){

str.append(map.get(s)+map.get(10));

}

if(g > 0 && s == 0 && q>0 ){

str.append(map.get(0) + map.get(g));

}else if(g > 0){

str.append(map.get(g));

}

public void print(){

System.out.println(str.toString());

}

public static void main(String[] args) {

Test2 test2 = new Test2();

test2.getString(344565345);

test2.print();

}

3、Java 的通信编程，编程题(或问答)，用JAVA SOCKET编程，读服务器几个字符，再写入本地显示？

import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.IOException;

import java.io.InputStream;

import java.io.InputStreamReader;

import java.io.OutputStreamWriter;

import java.net.ServerSocket;

import java.net.Socket;

public class Test3 {

public static void main(String[] args) {

ServerSocket ss = null;

try {

ss = new ServerSocket(8888);

while(true){

Socket socket = ss.accept();

System.out.println(socket.getInetAddress());

BufferedReader br = new BufferedReader(new InputStreamReader(socket.getInputStream()));

BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

bw.write("我是服务器端你说的是：" + br.readLine());

bw.close();

br.close();

socket.close();

}

} catch (IOException e) {

e.printStackTrace();

}finally{

try {

ss.close();

} catch (IOException e) {

e.printStackTrace();

}

import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.IOException;

import java.io.InputStreamReader;

import java.io.OutputStreamWriter;

import java.net.Socket;

import java.net.UnknownHostException;

public class Test4 {

public static void main(String[] args) {

Socket socket;

try {

socket = new Socket("127.0.0.1", 8888);

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(socket.getOutputStream()));

bw.write(br.readLine());

br.close();

bw.close();

socket.close();

} catch (UnknownHostException e) {

e.printStackTrace();

} catch (IOException e) {

e.printStackTrace();

}

4、用JAVA实现一种排序，JAVA类实现序列化的方法(二种)？如在COLLECTION框架中，实现比较要实现什么样的接口？

答：使用的是快速排序：

public class Test5 {

public int partition(Integer[] array,int low,int high){

int temp = array[low];

while(low < high) {

while(low <high && array[high] > temp){

high --;

}

sawp(array, low, high);

while(low <high && array[low] <temp) {

low ++;

}

sawp(array, low, high);

}

return low;

}

private void sawp(Integer[] array, int low, int high) {

Integer t = array[low];

array[low] = array[high];

array[high] = t;

}

public void Qsort(Integer[] array,int low,int high){

if(low <high){

int piv = partition(array,low,high);

Qsort(array,0,piv-1);

Qsort(array,piv +1,high);

}

public static void main(String[] args) {

Integer[] array = {5,9,4,16,15,24,2,38};

new Test5().Qsort(array,0,array.length - 1);

for (int i = 0; i < array.length; i++) {

System.out.print(" " + array[i]);

}

public class User implements Comparable<User> {

private int id ;

private String username;

private String password;

//相应的setter和getter方法省略

@Override

public int compareTo(User o) {

if(this.id > o.getId()){

return 1;

}else if(this.id < o.getId()){

return -1;

}else{

return 0;

}

import java.util.Comparator;

public class User2 implements Comparator<User2> {

private int id ;

private String username;

private String password;

//相应的setter和getter方法省略

@Override

public int compare(User2 o1, User2 o2) {

if(o1.getId() > o2.getId()){

return 1;

}else if(o1.getId() < o2.getId()){

return -1;

}else{

return 0;

}

5、编程：编写一个截取字符串的函数，输入为一个字符串和字节数，输出为按字节截取的字符串。但是要保证汉字不被截半个，如“我ABC”4，应该截为“我AB”，输入“我ABC汉DEF”，6，应该输出为“我ABC”而不是“我ABC+汉的半个”。

public class SplitString {

private String SplitStr;

private int SplitByte;

public SplitString(String str, int bytes) {

this.SplitStr = str;

this.SplitByte = bytes;

}

public void SplitIt() {

int loopCount;

loopCount = (SplitStr.length() % SplitByte == 0) ? (SplitStr.length() / SplitByte): (SplitStr.length() / SplitByte + 1);

for (int i = 1; i <= loopCount; i++) {

if (i == loopCount) {

System.out.println(SplitStr.substring((i - 1) * SplitByte,

SplitStr.length()));

} else {

System.out.println(SplitStr.substring((i - 1) * SplitByte,

(i * SplitByte)));

}

public static void main(String[] args) {

SplitString ss = new SplitString("test中dd文dsaf中男大3443n中国43中国人 0ewldfls=103", 4);

ss.SplitIt();

}

6、JAVA多线程编程。用JAVA写一个多线程程序，如写四个线程，二个加1，二个对一个变量减一，输出。

public class Test6 {

private static int count = 20;

public static void main(String[] args) {

Test6 test6 = new Test6();

Thread add = new Thread(test6.new myThreadAdd());

Thread add2 = new Thread(test6.new myThreadAdd());

Thread minus = new Thread(test6.new myThreadMinus());

Thread minus2 = new Thread(test6.new myThreadMinus());

add.start();

minus.start();

add2.start();

minus2.start();

}

class myThreadAdd implements Runnable {

@Override

public void run() {

while(true){

count ++ ;

System.out.println("这是加线程" + Thread.currentThread() +" count =" + count);

}

class myThreadMinus implements Runnable {

@Override

public void run() {

while(true) {

count --;

System.out.println("这是减线程" + Thread.currentThread() +" count =" + count);

}

7、算法程序题：

该公司笔试题就1个，要求在10分钟内作完。

题目如下：用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连。

解法1：效率不高（不太正确的这个输出的是必须是这6个数字组成的，不能少）

public class Test7 {

/**

* 用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求：

* "4 "不能在第三位， "3 "与 "5 "不能相连.

public static void main(String[] a) {

long start;

System.out.println("结果是：");

int count = 0;

for (start = 122345; start <= 543221; start++) {

String s = String.valueOf(start);

if (Validate(s)) {

if ((s.indexOf("35") == -1) && (s.indexOf("53") == -1)

&& (s.charAt(2) != '4')) {

System.out.println(s);

count++;

}

System.out.println("最后结果共" + count);

}

public static boolean Validate(String l) {

int[] a = new int[] { 0, 0, 0, 0, 0 };

for (int i = 0; i < 6; i++) {

if (l.charAt(i) == '1')

a[0]++;

if (l.charAt(i) == '2')

a[1]++;

if (l.charAt(i) == '3')

a[2]++;

if (l.charAt(i) == '4')

a[3]++;

if (l.charAt(i) == '5')

a[4]++;

}

if (a[0] == 1 && a[1] == 2 && a[2] == 1 && a[3] == 1 && a[4] == 1)

return true;

else

return false;

}

解法2：（不太正确的这个输出的是必须是这6个数字组成的，不能少）

import java.util.Set;

import java.util.TreeSet;

public class Test8 {

public static Set<String> set = new TreeSet<String>();

public static void perm(char[] n, int beg, int end) {

if (beg == end) {

addNumber(String.valueOf(n));

} else {

for (int i = beg; i <= end; ++i) {

swap(n, beg, i);

perm(n, beg + 1, end);

swap(n, beg, i);

}

public static void swap(char[] n, int x, int y) {

if (x == y || n[x] == n[y]) {

return;

}

char temp = n[x];

n[x] = n[y];

n[y] = temp;

}

public static void addNumber(String str) {

if (str.charAt(2) == '4' || str.contains("35") || str.contains("53")) {

return;

}

set.add(str);

}

public static void main(String args[]) {

char[] number = new char[] { '1', '2', '2', '3', '4', '5' };

perm(number, 0, number.length - 1);

System.out.println(set.size());

int cols = 10;

for (String s : set) {

System.out.print(s + " ");

if (cols-- == 1) {

System.out.println();

cols = 10;

}

解法3：真正的解法

public class Test9 {

public static void main(String[] args) {

boolean third = true;

boolean connect1 = true;

boolean connect2 = true;

boolean connect3 = true;

boolean connect4 = true;

for (int i = 1; i <= 5; i++) {

for (int j = 1; j <= 5; j++) {

connect1 = true;

if ((i == 3 && j == 5) || (i == 5 && j == 3)) {

connect1 = false;

}

for (int k = 1; k <= 5; k++) {

third = true;

connect2 = true;

if ((k == 3 && j == 5) || (k == 5 && j == 3)) {

connect2 = false;

}

if (k == 4) {

third = false;

}

for (int m = 1; m <= 5; m++) {

connect3 = true;

if ((k == 3 && m == 5) || (k == 5 && m == 3)) {

connect3 = false;

}

for (int n = 1; n <= 5; n++) {

connect4 = true;

if ((n == 3 && m == 5) || (n == 5 && m == 3)) {

connect4 = false;

}

if (third && connect1 && connect2 && connect3

&& connect4) {

System.out.println(i + "" + j + "" + k + "" + m

+ "" + n + "");

}

public class Test9_1 {

public static void main(String[] args) {

for (int i = 1; i <= 5; i++) {

for (int j = 1; j <= 5; j++) {

if ((i == 3 && j == 5) || (i == 5 && j == 3)) {

continue;

}

for (int k = 1; k <= 5; k++) {

if ((k == 3 && j == 5) || (k == 5 && j == 3)) {

continue;

}

if (k == 4) {

continue;

}

for (int m = 1; m <= 5; m++) {

if ((k == 3 && m == 5) || (k == 5 && m == 3)) {

continue;

}

for (int n = 1; n <= 5; n++) {

if ((n == 3 && m == 5) || (n == 5 && m == 3)) {

continue;

}

System.out.println(i + "" + j + "" + k + "" + m + "" + n + "");

}

解法4：基本思路：

1 把问题归结为图结构的遍历问题。实际上6个数字就是六个结点，把六个结点连接成无向连通图，对于每一个结点求这个图形的遍历路径，所有结点的遍历路径就是最后对这6个数字的排列组合结果集。

2 显然这个结果集还未达到题目的要求。从以下几个方面考虑：

1. 3，5不能相连：实际要求这个连通图的结点3，5之间不能连通, 可在构造图结构时就满足改条件，然后再遍历图。

2. 不能有重复: 考虑到有两个2，明显会存在重复结果，可以把结果集放在TreeSet中过滤重复结果

3. 4不能在第三位: 仍旧在结果集中去除满足此条件的结果。

/**

解题方案是把相邻问题抽象成一个2维数组，用0与1组成，如[0,1]或者[1,0]就表示0与1相邻的时候，如下图：

0 1 1 1 1 1

1 0 1 1 1 1

1 1 0 1 1 1

1 1 1 0 1 1

1 1 1 1 0 1

1 1 1 1 1 0

解释：0表示不能相邻，1表示可以相邻(当然你掉转也可以) [1,1],[2,2]...[6,6]这些当然为0了，自己与自己又怎可能相邻=。=

另外还需要设计一个boolean数组，标识第几个元素可用(即还没被用来排列)

import java.util.*;

public class DepthSearch {

//要排列的字符串数组

private String[] b = {"1","2","2","3","4","5"};

int n = b.length;

private String result ="";

//判断数组中哪个元素还可用与排列的标志位

private boolean[] visit = new boolean[n];

//用于标识相邻元素相通与否的2维数组

private int[][] a = new int[n][n];

//用于存放的排列结果的集合

private Set<String> set = new TreeSet<String>();

//计算有多少个元素被加入到TreeSet里面

private int count;

//执行main函数

public static void main(String[] args) {

new DepthSearch().start();

}

private void start(){

//初始化2维数组,1表示相连,0表示不通

for(int i=0;i<n;i++){

for(int j=0;j<n;j++){

if(i==j){

a[i][j]=0;

}

else{

a[i][j]=1;

}

//加入不能相邻元素的限制条件，把2维数组对应该元素设置为0,这里是3与5不能相邻(对应第4个元素和第6个元素)

a[3][5]=0;

a[5][3]=0;

//表示以第1到第6个元素为第1位的情况进行排列(循环6次)

for(int i=0;i<n;i++){

this.sort(i);

}

System.out.println("set中元素为"+set.size()+"个");

System.out.println("TreeSet所过滤掉的元素共有:"+(count-set.size())+"个");

System.out.println("所有排列如下：");

for(String s:set){

System.out.print(s+" , ");

}

private void sort(int startIndex){

//被拿了出来的元素设置标志为true,表示不可用，false为可用

result = result + b[startIndex];

visit[startIndex] = true;

//当长度等于6的时候，即满足一种排列组合，加到TreeSet里面

if(result.length()==6){

//用if判断：4不能放在第3位

if(result.indexOf("4")!=2){

set.add(result);

count++;

}

//2维数组a[][]表示当前元素与相邻元素,若为1，即表示可以相邻,false表示下一个元素可用

for(int i=0;i<n;i++){

if(a[startIndex][i]==1 && visit[i]==false){

sort(i);

}

//若不符合跳出循环，即result减去一个再进行排列，直到跳出最外循环为止

result = result.substring(0,result.length()-1);

visit[startIndex] = false;

}

8、写一个 Singleton 出来

1饱汉式：

public class Singleton {

private Singleton singleton = new Singleton();

private Singleton() {}

public Singleton newInstance(){

return singleton;

}

2饿汉式：

public class Singleton {

private Singleton singleton= null;

private Singleton (){}

public synchronized Singleton newInstance(){

if(singleton != null){

return singleton;

}else {

singleton = new Singleton ();

return singleton;

}

9、设计一个能随机产生100个大写英文字母的方法，在该方法中统计产生了多少元音字母，并输出这个数字。（选做）Math.random()方法可以随机产生0~1之间的double类型的小数。

import java.util.ArrayList;

import java.util.Iterator;

import java.util.List;

import java.util.Random;

public class Test10 {

List<Character> list = new ArrayList<Character>();

static int count = 0;

public void randomChar(){

List<Character> yuan = new ArrayList<Character>();

yuan.add('A');

yuan.add('E');

yuan.add('I');

yuan.add('O');

yuan.add('U');

Random random = new Random();

for(int i= 0;i<100;i++){

char c = (char)(random.nextInt(26) + 65);

list.add(c);

if(yuan.contains(c)){

count ++;

}

for (Iterator iterator = list.iterator(); iterator.hasNext();) {

Character type = (Character) iterator.next();

System.out.print(type + " ");

}

System.out.println();

}

public static void main(String[] args) {

new Test10().randomChar();

System.out.println("元音字母有:" + count + "个");

}

10、题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？
1.程序分析：兔子的规律为数列1,1,2,3,5,8,13,21....

import java.util.ArrayList;

import java.util.Iterator;

import java.util.List;

public class Test11 {

public void feibonacher(int n){

List<Integer> list = new ArrayList<Integer>();

int first = 1;

int second = 1;

list.add(first);

list.add(second);

for(int i=0;i<n;i++){

int temp = first + second;

list.add(temp);

first = second;

second = temp;

}

for (Iterator iterator = list.iterator(); iterator.hasNext();) {

Integer integer = (Integer) iterator.next();

System.out.print(integer + " ");

}

public static void main(String[] args) {

new Test11().feibonacher(20);

}

11、题目：判断101-200之间有多少个素数，并输出所有素数。

程序分析：判断素数的方法：用一个数分别去除2到sqrt(这个数)，如果能被整除，
则表明此数不是素数，反之是素数。

public class Test12 {

public static boolean isShushu(int n){

for(int i=2;i<Math.sqrt(n);i++){

if(n % i == 0){

return false;

}

return true;

}

public static void main(String[] args) {

for (int i = 101; i < 200; i++) {

if(isShushu(i)){

System.out.print(i + " ");

}

12、题目：打印出所有的"水仙花数"，所谓"水仙花数"是指一个三位数，其各位数字立方和等于该数本身。例如： 153是一个"水仙花数"，因为153=1的三次方＋5的三次方＋3的三次方。

public class Test13 {

public void printShuiXian(){

for (int i = 100; i < 999; i++) {

int b = i/100;

int s = (i % 100)/10;

int g = ( i % 10 );

if(i == Math.pow(b, 3) + Math.pow(s, 3) + Math.pow(g, 3)){

System.out.print(i + " ");

}

public static void main(String[] args) {

new Test13().printShuiXian();

}

13、题目：将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。
程序分析：对n进行分解质因数，应先找到一个最小的质数k，然后按下述步骤完成：
(1)如果这个质数恰等于n，则说明分解质因数的过程已经结束，打印出即可。
(2)如果n<>k，但n能被k整除，则应打印出k的值，并用n除以k的商,作为新的正整数你n,重复执行第一步。
(3)如果n不能被k整除，则用k+1作为k的值,重复执行第一步。

public class Test14 {

public void spiltInt(int n){

int t = 0;

for(int i=2;i<=n;i++){

if(n % i == 0){

t = i;

break;

}

if(n == t){

System.out.print(n + " ");

}else if(t != 0){

spiltInt(n/t);

System.out.print(t + " ");

}

public static void main(String[] args) {

new Test14().spiltInt(90);

}

14、题目：利用条件运算符的嵌套来完成此题：学习成绩>=90分的同学用A表示，60-89分之间的用B表示，60分以下的用C表示。

.程序分析：(a>b)?a:b这是条件运算符的基本例子。

public String getString(int coure){

return coure > 90 ? "A" : coure > 60 ? "B" : "C";

}

15、题目：输入两个正整数m和n，求其最大公约数和最小公倍数。

public class Test15 {

// 辗转相减法, 简单高效, 清晰快捷, 无除法运算

int GetMaxCommonDivide(int n, int m)

{

while (n != m) {

if (n > m)

n = n - m;

else

m = m - n;

}

return n;

}

//获取最小公约数

int GetMinCommonMultiple(int m, int n)

{

return m * n / GetMaxCommonDivide(m, n);

}

public static void main(String[] args) {

Test15 test15 = new Test15();

System.out.println("最大公约数：" + test15.GetMaxCommonDivide(12, 18));

System.out.println("最小公倍数：" + test15.GetMinCommonMultiple(12, 18));

}

16、题目：输入一行字符，分别统计出其中英文字母、空格、数字和其它字符的个数。

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

public class Test16 {

public void getCharCount(String str) {

char[] cs = str.toCharArray();

int number = 0;

int chars = 0;

int kongge = 0;

int unchar = 0;

for (int i = 0; i < cs.length; i++) {

if(cs[i] >= 'A' && cs[i] <= 'Z' || cs[i] >= 'a' && cs[i] <= 'z' ){

chars ++;

}else if(cs[i] >= '0' && cs[i] <= '9'){

number ++;

}else if(cs[i] == ' '){

kongge ++;

}else {

unchar ++;

}

System.out.println("字母有： " +chars + "个数字有：" +number + "个空格有：" +kongge + "个其他的有：" + unchar + "个");

}

public static void main(String[] args) {

try {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

String str = br.readLine();

new Test16().getCharCount(str);

} catch (IOException e) {

e.printStackTrace();

}

17、题目：求s=a+aa+aaa+aaaa+aa...a的值，其中a是一个数字。例如2+22+222+2222+22222(此时共有5个数相加)，几个数相加有键盘控制。

public class Test17 {

/**

* @param m 要加的数字

* @param n 有几个数相加

public int add(int m, int n) {

int sum = 0;

for (int i = 1; i <= n; i++) {

sum += getValue(m, i);

}

return sum;

}

private int getValue(int m, int n) {

int sum = m;

int count = 1;

for (int i = 0; i < n-1 ; i++) {

count *= 10;

sum += m * count;

}

System.out.println(sum);

return sum;

}

public static void main(String[] args) {

System.out.println(new Test17().add(8, 8));

}

18、题目：一个数如果恰好等于它的因子之和，这个数就称为"完数"。例如6=1＋2＋3.编程找出1000以内的所有完数。

import java.util.ArrayList;

import java.util.Iterator;

import java.util.List;

public class Test18 {

public void getWanShu(int m) {

List<Integer> num = new ArrayList<Integer>();

for (int i = 1; i <= m; i++) {

List<Integer> list = new ArrayList<Integer>();

for (int j = 2; j <=Math.sqrt(i); j++) {

list.add(1);

if(i % j == 0){

list.add(j);

int temp = i/j;

if(i != temp){

list.add(temp);

}

int sum = 0;

for (Iterator iterator = list.iterator(); iterator.hasNext();) {

Integer integer = (Integer) iterator.next();

sum += integer;

}

if(sum == i){

num.add(i);

}

print(num);

}

private void print(List<Integer> num) {

for (Iterator iterator = num.iterator(); iterator.hasNext();) {

Integer integer = (Integer) iterator.next();

System.out.print(integer + " ");

}

public static void main(String[] args) {

new Test18().getWanShu(1000);

}

19、题目：一球从100米高度自由落下，每次落地后反跳回原高度的一半；再落下，求它在第10次落地时，共经过多少米？第10次反弹多高？

public class Test19 {

public static final int HIGH = 100;

float distance = 0;

float currentHigh = HIGH;

/**

* @param n 要求的弹起的次数

* @param count 当前的弹起次数

public void rebound(int n,int count) {

distance += currentHigh;

currentHigh = currentHigh/2;

if(n == count){

System.out.println("第"+count+ "次落地时总路程是：" + distance + " 第"+count+ "次弹起的高度是： "+ currentHigh);

return ;

}else{

rebound(n, count+1);

}

public static void main(String[] args) {

new Test19().rebound(10 , 1);

}

20、题目：有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？

public class Test20 {

public void printCombine() {

String[] num = { "1", "2", "3", "4" };

String[] newNum = new String[3];

for (int i = 0; i < 4; i++) {

newNum[0] = num[i];

for (int j = 0; j < 4; j++) {

if(newNum[0].equals(num[j])){

continue;

}else{

newNum[1] = num[j];

}

for (int k = 0; k < 4; k++) {

if(newNum[0].equals(num[k]) || newNum[1].equals(num[k])){

continue;

}else{

newNum[2] = num[k];

for (int k2 = 0; k2 < newNum.length; k2++) {

System.out.print(newNum[k2]);

}

System.out.println();

}

public static void main(String[] args) {

new Test20().printCombine();

}

21、题目：企业发放的奖金根据利润提成。利润(I)低于或等于10万元时，奖金可提10%；利润高于10万元，低于20万元时，低于10万元的部分按10%提成，高于10万元的部分，可可提成7.5%；20万到40万之间时，高于20万元的部分，可提成5%；40万到60万之间时高于40万元的部分，可提成3%；60万到100万之间时，高于60万元的部分，可提成1.5%，高于100万元时，超过100万元的部分按1%提成，从键盘输入当月利润I，求应发放奖金总数？ 1.程序分析：请利用数轴来分界，定位。注意定义时需把奖金定义成长整型。

public class Test21 {

public long getBonus(long profit){

long bonus = 0;

if(profit > 1000000){

bonus += (profit-1000000)*0.01;

profit = profit % 1000000;

}

if(profit > 600000){

bonus += (profit-600000)*0.015;

profit = profit % 600000;

}

if(profit > 400000){

bonus += (profit-400000)*0.03;

profit = profit % 400000;

}

if(profit > 200000){

bonus += (profit-200000)*0.05;

profit = profit % 200000;

}

if(profit > 100000){

bonus += (profit-100000)*0.075;

profit = profit % 100000;

}

bonus += profit * 0.1;

return bonus;

}

public static void main(String[] args) {

System.out.println(new Test21().getBonus(5285585));

}

22、题目：输入某年某月某日，判断这一天是这一年的第几天(不能用工具类)？

1.程序分析：以3月5日为例，应该先把前两个月的加起来，然后再加上5天即本年的第几天，特殊情况，闰年且输入月份大于3时需考虑多加一天。

public class Test22 {

public int getHaoManyDay(String date){

int[] dayNum = {31,28,31,30,31,30,31,31,30,31,30,31};

int daySum = 0;

String[] strs = date.split("-");

int[] value = new int[strs.length];

for (int i = 0; i < strs.length; i++) {

value[i] = Integer.parseInt(strs[i]);

}

if(isBissextile(value[0])){

dayNum[1] = 29;

}

for(int i=0;i<value[1]-1;i++) {

daySum += dayNum[i];

}

daySum += value[2];

return daySum;

}

private boolean isBissextile(int year){

if((year % 400 ==0 ) || ((year % 4 == 0) && (year % 100 != 0))){

return true;

}else {

return false;

}

public static void main(String[] args) {

System.out.println(new Test22().getHaoManyDay("2011-3-2"));

}

23、题目：输出9*9口诀。
1.程序分析：分行与列考虑，共9行9列，i控制行，j控制列。

public class Test23 {

public static void main(String[] args) {

for (int i = 1; i <= 9; i++) {

for (int j = 1; j <= i; j++) {

System.out.print(j + " * " + i + " = " + (i*j) + " ");

}

System.out.println();

}

24、题目：打印出如下图案（菱形）
*

***

******

********

******

***

程序分析：先把图形分成两部分来看待，前四行一个规律，后三行一个规律，利用双重 for循环，第一层控制行，第二层控制列。

public class Test24 {

public static void main(String[] args) {

for(int i=1;i<=4;i++) {

StringBuffer sb = new StringBuffer();

for (int j = 0; j < 4-i; j++) {

sb.append(" ");

}

for (int k = 1; k <=(2*i-1); k++) {

sb.append("*");

}

System.out.println(sb.toString());

}

for (int i = 1; i <= 3; i++) {

StringBuffer sb = new StringBuffer();

for (int j = 0; j < i; j++) {

sb.append(" ");

}

for (int k = 1; k <= (7-2*i); k++) {

sb.append("*");

}

System.out.println(sb.toString());

}

25题目：有一分数序列：2/1，3/2，5/3，8/5，13/8，21/13...求出这个数列的前20项之和。

程序分析：请抓住分子与分母的变化规律。

public class Test25 {

public static void main(String[] args) {

float sum = 0;

float first = 1;

float second = 2;

for (int i = 1; i <= 20; i++) {

sum += second /first;

float temp = first + second;

first = second;

second = temp;

}

System.out.println("和为：" + sum);

}

26、题目：求1+2!+3!+...+20!的和；程序分析：此程序只是把累加变成了累乘。

public class Test26 {

public void getSum(int n){

long sum = 0;

for (int i = 1; i <= n; i++) {

sum += getFactorial(i);

}

System.out.println(sum);

}

private long getFactorial(int n){

long sum = 1;

for (int i = 1; i <= n; i++) {

sum = sum * i;

}

return sum;

}

public static void main(String[] args) {

new Test26().getSum(20);

}

27、题目：利用递归方法求5!。

1.程序分析：递归公式：fn=fn_1*4!

public class Test27 {

public long factorial(int n){

if(n == 1) {

return 1;

}

return n * factorial(n-1);

}

public static void main(String[] args) {

System.out.println(new Test27().factorial(5));

}

28、题目：有5个人坐在一起，问第五个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第三个人，又说比第2人大两岁。问第2个人，说比第一个人大两岁。最后问第一个人，他说是10岁。请问第五个人多大？ 1.程序分析：利用递归的方法，递归分为回推和递推两个阶段。要想知道第五个人岁数，需知道第四人的岁数，依次类推，推到第一人（10岁），再往回推。

public long factorial(int n){

if(n == 1) {

return 10;

}

return 2 + factorial(n-1);

}

29、题目：给一个不多于5位的正整数，要求：一、求它是几位数，二、逆序打印出各位数字。

public class Test29 {

public void test(int n) {

int w = n / 10000;

int q = n % 10000 / 1000;

int b = n % 1000 / 100;

int s = n % 100 / 10;

int g = n % 10 ;

int count = 0;

StringBuffer sb = new StringBuffer();

if(w != 0){

count = 5;

sb.append(g).append(s).append(b).append(q).append(w);

}else if(q != 0){

count = 4;

sb.append(g).append(s).append(b).append(q);

}else if(b != 0){

count = 3;

sb.append(g).append(s).append(b);

}else if(s != 0){

count = 2;

sb.append(g).append(s);

}else if(g != 0){

count = 1;

sb.append(g);

}

System.out.println("有" + count + "位数；逆序输出为：" + sb.toString());

}

public static void main(String[] args) {

new Test29().test(230);

}

30、题目：一个5位数，判断它是不是回文数。即12321是回文数，个位与万位相同，十位与千位相同。

public void test(int n) {

int w = n / 10000;

int q = n % 10000 / 1000;

int b = n % 1000 / 100;

int s = n % 100 / 10;

int g = n % 10 ;

if(w == g && q == s){

System.out.println(n + "是一个回文数！");

}else{

System.out.println(n + "不是一个回文数！");

}

31、题目：对10个数进行排序

package javams;

public class Test31 {

private int selectSort(int[] a, int low, int high){

int temp = a[low];

while(low < high) {

while(low < high && temp < a[high]) high--;

sawp(a,low,high);

while(low < high && temp > a[low]) low ++;

sawp(a,low,high);

}

return low;

}

private void sawp(int[] a, int low, int high) {

int temp = a[low];

a[low] = a[high];

a[high] = temp;

}

public void sort(int[] a, int low, int high){

if(low <high ) {

int n = selectSort(a, low, high);

sort(a, low, n-1);

sort(a, n+1,high);

}

public static void main(String[] args) {

int[] a = {5,25,12,3,6,14,4,8,13};

new Test31().sort(a, 0, a.length-1);

for (int i = 0; i < a.length; i++) {

System.out.print(a[i] + " ");

}

32、题目：打印出杨辉三角形（要求打印出10行如下图）

1.程序分析：
        1
       1 1
     1 2 1
    1 3 3 1
   1 4 6 4 1
1 5 10 10 5 1

public class Test32 {

public void printTriangle(int n){

int[] first = new int[2*n];

int[] second = new int[2*n];

int j = 0;

int temp = 0;

first[n-1] = 1;

for(int i=0;i< n; i++ ){

StringBuffer sb = new StringBuffer();

for (; j < n-i; j++) {

sb.append(" ");

}

j--;

for(;j<n;j++){

if(j == 0){

temp = first[j+1];

}else if(j == n-1){

temp = first[j];

}else{

temp = first[j] + first[j+1];

}

second[j] = temp;

sb.append(temp + " ");

}

System.out.println(sb.toString());

int[] t ;

t = second;

first = second;

second = first;

j = 0;

}

public static void main(String[] args) {

new Test32().printTriangle(10);

}

33、有如下整数类型的数组，现在求数组里面的子数组所有元素和最大的子数组。所谓的子数组如下：
{1,2}这个可以看做是下面数组的子数组，就是元素的下表相连的元素组合而成的数组。
int arr[]={1,2,0,5,-1,-2,4,8,12};

public class Test33 {

public void maxSunArray(int[] a){

int maximum = Integer.MIN_VALUE;

//从第i个数字开始

for (int i = 0; i < a.length; i++) {

//将j个连续的数字相加

for (int j = i; j < a.length; j++) {

int sum = 0 ;

for (int k = i; k <= j; k++) {

sum += a[k];

}

if(sum > maximum) {

maximum = sum;

}

System.out.println(maximum);

} public static void main(String[] args) {

new Test33().maxSunArray(new int[]{-9,-2,-3,-5,-3});

}

public void maxSunArray(int[] a){

int maximum = Integer.MIN_VALUE;

//从第i个数字开始

for (int i = 0; i < a.length; i++) {

//将j个连续的数字相加

int sum = 0 ;

for (int j = i; j < a.length; j++) {

sum += a[j];

if(sum > maximum) {

maximum = sum;

}

System.out.println(maximum);

}

public void maxSunArray2(int[] a){

int[] start = new int[a.length];

int[] all = new int[a.length];

start[a.length-1] = a[a.length-1];

all[a.length-1] = a[a.length-1];

for (int i = a.length-2; i >= 0; i--) {

start[i] = max(a[i],start[i+1] + a[i]);

all[i] = max(start[i] ,all[i+1]);

}

System.out.println(all[0]);

}

private int max(int m, int n){

return m > n ? m : n;

}

public void maxSunArray3(int[] a){

int start = a[a.length-1];

int all = a[a.length-1];

for (int i = a.length-2; i >= 0; i--) {

start = max(a[i],start + a[i]);

all = max(start ,all);

}

System.out.println(all);

}

private int max(int m, int n){

return m > n ? m : n;

}

34、题目：编写程序利用Random类的对象的链表中一随机的顺序存储一副52张的纸牌。用含有连个字符的字符串代表纸牌，例如“1C”表示梅花A,”JD”表示方片J等。从栈中输出4手牌，每手牌有13张纸牌。

import java.util.ArrayList;

import java.util.HashMap;

import java.util.Iterator;

import java.util.LinkedList;

import java.util.List;

import java.util.Map;

import java.util.Map.Entry;

import java.util.Random;

import java.util.Set;

import java.util.TreeSet;

public class Test34 {

static Map<Integer,String> map = new HashMap<Integer, String>();

static {

map.put(1, "A");

map.put(2, "2");

map.put(3, "3");

map.put(4, "4");

map.put(5, "5");

map.put(6, "6");

map.put(7, "7");

map.put(8, "8");

map.put(9, "9");

map.put(10, "10");

map.put(11, "J");

map.put(12, "Q");

map.put(13, "K");

}

public void card(){

String[] style = {"红桃","黑桃","梅花","方块"};

List<String> cards = new ArrayList<String>();

List<String> list = new LinkedList<String>();

for (int i = 0; i < style.length; i++) {

for (int j = 1; j <= map.size(); j++) {

cards.add(style[i] + map.get(j));

}

String[] cardArray = cards.toArray(new String[]{});

//随机打乱纸牌

random(cardArray);

//发牌

deal(cardArray);

}

private void deal(String[] cardArray) {

Set<String> a1 = new TreeSet<String>();

Set<String> a2 = new TreeSet<String>();

Set<String> a3 = new TreeSet<String>();

Set<String> a4 = new TreeSet<String>();

for (int i = 0; i < cardArray.length; i++) {

switch (i % 4) {

case 0:

a1.add(cardArray[i]);

break;

case 1:

a2.add(cardArray[i]);

break;

case 2:

a3.add(cardArray[i]);

break;

case 3:

a4.add(cardArray[i]);

break;

}

Set<String> temp = null;

for (int i = 1; i <= 4; i++) {

StringBuffer sb = new StringBuffer();

sb.append("玩家" + i + "的牌为：");

if(i == 1) {

temp = a1;

}else if(i == 2) {

temp = a2;

}else if(i == 3) {

temp = a3;

}else if(i == 4) {

temp = a4;

}

for (Iterator iterator = temp.iterator(); iterator.hasNext();) {

String string = (String) iterator.next();

sb.append(string + " ");

}

System.out.println(sb.toString());

}

private void random(String[] cardArray) {

for (int i = 0; i < 100; i++) {

Random random = new Random();

int a = random.nextInt(52);

int b = random.nextInt(52);

swap(cardArray,a,b);

}

private void swap(String[] cardArray, int a, int b) {

String temp = cardArray[a];

cardArray[a] = cardArray[b];

cardArray[b] = temp;

}

public static void main(String[] args) {

new Test34().card();

}

35、要求用三个线程处理，读取下面两个文件内容，计算数据写入data3.txt

计算公式：value1/(value2+value3);

date1.txt

Name,value1,value2,value3

N1,2,5,3

N1,3,1,2

N3,2,2,2

N2,1,1,1

data2.txt

Name,value1,value2,value3

N2,1,3,2

N3,1,3,6

N2,1,3,3

N1,2,4,1

import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.File;

import java.io.FileNotFoundException;

import java.io.FileReader;

import java.io.FileWriter;

import java.io.IOException;

public class Test35 {

StringBuffer sb = null;

int count = 0;

public synchronized StringBuffer readFile(String baseFilePath)

throws FileNotFoundException, IOException {

sb = new StringBuffer();

BufferedReader br = new BufferedReader(new FileReader(new File(

baseFilePath)));

String str = null;

while ((str = br.readLine()) != null) {

String[] s = str.split(",");

if (s.length == 4) {

sb.append(s[0]

+ ","

+ (Float.valueOf(s[1].trim()) / (Float.valueOf(s[2].trim()) + Float.valueOf(s[3].trim())))

+ "\r\n");

}

br.close();

return sb;

}

public synchronized void writeFile(String toFilePath, StringBuffer sb)

throws IOException {

BufferedWriter bw = new BufferedWriter(new FileWriter(new File(

toFilePath), true));

bw.write(sb.toString());

bw.close();

}

class ReadThread implements Runnable {

@Override

public void run() {

try {

while (count < 10) {

count++;

String filePath = null;

if (count % 2 == 0) {

filePath = "d:\\date1.txt";

} else {

filePath = "d:\\date2.txt";

}

readFile(filePath);

}

} catch (FileNotFoundException e) {

e.printStackTrace();

} catch (IOException e) {

e.printStackTrace();

}

class WriteThread implements Runnable {

@Override

public void run() {

try {

while (count < 10) {

if(sb != null) {

writeFile("d:\\date3.txt", sb);

}

} catch (FileNotFoundException e) {

e.printStackTrace();

} catch (IOException e) {

e.printStackTrace();

}

public static void main(String[] args) {

Test35 test35 = new Test35();

Thread readThread1 = new Thread(test35.new ReadThread());

Thread readThread2 = new Thread(test35.new ReadThread());

Thread writeThread = new Thread(test35.new WriteThread());

readThread1.start();

readThread2.start();

writeThread.start();

}

36.设计一个Java程序，其功能为：设计一个多边形类，在此类的基础上，设计三角形、四边形、八边形类，然后再设计一个测试类，用于检测所定义类的使用情况。

import java.util.ArrayList;

import java.util.Iterator;

import java.util.List;

/**

* 多边形类

class Polygon {

private List<Brim> brims;

public Polygon(List<Brim> brims) {

super();

this.brims = brims;

}

public Polygon() {

super();

}

public List<Brim> getBrims() {

return brims;

}

public void setBrims(List<Brim> brims) {

this.brims = brims;

}

@Override

public String toString() {

StringBuffer sb = new StringBuffer();

for (Iterator iterator = brims.iterator(); iterator.hasNext();) {

Brim type = (Brim) iterator.next();

sb.append("[边长" + type.getBrimLength() + "; 角度 :" + type.getAngle() + "],");

}

return brims.size() + "边形：【 " + sb.toString() + "】";

}

/**

* 边类

class Brim {

private float brimLength;

private float angle;

private Brim leftBrim;

private Brim rightBrim;

public Brim(float brimLength, float angle) {

super();

this.brimLength = brimLength;

this.angle = angle;

}

public float getBrimLength() {

return brimLength;

}

public void setBrimLength(float brimLength) {

this.brimLength = brimLength;

}

public float getAngle() {

return angle;

}

public void setAngle(float angle) {

this.angle = angle;

}

public Brim getLeftBrim() {

return leftBrim;

}

public void setLeftBrim(Brim leftBrim) {

this.leftBrim = leftBrim;

}

public Brim getRightBrim() {

return rightBrim;

}

public void setRightBrim(Brim rightBrim) {

this.rightBrim = rightBrim;

}

public class Test36 {

public static void main(String[] args) {

List<Brim> list = new ArrayList<Brim>();

Brim b1 = new Brim(3, 90);

Brim b2 = new Brim(4, 0);

Brim b3 = new Brim(5, 143);

b1.setLeftBrim(b3);

b1.setRightBrim(b2);

b2.setLeftBrim(b1);

b2.setRightBrim(b3);

b3.setLeftBrim(b2);

b3.setRightBrim(b1);

list.add(b1);

list.add(b2);

list.add(b3);

Polygon triangle = new Polygon(list);

System.out.println(triangle);

}

37.设计一个Java程序，其功能为：设计一个整数序列类，在此类的基础上，设计一个有序的整数序列类，然后再设计一个测试类，用于检测所定义类的使用情况。

class Collection {

private static int INDEX = 0;

private int length = 4;

private int[] coll ;

public Collection() {

coll = new int[length];

}

public void add(int m) {

if(INDEX < length ) {

coll[INDEX] = m;

INDEX ++ ;

}else {

length += length/2;

int[] temp = new int[length];

for (int i = 0; i < coll.length; i++) {

temp[i] = coll[i];

}

coll = temp;

coll[INDEX] = m;

INDEX ++ ;

}

public void print(){

for (int i = 0; i < INDEX; i++) {

System.out.print(coll[i] + " ");

}

public Integer get(int i) {

if(i > INDEX){

System.out.println("还没有添加！");

throw new ArrayIndexOutOfBoundsException(i);

}

return coll[i];

}

public int size(){

return INDEX;

}

public int[] getColl() {

return coll;

}

public void setColl(int[] coll) {

this.coll = coll;

}

class TreeCollection extends Collection {

@Override

public void add(int m) {

super.add(m);

if(super.size() > 1) {

int key = super.size()-1;

int[] coll = getColl();

int i = 0;

for(i = key-1;i>=0 ;i--) {

if(m >= get(i)){

for (int j = key-1;j>i;j--) {

coll[j+1] = coll[j];

}

coll[i+1] = m;

break;

}

if(i < 0) {

for (int j = key-1;j>=0 ;j--) {

coll[j+1] = coll[j];

}

coll[0] = m;

}

public class Test37 {

public static void main(String[] args) {

TreeCollection collection = new TreeCollection();

collection.add(32);

collection.add(12);

collection.add(8);

collection.add(5);

collection.add(14);

collection.add(4);

System.out.println(collection.size());

collection.print();

}

38、JAVA编程题:字符串"yekmaakkccekymbvb",求出字符串中有多少种字符,以及每个字符的个数?

import java.util.HashMap;

import java.util.Iterator;

import java.util.Map;

import java.util.Map.Entry;

public class Test38 {

public void printCharCount(String str){

Map<Character,Integer> map = new HashMap<Character, Integer>();

for (int i = 0; i < str.length(); i++) {

char c = str.charAt(i);

if(map.containsKey(c)){

map.put(c, map.get(c)+1);

}else{

map.put(c, 1);

}

for (Iterator iterator = map.entrySet().iterator(); iterator.hasNext();) {

Entry<Character,Integer> entry = (Entry<Character,Integer>) iterator.next();

System.out.println(entry.getKey() + " : " + entry.getValue());

}

public static void main(String[] args) {

new Test38().printCharCount("yekmaakkccekymbvb");

}

39、题目：100匹马背100担粮。大马一匹背3担，中马一匹背2担。小马2匹背一担。请编程输出所有满足条件的情况.

分析:

依题意:设大马匹数为X(匹),中马y(匹),小马z(匹).那么可以列出方程

x+y+z=100

3x+2y+z/2=100

0<=x<=33

0<=y<=50

0<=z<=100并且z必须能被2整除(因为一只小马背不动一担粮.)

其中x,y,z都是整数.

解出x,y,z

public class Test39 {

public static void main(String[] args) {

for(int i=0 ;i<=34 ;i++) {

for (int j = 0; j <= 50; j++) {

for (int k = 0; k <= 100 ; ) {

if(i+j+k == 100 && 3*i+2*j+k/2==100){

System.out.println("大马：" + i + "匹；中马 " + j +"匹；小马" + k + "匹；");

}

k += 2;

}

40、提供一个字符串，转化成10进制输出，例如“AA”,输出170

public class Test40 {

public int change16(String str){

int sum = 0;

for (int i = 0; i < str.length(); i++) {

sum = sum * 16;

String c = new String(new char[]{str.charAt(i)});

if(c.matches("\\d")){

sum += Integer.parseInt(c);

}else {

sum += ((int)(c.toLowerCase().charAt(0)) - 87);

}

return sum;

}

public static void main(String[] args) {

System.out.println(new Test40().change16("AA"));

}

41、用stringtokenizer的方法，建立一个replace()方法

public class Test41 {

public String replace(String str,Character oldStr, Character newStr) {

StringTokenizer st = new StringTokenizer(str, oldStr.toString());

StringBuffer sb = new StringBuffer();

int count = st.countTokens();

for (int i = 0; i < count ; i++) {

sb.append(st.nextToken());

if(i < count -1) {

sb.append(newStr);

}

return sb.toString();

}

public static void main(String[] args) {

System.out.println(new Test41().replace("my name is yixi ? how do you do sa?", 'd', 'y'));

}

42、编写一个class，提供void addElement(int element)方法提供int maxi()，提供int mini()，提供 int elementLength()，提供中间值int middle()

class Elements {

private static int INDEX = 0;

private int length = 4;

private int[] coll ;

private static int max = Integer.MIN_VALUE;

private static int min = Integer.MAX_VALUE;

public Elements() {

coll = new int[length];

}

public void addElement(int m) {

if(INDEX < length ) {

coll[INDEX] = m;

if(m > max) {

max = m;

}else if(m < min){

min = m;

}

INDEX ++ ;

}else {

length += length/2;

int[] temp = new int[length];

for (int i = 0; i < coll.length; i++) {

temp[i] = coll[i];

}

coll = temp;

if(m > max) {

max = m;

}else if(m < min){

min = m;

}

coll[INDEX] = m;

INDEX ++ ;

}

int maxi(){;

return max;

}

int mini(){;

return min;

}

int middle(){

int sum = 0;

for (int i = 0; i < coll.length; i++) {

sum += coll[i];

}

return sum / INDEX;

}

public int elementLength(){

return INDEX;

}

public class Test42 {

public static void main(String[] args) {

Elements elements = new Elements();

elements.addElement(5);

elements.addElement(3);

elements.addElement(8);

elements.addElement(12);

elements.addElement(1);

elements.addElement(-6);

System.out.println("max :" + elements.maxi());

System.out.println("min :" + elements.mini());

System.out.println("middle :" + elements.middle());

System.out.println("elementLength :" + elements.elementLength());

}

43、读取字符串序列，如果有“abcd“，则返回true. 提供一个每次读一个字符的函数

public class Test43 {

public boolean contains(String str,CharSequence s) {

return str.contains(s);

}

public boolean matches(String str, String regex) {

for (int i = 0; i < str.length()-regex.length(); i++) {

String temp = str.substring(i, i+regex.length());

if(regex.equals(temp)){

return true;

}

return false;

}

public static void main(String[] args) {

Test43 test43 = new Test43();

System.out.println(test43.contains("lkafhdsjfasda", "h"));;

System.out.println(test43.matches("lkafhdsjfasda", "sjf"));;

}

44、如何用java读取大文件

/**

*如何用java读取大文件

import java.io.RandomAccessFile;

import java.nio.ByteBuffer;

import java.nio.channels.FileChannel;

public class ReadBigFile {

public static void main(String[] args)throws Exception {

//定义缓冲区的大小为1KB

int bufSize = 1024;

byte [] bs = new byte[bufSize];

ByteBuffer byteBuffer = ByteBuffer.allocate(bufSize);

FileChannel channel = new RandomAccessFile("c:\\dmmsi.log","r").getChannel();

int size;

//读取到输入流的最后

while((size = channel.read(byteBuffer))!=-1){

byteBuffer.rewind();

byteBuffer.get(bs);

System.out.println(new String(bs, 0, size));

byteBuffer.clear();

}

channel.close();

}

45、代码设计

625这个数字很特别，625的平方等于390625，刚好其末3位是625本身。除了625，还有其它的3位数有这个特征吗？
请编写程序，寻找所有这样的3位数：它的平方的末3位是这个数字本身。
输出结果中，从小到大，每个找到的数字占一行。比如那个625就输出为：
625

public class Test45 {

public static void findNum(int m) {

if(m*m % 1000 == m){

System.out.print(m + " ");

}

public static void main(String[] args) {

for (int i = 100; i <= 999; i++) {

findNum(i);

}

46、代码设计
考虑方程式：a^3 + b^3 = c^3 + d^3
其中：“^”表示乘方。a、b、c、d是互不相同的小于30的正整数。
这个方程有很多解。比如：
a = 1，b=12，c=9，d=10 就是一个解。因为：1的立方加12的立方等于1729，而9的立方加10的立方也等于1729。
当然，a=12，b=1，c=9，d=10 显然也是解。
如果不计abcd交换次序的情况，这算同一个解。
你的任务是：找到所有小于30的不同的正整数解。把a b c d按从小到大排列，用逗号分隔，每个解占用1行。比如，刚才的解输出为：
1,9,10,12
不同解间的顺序可以不考虑。

import java.util.Arrays;

import java.util.HashMap;

import java.util.Iterator;

import java.util.Map;

import java.util.Map.Entry;

public class Test46 {

public Map<Integer,Integer[]> map = new HashMap<Integer,Integer[]>();

public void print(){

for (int i = 1; i < 30; i++) {

for (int j = 1; j < 30; j++) {

if(i == j){

continue;

}

for (int k = 1; k < 30 ; k++) {

if(k == j || k == i){

continue;

}

for (int p = 1; p < 30; p++) {

if(p == k || p == j || p == i){

continue;

}

if(i*i*i + j*j*j == k*k*k + p*p*p){

sort(new Integer[]{i,j,k,p});

}

for (Iterator iterator = map.entrySet().iterator(); iterator.hasNext();) {

Entry<Integer, Integer[]> type = (Entry<Integer, Integer[]>)iterator.next();

Integer[] t = type.getValue();

for (int i = 0; i < t.length; i++) {

System.out.print(t[i] + " ");

}

System.out.println();

}

private void sort(Integer[] is) {

Arrays.sort(is);

int sum = 0;

for (int i = 0; i < is.length; i++) {

sum = sum * 10;

sum += is[i];

}

map.put(sum,is);

}

public static void main(String[] args) {

new Test46().print();

}

47、代码设计
一个N位的十进制正整数，如果它的每个位上的数字的N次方的和等于这个数本身，则称其为花朵数。
例如：
当N=3时，153就满足条件，因为 1^3 + 5^3 + 3^3 = 153，这样的数字也被称为水仙花数（其中，“^”表示乘方，5^3表示5的3次方，也就是立方）。
当N=4时，1634满足条件，因为 1^4 + 6^4 + 3^4 + 4^4 = 1634。
当N=5时，92727满足条件。
实际上，对N的每个取值，可能有多个数字满足条件。

程序的任务是：求N=21时，所有满足条件的花朵数。注意：这个整数有21位，它的各个位数字的21次方之和正好等于这个数本身。
如果满足条件的数字不只有一个，请从小到大输出所有符合条件的数字，每个数字占一行。因为这个数字很大，请注意解法时间上的可行性。要求程序在3分钟内运行完毕。

import java.math.BigInteger;

import java.util.Arrays;

public class Narcissistic {

/**table用于存放0-9的每个数的n字幕的值防止重复运算**/

private static BigInteger[] table = new BigInteger[10];

public static void main(String[] args) {

long time = System.nanoTime();

find(21);

time = System.nanoTime() - time;

System.out.println(time / 1000000000.0 + "s");

}

public static void find(int n) {

//table的初始化

for (int i = 0; i < 10; i++)

table[i] = BigInteger.valueOf(i).pow(n);

//用于存储n位数据的数组每一位都是数组的一个值

int[] nums = new int[n];

//游标用于管理当前变化的是n位数据的哪一位也就是数组中相应的下标

int index = 0;

//给数组填充的数据范围是0~9 即每一位数字的范围

int num = 0;

while (true) {

if (index < nums.length && num < 10) {

nums[index] = num;

index++;

continue;

} else if (index >= nums.length) {

BigInteger big = sum(nums);

int[] temp = getArray(big);

if (check(nums, true, temp, false))

System.out.println(big);

} else if (index <= 0) {

break;

}

index--;

num = nums[index] + 1;

}

/**比较两个数组是否相等**/

public static boolean check(int[] a1, boolean copy1, int[] a2, boolean copy2) {

if (a1.length != a2.length)

return false;

if (copy1)

a1 = a1.clone();

if (copy2)

a2 = a2.clone();

Arrays.sort(a1);

Arrays.sort(a2);

return Arrays.equals(a1, a2);

}

/**将数组中的值迭加迭加的是相应的数的n字幂**/

public static BigInteger sum(int[] nums) {

BigInteger sum = BigInteger.ZERO;

for (int i = 0; i < nums.length; i++)

sum = sum.add(table[nums[i]]);

return sum;

}

/**将BigInteger变成由每个数字组成的int数组**/

public static int[] getArray(BigInteger big) {

String s = String.valueOf(big);

int length = s.length();

int[] res = new int[length];

for (int i = 0; i < length; i++)

res[i] = s.charAt(i) - '0';

return res;

}

import java.math.BigInteger;

import java.util.Hashtable;

public class Main {

private static final int SIZE = 21;

private int[] countArray = new int[10]; // 个数列表

private int[] countSumArray = new int[10]; // 个数总数

private BigInteger[] sumArray = new BigInteger[10];// 值总数

private int offset = 0;// 浮标

/**

* 设置当前浮标对应的个数，个数的总数，值总数

* @param num

* 个数

private void setValue(int num) {

countArray[offset] = num;

if (offset == 0) {

countSumArray[offset] = num;

sumArray[offset] = p(9 - offset).multiply(n(num));

} else {

countSumArray[offset] = countSumArray[offset - 1] + num;

sumArray[offset] = sumArray[offset - 1].add(p(9 - offset).multiply(

n(num)));

}

/**

* 检验当前数据是否匹配

* @return

private boolean checkPersentArray() {

BigInteger minVal = sumArray[offset];// 当前已存在值

BigInteger maxVal = sumArray[offset].add(p(9 - offset).multiply(

n(SIZE - countSumArray[offset])));// 当前已存在值+可能存在的最大值

// 最小值匹配

if (minVal.compareTo(MAX) > 0) {

return false;

}

// 最大值匹配

if (maxVal.compareTo(MIN) < 0) {

return false;

}

String minStr = minVal.compareTo(MIN) > 0 ? minVal.toString() : MIN

.toString();

String maxStr = maxVal.compareTo(MAX) < 0 ? maxVal.toString() : MAX

.toString();

// 找到最小值与最大值间首部相同的部分

int[] sameCountArray = new int[10];

for (int i = 0; i < SIZE; i++) {

char c;

if ((c = minStr.charAt(i)) == maxStr.charAt(i)) {

sameCountArray[c - '0'] = sameCountArray[c - '0'] + 1;

} else {

break;

}

// 判断如果相同部分有数据大于现在已记录的位数，返回false

for (int i = 0; i <= offset; i++) {

if (countArray[i] < sameCountArray[9 - i]) {

return false;

}

// 如果当前值的总数为SIZE位，那么判断该值是不是需要查找的值

if (countSumArray[offset] == SIZE) {

String sumStr = sumArray[offset].toString();

BigInteger sum = ZERO;

for (int i = 0; i < sumStr.length(); i++) {

sum = sum.add(p(sumStr.charAt(i) - '0'));

}

return sum.compareTo(sumArray[offset]) == 0;

}

return true;

}

/**

* 退出循环，打印

* @return

private void success() {

System.out.println("find a match number:" + sumArray[offset]);

}

/**

* 将浮标指向下一位数

private void next() {

offset++;

setValue(SIZE - countSumArray[offset - 1]);

}

/**

* 回退浮标，找到最近的浮标，并减一

private boolean back() {

// 回退浮标，找到最近的浮标，并减一

if (countArray[offset] == 0) {

while (countArray[offset] == 0) {

if (offset > 0) {

offset--;

} else {

return true;

}

if (offset > 0) {

setValue(countArray[offset] - 1);

return false;

} else {

return true;

}

/**

* 测试程序

* @param startValue

* 测试匹配数中包含9的个数

* @param startTime

* 程序启动时间

private void test(int startValue, long startTime) {

// 设置9的个数

offset = 0;

setValue(startValue);

while (true) {

if (checkPersentArray()) {// 检查当前提交数据是否匹配

// 匹配且总数正好为SIZE的位数，那么就是求解的值

if (countSumArray[offset] == SIZE) {

success();

}

// 总数不为SIZE，且当前值不在第10位（即不等于0）

if (offset != 9) {

next();

continue;

}

// 总数不为SIZE，且当前值在第10位。

if (back()) {

break;

}

} else {

if (back()) {

break;

}

System.out.println(Thread.currentThread() + " End,Spend time "

+ (System.currentTimeMillis() - startTime) / 1000 + "s");

}

/**

* 主函数

public static void main(String[] args) {

final long startTime = System.currentTimeMillis();

int s = MAX.divide(p(9)).intValue();

for (int i = 0; i <= s; i++) {

// new Main().test(i, startTime);

// 启动十个线程同时运算

final int startValue = i;

new Thread(new Runnable() {

public void run() {

new Main().test(startValue, startTime);

}

}).start();

}

private static final BigInteger ZERO = new BigInteger("0");

private static final BigInteger MIN;

private static final BigInteger MAX;

/**

* 0-SIZE间的BigInteger

private static final BigInteger n(int i) {

return (BigInteger) ht.get("n_" + i);

}

/**

* 0-9的次方的BigInteger

private static final BigInteger p(int i) {

return (BigInteger) ht.get("p_" + i);

}

/**

* 用于缓存BigInteger数据，并初始化0-SIZE间的BigInteger和0-9的次方的BigInteger

private static Hashtable<String, Object> ht = new Hashtable<String, Object>();

static {

int s = SIZE < 10 ? 10 : SIZE;

for (int i = 0; i <= s; i++) {

ht.put("n_" + i, new BigInteger(String.valueOf(i)));

}

for (int i = 0; i <= 10; i++) {

ht.put("p_" + i, new BigInteger(String.valueOf(i)).pow(SIZE));

}

MIN = n(10).pow(SIZE - 1);

MAX = n(10).pow(SIZE).subtract(n(1));

}

48、下列代码把16进制表示的串转换为3进制表示的串。试完善之

例如：x=“5”
则返回：“12”
又例如：x=”F”
则返回：“120”

/**

* 功能：将一个数从M进制转换成N进制 MValue：M进制数的字符串表示方法 Shang：保存中间运算结果 M：M进制 N：N进制

public class M2N {

public static String Shang = null;

public static String m2n(String str,int m,int n) {

String nValue = "";

Shang = str;

while (Shang.length() > 0) {

nValue = qiuyu(Shang,m,n) + nValue;

}

return nValue;

}

/**

* 功能：对给定的M进制字符串对n求余。

* @param MTempValue

* @param m

* @param n

* @return

public static String qiuyu(String MTempValue,int M,int N) {

Shang = "";

int temp = 0;

while (MTempValue.length() > 0) {

int t = getIntFromStr(MTempValue.substring(0, 1));

MTempValue = MTempValue.substring(1);

temp = temp * M + t;

Shang += getStrFromInt(temp / N);

temp = temp % N;

}

while (Shang.length() > 0 && Shang.charAt(0) == '0') {

Shang = Shang.substring(1);

}

return getStrFromInt(temp);

}

public static int getIntFromStr(String str) {

return str.charAt(0) <= '9' && str.charAt(0) >= '0' ? str.charAt(0) - '0'

: str.charAt(0) - 'a' + 10;

}

public static String getStrFromInt(int value) {

String result = null;

if (value >= 0 && value <= 9)

result = String.valueOf((char) ('0' + value));

else if (value > 9 && value < 36) {

result = String.valueOf((char) ('a' + value - 10));

} else {

result = "-1";// 出错误了

}

return result;

}

49、下列代码求出一个二进制串中连续的1或连续的0出现的最大次数。请填缺失代码。

例如：s = “101100111100011”
则返回：4
又例如：s=”0111100000”
则返回：5

public class Test49 {

public static int getMaxCount(String str) {

int max = 0;

for (int i = 0; i < str.length();) {

int temp = 1;

char c = str.charAt(i);

int j = 0;

for (j = i+1; j < str.length(); j++) {

if(str.charAt(j) == c){

temp ++;

continue;

}

break;

}

if(temp > max) {

max = temp;

}

i = j;

}

return max;

}

public static void main(String[] args) {

System.out.println(getMaxCount("101100111100011"));

}

50、编写一个自定义的异常类，包含一个product( )方法（用于两个数相乘），如果product( )方法中的两个参数的乘积小于0，则抛出一个自定义异常类的对象，输出错误信息和乘积的值。另外要求product( )方法要用throws关键字声明该方法要抛出自定义异常和算术异常。

public class Test50 {

public int product(int m, int n) throws MyExecption {

if(m * n < 0) {

throw new MyExecption("成绩的值小于0；值为：" + m*n);

}

return m * n;

}

public static void main(String[] args) {

try {

new Test50().product(10, -1);

} catch (MyExecption e) {

System.out.println(e.getMessage());

}

class MyExecption extends Exception {

private String message = "";

@Override

public String getMessage() {

return message;

}

public MyExecption() {

super();

}

public MyExecption(String message) {

super(message);

this.message = message;

}

51、java单例模式读取properties配置文件

class ReadProperties {

private static Properties properties = new Properties();

static{

try {

properties.load(ReadProperties.class.getClassLoader().getResourceAsStream("***.properties"));

} catch (IOException e) {

e.printStackTrace();

}

private ReadProperties() {

}

public static String read(String key){

return (String) properties.get(key);

}

52、给你一个字符串过滤掉里面的字母

public class Test52 {

public String filter(String str) {

StringBuffer sb = new StringBuffer();

for (int i = 0; i < str.length(); i++) {

char c = str.charAt(i);

if(c >= '0' && c <= '9') {

sb.append(c);

}

return sb.toString();

}

public static void main(String[] args) {

System.out.println(new Test52().filter("adg5asdfga1asd5adsd8as4"));

}

53、在1-100000之间抽调一个数，求出这个数是哪一个？

public class Test53 {

public static int find(int[] t) {

int demo = 0;

for (int i = 0; i < t.length; i++) {

if(i+1 == t[i]){

continue;

}else{

demo = i+1;

return demo;

}

return 0;

}

public static void main(String[] args) {

System.out.println(find(new int[] { 1, 2, 3, 4, 5, 7, 8, 9, 10 }));

}

54．二分搜索技术

public class Test54 {

/**

* 二分搜索

* @param t 要搜索的数组(必须是已经排好了序的)

* @param m 要搜索的数

* @return 若找到返回在数组中的位置没找到返回-1;

public static int binarySearch(int[] t, int m) {

int low = 0;

int row = t.length;

int middle = low + (row-low)/2;

while(low <= row) {

if(t[middle] == m ) {

return middle;

}else if(t[middle] > m) {

row = middle - 1;

}else{

low = middle + 1;

}

middle = (low + row) / 2;

}

return -1;

}

public static void main(String[] args) {

int[] t = {1,5,6,9,12,25,31,33,36,45};

System.out.println(binarySearch(t, 12));

System.out.println(binarySearch(t, 20));

}

55、合并(归并)排序

public class Test55 {

public void mergeSort(int[] t,int low,int row) {

if(low == row) {

return ;

}

int m = (low + row) / 2;

mergeSort(t, low, m);

mergeSort(t, m+1, row);

sort(t,low,m,row);

}

/**将有序的t[low..m] 和 t[m+1 .. row]归并为有序的t[low..row]**/

private void sort(int[] t, int low, int m, int row) {

int[] temp = new int[row-low +1];

int index = 0;

int i=0,j=0;

for (i = low,j= m+1; i <= m && j<=row;) {

if(t[i] >= t[j]) {

temp[index] = t[j];

j++;

}else{

temp[index] = t[i];

i++;

}

index ++;

}

while(i <= m){

temp[index] = t[i];

i++;

index ++;

}

while(j <=row){

temp[index] = t[j];

j++;

index ++;

}

for (int k= 0; k< temp.length; k++) {

t[low + k] = temp[k];

}

public static void main(String[] args) {

int[] t = {5,2,14,9,13,24,3,21,16};

new Test55().mergeSort(t, 0, t.length-1);

for (int i = 0; i < t.length; i++) {

System.out.print(t[i] + " ");

}

56、距阵连乘

public class Test56 {

public static int[][] matrix(int[][] a,int[][] b){

int ar = a[0].length;

int ac = a.length;

int br = b[0].length;

int bc = b.length;

int[][] temp = new int[ac][br];

if(ar != bc) {

System.out.println("距阵不能连乘！");

}

for (int i = 0; i < ac; i++) {

for (int j = 0; j < br; j++) {

int sum = 0;

for (int k = 0; k < ar; k++) {

sum += a[i][k]* b[k][j];

}

temp[i][j] = sum;

}

return temp;

}

public static void main(String[] args) {

int[][] a = {{2,5,1,3},{8,4,6,7},{5,1,7,5},{6,8,9,4},{3,8,4,4}};

int[][] b = {{9,2,5,1,3},{5,8,4,6,7},{3,5,1,7,5},{7,6,8,9,4}};

int[][] t = matrix(a, b);

for (int i = 0; i < t.length; i++) {

for (int j = 0; j < t[i].length; j++) {

System.out.print(t[i][j] + " ");

}

System.out.println();

}

57. 题目：输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

分析：我们用后序遍历的方式遍历二叉树的每一个结点，在遍历到一个结点之前我们已经遍历了它的左右子树。只要在遍历每个结点的时候记录它的深度（某一结点的深度等于它到叶节点的路径的长度），我们就可以一边遍历一边判断每个结点是不是平衡的。下面是这种思路的参考代码：

bool IsBalanced(BinaryTreeNode* pRoot, int* pDepth)

{

if(pRoot == NULL)

{

*pDepth = 0;

return true;

}

int left, right;

if(IsBalanced(pRoot->m_pLeft, &left)

&& IsBalanced(pRoot->m_pRight, &right))

{

int diff = left - right;

if(diff <= 1 && diff >= -1)

{

*pDepth = 1 + (left > right ? left : right);

return true;

}

return false;

}

我们只需要给上面的函数传入二叉树的根结点以及一个表示结点深度的整形变量就可以了：

bool IsBalanced(BinaryTreeNode* pRoot)

{

int depth = 0;

return IsBalanced(pRoot, &depth);

}

在上面的代码中，我们用后序遍历的方式遍历整棵二叉树。在遍历某结点的左右子结点之后，我们可以根据它的左右子结点的深度判断它是不是平衡的，并得到当前结点的深度。当最后遍历到树的根结点的时候，也就判断了整棵二叉树是不是平衡二叉树了。

Java实现：

public class Test57 {

private static boolean flag = true;

private static int balanced(Tree root){

int m = 0;

if(root == null) {

return 0;

}

int left = balanced(root.getLeftTree());

int right = balanced(root.getRightTree());

int t = left - right;

if( t >= -1 && t<= 1) {

m = 1 + (left > right ? left : right);

}else {

flag = false;

}

return m;

}

public static boolean isBalanced (Tree root) {

balanced(root);

return flag;

}

public static void main(String[] args) {

Tree root = new Tree(23);

Tree r1 = new Tree(12);

Tree r2 = new Tree(7);

Tree r3 = new Tree(45);

Tree r4 = new Tree(2);

Tree r5 = new Tree(14);

root.setLeftTree(r1);

root.setRightTree(r2);

r1.setLeftTree(r3);

r1.setRightTree(r4);

r2.setLeftTree(r5);

System.out.println(isBalanced(root));

}

class Tree {

private int data;

private Tree leftTree;

private Tree rightTree;

public Tree(int data) {

super();

this.data = data;

}

public int getData() {

return data;

}

public void setData(int data) {

this.data = data;

}

public Tree getLeftTree() {

return leftTree;

}

public void setLeftTree(Tree leftTree) {

this.leftTree = leftTree;

}

public Tree getRightTree() {

return rightTree;

}

public void setRightTree(Tree rightTree) {

this.rightTree = rightTree;

}

58、题目：输入一个字符串，输出该字符串中字符的所有组合。举个例子，如果输入abc，它的组合有a、b、c、ab、ac、bc、abc。

分析：假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第一个字符，我们有两种选择：一是把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选取m-1个字符；而是不把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选择m个字符。这两种选择都很容易用递归实现。下面是这种思路的参考代码：

void Combination(char* string)

{

if(string == NULL)

return;

int length = strlen(string);

vector<char> result;

for(int i = 1; i <= length; ++ i)

{

Combination(string, i, result);

}

void Combination(char* string, int number, vector<char>& result)

{

if(number == 0)

{

vector<char>::iterator iter = result.begin();

for(; iter < result.end(); ++ iter)

printf("%c", *iter);

printf("\n");

return;

}

if(*string == '\0')

return;

result.push_back(*string);

Combination(string + 1, number - 1, result);

result.pop_back();

Combination(string + 1, number, result);

}

由于组合可以是1个字符的组合，2个字符的字符……一直到n个字符的组合，因此在函数void Combination(char* string)，我们需要一个for循环。另外，我们一个vector来存放选择放进组合里的字符。

Java的一种实现：

public class Test58 {

public static void main(String[] args) {

String str = "abcdef";

int N = str.length();

int num = (int) Math.pow(2, N);

//思想是将每个字符的下标当作一位 1 代表选择， 0 表示不选择现在跌代所有的可能

for (int i = 1; i < num; i++) {

//比较每一位字符

for (int j = 0; j < N; j++) {

//标记为1的字符才输出标记为0 的不输出 ( i >> j ) & 1 是将i转化成的二进制右移j位后比较最后一位是否是1

if (((i >> j) & 1) != 0)

System.out.print(str.charAt(j));

}

System.out.println();

}

59、题目：某公司有几万名员工，请完成一个时间复杂度为O(n)的算法对该公司员工的年龄作排序，可使用O(1)的辅助空间。

分析：排序是面试时经常被提及的一类题目，我们也熟悉其中很多种算法，诸如插入排序、归并排序、冒泡排序，快速排序等等。这些排序的算法，要么是O(n²)的，要么是O(nlogn)的。可是这道题竟然要求是O(n)的，这里面到底有什么玄机呢？

题目特别强调是对一个公司的员工的年龄作排序。员工的数目虽然有几万人，但这几万员工的年龄却只有几十种可能。上班早的人一般也要等到将近二十岁才上班，一般人再晚到了六七十岁也不得不退休。

由于年龄总共只有几十种可能，我们可以很方便地统计出每一个年龄里有多少名员工。举个简单的例子，假设总共有5个员工，他们的年龄分别是25、24、26、24、25。我们统计出他们的年龄，24岁的有两个，25岁的也有两个，26岁的一个。那么我们根据年龄排序的结果就是：24、24、25、25、26，即在表示年龄的数组里写出两个24、两个25和一个26。

想明白了这种思路，我们就可以写出如下代码：

void SortAges(int ages[], int length)

{

if(ages == NULL || length <= 0)

return;

const int oldestAge = 99;

int timesOfAge[oldestAge + 1];

for(int i = 0; i <= oldestAge; ++ i)

timesOfAge[i] = 0;

for(int i = 0; i < length; ++ i)

{

int age = ages[i];

if(age < 0 || age > oldestAge)

throw new std::exception("age out of range.");

++ timesOfAge[age];

}

int index = 0;

for(int i = 0; i <= oldestAge; ++ i)

{

for(int j = 0; j < timesOfAge[i]; ++ j)

{

ages[index] = i;

++ index;

}

在上面的代码中，允许的范围是0到99岁。数组timesOfAge用来统计每个年龄出现的次数。某个年龄出现了多少次，就在数组ages里设置几次该年龄。这样就相当于给数组ages排序了。该方法用长度100的整数数组辅助空间换来了O(n)的时间效率。由于不管对多少人的年龄作排序，辅助数组的长度是固定的100个整数，因此它的空间复杂度是个常数，即O(1)。

Java实现：

public class Test59 {

public static void sortAges(int[] ages) {

//假设公司中最大的员工的年龄小于100岁

int[] temp = new int[100];

for (int i = 0; i < ages.length; i++) {

if(ages[i] < 0 || ages[i] >= 100 ){

System.out.println("年龄超出界限");

continue;

}

temp[ages[i]] ++;

}

for (int i = 0; i < temp.length; i++) {

if(temp[i] != 0) {

for (int j = 0; j < temp[i]; j++) {

System.out.print(i + " ");

}

public static void main(String[] args) {

int[] ages = {20,21,23,20,34,16,21,27,23,24,20,26,27,34,30,25,15};

sortAges(ages);

}

60、题目：写一个函数，求两个整数的之和，要求在函数体内不得使用＋、－、×、÷。

分析：首先我们可以分析人们是如何做十进制的加法的，比如是如何得出5+17=22这个结果的。实际上，我们可以分成三步的：第一步只做各位相加不进位，此时相加的结果是12（个位数5和7相加不要进位是2，十位数0和1相加结果是1）；第二步做进位，5+7中有进位，进位的值是10；第三步把前面两个结果加起来，12+10的结果是22，刚好5+17=22。

前面我们就在想，求两数之和四则运算都不能用，那还能用什么啊？对呀，还能用什么呢？对数字做运算，除了四则运算之外，也就只剩下位运算了。位运算是针对二进制的，我们也就以二进制再来分析一下前面的三步走策略对二进制是不是也管用。

5的二进制是101，17的二进制10001。还是试着把计算分成三步：第一步各位相加但不计进位，得到的结果是10100（最后一位两个数都是1，相加的结果是二进制的10。这一步不计进位，因此结果仍然是0）；第二步记下进位。在这个例子中只在最后一位相加时产生一个进位，结果是二进制的10；第三步把前两步的结果相加，得到的结果是10110，正好是22。由此可见三步走的策略对二进制也是管用的。

接下来我们试着把二进制上的加法用位运算来替代。第一步不考虑进位，对每一位相加。0加0与1加1的结果都0，0加1与1加0的结果都是1。我们可以注意到，这和异或的结果是一样的。对异或而言，0和0、1和1异或的结果是0，而0和1、1和0的异或结果是1。接着考虑第二步进位，对0加0、0加1、1加0而言，都不会产生进位，只有1加1时，会向前产生一个进位。此时我们可以想象成是两个数先做位与运算，然后再向左移动一位。只有两个数都是1的时候，位与得到的结果是1，其余都是0。第三步把前两个步骤的结果相加。如果我们定义一个函数AddWithoutArithmetic，第三步就相当于输入前两步骤的结果来递归调用自己。

public class Test60 {

public static int addWithoutArithmetic(int num1, int num2)

{

//当再也没有要进的位时结束

if(num2 == 0)

return num1;

//先算出不进位的值

int sum = num1 ^ num2;

//算出要进位的位置(注意<<1的作用)

int carry = (num1 & num2) << 1;

//继续迭代

return addWithoutArithmetic(sum, carry);

}

public static void main(String[] args) {

System.out.println(addWithoutArithmetic(112, 223));

}

61、求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句（A?B:C）

分析：我们仍然围绕循环做文章。循环只是让相同的代码执行n遍而已，我们完全可以不用for和while达到这个效果。比如定义一个类，我们new一含有n个这种类型元素的数组，那么该类的构造函数将确定会被调用n次。我们可以将需要执行的代码放到构造函数里。如下代码正是基于这个思路：

class Temp
{
public:
      Temp() { ++ N; Sum += N; }
      static void Reset() { N = 0; Sum = 0; }
      static int GetSum() { return Sum; }
private:
      static int N;
      static int Sum;
};
int Temp::N = 0;
int Temp::Sum = 0;
int solution1_Sum(int n)
{
      Temp::Reset();
      Temp *a = new Temp[n];
      delete []a;
      a = 0;
      return Temp::GetSum();
}

我们同样也可以围绕递归做文章。既然不能判断是不是应该终止递归，我们不妨定义两个函数。一个函数充当递归函数的角色，另一个函数处理终止递归的情况，我们需要做的就是在两个函数里二选一。从二选一我们很自然的想到布尔变量，比如ture（1）的时候调用第一个函数，false（0）的时候调用第二个函数。那现在的问题是如和把数值变量n转换成布尔值。如果对n连续做两次反运算，即!!n，那么非零的n转换为true，0转换为false。有了上述分析，我们再来看下面的代码：

class A;
A* Array[2];
class A
{

public:
      virtual int Sum (int n) { return 0; }
};
class B: public A
{
public:
      virtual int Sum (int n) { return Array[!!n]->Sum(n-1)+n; }
};
int solution2_Sum(int n)
{
      A a;
      B b;
      Array[0] = &a;
      Array[1] = &b;
      int value = Array[1]->Sum(n);
      return value;
}

这种方法是用虚函数来实现函数的选择。当n不为零时，执行函数B::Sum；当n为0时，执行A::Sum。我们也可以直接用函数指针数组，这样可能还更直接一些：

typedef int (*fun)(int);
int solution3_f1(int i)
{
      return 0;
}
int solution3_f2(int i)
{
      fun f[2]={solution3_f1, solution3_f2};
      return i+f[!!i](i-1);
}

另外我们还可以让编译器帮我们来完成类似于递归的运算，比如如下代码：

template <int n> struct solution4_Sum
{
enum Value { N = solution4_Sum<n - 1>::N + n};
};

template <> struct solution4_Sum<1>
{
enum Value { N = 1};
};

solution4_Sum<100>::N就是1+2+...+100的结果。当编译器看到solution4_Sum<100>时，就是为模板类solution4_Sum以参数100生成该类型的代码。但以100为参数的类型需要得到以99为参数的类型，因为solution4_Sum<100>::N=solution4_Sum<99>::N+100。这个过程会递归一直到参数为1的类型，由于该类型已经显式定义，编译器无需生成，递归编译到此结束。由于这个过程是在编译过程中完成的，因此要求输入n必须是在编译期间就能确定，不能动态输入。这是该方法最大的缺点。而且编译器对递归编译代码的递归深度是有限制的，也就是要求n不能太大。

Java实现：下面的实现是仿照上面第一种的想法实现的但是在java中行不通，因为Temp[] t = new Temp[n]; 并不能调用相应的构造函数而第二种方法的!!i在java中也是不允许的所以在java中暂时还没找到方法

public class Test61 {

public static void main(String[] args) {

System.out.println(solution(10));

}

public static int solution( int n) {

Temp.reset();

Temp[] t = new Temp[n];

return Temp.getSum();

}

class Temp {

public static int sum = 0;

public static int N = 0;

public Temp() {

super();

++N;

sum += N;

}

public static int getSum(){

return sum;

}

public static void reset(){

N = 0;

sum = 0;

}

62、题目：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

例如：如果输入如下矩阵：

1              2              3              4
5              6              7              8
9              10           11           12
13           14           15           16

则依次打印出数字1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10。

public class Test62 {

public static void printArray(int[][] a) {

int col = a.length-1;

int row = a[0].length-1;

int left = 0;

int top = 0;

while(left <= row && top <= col ) {

for (int i = left; i <= row; i++) {

System.out.print(a[top][i] + " ");

}

top ++ ;

for (int i = top; i <= col; i++) {

System.out.print(a[i][row] + " ");

}

row --;

for (int i = row; i >= left ; i--) {

System.out.print(a[col][i] + " ");

}

col --;

for (int i = col; i >= top; i--) {

System.out.print(a[i][left] + " ");

}

left++;

}

public static void main(String[] args) {

printArray(new int[][]{

{4,5,6,7},

{2,1,3,7},

{6,5,8,2},

{4,2,8,6},

{7,5,8,1}});

}

63、题目：输入一个字符串，输出该字符串中对称的子字符串的最大长度。比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。

public class Test63 {

public static int getSymmetrySonLength(String str) {

int len = 1;

char[] c = str.toCharArray();

for (int i = 0; i < c.length; i++) {

int n = 1;

while(i>=(n-1) && i+n < c.length && c[i+n] == c[i-(n-1)]) {

n++;

}

if(len < (n-1) * 2 ) {

len = (n-1) * 2;

}

return len;

}

public static void main(String[] args) {

System.out.println(getSymmetrySonLength("lgooge"));

}

64、题目：从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2-10为数字本身，A为1，J为11，Q为12，K为13，而大小王可以看成任意数字。

分析：我们需要把扑克牌的背景抽象成计算机语言。不难想象，我们可以把5张牌看成由5个数字组成的数组。大小王是特殊的数字，我们不妨把它们都当成0，这样和其他扑克牌代表的数字就不重复了。

接下来我们来分析怎样判断5个数字是不是连续的。最直观的是，我们把数组排序。但值得注意的是，由于0可以当成任意数字，我们可以用0去补满数组中的空缺。也就是排序之后的数组不是连续的，即相邻的两个数字相隔若干个数字，但如果我们有足够的0可以补满这两个数字的空缺，这个数组实际上还是连续的。举个例子，数组排序之后为{0，1，3，4，5}。在1和3之间空缺了一个2，刚好我们有一个0，也就是我们可以它当成2去填补这个空缺。

于是我们需要做三件事情：把数组排序，统计数组中0的个数，统计排序之后的数组相邻数字之间的空缺总数。如果空缺的总数小于或者等于0的个数，那么这个数组就是连续的；反之则不连续。最后，我们还需要注意的是，如果数组中的非0数字重复出现，则该数组不是连续的。换成扑克牌的描述方式，就是如果一副牌里含有对子，则不可能是顺子。

Java实现：

import java.util.Arrays;

public class Test64 {

public final static int W = 0;

public final static int A = 1;

public final static int J = 11;

public final static int Q = 12;

public final static int K = 13;

public static boolean isSequence(int[] a ) {

Arrays.sort(a);

int Wnum = 0;

int kong = 0;

for (int i = 0; i < a.length; i++) {

if(a[i] == W){

Wnum ++ ;

}else {

if(i <a.length-1 ) {

if(a[i] == a[i+1]) {

return false;

}else if(a[i]+1 != a[i+1]) {

kong++;

}

if(Wnum >= kong){

return true;

}

return false;

}

public static void main(String[] args) {

int[] a = {8,6,W,3,5,W};

System.out.println(isSequence(a));

}

65、题目：用递归颠倒一个栈。例如输入栈{1, 2, 3, 4, 5}，1在栈顶。颠倒之后的栈为{5, 4, 3, 2, 1}，5处在栈顶。

分析：考虑怎么递归。我们把栈{1, 2, 3, 4, 5}看成由两部分组成：栈顶元素1和剩下的部分{2, 3, 4, 5}。如果我们能把{2, 3, 4, 5}颠倒过来，变成{5, 4, 3, 2}，然后在把原来的栈顶元素1放到底部，那么就整个栈就颠倒过来了，变成{5, 4, 3, 2, 1}。

接下来我们需要考虑两件事情：一是如何把{2, 3, 4, 5}颠倒过来变成{5, 4, 3, 2}。我们只要把{2, 3, 4, 5}看成由两部分组成：栈顶元素2和剩下的部分{3, 4, 5}。我们只要把{3, 4, 5}先颠倒过来变成{5, 4, 3}，然后再把之前的栈顶元素2放到最底部，也就变成了{5, 4, 3, 2}。

至于怎么把{3, 4, 5}颠倒过来……很多读者可能都想到这就是递归。也就是每一次试图颠倒一个栈的时候，现在栈顶元素pop出来，再颠倒剩下的元素组成的栈，最后把之前的栈顶元素放到剩下元素组成的栈的底部。递归结束的条件是剩下的栈已经空了。这种思路的代码如下：

template<typename T> void ReverseStack(std::stack<T>& stack)

{

if(!stack.empty())

{

T top = stack.top();

stack.pop();

ReverseStack(stack);

AddToStackBottom(stack, top);

}

我们需要考虑的另外一件事情是如何把一个元素e放到一个栈的底部，也就是如何实现AddToStackBottom。这件事情不难，只需要把栈里原有的元素逐一pop出来。当栈为空的时候，push元素e进栈，此时它就位于栈的底部了。然后再把栈里原有的元素按照pop相反的顺序逐一push进栈。

注意到我们在push元素e之前，我们已经把栈里原有的所有元素都pop出来了，我们需要把它们保存起来，以便之后能把他们再push回去。我们当然可以开辟一个数组来做，但这没有必要。由于我们可以用递归来做这件事情，而递归本身就是一个栈结构。我们可以用递归的栈来保存这些元素。

基于如上分析，我们可以写出AddToStackBottom的代码：

template<typename T> void AddToStackBottom(std::stack<T>& stack, T t)

{

if(stack.empty())

{

stack.push(t);

}

else

{

T top = stack.top();

stack.pop();

AddToStackBottom(stack, t);

stack.push(top);

}

Java实现：

import java.util.Stack;

public class Test65 {

public void reverseStack(Stack<Integer> stack) {

if(!stack.isEmpty()) {

int top = stack.pop();

//将除头元素外剩下的元素进行翻转

reverseStack(stack);

//将头元素放在最下面完成所有的元素翻转

addToStackBottom(stack, top);

}

private void addToStackBottom(Stack<Integer> stack, int t) {

if(stack.isEmpty()) {

//将t放在栈底

stack.push(t);

}else{

//将栈里的元素暂存在递归的栈中当push(t)后再放回原来的位置

int top = stack.pop();

addToStackBottom(stack, t);

stack.push(top);

}

public static void main(String[] args) {

Stack<Integer> stack = new Stack<Integer>();

stack.push(4);

stack.push(3);

stack.push(5);

stack.push(1);

new Test66().reverseStack(stack);

while(!stack.isEmpty()){

System.out.print(stack.pop() + " ");

}

System.out.println();

}

66、题目：输入数字n，按顺序输出从1最大的n位10进制数。比如输入3，则输出1、2、3一直到最大的3位数即999。

分析：

最容易想到的方法是先求出最大的n位数是什么，然后用一个循环从1开始逐个输出。很快，我们就能写出如下代码：

// Print numbers from 1 to the maximum number with n digits, in order

void Print1ToMaxOfNDigits_1(int n)

{

// calculate 10^n

int number = 1;

int i = 0;

while(i++ < n)

number *= 10;

// print from 1 to (10^n - 1)

for(i = 1; i < number; ++i)

printf("%d\t", i);

}

初看之下，好像没有问题。但如果我们仔细分析这个问题，就能注意到这里没有规定n的范围，当我们求最大的n位数的时候，是不是有可能用整型甚至长整型都会溢出？

分析到这里，我们很自然的就想到我们需要表达一个大数。最常用的也是最容易实现的表达大数的方法是用字符串或者整型数组（当然不一定是最有效的）。

用字符串表达数字的时候，最直观的方法就是字符串里每个字符都是’0’到’9’之间的某一个字符，表示数字中的某一位。因为数字最大是n位的，因此我们需要一个n+1位字符串（最后一位为结束符号’\0’）。当实际数字不够n位的时候，在字符串的前半部分补零。这样，数字的个位永远都在字符串的末尾（除去结尾符号）。

首先我们把字符串中每一位数字都初始化为’0’。然后每一次对字符串表达的数字加1，再输出。因此我们只需要做两件事：一是在字符串表达的数字上模拟加法。另外我们要把字符串表达的数字输出。值得注意的是，当数字不够n位的时候，我们在数字的前面补零。输出的时候这些补位的0不应该输出。比如输入3的时候，那么数字98以098的形式输出，就不符合我们的习惯了。

基于上述分析，我们可以写出如下代码：

void Print1ToMaxOfNDigits_2(int n)

{

if(n <= 0)

return;

char *number = new char[n + 1];

memset(number, '0', n);

number[n] = '\0';

while(!Increment(number))

{

PrintNumber(number);

}

delete []number;

}

bool Increment(char* number)

{

bool isOverflow = false;

int nTakeOver = 0;

int nLength = strlen(number);

for(int i = nLength - 1; i >= 0; i --)

{

int nSum = number[i] - '0' + nTakeOver;

if(i == nLength - 1)

nSum ++;

if(nSum >= 10)

{

if(i == 0)

isOverflow = true;

else

{

nSum -= 10;

nTakeOver = 1;

number[i] = '0' + nSum;

}

else

{

number[i] = '0' + nSum;

break;

}

return isOverflow;

}

void PrintNumber(char* number)

{

bool isBeginning0 = true;

int nLength = strlen(number);

for(int i = 0; i < nLength; ++ i)

{

if(isBeginning0 && number[i] != '0')

isBeginning0 = false;

if(!isBeginning0)

{

printf("%c", number[i]);

}

printf("\t");

}

第二种思路基本上和第一种思路相对应，只是把一个整型数值换成了字符串的表示形式。同时，值得提出的是，判断打印是否应该结束时，我没有调用函数strcmp比较字符串number和”99…999”（n个9）。这是因为strcmp的时间复杂度是O(n)，而判断是否溢出的平均时间复杂度是O(1)。

第二种思路虽然比较直观，但由于模拟了整数的加法，代码有点长。要在面试短短几十分钟时间里完整正确写出这么长代码，不是件容易的事情。接下来我们换一种思路来考虑这个问题。如果我们在数字前面补0的话，就会发现n位所有10进制数其实就是n个从0到9的全排列。也就是说，我们把数字的每一位都从0到9排列一遍，就得到了所有的10进制数。只是我们在输出的时候，数字排在前面的0我们不输出罢了。

全排列用递归很容易表达，数字的每一位都可能是0到9中的一个数，然后设置下一位。递归结束的条件是我们已经设置了数字的最后一位。

void Print1ToMaxOfNDigits_3(int n)

{

if(n <= 0)

return;

char* number = new char[n + 1];

number[n] = '\0';

for(int i = 0; i < 10; ++i)

{

number[0] = i + '0';

Print1ToMaxOfNDigitsRecursively(number, n, 0);

}

delete[] number;

}

void Print1ToMaxOfNDigitsRecursively(char* number, int length, int index)

{

if(index == length - 1)

{

PrintNumber(number);

return;

}

for(int i = 0; i < 10; ++i)

{

number[index + 1] = i + '0';

Print1ToMaxOfNDigitsRecursively(number, length, index + 1);

}

函数PrintNumber和前面第二种思路中的一样，这里就不重复了。对比这两种思路，我们可以发现，递归能够用很简洁的代码来解决问题。

Java实现：

public class Test66 {

public void print1ToMaxOfNDigits(int n) {

char[] c = new char[n];

for (int i = 0; i < 10; i++) {

c[0] = (char)(i + '0');

Print1ToMaxOfNDigitsRecursively(c,n,0);

}

private void Print1ToMaxOfNDigitsRecursively(char[] c, int n, int index) {

if(index == n-1) {

print(c);

return ;

}

for(int i = 0; i < 10; ++i) {

c[index + 1] = (char)(i + '0');

Print1ToMaxOfNDigitsRecursively(c, n, index + 1);

}

private void print(char[] c) {

String str = new String(c);

for (int i = 0; i < str.length(); i++) {

if(str.charAt(i) != '0'){

str = str.substring(i);

break;

}

System.out.println(str);

}

public static void main(String[] args) {

new Test67().print1ToMaxOfNDigits(4);

}

67、题目：我们把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第1500个丑数。

所谓一个数m是另一个数n的因子，是指n能被m整除，也就是n % m == 0。根据丑数的定义，丑数只能被2、3和5整除。也就是说如果一个数如果它能被2整除，我们把它连续除以2；如果能被3整除，就连续除以3；如果能被5整除，就除以连续5。如果最后我们得到的是1，那么这个数就是丑数，否则不是。

基于前面的分析，我们可以写出如下的函数来判断一个数是不是丑数：

bool IsUgly(int number)

{

while(number % 2 == 0)

number /= 2;

while(number % 3 == 0)

number /= 3;

while(number % 5 == 0)

number /= 5;

return (number == 1) ? true : false;

}

接下来，我们只需要按顺序判断每一个整数是不是丑数，即：

int GetUglyNumber_Solution1(int index)

{

if(index <= 0)

return 0;

int number = 0;

int uglyFound = 0;

while(uglyFound < index)

{

++number;

if(IsUgly(number))

{

++uglyFound;

}

return number;

}

我们只需要在函数GetUglyNumber_Solution1中传入参数1500，就能得到第1500个丑数。该算法非常直观，代码也非常简洁，但最大的问题我们每个整数都需要计算。即使一个数字不是丑数，我们还是需要对它做求余数和除法操作。因此该算法的时间效率不是很高。

接下来我们换一种思路来分析这个问题，试图只计算丑数，而不在非丑数的整数上花费时间。根据丑数的定义，丑数应该是另一个丑数乘以2、3或者5的结果（1除外）。因此我们可以创建一个数组，里面的数字是排好序的丑数。里面的每一个丑数是前面的丑数乘以2、3或者5得到的。

这种思路的关键在于怎样确保数组里面的丑数是排好序的。我们假设数组中已经有若干个丑数，排好序后存在数组中。我们把现有的最大丑数记做M。现在我们来生成下一个丑数，该丑数肯定是前面某一个丑数乘以2、3或者5的结果。我们首先考虑把已有的每个丑数乘以2。在乘以2的时候，能得到若干个结果小于或等于M的。由于我们是按照顺序生成的，小于或者等于M肯定已经在数组中了，我们不需再次考虑；我们还会得到若干个大于M的结果，但我们只需要第一个大于M的结果，因为我们希望丑数是按从小到大顺序生成的，其他更大的结果我们以后再说。我们把得到的第一个乘以2后大于M的结果，记为M₂。同样我们把已有的每一个丑数乘以3和5，能得到第一个大于M的结果M₃和M₅。那么下一个丑数应该是M₂、M₃和M₅三个数的最小者。

前面我们分析的时候，提到把已有的每个丑数分别都乘以2、3和5，事实上是不需要的，因为已有的丑数是按顺序存在数组中的。对乘以2而言，肯定存在某一个丑数T₂，排在它之前的每一个丑数乘以2得到的结果都会小于已有最大的丑数，在它之后的每一个丑数乘以2得到的结果都会太大。我们只需要记下这个丑数的位置，同时每次生成新的丑数的时候，去更新这个T₂。对乘以3和5而言，存在着同样的T₃和T₅。

有了这些分析，我们不难写出如下的代码：

int GetUglyNumber_Solution2(int index)

{

if(index <= 0)

return 0;

int *pUglyNumbers = new int[index];

pUglyNumbers[0] = 1;

int nextUglyIndex = 1;

int *pMultiply2 = pUglyNumbers;

int *pMultiply3 = pUglyNumbers;

int *pMultiply5 = pUglyNumbers;

while(nextUglyIndex < index)

{

int min = Min(*pMultiply2 * 2, *pMultiply3 * 3, *pMultiply5 * 5);

pUglyNumbers[nextUglyIndex] = min;

while(*pMultiply2 * 2 <= pUglyNumbers[nextUglyIndex])

++pMultiply2;

while(*pMultiply3 * 3 <= pUglyNumbers[nextUglyIndex])

++pMultiply3;

while(*pMultiply5 * 5 <= pUglyNumbers[nextUglyIndex])

++pMultiply5;

++nextUglyIndex;

}

int ugly = pUglyNumbers[nextUglyIndex - 1];

delete[] pUglyNumbers;

return ugly;

}

int Min(int number1, int number2, int number3)

{

int min = (number1 < number2) ? number1 : number2;

min = (min < number3) ? min : number3;

return min;

}

和第一种思路相比，这种算法不需要在非丑数的整数上做任何计算，因此时间复杂度要低很多。感兴趣的读者可以分别统计两个函数GetUglyNumber_Solution1(1500)和GetUglyNumber_Solution2(1500)的运行时间。当然我们也要指出，第二种算法由于要保存已经生成的丑数，因此需要一个数组，从而需要额外的内存。第一种算法是没有这样的内存开销的。

68、题目：给定链表的头指针和一个结点指针，在O(1)时间删除该结点。链表结点的定义如下：

struct ListNode

{

int m_nKey;

ListNode* m_pNext;

};

函数的声明如下：

void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);

详见编程之美其实就是将这个要删除的节点的下一个节点删掉再将下一个的值给要删除的节点完成逻辑上的删除

69. 题目：输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求时间复杂度为O(n)。

分析：如果不考虑时间复杂度，最简单的思路应该是从头扫描这个数组，每碰到一个偶数时，拿出这个数字，并把位于这个数字后面的所有数字往前挪动一位。挪完之后在数组的末尾有一个空位，这时把该偶数放入这个空位。由于碰到一个偶数，需要移动O(n)个数字，因此总的时间复杂度是O(n^２)。

要求的是把奇数放在数组的前半部分，偶数放在数组的后半部分，因此所有的奇数应该位于偶数的前面。也就是说我们在扫描这个数组的时候，如果发现有偶数出现在奇数的前面，我们可以交换他们的顺序，交换之后就符合要求了。

因此我们可以维护两个指针，第一个指针初始化为数组的第一个数字，它只向后移动；第二个指针初始化为数组的最后一个数字，它只向前移动。在两个指针相遇之前，第一个指针总是位于第二个指针的前面。如果第一个指针指向的数字是偶数而第二个指针指向的数字是奇数，我们就交换这两个数字。

基于这个思路，我们可以写出如下的代码：

void Reorder(int *pData, unsigned int length, bool (*func)(int));
bool isEven(int n);
void ReorderOddEven(int *pData, unsigned int length)
{
      if(pData == NULL || length == 0)
            return;
      Reorder(pData, length, isEven);
}
void Reorder(int *pData, unsigned int length, bool (*func)(int))
{
      if(pData == NULL || length == 0)
            return;
      int *pBegin = pData;
      int *pEnd = pData + length - 1;
      while(pBegin < pEnd)
      {
            // if *pBegin does not satisfy func, move forward
            if(!func(*pBegin))
            {
                  pBegin ++;
                  continue;
            }
            // if *pEnd does not satisfy func, move backward
            if(func(*pEnd))
            {
                  pEnd --;
                  continue;
            }
            // if *pBegin satisfy func while *pEnd does not,
            // swap these integers
            int temp = *pBegin;
            *pBegin = *pEnd;
            *pEnd = temp;
      }
}
bool isEven(int n)
{
      return (n & 1) == 0;
}

讨论：

上面的代码有三点值得提出来和大家讨论：

１．函数isEven判断一个数字是不是偶数并没有用%运算符而是用&。理由是通常情况下位运算符比%要快一些；

２．这道题有很多变种。这里要求是把奇数放在偶数的前面，如果把要求改成：把负数放在非负数的前面等，思路都是都一样的。

３．在函数Reorder中，用函数指针func指向的函数来判断一个数字是不是符合给定的条件，而不是用在代码直接判断（hard code）。这样的好处是把调整顺序的算法和调整的标准分开了（即解耦，decouple）。当调整的标准改变时，Reorder的代码不需要修改，只需要提供一个新的确定调整标准的函数即可，提高了代码的可维护性。例如要求把负数放在非负数的前面，我们不需要修改Reorder的代码，只需添加一个函数来判断整数是不是非负数。这样的思路在很多库中都有广泛的应用，比如在ＳＴＬ的很多算法函数中都有一个仿函数（functor）的参数（当然仿函数不是函数指针，但其思想是一样的）。如果在面试中能够想到这一层，无疑能给面试官留下很好的印象。

Java实现:

public class Test69 {

public void reorder(int[] a) {

int start = 0;

int end = a.length-1;

int i = 0;

int j = a.length-1;

while(start < end) {

for (; i < end; i++) {

if(isEvent(a[i])) {

start = i;

i++;

break;

}

for (; j > start; j--) {

if(!isEvent(a[j])) {

end = j;

j--;

break;

}

if(i > j) {

return;

}

swap(a,start,end);

start ++ ;

end--;

}

private void swap(int[] a, int start, int end) {

int temp = a[start];

a[start] = a[end];

a[end] = temp;

}

/**判断是不是偶数是的话就返回true**/

private boolean isEvent(int i) {

return (i & 1)== 0;

}

public static void main(String[] args) {

int[] a = {2,5,6,8,1,4,7,9,6,14,13,12};

new Test69().reorder(a);

for (int i = 0; i < a.length; i++) {

System.out.print(a[i] + " ");

}

70、题目：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如输入12，从1到12这些整数中包含1 的数字有1，10，11和12，1一共出现了5次。

分析：

觉得可以一位一位考虑，对于10^b位：如12345的第5位：
1)此位大于1，这一位上1的个数有 1234+ 1种
2)此位等于0，为 1234种
3)此位等于1，在0的基础上加上1234 +1种

public class Test70 {

int num_of_1(int n)

{

int pows[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 100000000};

int b = 0, count = 0;

while(n >= pows[b]){

switch( (n % pows[b+1]) / pows[b]){

case 0:

count += (n / pows[b + 1]) * pows[b];

break;

case 1:

count += (n / pows[b + 1]) * pows[b];

count += n % pows[b] + 1;

break;

default:

count += (n / pows[b + 1] + 1) * pows[b];

}

b++;

}

return count;

}

public static void main(String[] args) {

System.out.println(new Test70().num_of_1(12));

}

71、题目：一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。求总共有多少总跳法，并分析算法的时间复杂度。

首先我们考虑最简单的情况。如果只有1级台阶，那显然只有一种跳法。如果有2级台阶，那就有两种跳的方法了：一种是分两次跳，每次跳1级；另外一种就是一次跳2级。

现在我们再来讨论一般情况。我们把n级台阶时的跳法看成是n的函数，记为f(n)。当n>2时，第一次跳的时候就有两种不同的选择：一是第一次只跳1级，此时跳法数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1)；另外一种选择是第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2)。因此n级台阶时的不同跳法的总数f(n)=f(n-1)+(f-2)。

我们把上面的分析用一个公式总结如下：

        /  1                         n=1
f(n)=      2                          n=2
        \  f(n-1)+(f-2)               n>2

分析到这里，相信很多人都能看出这就是我们熟悉的Fibonacci序列。至于怎么求这个序列的第n项

72、题目：输入一个整数，求该整数的二进制表达中有多少个1。例如输入10，由于其二进制表示为1010，有两个1，因此输出2。

public class Test71 {

public int num2_of_1(int n) {

int count =0;

while(n>0) {

if((n & 1) == 1){

count ++ ;

}

n = n >> 1;

}

return count;

}

public static void main(String[] args) {

System.out.println(new Test71().num2_of_1(10));

}

这个思路当输入i是正数时没有问题，但当输入的i是一个负数时，不但不能得到正确的1的个数，还将导致死循环。以负数0x80000000为例，右移一位的时候，并不是简单地把最高位的1移到第二位变成0x40000000，而是0xC0000000。这是因为移位前是个负数，仍然要保证移位后是个负数，因此移位后的最高位会设为1。如果一直做右移运算，最终这个数字就会变成0xFFFFFFFF而陷入死循环。为了避免死循环，我们可以不右移输入的数字i。首先i和1做与运算，判断i的最低位是不是为1。接着把1左移一位得到2，再和i做与运算，就能判断i的次高位是不是1……这样反复左移，每次都能判断i的其中一位是不是1

public int num2_of_1_new(int n) {

int count =0;

int t = 1;

while(t !=0 ) {

if((n & t) == 1){

count ++ ;

}

t = t << 1;

}

return count;

}

另外一种思路是如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减去1，那么原来处在整数最右边的1就会变成0，原来在1后面的所有的0都会变成1。其余的所有位将不受到影响。举个例子：一个二进制数1100，从右边数起的第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成1，而前面的1保持不变，因此得到结果是1011。

我们发现减1的结果是把从最右边一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000。也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0。那么一个整数的二进制有多少个1，就可以进行多少次这样的操作

public int numberOf1_Solution(int i) {

int count = 0;

while (i != 0)

{

++ count;

i = (i - 1) & i;

}

return count;

}

73、题目：输入一个正整数数组，将它们连接起来排成一个数，输出能排出的所有数字中最小的一个。例如输入数组{32, 321}，则输出这两个能排成的最小数字32132。请给出解决问题的算法，并证明该算法。

这道题其实是希望我们能找到一个排序规则，根据这个规则排出来的数组能排成一个最小的数字。要确定排序规则，就得比较两个数字，也就是给出两个数字m和n，我们需要确定一个规则m和n哪个更大，而不是仅仅只是比较这两个数字的数值哪个更大。

根据题目的要求，两个数字m和n排成的数字mn和nm，如果mn<nm，那么我们应该输出mn，也就是m应该排在n的前面，也就是m小于n；反之，如果nm<mn，n小于m。如果mn==mn，m等于n。

接下来我们考虑怎么去拼接数字，即给出数字m和n，怎么得到数字mn和nm并比较它们的大小。直接用数值去计算不难办到，但需要考虑到的一个潜在问题是m和n都在int能表达的范围内，但把它们拼起来的数字mn和nm就不一定能用int表示了。所以我们需要解决大数问题。一个非常直观的方法就是把数字转换成字符串。

另外，由于把数字m和n拼接起来得到的mn和nm，它们所含有的数字的个数肯定是相同的。因此比较它们的大小只需要按照字符串大小的比较规则就可以了。

基于这个思路，我们可以写出下面的代码：

const int g_MaxNumberLength = 10;

char* g_StrCombine1 = new char[g_MaxNumberLength * 2 + 1];

char* g_StrCombine2 = new char[g_MaxNumberLength * 2 + 1];

void PrintMinNumber(int* numbers, int length)

{

if(numbers == NULL || length <= 0)

return;

char** strNumbers = (char**)(new int[length]);

for(int i = 0; i < length; ++i)

{

strNumbers[i] = new char[g_MaxNumberLength + 1];

sprintf(strNumbers[i], "%d", numbers[i]);

}

qsort(strNumbers, length, sizeof(char*), compare);

for(int i = 0; i < length; ++i)

printf("%s", strNumbers[i]);

printf("\n");

for(int i = 0; i < length; ++i)

delete[] strNumbers[i];

delete[] strNumbers;

}

int compare(const void* strNumber1, const void* strNumber2)

{

strcpy(g_StrCombine1, *(const char**)strNumber1);

strcat(g_StrCombine1, *(const char**)strNumber2);

strcpy(g_StrCombine2, *(const char**)strNumber2);

strcat(g_StrCombine2, *(const char**)strNumber1);

return strcmp(g_StrCombine1, g_StrCombine2);

}

上述代码中，我们在函数compare中定义比较规则，并根据该规则用库函数qsort排序。最后把排好序的数组输出，就得到了根据数组排成的最小的数字。

找到一个算法解决这个问题，不是一件容易的事情。但更困难的是我们需要证明这个算法是正确的。接下来我们来试着证明。

首先我们需要证明之前定义的比较两个数字大小的规则是有效的。一个有效的比较需要三个条件：1.自反性，即a等于a；2.对称性，即如果a大于b，则b小于a；3.传递性，即如果a小于b，b小于c，则a小于c。现在分别予以证明。

自反性。显然有aa=aa，所以a=a。

2. 对称性。如果a小于b，则ab<ba，所以ba>ab。因此b大于a。

3. 传递性。如果a小于b，则ab<ba。当a和b用十进制表示的时候分别为l位和m位时，ab=a×10^m+b，ba=b×10^l+a。所以a×10^m+b<b×10^l+a。于是有a×10^m-a< b×10^l –b，即a(10^m -1)<b(10^l-1)。所以a/(10^l -1)<b/(10^m -1)。

如果b小于c，则bc<cb。当c表示成十进制时为m位。和前面证明过程一样，可以得到b/(10^m -1)<c/(10ⁿ -1)。

所以a/(10^l -1)< c/(10ⁿ -1)。于是a(10ⁿ -1)<c(10^l -1)，所以a×10ⁿ +c<c×10^l +a，即ac<ca。

所以a小于c。

在证明了我们排序规则的有效性之后，我们接着证明算法的正确性。我们用反证法来证明。

我们把n个数按照前面的排序规则排好顺序之后，表示为A₁A₂A₃…A_n。我们假设这样排出来的两个数并不是最小的。即至少存在两个x和y（0<x<y<n），交换第x个数和地y个数后，A₁A₂…A_y…A_x…A_n<A₁A₂…A_x…A_y…A_n。

由于A₁A₂…A_x…A_y…A_n是按照前面的规则排好的序列，所以有A_x<A_x+1<A_x+2<…<A_y-2<A_y-1<A_y。

由于A_y-1小于A_y，所以A_y-1A_y<A_yA_y-1。我们在序列A₁A₂…A_x…A_y-1A_y…A_n交换A_y-1和A_y，有A₁A₂…A_x…A_y-1A_y…A_n<A₁A₂…A_x…A_yA_y-1…A_n（这个实际上也需要证明。感兴趣的读者可以自己试着证明）。我们就这样一直把A_y和前面的数字交换，直到和A_x交换为止。于是就有A₁A₂…A_x…A_y-1A_y…A_n<A₁A₂…A_x…A_yA_y-1…A_n< A₁A₂…A_x…A_yA_y-2A_y-1…A_n<…< A₁A₂…A_yA_x…A_y-2A_y-1…A_n。

同理由于A_x小于A_x+1，所以A_xA_x+1<A_x+1A_x。我们在序列A₁A₂…A_yA_xA_x+1…A_y-2A_y-1…A_n仅仅只交换A_x和A_x+1，有A₁A₂…A_yA_xA_x+1…A_y-2A_y-1…A_n<A₁A₂…A_yA_x+1A_x…A_y-2A_y-1…A_n。我们接下来一直拿A_x和它后面的数字交换，直到和A_y-1交换为止。于是就有A₁A₂…A_yA_xA_x+1…A_y-2A_y-1…A_n<A₁A₂…A_yA_x+1A_x…A_y-2A_y-1…A_n<…< A₁A₂…A_yA_x+1A_x+2…A_y-2A_y-1A_x…A_n。

所以A₁A₂…A_x…A_y…A_n< A₁A₂…A_y…A_x…A_n。这和我们的假设的A₁A₂…A_y…A_x…A_n <A₁A₂…A_x…A_y…A_n相矛盾。

所以假设不成立，我们的算法是正确的。

74、题目：二叉树的结点定义如下：

struct TreeNode

{

int m_nvalue;

TreeNode* m_pLeft;

TreeNode* m_pRight;

};

输入二叉树中的两个结点，输出这两个结点在数中最低的共同父结点。

所谓共同的父结点，就是两个结点都出现在这个结点的子树中。因此我们可以定义一函数，来判断一个结点的子树中是不是包含了另外一个结点。这不是件很难的事，我们可以用递归的方法来实现：

bool HasNode(TreeNode* pHead, TreeNode* pNode)

{

if(pHead == pNode)

return true;

bool has = false;

if(pHead->m_pLeft != NULL)

has = HasNode(pHead->m_pLeft, pNode);

if(!has && pHead->m_pRight != NULL)

has = HasNode(pHead->m_pRight, pNode);

return has;

}

我们可以从根结点开始，判断以当前结点为根的树中左右子树是不是包含我们要找的两个结点。如果两个结点都出现在它的左子树中，那最低的共同父结点也出现在它的左子树中。如果两个结点都出现在它的右子树中，那最低的共同父结点也出现在它的右子树中。如果两个结点一个出现在左子树中，一个出现在右子树中，那当前的结点就是最低的共同父结点。基于这个思路，我们可以写出如下代码：

TreeNode* LastCommonParent_1(TreeNode* pHead, TreeNode* pNode1, TreeNode* pNode2)

{

if(pHead == NULL || pNode1 == NULL || pNode2 == NULL)

return NULL;

// check whether left child has pNode1 and pNode2

bool leftHasNode1 = false;

bool leftHasNode2 = false;

if(pHead->m_pLeft != NULL)

{

leftHasNode1 = HasNode(pHead->m_pLeft, pNode1);

leftHasNode2 = HasNode(pHead->m_pLeft, pNode2);

}

if(leftHasNode1 && leftHasNode2)

{

if(pHead->m_pLeft == pNode1 || pHead->m_pLeft == pNode2)

return pHead;

return LastCommonParent_1(pHead->m_pLeft, pNode1, pNode2);

}

// check whether right child has pNode1 and pNode2

bool rightHasNode1 = false;

bool rightHasNode2 = false;

if(pHead->m_pRight != NULL)

{

if(!leftHasNode1)

rightHasNode1 = HasNode(pHead->m_pRight, pNode1);

if(!leftHasNode2)

rightHasNode2 = HasNode(pHead->m_pRight, pNode2);

}

if(rightHasNode1 && rightHasNode2)

{

if(pHead->m_pRight == pNode1 || pHead->m_pRight == pNode2)

return pHead;

return LastCommonParent_1(pHead->m_pRight, pNode1, pNode2);

}

if((leftHasNode1 && rightHasNode2)

|| (leftHasNode2 && rightHasNode1))

return pHead;

return NULL;

}

接着我们来分析一下这个方法的效率。函数HasNode的本质就是遍历一棵树，其时间复杂度是O(n)（n是树中结点的数目）。由于我们根结点开始，要对每个结点调用函数HasNode。因此总的时间复杂度是O(n²)。

我们仔细分析上述代码，不难发现我们判断以一个结点为根的树是否含有某个结点时，需要遍历树的每个结点。接下来我们判断左子结点或者右结点为根的树中是否含有要找结点，仍然需要遍历。第二次遍历的操作其实在前面的第一次遍历都做过了。由于存在重复的遍历，本方法在时间效率上肯定不是最好的。

前面我们提过如果结点中有一个指向父结点的指针，我们可以把问题转化为求两个链表的共同结点。现在我们可以想办法得到这个链表。

bool GetNodePath(TreeNode* pHead, TreeNode* pNode, std::list<TreeNode*>& path)

{

if(pHead == pNode)

return true;

path.push_back(pHead);

bool found = false;

if(pHead->m_pLeft != NULL)

found = GetNodePath(pHead->m_pLeft, pNode, path);

if(!found && pHead->m_pRight)

found = GetNodePath(pHead->m_pRight, pNode, path);

if(!found)

path.pop_back();

return found;

}

由于这个路径是从跟结点开始的。最低的共同父结点就是路径中的最后一个共同结点：

TreeNode* LastCommonNode

(

const std::list<TreeNode*>& path1,

const std::list<TreeNode*>& path2

)

{

std::list<TreeNode*>::const_iterator iterator1 = path1.begin();

std::list<TreeNode*>::const_iterator iterator2 = path2.begin();

TreeNode* pLast = NULL;

while(iterator1 != path1.end() && iterator2 != path2.end())

{

if(*iterator1 == *iterator2)

pLast = *iterator1;

iterator1++;

iterator2++;

}

return pLast;

}

有了前面两个子函数之后，求两个结点的最低共同父结点就很容易了。我们先求出从根结点出发到两个结点的两条路径，再求出两条路径的最后一个共同结点。代码如下：

TreeNode* LastCommonParent_2(TreeNode* pHead, TreeNode* pNode1, TreeNode* pNode2)

{

if(pHead == NULL || pNode1 == NULL || pNode2 == NULL)

return NULL;

std::list<TreeNode*> path1;

GetNodePath(pHead, pNode1, path1);

std::list<TreeNode*> path2;

GetNodePath(pHead, pNode2, path2);

return LastCommonNode(path1, path2);

}

这种思路的时间复杂度是O(n)，时间效率要比第一种方法好很多。但同时我们也要注意到，这种思路需要两个链表来保存路径，空间效率比不上第一个方法。

75、题目：把n个骰子扔在地上，所有骰子朝上一面的点数之和为S。输入n，打印出S的所有可能的值出现的概率。

分析：玩过麻将的都知道，骰子一共6个面，每个面上都有一个点数，对应的数字是1到 6之间的一个数字。所以，n个骰子的点数和的最小值为n，最大值为6n。因此，一个直观的思路就是定义一个长度为6n-n的数组，和为S的点数出现的次数保存到数组第S-n个元素里。另外，我们还知道n个骰子的所有点数的排列数6^n。一旦我们统计出每一点数出现的次数之后，因此只要把每一点数出现的次数除以n^6，就得到了对应的概率。

该思路的关键就是统计每一点数出现的次数。要求出n个骰子的点数和，我们可以先把n个骰子分为两堆：第一堆只有一个，另一个有n-1个。单独的那一个有可能出现从1到6的点数。我们需要计算从1到6的每一种点数和剩下的n-1个骰子来计算点数和。接下来把剩下的n-1个骰子还是分成两堆，第一堆只有一个，第二堆有n-2个。我们把上一轮那个单独骰子的点数和这一轮单独骰子的点数相加，再和剩下的n-2个骰子来计算点数和。分析到这里，我们不难发现，这是一种递归的思路。递归结束的条件就是最后只剩下一个骰子了。

基于这种思路，我们可以写出如下代码：

int g_maxValue = 6;

void PrintSumProbabilityOfDices_1(int number)

{

if(number < 1)

return;

int maxSum = number * g_maxValue;

int* pProbabilities = new int[maxSum - number + 1];

for(int i = number; i <= maxSum; ++i)

pProbabilities[i - number] = 0;

SumProbabilityOfDices(number, pProbabilities);

int total = pow((float)g_maxValue, number);

for(int i = number; i <= maxSum; ++i)

{

float ratio = (float)pProbabilities[i - number] / total;

printf("%d: %f\n", i, ratio);

}

delete[] pProbabilities;

}

void SumProbabilityOfDices(int number, int* pProbabilities)

{

for(int i = 1; i <= g_maxValue; ++i)

SumProbabilityOfDices(number, number, i, 0, pProbabilities);

}

void SumProbabilityOfDices(int original, int current, int value, int tempSum, int* pProbabilities)

{

if(current == 1)

{

int sum = value + tempSum;

pProbabilities[sum - original]++;

}

else

{

for(int i = 1; i <= g_maxValue; ++i)

{

int sum = value + tempSum;

SumProbabilityOfDices(original, current - 1, i, sum, pProbabilities);

}

上述算法当number比较小的时候表现很优异。但由于该算法基于递归，它有很多计算是重复的，从而导致当number变大时性能让人不能接受。关于递归算法的性能讨论，详见本博客系列的第16题。

我们可以考虑换一种思路来解决这个问题。我们可以考虑用两个数组来存储骰子点数每一总数出现的次数。在一次循环中，第一个数组中的第n个数字表示骰子和为n出现的次数。那么在下一循环中，我们加上一个新的骰子。那么此时和为n的骰子出现的次数，应该等于上一次循环中骰子点数和为n-1、n-2、n-3、n-4、n-5与n-6的总和。所以我们把另一个数组的第n个数字设为前一个数组对应的第n-1、n-2、n-3、n-4、n-5与n-6之和。基于这个思路，我们可以写出如下代码：

void PrintSumProbabilityOfDices_2(int number)

{

double* pProbabilities[2];

pProbabilities[0] = new double[g_maxValue * number + 1];

pProbabilities[1] = new double[g_maxValue * number + 1];

for(int i = 0; i < g_maxValue * number + 1; ++i)

{

pProbabilities[0][i] = 0;

pProbabilities[1][i] = 0;

}

int flag = 0;

for (int i = 1; i <= g_maxValue; ++i)

pProbabilities[flag][i] = 1;

for (int k = 2; k <= number; ++k)

{

for (int i = k; i <= g_maxValue * k; ++i)

{

pProbabilities[1 - flag][i] = 0;

for(int j = 1; j <= i && j <= g_maxValue; ++j)

pProbabilities[1 - flag][i] += pProbabilities[flag][i - j];

}

flag = 1 - flag;

}

double total = pow((double)g_maxValue, number);

for(int i = number; i <= g_maxValue * number; ++i)

{

double ratio = pProbabilities[flag][i] / total;

printf("%d: %f\n", i, ratio);

}

delete[] pProbabilities[0];

delete[] pProbabilities[1];

}

值得提出来的是，上述代码没有在函数里把一个骰子的最大点数硬编码(hard code)为6，而是用一个变量g_maxValue来表示。这样做的好处时，如果某个厂家生产了最大点数为4或者8的骰子，我们只需要在代码中修改一个地方，扩展起来很方便。

Java实现：

import java.util.HashMap;

import java.util.Iterator;

import java.util.Map;

import java.util.Map.Entry;

public class Test75 {

Map<Integer, Integer> map = new HashMap<Integer, Integer>();

public void printSumProbabilityOfDices(int n) {

int sum = 0;

getSum(sum ,n);

print(n);

}

public void getSum(int sum,int n) {

if(n < 1 ) {

if(map.containsKey(sum)) {

map.put(sum, map.get(sum) + 1);

}else {

map.put(sum, 1);

}

return;

}

for (int i = 1; i <= 6; i++) {

sum = sum + i;

getSum(sum,n-1);

sum = sum - i;

}

private void print(int n){

for (Iterator iterator = map.entrySet().iterator(); iterator.hasNext();) {

Entry<Integer, Integer> type = (Entry<Integer, Integer>) iterator.next();

System.out.println("点数是" + type.getKey() + "的概率是：" + (type.getValue() / Math.pow(6, n)));

}

public static void main(String[] args) {

new Test75().printSumProbabilityOfDices(6);

}