035--算法常用面试题汇总

VIP免费
2024-12-11 0 0 124.11KB 11 页 5.9玖币
侵权投诉
算法常用面试题汇总
1.说一下什么是二分法？使用二分法时需要注意什么？如何用代码实现？
二分法查找（Binary Search）也称折半查找，是指当每次查询时，将数据分为前后两部
分，再用中值和待搜索的值进行比较，如果搜索的值大于中值，则使用同样的方式（二分
法）向后搜索，反之则向前搜索，直到搜索结束为止。
二分法使用的时候需要注意：二分法只适用于有序的数据，也就是说，数据必须是从小到
大，或是从大到小排序的。
public class Lesson7_4 {
public static void main(String[] args) {
// 二分法查找
int[] binaryNums = {1, 6, 15, 18, 27, 50};
int findValue = 27;
int binaryResult = binarySearch(binaryNums, 0, binaryNums.length - 1,
findValue);
System.out.println("元素第一次出现的位置（从 0开始）：" + binaryResult);
}
/**
* 二分查找，返回该值第一次出现的位置（下标从 0 开始）
* @param nums 查询数组
* @param start 开始下标
* @param end 结束下标
* @param findValue 要查找的值
* @return int
*/
private static int binarySearch(int[] nums, int start, int end, int
findValue) {
if (start <= end) {
// 中间位置
int middle = (start + end) / 2;
// 中间的值
int middleValue = nums[middle];
if (findValue == middleValue) {
// 等于中值直接返回
return middle;
} else if (findValue < middleValue) {
// 小于中值，在中值之前的数据中查找
return binarySearch(nums, start, middle - 1, findValue);
} else {
// 大于中值，在中值之后的数据中查找
return binarySearch(nums, middle + 1, end, findValue);
}
}
return -1;
}
}
执行结果如下：
元素第一次出现的位置（从 0开始）：4
2.什么是斐波那契数列？用代码如何实现？
斐波那契数列（Fibonacci Sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契
（Leonardoda Fibonacci “ ”）以兔子繁殖为例子而引入，故又称为 兔子数列 ，指的是这样
一个数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,
233，377，610，987，1597，2584，4181，6765，10946，17711…… 在数学上，斐波
那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)
（n>=3，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应
用。
斐波那契数列之所以又称黄金分割数列，是因为随着数列项数的增加，前一项与后一项之
比越来越逼近黄金分割的数值 0.6180339887……
斐波那契数列指的是这样一个数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,
233，377，610，987，1597，2584，4181，6765，10946，17711……
斐波那契数列的特征 ：第三项开始（含第三项）它的值等于前两项之和。
斐波那契数列代码实现示例，如下所示：
public class Lesson7_4 {
public static void main(String[] args) {
// 斐波那契数列
int fibonacciIndex = 7;
int fibonacciResult = fibonacci(fibonacciIndex);
System.out.println("下标(从0开始)" + fibonacciIndex + "的值为：" +
fibonacciResult);
}
/**
* 斐波那契数列
* @param index 斐波那契数列的下标（从 0开始）
* @return int
*/
private static int fibonacci(int index) {
if (index == 0 || index == 1) {
return index;
} else {
return fibonacci(index - 1) + fibonacci(index - 2);
}
}
}
执行结果如下：
下标(从0开始)7 的值为：13
3.一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子
来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？请使用代码实现。
先来分析一下，本题目
• 第一个月：有 1 对小兔子；
•第二个月：小兔子变成大兔子；
•第三个月：大兔子下了一对小兔子；
•第四个月：大兔子又下了一对小兔子，上个月的一对小兔子变成了大兔子；
• ……
最后总结的规律如下列表所示：
月数 1 2 3 4 5 6 7 8 9 10 11 12 …
幼仔对
数
1 0 1 1 2 3 5 8 1
3
21 34 55 …
成兔对
数
0 1 1 2 3 5 8 13 2
1
34 55 89
总对数 1 1 2 3 5 8 13 21 3
4
55 89 144
可以看出，兔子每个月的总对数刚好符合斐波那契数列，第 12 个月的时候，总共有 144
对兔子。 实现代码如下：
public class Lesson7_4 {
public static void main(String[] args) {
// 兔子的总对数
int rabbitNumber = fibonacci(12);
System.out.println(" 第12 个月兔子的总对数是：" + rabbitNumber);
}
/**
* 斐波那契数列
* @param index 斐波那契数列的下标（从 0开始）
* @return int
*/
private static int fibonacci(int index) {
if (index == 0 || index == 1) {
return index;
} else {
return fibonacci(index - 1) + fibonacci(index - 2);
}
}
}
执行结果如下：
第 12 个月兔子的总对数是：144
摘要：

算法常用面试题汇总1.说一下什么是二分法？使用二分法时需要注意什么？如何用代码实现？二分法查找（BinarySearch）也称折半查找，是指当每次查询时，将数据分为前后两部分，再用中值和待搜索的值进行比较，如果搜索的值大于中值，则使用同样的方式（二分法）向后搜索，反之则向前搜索，直到搜索结束为止。二分法使用的时候需要注意：二分法只适用于有序的数据，也就是说，数据必须是从小到大，或是从大到小排序的。publicclassLesson7_4{publicstaticvoidmain(String[]args){//二分法查找int[]binaryNums={1,6,15,18,27,50};int...

展开>> 收起<<
035--算法常用面试题汇总.docx

共11页,预览3页

还剩页未读， 继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

相关推荐

更多
立即下载
分类：计算机 价格：5.9玖币 属性：11 页 大小：124.11KB 格式：DOCX 时间：2024-12-11

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

高考理综 人际关系 配电装置 动力学连接体 力的合成 全宋诗作者索引 公务员考试
/ 11
评分 收藏
分享
立即下载 VIP免费下载
客服
关注