数据结构与算法面试系列-03
2022年7月17日
数据结构与算法面试系列-03
1. 一球从100米高度自由落下，每次落地后反跳回原高度的一半；再落下，求它在 第10次落地时，共经过多少米？第10次反弹多高？
程序代码
package com.jingxuan.system;
public class Sphere {
public static void main(String[] args) {
double s = 0;
double t = 100;
for (int i = 1; i <= 10; i++) {
s += t;
t = t / 2;
}
System.out.println("第10次落地时，共经过" +s+ "米");
System.out.println("第10次反弹" +t+ "米");
}
}
执行结果
第10次落地时，共经过199.8046875米
第10次反弹0.09765625米
2. 有一分数序列：2/1，3/2，5/3，8/5，13/8，21/13...求出这个数列的前20项之和。
程序分析：分子与分母的变化规律，分母等于前一个分子，分子是前一个分子加当前分母之和。关注Java精选公众号，内涵算法题100+道面试题，其他面试题3000+道题。
程序代码如下：
package com.jingxuan.system;
public class Fenshu20 {
public static void main(String[] args) {
float fm = 1f;
float fz = 1f;
float temp;
float sum = 0f;
for (int i = 0; i < 20; i++) {
temp = fm;
fm = fz;
fz = fz + temp;
sum += fz / fm;
System.out.println(fz + "/" + fm);
}
System.out.println("这个数列的前20项之和为" + sum);
}
}
运行结果如下：
2.0/1.0
3.0/2.0
5.0/3.0
8.0/5.0
13.0/8.0
21.0/13.0
34.0/21.0
55.0/34.0
89.0/55.0
144.0/89.0
233.0/144.0
377.0/233.0
610.0/377.0
987.0/610.0
1597.0/987.0
2584.0/1597.0
4181.0/2584.0
6765.0/4181.0
10946.0/6765.0
17711.0/10946.0
这个数列的前20项之和为32.660263
3. 【腾讯】说说下面这道题的结果？
欢迎大家关注微信公众号： Java精选 ，专注分享前沿资讯，BATJ 大厂面试题解读，架构技术干货，微服务、高可用等架构设计，10年开发老兵帮你少走弯路，欢迎各领域程序员交流学习！
此类面试题只能在微信小程序： Java精选面试题 ，查阅全部内容，感谢支持！
4. Java 中如何将一个数组逆序输出？
程序分析：循环遍历从后往前取数组长度减1作为数的索引值，然后输出其数据。
程序代码如下：
package com.jingxuan.system;
public class ArraysReverse {
public static void main(String[] args) {
int[] n = { 61, 62, 21, 34, 25, 82 };
System.out.println("数组逆序输出为");
for (int i = n.length; i > 0; i--) {
System.out.print(n[i-1] + " ");
}
}
}
运行结果如下：
数组逆序输出为
82 25 34 21 62 61
5. 如何取一个整数中从右端开始的4～7位的数字？
程序分析：
1）先使a右移4位。
2）设置一个低4位全为1,其余全为0的数。可用(0 < <4)
3）将上面二者进行&运算。
程序代码如下：
package com.jingxuan.system;
public class IntAchieve {
public static void main(String[] args) {
int a = 0;
long b = 18745678948379l;
a = (int) Math.floor(b % Math.pow(10, 7) / Math.pow(10, 3));
System.out.println("从右端开始的4～7位：" + a);
}
}
运行结果如下：
从右端开始的4～7位：8948
6. Java 中如何实现杨辉三角形？
程序分析：
1、第n行有n个数字。
2、每一行的开始和结尾数字都为1。
用二维数组表示就是a[i][0]=1; a[i][j]=1(当i==j时)。
3、第n+1行的第i个数字等于第n行的i-1个数字加上第n行的i个数字。
用二维数组表示就是 a[i+1][j]=a[i][j-1]+a[i][j]。
程序代码如下：
package com.jingxuan.system;
public class YHSJ {
public static void main(String[] args) {
int[][] arr = new int[10][];
for (int i = 0; i < arr.length; i++) {
arr[i] = new int[i + 1];
}
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
if (j == 0 || i == j) {
arr[i][j] = 1;
} else {
arr[i][j] = arr[i - 1][j] + arr[i - 1][j - 1];
}
}
}
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
}
运行结果如下：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
7. Java 如何实现数组中整数按从小到大顺序输出？
程序分析：利用指针方法。
程序代码如下：
package com.jingxuan.system;
public class ArraysOrder {
public static void main(String[] args) {
int[] arrays = { 600, 56, 220, 122, 501 };
for (int i = arrays.length; --i >= 0;) {
for (int j = 0; j < i; j++) {
if (arrays[j] > arrays[j + 1]) {
int temp = arrays[j];
arrays[j] = arrays[j + 1];
arrays[j + 1] = temp;
}
}
}
for (int n = 0; n < arrays.length; n++)
System.out.println(arrays[n]);
}
}
运行结果如下：
56
122
220
501
600
8. 如何实现数组中最大与第一个元素交换，最小与最后一个元素交换并输出数组？
程序代码如下：
package com.jingxuan.system;
public class ArraysZDY {
public static void main(String[] args) {
int i, min, max, temp1, temp2;
int a[] = {92,12,33,83,68,54};
max = 0;
min = 0;
for (i = 1; i < a.length; i++) {
if (a[i] > a[max])
max = i;
if (a[i] < a[min])
min = i;
}
temp1 = a[0];
temp2 = a[min];
a[0] = a[max];
a[max] = temp1;
if (min != 0) {
a[min] = a[a.length - 1];
a[a.length - 1] = temp2;
} else {
a[max] = a[a.length - 1];
a[a.length - 1] = temp1;
}
for (i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
}
运行结果如下：
92 54 33 83 68 12
9. 有n个整数，使其前面各数顺序向后移m个位置，最后m个数变成最前面的m个数
程序代码如下：
package com.jingxuan.system;
import java.util.Scanner;
public class ArraysWeiYi {
private static Scanner s;
public static void main(String[] args) {
int N = 5;
int[] a = new int[N];
s = new Scanner(System.in);
System.out.println("请输入5个整数：");
for (int i = 0; i < N; i++) {
a[i] = s.nextInt();
}
System.out.print("你输入的数组为：");
for (int i = 0; i < N; i++) {
System.out.print(a[i] + " ");
}
System.out.print("\n请输入向后移动的位数：");
int m = s.nextInt();
int[] b = new int[m];
for (int i = 0; i < m; i++) {
b[i] = a[N - m + i];
}
for (int i = N - 1; i >= m; i--) {
a[i] = a[i - m];
}
for (int i = 0; i < m; i++) {
a[i] = b[i];
}
System.out.print("位移后的数组是：");
for (int i = 0; i < N; i++) {
System.out.print(a[i] + " ");
}
}
}
运行结果如下：
请输入5个整数：
1
2
3
4
5
你输入的数组为：1 2 3 4 5
请输入向后移动的位数：3
位移后的数组是：3 4 5 1 2
10. 在排序数组中如何查找元素的第一位和末尾位置？
欢迎大家关注微信公众号： Java精选 ，专注分享前沿资讯，BATJ 大厂面试题解读，架构技术干货，微服务、高可用等架构设计，10年开发老兵帮你少走弯路，欢迎各领域程序员交流学习！
此类面试题只能在微信小程序： Java精选面试题 ，查阅全部内容，感谢支持！
11. 有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位。
程序分析：程序分析：假设有5个人，围成一圈，顺序排号，报数1、2、3、1、2，分别对应a、b、c、d、e；剩下a、b、d、e，继续报数3、1、2、3；剩下b、d，继续报数1、2，没有退出圈子的人，继续报数3、1；剩下d，最后留下来的是第4位。
程序代码如下：
package com.jingxuan.system;
import java.util.Scanner;
public class LeaveH {
private static Scanner s;
public static void main(String[] args) {
System.out.print("请输入有几个人参加：");
s = new Scanner(System.in);
int n = s.nextInt();
boolean[] arr = new boolean[n];
for (int i = 0; i < arr.length; i++) {
arr[i] = true;
}
int leftCount = n;
int countNum = 0;
int index = 0;
while (leftCount > 1) {
if (arr[index] == true) {
countNum++;
if (countNum == 3) {
countNum = 0;
arr[index] = false;
leftCount--;
}
}
index++;
if (index == n) {
index = 0;
}
}
for (int i = 0; i < n; i++) {
if (arr[i] == true) {
System.out.println( "最后留下的是原来第" + (i+1) + "号");
}
}
}
}
运行结果如下：
请输入有几个人参加：5
最后留下的是原来第4号
12. 海滩上有一堆桃子，五只猴子来分。第一只猴子把这堆桃子凭据分为五份，多了一个，这只猴子把多的一个扔入海中，拿走了一份。第二只猴子把剩下 的桃子又平均分成五份，又多了一个，它同样把多的一个扔入海中，拿走了一份，第三、第四、第五只猴子都是这样做的，问海滩上原来最少有多少个桃子？
程序代码如下：
package com.jingxuan.system;
public class Dg {
static int ts = 0;// 桃子总数
static int fs = 1;// 记录分的次数
static int hs = 5;// 猴子数量
static int tsscope = 5000;// 桃子数的取值范围
public static int fT(int t) {
if (t == tsscope) {
return 0;
} else {
if ((t - 1) % hs == 0 && fs <= hs) {
if (fs == hs) {
System.out.println("桃子数为" + ts + "时满足分桃条件");
}
fs += 1;
return fT((t - 1) / 5 * 4);
} else {
fs = 1;
return fT(ts += 1);
}
}
}
public static void main(String[] args) {
fT(0);
}
}
运行结果如下：
桃子数为3121时满足分桃条件
13. 编写一个函数，输入n为偶数时，调用函数求1/2+1/4+...+1/n,当输入n为奇数时，调用函数1/1+1/3+...+1/n
程序代码如下：
package com.jingxuan.system;
import java.util.Scanner;
public class JiSuan {
private static Scanner sc;
public static void main(String[] args) {
sc = new Scanner(System.in);
System.out.println("请输入一个数字：");
double num = sc.nextDouble();
double sum = 0;
if (num % 2 == 0) {
for (int i = 2; i <= num; i = i + 2) {
sum = sum + (1.0 / i);// 因为i为整数
}
System.out.println("输入的偶数运算和为" + sum);
} else {
for (int i = 1; i <= num; i = i + 2) {
sum = sum + (1.0 / i);
}
System.out.println("输入的奇数运算和为" + sum);
}
}
}
运行结果如下：
请输入一个数字：
6
输入的偶数运算和为0.9166666666666666
14. 什么是平衡二叉树？
平衡二叉树是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
构造与调整方法平衡二叉树的常用算法有红黑树、AVL、Treap等。
最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。
平衡二叉树是对二叉排序树的优化，防止二叉排序树在最坏情况（插入顺序恰好是有序的）下平均查找时间为n，二叉排序树在此时形如一个单链表，而平衡二叉树查找元素的次数不超过树的深度，时间复杂度为logN。
15. 写一个函数，求一个字符串的长度，在main函数中输入字符串，并输出其长度。
程序代码如下：
package com.jingxuan.system;
import java.util.Scanner;
public class ArraysLength {
private static Scanner s;
public static void main(String[] args) {
s = new Scanner(System.in);
System.out.println("请输入一个字符串：");
String mys = s.next();
System.out.println("数组长度为" + str_len(mys));
}
public static int str_len(String x) {
return x.length();
}
}
运行结果如下：
请输入一个字符串：
123456789
数组长度为9
16. 利用递归方法求 5!（5的阶乘）
程序分析：递归公式：fn=fn_1*4! ，5!表示5的阶乘，即：5×4×3×2×1=120。关注Java精选公众号，内涵算法题100+道面试题，其他面试题3000+道题。
程序代码如下：
package com.jingxuan.system;
public class Factorial {
public static void main(String[] args) {
System.out.println("5的阶乘为" + recursion(5));
}
public static long recursion(int n) {
long value = 0;
if (n == 1 || n == 0) {
value = 1;
} else if (n > 1) {
value = n * recursion(n - 1);
}
return value;
}
}
运行结果如下：
5的阶乘为120
17. 求数组中某个数字出现的次数？
假设数组中都是数字，计算所有数字出现的次数，并找到只出现一次的数字。
程序代码
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
public class Solution {
public static void main(String[] args) {
int[] nums = { 1, 1, 2, 2, 3, 4, 5, 6, 33, 56 };
Iterator<Map.Entry<Integer, Integer>> it = singleNumber(nums).entrySet().iterator();
while (it.hasNext()) {
Map.Entry<Integer, Integer> entry = it.next();
System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
}
}
public static Map<Integer, Integer> singleNumber(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int i : nums) {
map.put(i, map.get(i)!= null ? (map.get(i)+1) : 1);
}
return map;
}
}
输出结果
key= 1 and value= 2
key= 33 and value= 1
key= 2 and value= 2
key= 3 and value= 1
key= 4 and value= 1
key= 5 and value= 1
key= 6 and value= 1
key= 56 and value= 1
18. 有一对兔子，从出生后第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个月时的兔子都可以生育了。Java精选公众号，回复“面试资料”领取免费面试题集。
程序代码
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
19. 猴子吃桃问题：猴子第一天摘下若干个桃子，当即吃了一半，还不瘾，又多吃了一个第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第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
20. 说一说 LRU 缓存算法的实现原理？
1、LRU(Least recently used) 根据数据的历史访问记录来进行淘汰数据，其核心思想是"如果数据最近这段时间一直都没有访问，那么将来被访问的概率也会很低"，两种理解是一样的。常用于页面置换算法，为虚拟页式存储管理服务。
2、达到这样一种情形的算法是最理想的:每次调换出页面是所有内存页面中最迟将被使用的，这可以最大限度的推迟页面调换，这种算法被称为理想页面置换算法。可惜的是这种算法无法实现。为了尽量减少与理想算法的差距，产生了各种精妙的算法，最近最少使用页面置换算法便是其中一个。
LRU算法的提出是基于这样一个事实：在前面几条指令中频繁的页面很可能在后面的几条指令中频繁使用。反过来说已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个就是著名的局部性原理-比内存速度还要快的cache，也是基于同样的原理运行的。因此我们只需要在每次调换时找到最近较少使用的那个页面调出内存。
