原创

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精选”(w_z90110),回复关键字领取资料:如MysqlHadoopDubboCAS源码等等,免费领取视频教程、资料文档和项目源码。

涵盖:程序人生、搞笑视频、算法与数据结构、黑客技术与网络安全、前端开发、JavaPythonRedis缓存、Spring源码、各大主流框架、Web开发、大数据技术、StormHadoopMapReduceSparkElasticSearch、单点登录统一认证、分布式框架、集群、安卓开发、iOS开发、C/C++.NETLinuxMysqlOracleNoSQL非关系型数据库、运维等。

评论

分享:

支付宝

微信