Java算法篇—Java经典面试算法题01期
算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。
如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
【问题一】有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？
下方区域查看答案解析！
-▼-
程序分析：
兔子的规律为数列1,1,2,3,5,8,13,21....
具体分析如下：
f(1) = 1(第1个月有一对兔子）
f(2) = 1(第2个月还是一对兔子）
f(3) = 2(原来有一对兔子，第3个开始，每个月生一对兔子）
f(4) = 3(原来有两对兔子，有一对可以生育）
f(5) = 5(原来有3对兔子，第3个月出生的那对兔子也可以生育了，那么现在有两对兔子可以生育）
f(6) = 8(原来有5对兔子，第4个月出生的那对兔子也可以生育了，那么现在有3对兔子可以生育）
..............
由以上可以看出，第n个月兔子的对数为
f(n) = f(n - 1) + f(n - 2);
f(n-1)是上个月的兔子数量，是原来有的。
f(n-2)是可以生育的兔子数，即多出来的数量。第n-2个月开始后的第3个月是第n个月，此时第n-2个月时的兔子都可以生育了。
程序代码
public class Demo01 {
public static void main(String args[]) {
for (int i = 1; i <= 20; i++)
System.out.println(f(i) + " ");
}
public static int f(int x) {
if (x == 1||x == 2)
return 1;
else
return f(x - 1) + f(x - 2);
}
}
或
public class Demo011 {
public static void main(String args[]) {
math math = new math();
for (int i = 1; i <= 20; i++)
System.out.println(math.f(i) + " ");
}
}
/**
* 内部类
*/
class math {
public int f(int x) {
if (x == 1 || x == 2)
return 1;
else
return f(x - 1) + f(x - 2);
}
}
运行结果
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
【问题二】打印出所有的水仙花数 ，所谓水仙花数是指一个三位数，其各位数字立方和等于该数本身。例如：153是一个水仙花数，因为153=1的三次方＋5的三次方＋3的三次方。
下方区域查看答案解析！
-▼-
程序分析：
利用for循环控制100-999个数，每个数分解出个位，十位，百位。
程序代码
public class Demo02 {
public static void main(String args[]) {
for (int i = 100; i <= 999; i++)
if (shuixianhua(i) == true)
System.out.println(i + " ");
}
public static boolean shuixianhua(int x) {
int i = 0, j = 0, k = 0;
i = x / 100;
j = (x % 100) / 10;
k = x % 10;
if (x == i * i * i + j * j * j + k * k * k)
return true;
else
return false;
}
}
运行结果
153 370 371 407
【问题三】将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。
下方区域查看答案解析！
-▼-
程序分析：
对n进行分解质因数，应先找到一个最小的质数i，然后按下述步骤完成：
1）如果这个质数恰等于n，则说明分解质因数的过程已经结束，打印出即可。
2）如果n > i，但n能被i整除，则应打印出i的值，并用n除以i的商,作为新的正整数你,重复执行第一步。
3）如果n不能被i整除，则用i+1作为i的值,重复执行第一步。
程序代码
import java.util.Scanner;
public class Demo03 {
private static Scanner in;
public static void fenjie(int n) {
for (int i = 2; i <= n; i++) {
if (n % i == 0) {
System.out.print(i);
if(n!=i){
System.out.print("*");
}
fenjie(n/i);
}
}
System.exit(0);
}
public static void main(String[] args) {
in = new Scanner(System.in);
System.out.println("请输入N的值：");
int n = in.nextInt();
System.out.print( "分解质因数：" + n +"=");
fenjie(n);
}
}
运行结果
请输入N的值：
100
分解质因数：100=2*2*5*5
【问题四】输入一行字符，分别统计出其中英文字母、空格、数字和其它字符的个数。
下方区域查看答案解析！
-▼-
程序分析：
利用for循环语句,if条件语句。
程序代码
import java.util.Scanner;
public class Demo04 {
private static Scanner in;
private static int digital, character, blank, other;
public static void main(String[] args) {
System.out.println("请输入一个字符串");
in = new Scanner(System.in);
String str = in.nextLine();
char[] ch = str.toCharArray();
count(ch);
}
public static void count(char[] arr) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] >= '0' && arr[i] <= '9') {
digital++;
} else if ((arr[i] >= 'a' && arr[i] <= 'z')
|| (arr[i] >= 'A' && arr[i] <= 'Z')) {
character++;
} else if (arr[i] == ' ') {
blank++;
} else {
other++;
}
}
System.out.println("数字个数：" + digital);
System.out.println("英文字母个数：" + character);
System.out.println("空格个数：" + blank);
System.out.println("其他字符个数：" + other);
}
}
运行结果
请输入一个字符串
123456 blog.yoodb.com _
数字个数：6
英文字母个数：12
空格个数：2
其他字符个数：3
【问题五】输入三个整数x,y,z，请把这三个数由小到大输出。
下方区域查看答案解析！
-▼-
程序分析：
我们想办法把最小的数放到x上，先将x与y进行比较，如果x>y则将x与y的值进行交换，然后再用x与z进行比较，如果x>z则将x与z的值进行交换，这样能使x最小。
程序代码
import java.util.Arrays;
import java.util.Scanner;
public class Demo05 {
private static Scanner in;
public static void main(String[] args) {
System.out.println("请输入三个数：");
in = new Scanner(System.in);
int[] arr = new int[3];
for (int i = 0; i < 3; i++) {
arr[i] = in.nextInt();
}
Arrays.sort(arr);
for (int i=0;i<arr.length;i++) {
System.out.print(arr[i] + " ");
}
}
}
或
import java.util.Scanner;
public class Demo051 {
private static Scanner in;
public static void main(String[] args) {
System.out.println("请输入三个数：");
in = new Scanner(System.in);
int[] arr = new int[3];
for (int i = 0; i < 3; i++) {
arr[i] = in.nextInt();
}
int x = arr[0], y = arr[1], z = arr[2];
if (x > y) {
int t = x;
x = y;
y = t;
}
if (x > z) {
int t = x;
x = z;
z = t;
}
if (y > z) {
int t = y;
y = z;
z = t;
}
System.out.print(x + " " + y + " " + z);
}
}
运行结果
请输入三个数：
4
8
6
4 6 8
【问题六】猴子吃桃问题：猴子第一天摘下若干个桃子，当即吃了一半，还不瘾，又多吃了一个第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时，见只剩下一个桃子了。求第一天共摘了多少。
下方区域查看答案解析！
-▼-
程序分析：
采取逆向思维的方法，从后往前推断。
程序代码
public class Demo06 {
public static void main(String[] args) {
int sum = 1;
for (int i = 0; i < 9; i++) {
sum = (sum + 1) * 2;
}
System.out.println("第一天共摘"+sum);
}
}
运行结果
第一天共摘1534
【问题七】两个乒乓球队进行比赛，各出三人。甲队为a,b,c三人，乙队为x,y,z三人。已抽签决定比赛名单。有人向队员打听比赛的名单。a说他不和x比，c说他不和x,z比，请编程序找出三队赛手的名单。
下方区域查看答案解析！
-▼-
程序分析：
根据不同队员进行对比，如果不符合条件，遍历另一队员进行判断。
程序代码
public class Demo07 {
static char[] m = { 'a', 'b', 'c' };
static char[] n = { 'x', 'y', 'z' };
public static void main(String[] args) {
for (int i = 0; i < m.length; i++) {
for (int j = 0; j < n.length; j++) {
if (m[i] == 'a' && n[j] == 'x') {
continue;
} else if (m[i] == 'a' && n[j] == 'y') {
continue;
} else if ((m[i] == 'c' && n[j] == 'x')
|| (m[i] == 'c' && n[j] == 'z')) {
continue;
} else if ((m[i] == 'b' && n[j] == 'z')
|| (m[i] == 'b' && n[j] == 'y')) {
continue;
} else
System.out.println(m[i] + " vs " + n[j]);
}
}
}
}
或
public class Demo071 {
public String a, b, c;
public Demo071(String a, String b, String c) {
this.a = a;
this.b = b;
this.c = c;
}
public static void main(String[] args) {
Demo071 arr_a = new Demo071("a", "b", "c");
String[] b = { "x", "y", "z" };
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
Demo071 arr_b = new Demo071(b[i], b[j], b[k]);
if (!arr_b.a.equals(arr_b.b) & !arr_b.b.equals(arr_b.c)
& !arr_b.c.equals(arr_b.a) & !arr_b.a.equals("x")
& !arr_b.c.equals("x") & !arr_b.c.equals("z")) {
System.out.println(arr_a.a + " vs " + arr_b.a);
System.out.println(arr_a.b + " vs " + arr_b.b);
System.out.println(arr_a.c + " vs " + arr_b.c);
}
}
}
}
}
}
运行结果
a vs z
b vs x
c vs y
【问题八】打印出如下图案（菱形）
下方区域查看答案解析！
-▼-
程序分析：
先把图形分成两部分来看待，前四行一个规律，后三行一个规律，利用双重for循环，第一层控制行，第二层控制列。
*
***
*****
*******
*****
***
*
程序代码
public class Demo08 {
public static void main (String[]args)
{
int lay = 7;
for(int m = 1; m <=(lay+1)/2; m++)
{
for(int b = 1; b <=(lay+1)/2-m ; b++)
System.out.print(" ");
for(int c = 1; c <= m*2-1; c++)
System.out.print("*");
System.out.println();
}
for(int d =(lay+1)/2-1;d >= 1; d --)
{
for(int b = 1; b <= (lay+1)/2-d; b++)
System.out.print(" ");
for(int c = (lay+1)/2-d; c <=(lay+1)/2-2+d; c ++)
System.out.print("*");
System.out.println();
}
}
}
运行结果
*
***
*****
*******
*****
***
*
推荐阅读
Java精选
关注微信公众号“Java精选”（w_z90110），回复关键字领取资料：如Hadoop，Dubbo，CAS源码等等，免费领取资料视频和项目。
涵盖：程序人生、搞笑视频、算法与数据结构、黑客技术与网络安全、前端开发、Java、Python、Redis缓存、Spring源码、各大主流框架、Web开发、大数据技术、Storm、Hadoop、MapReduce、Spark、elasticsearch、单点登录统一认证、分布式框架、集群、安卓开发、iOS开发、C/C++、.NET、Linux、Mysql、Oracle、NoSQL非关系型数据库、运维等。