Java面试题整理
最近看面经，发现好多要整理的呀。这里专门开一个章节记录下面经的过程，有基础题、算法题和流程题等。大多数都是在牛客上看到的，尝试自己做做，有时间就更新一下吧~
01.百度Java面试题
1. 二叉树的层序遍历，以二维数组的形式输出结果
解答思路：二叉树的层次遍历可以使用的是广度优先搜索的算法实现。具体使用的方法是创建一个队列，将根节点加入到队列中去；当队列不为空是，对队列执行以下操作：
- 取出队首的元素，访问该节点
- 如果该节点存在左节点，将其加入队列
- 如果该节点存在右节点，将其加入队列
- 重复上述的两步，直到队列为空。
给出以下的具体代码：
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val){
this.val=val;
}
}
public class BFSTraversal {
//二叉树的层序遍历
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
//在每一层遍历开始前，先记录队列中的结点数量n（也就是这一层的结点数量），然后一口气处理完这一层的n个结点。将当前层的所有结点出队列，再将下一层的所有结点入队列，这样就实现了层序遍历。
List<Integer> levelNodes = new ArrayList<>();//每一层一个List数组
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
levelNodes.add(node.val);
if (node.left != null)
queue.offer(node.left);
if (node.right != null)
queue.offer(node.right);
}
result.add(levelNodes);//[[,]]
}
return result;
}
public static void main(String[] args) {
// 创建一棵二叉树示例
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
// 调用levelOrder方法进行广度优先遍历(但是是层序遍历)，区分每一层，返回二维数组
List<List<Integer>> result = traversal.levelOrder(root);
// 输出结果
System.out.println("层序遍历输出："+result);
}
}-
总结：熟练手撕，唯手熟尔
2. 给出socket通信的过程
基础的题目，看似简单，但是需要完整的回答~
- 服务端先启动，绑定一个端口号和ip地址
- 然后是客户端启动，向服务端发送信息请求连接
- 服务端收到请求后，就建立自己的soket对象，向客户端发送响应，等待客户端发送数据
- 客户端接收到服务端发送的响应后，就建立自己的sokect对象，通过该Socket对象与服务器端进行通信
- 服务器端和客户端通过各自的Socket对象进行通信，直到通信结束~
- 通信结束后就关闭socket对象，然后释放网络资源
- 在通信过程中，Socket对象扮演着重要的角色，它通过网络传输数据并完成通信。在Java中，可以使用Java Socket API实现Socket通信
3. 返回最长的满足条件的字符子串
给定字符串s和pattern，返回s中最长子串，要求该子串按顺序包含pattern中的字符，并且子串的字符可以重复。**比如pattern=abc，子串aabbc、abbc即可，但是aabb就不行，因为没有包括所有字母。**要求返回最长的子串，没有就返回null
思路：乍一看是最长的子字符串，想到的是动态规划dp。但是考虑到可以重复出现，并且并不需要返回长度，而是字符的substring( )进行截取。所以可以考虑双指针进行滑动窗口的解答。下面是口头的解答过程：
- 首先是利用双指针对字符串进行分割，在左指针右移的过程中，此时遇到和pattern对应位置相等的字符的时候记录到新的字符串中，由于可以存在重复的情况，所以还需要判断此时的左指针后一位是否也匹配，不断循环直到不匹配了，左右指针才都右移一位。
- 当右指针和pattern的长度相等，且此时新字符串大于最长的长度，更新即可。
- 最后返回新字符串。
代码如下：
//利用滑动窗口进行解答
public class Solution {
public String findLongestSubstring(String s, String pattern) {
int n = s.length();
int m = pattern.length();
String res = "";
int maxLen = 0;
for (int i = 0; i < n; i++) {
int j = 0;
StringBuilder substr = new StringBuilder();
while (i < n && j < m && s.charAt(i) == pattern.charAt(j)) {
substr.append(s.charAt(i));
while (i + 1 < n && s.charAt(i + 1) == pattern.charAt(j)) {
i++;
substr.append(s.charAt(i));
}
i++;
j++;
}
if (j == m && substr.length() > maxLen) {
maxLen = substr.length();
res = substr.toString();
}
}
return maxLen != 0 ? res : null;
}
// 举例测试：
public static void main(String[] args) {
Solution solution = new Solution();
String s = "scaewaabbccfaaabbbccccsdas";
String pattern = "abc";
String longestSubstring = solution.findLongestSubstring(s, pattern);
if (longestSubstring != null) {
System.out.println("最长子串: " + longestSubstring);
} else {
System.out.println("没有找到满足条件的子串");
}
}
}
//这个代码首先遍历字符串s，然后在每个位置上尝试匹配pattern。
// 如果当前位置的字符与pattern的当前字符相同，则进入一个内层循环，不断地向后查找相同的字符并将其添加到子串中，直到找到一个不同的字符或到达s的末尾。
// 然后将pattern的指针向前移动一位，继续查找下一个字符。
// 当pattern的所有字符都被匹配完，就找到了一个符合条件的子串。然后比较其长度与当前最长子串的长度，如果更长则更新最长子串。
// 最后返回最长的子串，如果没有找到符合条件的子串则返回None。
4. 写出快速排序的实现代码
给出具体的代码，需要熟记和多练习：
public class Quick {
public void sort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
private void quickSort(int[] arr, int left, int right) {
if (left < right) {
int partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
}
private int partition(int[] arr, int left, int right) {
int pivot = arr[right]; // 选择最右边的元素作为基准值
int i = left - 1; // 定义分区点，并初始化为左边界-1
for (int j = left; j < right; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, right); // 将基准值放到合适的位置
return i + 1; // 返回基准值的最终位置
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args){
int[] arr={2,14,2,3,5,8,5,9,6,4,3};
Quick q=new Quick();
q.sort(arr);
for (int j : arr) {
System.out.print(j + " ");
}
}
}
-
上述代码中的快速排序的核心是在
QuickSort类中的quickSort方法和partition方法。quickSort方法是快速排序算法的入口，通过递归实现了对数组的分区和排序。它首先确定基准值的位置，然后对左右两个子数组分别进行递归排序，直到排序完成。partition方法是快速排序算法的关键，它定义了如何对数组进行分区操作。在分区过程中，选择一个基准值，将小于基准值的元素放在基准值的左边，大于基准值的元素放在右边，并返回基准值的最终位置。
这两个方法共同构成了快速排序算法的核心逻辑，通过不断地分区和排序，最终实现了对整个数组的排序。
5. 谈谈你对数据库中的索引的理解
定义：索引就是加快检索表中数据的方法。数据库的索引类似于书籍的索引。在书籍中，索引允许用户不必翻阅完整个书就能迅速地找到所需要的信息。在数据库中，索引也允许数据库程序迅速地找到表中的数据，而不必扫描整个数据库。
作用是加速查询 底层是通过B+树实现的 索引又分为聚簇索引和非聚簇索引，区别是索引和数据是否储存在一起。
拿InnoDB主键索引举个例子，这是一个聚簇索引，在非叶子节点中存放数据为主键数据，以及其指向的页的页号(数据库底层是以页为基本储存单位)，在叶子节点存放完整的数据 而如果我们拿一张表的另一个或多个字段创建索引，那个就会形成一个非聚簇索引，其非叶子节点和聚簇索引的结构类似，但是其叶子节点并不会存放完整的数据，而是存放对应数据的主键。
在具体的查询过程中，如果采用聚簇索引，则会直接通过B+树找到完整的数据并返回，但是如果使用非聚簇索引，则会先找到具体数据的主键的值，再用该主键的值去到主键索引中找到完整的数据。
当然，如果是索引覆盖的情况(即查找的字段被创建索引的字段所包含)那么将不会进行回表操作，直接返回值。
我们在使用索引时应该要避免索引失效，遵循最左匹配原则，即我们使用的where关键字时，后面的条件的顺序要和当初创建索引时的顺序相匹配，并且只能是前几个连续的。
索引失效将会导致全表扫描，大大降低数据查询效率。 索引的使用并不是由我们决定的，而是由查询优化器通过预估计算后选出最合适的索引进行查询。
6. 现在普通关系数据库用得数据结构是什么类型的数据结构
1.普通关系数据库的数据结构是关系型数据结构、也就是由一行一列组成的二维表。
2.行代表对象、列代表属性。
3.使用sql语句，具有ACID特性（原子性、一致性、隔离性和持久性）
7. 索引的优点和缺点
索引的优点:
- .创建唯一性索引，保证数据库表中每一行数据的唯一性
- 大大加快数据的检索速度，这也是创建索引的最主要的原因
- 加速表和表之间的连接，特别是在实现数据的参考完整性方面特别有意义。
- 在使用分组和排序子句进行数据检索时，同样可以显著减少查询中分组和排序的时间。
- 通过使用索引，可以在查询的过程中使用优化隐藏器，提高系统的性能。
索引的缺点：
- 创建索引和维护索引要耗费时间，这种时间随着数据量的增加而增加。
- 索引需要占物理空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，如果要建立聚簇索引，那么需要的空间就会更大。
- 当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，降低了数据的维护速度。
省流版：
- 优点：
- 加快查询、分组、排序的速度，提高效率
- 如果使用唯一性索引，保证数据库表中每一行数据的唯一性
- 缺点：
- 维护索引和创建索引需要格外的空间和时间，使同一行数据的数据量变的庞大
- 当对表中的数据进行增删改查的时候，要保证索引的正确，这个时候就要动态维护。大大降低对数据量的维护速率~
8. session、cookie和cache的区别是什么
session是一种服务器存储数据的方式，通过在服务器上建立一个唯一sessionID来跟踪会话，可以存储任何类型的数据
优点：数据不容易被篡改和伪造
缺点：需要管理和维护
cookie是一种客户端存储数据的方式，通过小型的文本文件来保存数据。
优点：不用管理维护
缺点：数据不安全
cache是一种缓存的方式，将经常使用数据存储到内存中提高速度。
优点就是快。
缺点也是需要维护，避免数据过期。缓存数据大小不能太大 。
9. session是存储在什么地方，以什么形式存储的？
- Session是存储在服务器端的一种会话机制，用于跟踪用户的会话状态。Session的具体存储方式中常见的有两种：
- 基于内存的Session存储：Session对象存储在服务器的内存，可以快速读写，但是当服务器重启或者负载均衡到其他服务器的时候，Session会丢失。
- 基于持久化的Session存储：Session对象存储在外部持久化存储中，比如数据库、文件系统等等，保证Session下不会丢失，但会增加系统的读写负担。
- Session存储的形式也可以是键值对的形式。即以键值对的方式存储Session对象的属性和值。具体来说，可以使用Java Servlet API提供的HttpSession接口来操作Session对象。
- 例如，可以通过HttpSession的setAttribute()方法设置Session的属性值，通过getAttribute()方法获取Session的属性值。
10. 重载（Overload）和重写（Override）的区别？
答：方法的重载和重写都是实现多态的方式，区别在于前者实现的是编译时的多态性，而后者实现的是运行时的多态性。
- 重载发生在一个类中，同名的方法如果有不同的参数列表（参数类型不同、参数个数不同或者二者都不同）则视为重载；
- 重写发生在子类与父类之间，重写要求子类被重写方法与父类被重写方法有相同的参数列表，有兼容的返回类型，比父类被重写方法更好访问，不能比父类被重写方法声明更多的异常（里氏代换原则）。
- 重载对返回类型没有特殊的要求，不能根据返回类型进行区分。
02. Java基础面试
1. 抽象类和接口的区别与联系？
- 相同点：
- 二者都不能实现实例化
- 均可以拥有抽象方法
- 不同点：
- 抽象类定义的关键字是abstract class，接口方法的关键字是interface
- 属性上：抽象类可以有静态变量、常量和成员变量；接口只能拥有常量
- 抽象方法可以拥有普通的方法，但是接口类的jdk在1.8之前只能拥有抽象方法（1.8之后增添了静态方法和默认方法）
- 抽象方法可以存在构造方法，接口不能拥有构造方法
- 一个类只能单继承以各父类，而一个接口可以继承多个父接口。同时，一个类可以实现多个接口，但是并没有实现多个父类的说法
- 抽象方法在业务上更多地是模板操作，存在和自己相同的功能，可以有优化补充的多种形式，而接口更像是一种规范和要求，实现需要按照要求要求来进行。
2. String、StringBuffer、StringBuilder之间有什么区别？（简短 ）
- String：不可变字符序列，效率低，复用率高；
- 任何对 String 的操作实际上都会生成一个新的 String 对象，原始的 String 对象并不会改变。这种特性使得 String 在多线程环境下是安全的。
- 当需要修改一个字符串时，每次操作都会生成一个新的字符串对象，这可能导致大量的内存开销。
- StringBuffer：可变字符序列、效率较高（增删）、线程安全、方法同步、多线程可直接使用；
- 可变，它的所有公共方法都是同步的，所以它是线程安全的。
- 在单线程情况下，使用 StringBuffer 会带来额外的同步开销，性能相对较低。
- StringBuilder：可变字符序列、效率最高、线程不安全、方法不同步、适用于单线程、多线程需要加锁；
- StringBuilder 的方法不是同步的，因此它不是线程安全的。
- 由于不需要处理同步的开销，StringBuilder 的性能通常比 StringBuffer 更好，因此在单线程环境下，推荐使用 StringBuilder。
3. hashCode()和equals()的区别,为什么重写equals()就要重写hashCode()
- 得分点 hashCode()用途、equals()用途、hashCode()、equals()约定 ；
- 标准回答 ：
- hashCode()：获取哈希码；equals()：比较两个对象是否相等。
- 二者两个约定：如果两个对象相等，它们必须有相同的哈希码；若两个对象的哈希码相同，他们却不一定相等。
- 也就是说,equals()比较两个对象相等时hashCode()一定相等，hashCode()相等的两个对象equqls()不一定相等。
- 加分回答：由于hashCode()与equals()具有联动关系，equals()重写时，hashCode()进行重写，使得这两个方法始终满足相关的约定。
