数据结构与算法面试系列-02

1. 一个整数，它加上100后是一个完全平方数，加上168又是一个完全平方数，请问该数是多少？

程序分析：在10万以内判断，先将该数加上100后再开方，再将该数加上168后再开方，如果开方后的结果满足如下条件，即是结果。请看具体分析：

程序代码如下：

package com.yoodb.util;public class Demo03 {public static void main(String[] args) {for (int i = 1; i < 1000; i++) {int m = (int) Math.sqrt((i + 100));int n = (int) Math.sqrt((i + 100 + 168));if (m * m == i + 100 && n * n == i + 100 + 168) {System.out.println("这个数是" + i);}}}
}

运行结果如下：

这个数是21
这个数是261

2. 输入某年某月某日，判断这一天是这一年的第几天？

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

程序代码如下：

package com.yoodb.util;import java.util.GregorianCalendar;
import java.util.Scanner;public class Demo04 {private static Scanner scan;public static void main(String[] args) {scan = new Scanner(System.in);System.out.println("输入年份：");int year = scan.nextInt();System.out.println("输入月份：");int month = scan.nextInt();System.out.println("输入日期：");int day = scan.nextInt();//判断是否是闰年,GregorianCalendar:判断年份是否是闰年的方法GregorianCalendar gre = new GregorianCalendar();boolean isLeapYear = gre.isLeapYear(year);//返回true:是闰年，false：不是闰年int ap = isLeapYear ? 29 : 28;//判断2月份的天数int days = 0;switch (month) {case 1:days = day;break;case 2:days = 31 + day;break;case 3:days = 31 + ap + day;break;case 4:days = 31 + ap + 31 + day;break;case 5:days = 31 + ap + 31 + 30 + day;break;case 6:days = 31 + ap + 31 + 30 + 31 + day;break;case 7:days = 31 + ap + 31 + 30 + 31 + 30 + day;break;case 8:days = 31 + ap + 31 + 30 + 31 + 30 + 31 + day;break;case 9:days = 31 + ap + 31 + 30 + 31 + 30 + 31 + 31 + day;break;case 10:days = 31 + ap + 31 + 30 + 31 + 30 + 31 + 31 + 30 + day;break;case 11:days = 31 + ap + 31 + 30 + 31 + 30 + 31 + 31 + 30 + 31 + day;break;case 12:days = 31 + ap + 31 + 30 + 31 + 30 + 31 + 31 + 30 + 31 + 30 + day;break;default:System.out.println("月份输入错误!");break;}System.out.println("这一天是这一年的第" + days + "天");}
}

运行结果如下：

输入年份：
2020
输入月份：
2
输入日期：
10
这一天是这一年的第41天

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

程序分析：可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去掉不满足条件的排列。

程序代码如下：

package com.yoodb.util;public class Demo05 {public static void main(String[] args) {int count = 0;for (int x = 1; x < 5; x++) {for (int y = 1; y < 5; y++) {for (int z = 1; z < 5; z++) {if (x != y && y != z && x != z) {count++;System.out.print(x * 100 + y * 10 + z + "\t");if (count % 4 == 0) {System.out.println();}}}}}System.out.println("共有" + count + "个三位数");}
}

运行结果如下：

123 124 132 134
142 143 213 214
231 234 241 243
312 314 321 324
341 342 412 413
421 423 431 432
共有24个三位数

4. 有5个人坐在一起，问第五个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第三个人，又说比第2人大两岁。问第2个人，说比第一个人大两岁。最后问第一个人，他说是10岁。请问第五个人多大？

程序分析：

利用递归的方法，递归分为回推和递推两个阶段。要想知道第五个人岁数，需知道第四人的岁数，依次类推，推到第一人（10岁），再往回推。

程序代码

public class Demo09 {public static int getAge(int n) {if (n == 1) {return 10;}return 2 + getAge(n - 1);}public static void main(String[] args) {System.out.println("第五个的年龄为" + getAge(