面试题目备考

本文主要是介绍面试题目备考，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

面试题目准备

〇、面经链接

1、字节跳动
https://www.nowcoder.com/discuss/453852?type=post&order=jing&pos=&page=3&channel=-2&source_id=search_post&subType=2 主JVM、zk、redis等
https://www.nowcoder.com/discuss/445316?type=post&order=time&pos=&page=1&channel=-2&source_id=search_post&subType=2 主网络、数据库
https://www.cnblogs.com/flyingcr/p/10428280.html 主网络tcp、三次握手、Java
https://www.nowcoder.com/discuss/317487?order=0&page=1&pos=6&type=0 主JVM、GC 、线程、秒杀
https://blog.csdn.net/weixin_33805152/article/details/106618948 主网络、线程池、事务、redis
https://www.sohu.com/a/404254709_463974 主MySQL、redis、kafka、zset的实现和源码
https://www.nowcoder.com/discuss/476824?type=post&order=time&pos=&page=1&channel=-2&source_id=search_post&subType=2 主http、三次握手、Java内存、netty、redis、四次挥手、os内存模型
https://leetcode-cn.com/circle/discuss/A0YstA/ 主锁、分布式锁、数据库的实现B、redis的实现、集群保证数据一致性、网络拥塞控制、kafka如何保证顺序
2、华为

一、问答题

（一）Java核心

1、Java基础

变量
1. 静态变量
  1. 存放位置
  2. 什么时候初始化？
  3. 如何初始化？
IO流

分类：
- 输入流：InputStream/Reader（基类）
- 输出流：OutputStream/Writer
- 引出：Stream流，以后可以总结
BIO、NIO、AIO的区别
- BIO（Blocking I/O）：
  - 同步阻塞IO模式
  - 读写阻塞在一个线程内，适用连接数少
  - 无法解决高并发（提供Socket和ServerSocket套接字）
- NIO（Non-blocking I/O）：
  - 同步非阻塞IO模式，NIO框架对应java.nio包（jdk1.4）
  - 支持面向缓冲，基于通道，仍然是同步操作，线程自己进行IO操作
  - 支持SocketChannel和ServerSocketChannel套接字通道（均支持阻塞或非阻塞方式），可以分别应对低负载、低阻塞和高负载、高阻塞。
- AIO（Asynchronous I/O）
  - NIO2，异步非阻塞I/O模式
  - 基于事件和回调机制实现

序列化

概念
- 序列化：对象写入文件（ObjectOutputStream.writeObject(Obj)）
- 反序列化：文件读出到对象（Obj = ObjectInputStream.readObject()）
注意：
- static和瞬态关键字transient不会被序列化
- InvalidClassException异常解决：显式声明序列化id，即final long serialVersionUID = 1L;

问题

int类型，如何序列化成字节流

ObjectOutputStream oos=new ObjectOutputStream(new FileOutputStream("src\\person.txt"));
oos.writeObject(new Person("小美女",18));

跨平台的序列化：
- 存为json文件，可以使用Jackson的库

new ObjectMapper().writeValueAsString(new Reassignment(partitionListFilterDownBroker));

2、集合

Map
1. HashMap是线程安全的吗，为什么？

3、多线程

进程与线程
1. 概念：运行过程、执行单位
2. Java内存区域-线程共享★和独占
3. 线程切换的代价为什么小：
  1. 时间片轮转切换保存执行现场，线程中共享进程中的资源无需切换【不切换资源】
  2. 切换线程不会影响TLB（负责缓存内存中的逻辑地址和物理地址的映射信息）【不清空缓存】
4. 进程的挂起：
  1. wait和notify用于挂起和唤醒，用于暂停线程的运行，也可通过休眠方式挂起
  2. 等待资源时，释放锁，避免资源浪费，资源就绪后再唤醒
5. 进程间通信的方式：*IPC方式*包括：管道、系统IPC（信号量、消息队列、共享内存）和套接字（socket）。
多线程与死锁
1. 线程的生命周期和状态
2. 多线程引发的问题：上下文切换（时间片）、死锁（等待临界资源）
3. 死锁的产生条件与避免
4. sleep和wait、start和run
synchronized关键字
1. 使用：修饰静态方法、实例方法、代码块
2. 底层原理：代码块monitorenter和修饰方法的ACC_SYNCHRONIZED标识
3. ReentranLock：API+高级功能（等待可中断、公平锁、选择性通知）
volatile关键字
1. Java内存模型中线程保存至本地内存（寄存器）而非主存，易导致数据不一致---volatile保证变量可见性+防止指令重排序
2. 并发编程：原子性（synchronized）、可见性、有序性
3. synchronized保证同步性，同时保证可见性和原子性，性能不如volatile
ThreadLocal关键字
1. 修饰变量，每个线程有该变量的私有值，可通过get/set修改
2. 包含~Map，该类是对Map的封装，key是Thread，value是set的值
3. key是弱引用，value是强引用，会出现key为null的Entry，无法被GC回收，产生内存泄露。
4. 解决：增删改时，手动调用remove()
线程池
1. 好处：降低消耗，提高利用率，便于管理
2. Runnable不返回结果，Callable可以，Executors可以实现互转
3. execute提交无返回值任务到线程池，submit提交有返回值任务（内部调用execute），返回Future对象取返回值get()
4. 创建：ThreadPoolExecutor构造选参/Executors的newXXThreadPool--定量、单个、cache
5. 饱和策略：池满&队列满--抛异常、加Q容量、丢弃（线程/未处理任务）
6. 原理：获取线程池状态，判断核心线程池min是否已满且处于RUNNING，满则判断队列可否加入任务，再判断线程池max是否满，如果执行失败，拒绝命令并执行饱和策略
7. 线程池的选型，为什么，底层实现原理
8. 线程池的核心参数，如何确定线程池的大小
Atomic原子类
1. 基本类型、数组类型、引用类型、对象的属性修改类型
2. 无需加锁也能保证线程安全，get/lazySet/compareAndSet(e,u)
3. CAS：现有值等于预期则更新为输入值
AQS
1. JUC.locks.AbstractQueueSynchronizer，构建锁和同步器的框架
2. 自定义同步器需要继承并调用模板方法(tryAcquire/tryRelease Shared)
3. 可重入锁ReentranLock和CountDownLatch的state分别为1和n
4. 三大组件=Semaphore、CountDownLatch（控制线程等待的倒计时器）、CycliBarrier（循环栅栏，阻塞一组线程同时放开）

4、JVM

内存模型
1. Java中堆和栈的区别
2. java 实例放在哪个区，常量放在哪个区；
优化
1. JVM优化的流程

5、GC

G1和CMS垃圾回收器

2、MQ

3、数据库

4、Redis

5、网络

6、多线程

7、GO语言

8、反问
您觉得经过这一小时的交流，我整体怎么样？应该向什么方向去深入学习和思考比较好呢？

（二）数据库

1、MySQL

存储引擎
- 有哪些存储引擎及区别
联合查询/多表查询
- left join、inner join：inner的就是差集、left的就是保左边；
索引
- 联合索引及sql的执行效率
- MySQL索引的作用和实现
- 对于 SELECT id, age FROM user WHERE status = 0 and age > 12; 这条语句，怎样建立索引比较好？
- 怎么知道一条语句是否使用了索引
- 如果一条语句的查询关键字包含了索引中的关键字，但是 MySQL 引擎还是没有使用索引，有可能是什么原因？
- 聚集索引和非聚集索引的区别
- 覆盖索引，联合索引原理
- MySQL索引在什么情况下会失效
- MySQL的索引模型
- InnoDB索引实现
优化
- 查询优化器
- 数据库优化流程
- 数据库优化流程
事务
- 概念：逻辑上的操作，要么都执行要不都不执行
- 四大特性：ACID
- 事务并发带来的问题
  - 脏读★：一读一改
  - 丢失修改：两个均改
  - 不可重复读：多事务同时读写（修改）
  - 幻读★：多事务同时读写（插入）
- 事务隔离级别
  - 读未提交
  - 读已提交：解决脏读
  - 可重复读：可能产生幻读
  - 可串行化：服从ACID，事务之间不会互相干扰
- 默认隔离级别
  - MySQL的InnoDB是可重复读(Select @@tx_isolation)
  - InnoDB引擎使用了Next-Key Lock算法，达到了串行化的级别
  - InnoDB在分布式事务下会用可串行化级别
  - Mysql 的幻读是怎么个情况，Mysql 是如何避免的。
- 锁
  - 乐观锁与悲观锁的区别？
  - 用过哪些分布式锁。答了 mysql，redis， zookeeper 分别聊了一下优缺点。
集群
- Mysql 集群在保证强一致性的情况下，如何保证高并发
- Mysql 集群如何保证数据的一致性。分别回答了弱一致性和强一致性
- 主从同步怎么搞的？分哪几个过程？如果有一台新机器要加到从机里，怎么个过程。
分库分表
- 大库 DDL 怎么做比较好
其他：
- Mysql 用的是什么数据结构
- MySQL字段类型的长短会对性能有影响吗
- 如何分析一条语句的执行过程。delete from t1 limit 3和delete from t1的区别？
- Mysql 集群在保证强一致性的情况下，如何保证高并发

2、Redis

常用数据结构
1. zet的结构及插入时间复杂度
2. redis 的 zset 怎么实现的？
3. redis数据结构的底层实现
4. zset 延时队列怎么实现的
5. redis 数据结构有哪些？分别怎么实现的？
6. Redis 的 ZSET 怎么实现的？尽量介绍的全一点，跳跃表加哈希表以及压缩链表
7. Redis 的 ZSET 做排行榜时，如果要实现分数相同时按时间顺序排序怎么实现
持久化与缓存
1. Redis持久化方式
2. redis缓存过期策略，准备同步，哨兵机制和集群的区别
3. redis持久化原理
执行
1. Redis单进程还是多进程？？我印象挺深的，为什么面试官要说单进程而不是单线程
2. Redis读写分离
3. 场景题：Redis主从部署，在写请求特别多的场景下，如何保证在从节点读到的数据不是脏数据
4. Redis是单进程单线程，那为什么RDB时候不会阻塞
5. redis key 的过期策略
6. redis如何实现高可用
集群
1. Redis集群策略、分槽
2. Redistribution集群中不同节点如何通信
3. 延迟双删解决主从Redis节点的数据一致性
4. redis 主从同步是怎样的过程？
5. redis 哨兵和集群
6. redis 的跳表知道吗，为什么不用红黑树。我回答了因为红黑树实现比跳表复杂。但是面试官不是很满意，后来查了一下是有这部分原因的。
7. redis 集群是怎么实现的，说一下一致性 hash。

3、MongoDB

4. 其他

用过什么数据库，各数据库的应用场景。
binlog 日志和 redolog 日志清楚吗？说了两个日志的作用以及两阶段提交

（三）计算机网络、操作系统、数据结构

HTTP和HTTPS
1. Https的过程讲一下。先是说了http+ssl，dns之后，准备讲ssl的原理时，他示意我说回答一下传输层相关的。然后我就回答了tcp三次握手，对着服务器端指定端口，比如80端口发起连接，之后就是正常的数据请求了。
2. HTTP 和 HTTPS 的区别
3. 详细描述一下 HTTPS 的加密过程，需要几次通信
4. http常用方法
5. HTTP 包结构。
6. https原理
7. http各种返回码，401和406啥区别？
8. 一个完整的 HTTP 请求会涉及到哪些协议
9. Https的过程讲一下。先是说了http+ssl，dns之后，准备讲ssl的原理时，他示意我说回答一下传输层相关的。然后我就回答了tcp三次握手，对着服务器端指定端口，比如80端口发起连接，之后就是正常的数据请求了
10. 详细描述一下 HTTPS 的加密过程，需要几次通信
TCP和IP
1. TCP四次挥手，结合CS两端点的TCP栈和上层应用的交互来解释四次挥手，以及为何需要中间那个FIN-WAIT-2这个过程，最后由被动关闭一方的上层应用通过调用socket.closed()来结束数据传输，进入最终的FIN模式；
2. TCP 三次握手和四次挥手，说一下 time_wait。
3. TCP流量控制、拥塞控制
4. 详细描述一下 HTTPS 的加密过程，需要几次通信
5. http keepalive、tcp keepalive
6. TCP流量控制是通过接收端发送带有接受窗口剩余大小的ACK来实现的，那么如果接收端的TCP没有CPU调度会发送ACK吗，会不会因为接受窗口满了并且不能及时发送ACK导致数据丢失
7. TIME_WAIT 是什么？TIME_WAIT 为什么是 2MSL 而不是 1MSL 或者 3MSL？
8. TCP 的包怎么保证有序性？
9. TCP和UDP的区别和各自的应用
10. linux中管道的底层原理
OSI七层或者TCP/IP四层模型
1. ICMP协议
2. OSI七层模型
OS的内存模型
1. 操作系统分页和分段的区别
2. 对于进程管理这一块，你有什么可以说的？如果一个进程占用了过多时间，怎么办？
3. 对于内存管理这一块，你有什么可以说的？虚拟内存怎么优化？
4. Socket 编程用了哪些系统调用？
5. 操作系统内存模型
进程
1. 进程的调度
2. 令牌桶原理、数据结构？？数据结构这个我是真的懵了，后来想可以用一个volatile自增字段+阻塞队列实现
3. 你提到了 Unix Domain Socket，那 Unix Domain Socket 和绑定 localhost 的 Socket 有什么区别？哪个性能更高？
锁
1. 用过哪些锁，自旋锁和互斥锁有什么区别
2. 用过哪些分布式锁
3. 分布式锁的实现、原理
数据结构
1. 跳表结构
2. 动态规划与贪心有什么区别
3. B 树和 B+ 树的区别，为什么 mysql 要用 B+ 树，mongodb 要用 B 树。
相关操作
1. Linux查看具体端口是否被占用
2. 查看 CPU 的命令和磁盘 IO 的命令
加密
1. 对称加密、非对称加密
2. MD5是对称加密么
管道
1. linux中管道的底层原理
其他
1. select 和 epoll

（四）Java EE

Netty
1. 说一下Netty的IO原理，答：Reactor反应模型，Linux那边叫做IO多路复用。一个线程用来接收请求，将读写事件交给背后的worker线程。Redis、Nginx、Netty都是用到了这种模型。Redis其实也是多线程，只不过是用单线程来接收请求，在客户端看起来是串行接收执行，所以效果上就是单线程。但是IO多路复用才是Redis能高并发的底层保证。
Jsp & Servlet
1. post请求返回的100状态码是协议规定的还是浏览器规定的
2. 知道 Cookie 吗？
3. 知道 Cookie 吗？
4. 列举 HTTP 状态码。

（五）框架

（六）Kafka

Kafka 选主怎么做的？
kafka 与 rabbitmq区别
kafka 分区怎么同步的
kafka 怎么保证不丢消息的
kafka 为什么可以扛住这么高的qps
kafka partition broker consumer consumer group topic 等都是啥关系？

（七）大数据

zookeeper
1. 为什么用zookeeper做服务发现
2. zookeeper如何维护长连接的状态
3. zookeeper主从架构怎么保证数据同步

（八）其他中间件

MQ
1. MQ作用、原理以及主要组件
2. kafka了解吗，各个MQ的对比
3. RocketMQ中topic、queue的具体含义
4. 集群消费、广播消费
5. 队列泄洪
6. 项目中怎么用MQ的
7. rabbitmq 的工作原理。我只是用过，但是没有具体研究过，凉凉。。。
8. kafka 的工作原理，如何保证顺序等
微服务
1. 集群消费、广播消费
2. 为什么项目里要用protobuf，protobuf 的好处
3. 市面主流的RPC框架了解多少
4. 为什么要实现一个RPC框架
5. 微服务的好处
6. 问什么不用本地调用，而要用微服务
7. 项目中RPC框架中怎么定义协议的
8. dubbo服务发现
9. 注册中心服务判活
10. 项目中限流怎么做的
11. dubbo的好处
12. 微服务网关模块的具体逻辑，为什么要用网关
13. 网关模块怎么可以保证整个系统的安全性
14. 微服务的业务模块拆分，为什么要这样拆分
15. Dubbo原理介绍
16. 微服务的特点，如何实现服务发现和负载均衡
秒杀
1. 秒杀项目中缓存预热
2. 秒杀优化，压测QPS
3. 服务发现是怎么实现的
4. 熔断是怎么实现的
其他概念
1. 负载均衡策略
  1. 哈希一致性
Netty
1. 说一下Netty的IO原理

二、算法题

1、打家劫舍及变种

标准打家劫舍
- 自顶向下：递归，res = Math.max(dp(nums, start + 1),nums[start] + dp(nums, start + 2)
- 重叠子问题：备忘录优化，memo[start] != -1,return
- 自底向上：数组从n-1到0倒着找，dp[i] = Math.max(dp[i + 1], nums[i] + dp[i + 2]);【正着找也可，需要先初始化】
- 自底向上的优化：三个变量，空间复杂度为O(1)
打家劫舍Ⅱ：房子围成一圈（环形数组，之前讲过单调栈解决）
- 方式：计算0-n-1和1到n的最大值，函数调用
打家劫舍Ⅲ：房子是二叉树，相连节点不能同时被抢
- 计算抢/不抢的最大值，使用自顶向下+备忘录map

int do_it = root.val
        + (root.left == null ? 
            0 : rob(root.left.left) + rob(root.left.right))
        + (root.right == null ? 
            0 : rob(root.right.left) + rob(root.right.right));
int res = Math.max(do_it, not_do);
memo.put(root, res);

打家劫舍变种：删除并获得点数（不能删除值相邻的元素，问能得到的最大点数）
- 数组转化为dp[index]=num的形式，转换为打家劫舍
- 也可不对数组转换，改为使用map

2、重复字符的全排列

题目：写一种方法，计算某字符串的所有排列组合。

 输入：S = "qqe"
 输出：["eqq","qeq","qqe"]
 public String[] permutation(String S)

解答：set记录所有可能，dfs(arr,len,string)遍历，该位置未添加过继续+1

class Solution {
    Set<String> res = new HashSet<>();
    boolean[] visit;
    public String[] permutation(String S) {
        char[] arr = S.toCharArray();
        visit = new boolean[arr.length];
        dfs(arr, 0, "");
        return res.toArray(new String[0]);
    }
    void dfs(char[] arr, int idx, String path) {
        if (idx == arr.length) {
            res.add(String.valueOf(path));
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            if (!visit[i]) {
                visit[i] = true;
                dfs(arr, idx + 1, path + arr[i]);
                visit[i] = false;
            }
        }
    }
}

指定位数的数字全排列

static void arrange(int a[], int start, int end) {

		if (start == end) {		
			for (int i : a) {
				System.out.print(i);
			}
			System.out.println();
			return;
		}
		for (int i = start; i <= end; i++) {
			swap(a, i, start);
			arrange(a, start + 1, end);
			swap(a, i, start);
		}
	}

	static void swap(int arr[], int i, int j) {
		int te = arr[i];
		arr[i] = arr[j];
		arr[j] = te;
	}

3、遍历螺旋矩阵

while里面套4个for循环

import java.util.*;
 
//  1 2 3    螺旋 1 2 3 6 9 8 7 4 5
//  4 5 6
//  7 8 9
public class Solution {
    public ArrayList<integer> spiralOrder(int[][] matrix) {
        ArrayList<integer> res = new ArrayList<>();
        if(matrix.length == 0)
            return res;
        // 定义四个指针，并且充当边界限制的作用
        int top = 0, bottom = matrix.length-1;
        int left = 0, right = matrix[0].length-1;
 
        while( top < (matrix.length+1)/2 && left < (matrix[0].length+1)/2 ){
            //上面  左到右
            for(int i = left; i <= right; i++){
                res.add(matrix[top][i]);
            }
 
            //右边 上到下
            for(int i = top+1; i <= bottom; i++){
                res.add(matrix[i][right]);
            }
 
            //下面  右到左
            for(int i = right-1; top!=bottom && i>=left; i--){
                res.add(matrix[bottom][i]);
            }
 
            //左边 下到上
            for(int i = bottom-1; left!=right && i>=top+1; i--){
                res.add(matrix[i][left]);
            }
            // 遍历完一圈之后，所有往里面靠
            ++top;
            --bottom;
            ++left;
            --right;
        }
        return res;
    }
}

4、带有随机链表指针的深拷贝

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        
    }
}

使用map<Node,Node>

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null){
            return head;
        }
        // map方法，空间复杂度O(n)
        Node node = head;
        // 使用hash表存储旧结点和新结点的映射
        Map<Node,Node> map = new HashMap<>();
        while(node != null){
            Node clone = new Node(node.val,null,null);
            map.put(node,clone);
            node = node.next;
        }
        node = head;
        while(node != null){
            map.get(node).next = map.get(node.next);
            map.get(node).random = map.get(node.random);
            node = node.next;
        }
        return map.get(head);
    }
}

5、链表节点两两反转：两两交换其中相邻的节点，并返回交换后的链表

解法1：递归

class Solution {
    public ListNode swapPairs(ListNode head) {
      	//终止条件：链表只剩一个节点或者没节点了，没得交换了。返回的是已经处理好的链表
        if(head == null || head.next == null){
            return head;
        }
      	//一共三个节点:head, next, swapPairs(next.next)
      	//下面的任务便是交换这3个节点中的前两个节点
        ListNode next = head.next;
        head.next = swapPairs(next.next);
        next.next = head;
      	//根据第二步：返回给上一级的是当前已经完成交换后，即处理好了的链表部分
        return next;
    }
}

递归三部曲
- 找终止条件
- 找返回值
- 本级递归应该做什么
解法2：迭代

 //迭代
    public ListNode swapPairs(ListNode head) {
        ListNode newHead = new ListNode(0);
        ListNode cur = newHead;
        newHead.next = head;
        while(cur.next != null && cur.next.next != null){
            ListNode a = cur.next;
            ListNode b = a.next;
            cur.next = b;
            a.next = b.next;
            b.next = a;
            cur = a;
        }
        return newHead.next;
    }

解法3：用栈操作
- Stack stack = new Stack<>();
- 或Deque stack2 = new ArrayDeque<>();
- 区别：元素顺序不同

6、链表节点k个一组反转

解法1：递归（同上，重点在于当前过程如何交换k个节点的顺序/反转当前的k个节点）

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode prev = null;
        ListNode cur = head;
        ListNode next = null;
        ListNode check = head;
        int canProceed = 0;
        int count = 0;
        // 检查链表长度是否满足翻转
        while (canProceed < k && check != null) {
            check = check.next;
            canProceed++;
        }
        // 满足条件，进行翻转
        if (canProceed == k) {
            while (count < k && cur != null) {
                next = cur.next;
                cur.next = prev;
                prev = cur;
                cur = next;
                count++;
            }
            if (next != null) {
                // head 为链表翻转后的尾节点
                head.next = reverseKGroup(next, k);
            }
            // prev 为链表翻转后的头结点
            return prev;
        } else {
            // 不满住翻转条件，直接返回 head 即可
            return head;
        }
    }
}

解法2：使用一个栈操作，栈满插入
解法3：头插法

import java.util.*;
public class Solution {
    public ListNode reverseKGroup (ListNode head, int k) {
        if(head==null||head.next==null||k==1) return head;
        ListNode res = new ListNode(0);
        res.next = head;
        int length = 0;
        ListNode pre = res,
                 cur = head,
                 temp = null;
        while(head!=null){
            length++;
            head = head.next;
        }
        //分段使用头插法将链表反序
        for(int i=0; i<length/k; i++){
            //pre作为每一小段链表的头节点，负责衔接
            for(int j=1; j<k; j++){
                temp = cur.next;
                cur.next = temp.next;
                //相当于头插法，注意：
                //temp.next = cur是错误的，temp需要连接的不是前一节点，而是子序列的头节点
                temp.next = pre.next;
                pre.next = temp;
            }
            //每个子序列反序完成后，pre，cur需要更新至下一子序列的头部
            pre = cur;
            cur = cur.next;
        }
        return res.next;
    }
}

7 反转链表

解法1：迭代

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null, cur = head, next = null;
        while(cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

解法2：递归

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode node = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return node;
    }
}

8、删除字符串中的子串ab

解法1：使用StringBuffer的indexOf和delete方法
- 以后遇到字符串问题均可考虑使用现有的包或库

public String removeOccurrences(String s, String part) {
        StringBuffer sub = new StringBuffer(s);
        while (sub.indexOf(part) != -1) {
            int index = sub.indexOf(part);
            sub.delete(index, index + part.length());
        }
        return sub.toString();
    }

解法2：直接用String类型，进行递归

class Solution {
    public String removeOccurrences(String s, String part) {
         if(!s.contains(part)){
             return s;
         }
          int i = s.indexOf(part);
          s = s.substring(0, i) + s.substring(i + part.length());
         return removeOccurrences(s,part);
    }
}

9、数组中字符串的匹配

解法1：双层循环+indexOf函数
解法2：使用contains函数

    public List<String> stringMatching(String[] words) {
        List<String> res = new ArrayList<>();
        for (String word : words) {
            for (int i = 0; i < words.length; i++) {
                if (word.length() >= words[i].length()) continue;
                if (words[i].contains(word)) {
                	res.add(word);
                    break;
                }
            }
        }
        return res;
    }

10、买卖股票一（类似打家劫舍）

动态规划递推式：前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格}

记录最小价格
记录最大收益★

class Solution {    public int maxProfit(int[] prices) {        if(prices.length <= 1)            return 0;        int min = prices[0], max = 0;        for(int i = 1; i < prices.length; i++) {            max = Math.max(max, prices[i] - min);            min = Math.min(min, prices[i]);        }        return max;    }}

11、买卖股票二

题目：计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
解法1：贪心-只要大于前一天，就将这两天的差值相加

class Solution {
    public int maxProfit(int[] prices) {
        int ans=0;
        for(int i=1;i<=prices.length-1;i++)
        {
            if(prices[i]>prices[i-1])
            {
                ans+=prices[i]-prices[i-1];
            }
        }
        return ans;
    }
}

12、买卖股票三

题目：计算你所能获取的最大利润。你最多可以完成两笔交易。
解法1：计算0到i和i到len-1的最大收益和

class Solution {
    
    public int maxProfit(int[] prices) {
        int max = 0;
        for (int i = 0; i < prices.length; i++) {
            max = Math.max(max, func(prices, 0, i) + func(prices, i, prices.length));
        }
        return max;
    }

    private int func(int[] prices, int start, int end) {
        int min = prices[start];
        int profit = 0;
        for (int i = start; i < end; i++) {
            profit = Math.max(prices[i] - min, profit);
            min = Math.min(min, prices[i]);
        }
        return profit;
    }
}

解法2：使用4个变量（分别表示第一天买入、卖出、第二天买入、卖出的最大收益），一层循环即可

class Solution {
    public int maxProfit(int[] prices) {
        /**
        对于任意一天考虑四个变量:
        fstBuy: 在该天第一次买入股票可获得的最大收益 
        fstSell: 在该天第一次卖出股票可获得的最大收益
        secBuy: 在该天第二次买入股票可获得的最大收益
        secSell: 在该天第二次卖出股票可获得的最大收益
        分别对四个变量进行相应的更新, 最后secSell就是最大
        收益值(secSell >= fstSell)
        **/
        int fstBuy = Integer.MIN_VALUE, fstSell = 0;
        int secBuy = Integer.MIN_VALUE, secSell = 0;
        for(int p : prices) {
            fstBuy = Math.max(fstBuy, -p);
            fstSell = Math.max(fstSell, fstBuy + p);
            secBuy = Math.max(secBuy, fstSell - p);
            secSell = Math.max(secSell, secBuy + p); 
        }
        return secSell;
    }
}

13、跳跃游戏/走格子

题目：nums的每个元素表示能跳的最大长度，问能否到达最后一个下标

class Solution {
    public boolean canJump(int[] nums) {
        int reach = 0;
        for(int i = 0; i < nums.length; i ++) {
            if(reach < i) {
                return false;
            }
            reach = Math.max(reach, i + nums[i]);
        }
        return reach >= nums.length - 1;
    }
}

14、跳跃游戏Ⅱ/走格子+陷阱

题目：使用最少次数到达最后一个位置

class Solution {
    public int jump(int[] nums) {
        int steps = 0, start = 0, end = 0;
        while(end < nums.length - 1) {
            int max = end;
            for(int i = start; i <= end; i++) {
                if(nums[i] + i > max) {
                    max = nums[i] + i;//寻找能跳跃到的最大位置处作为end
                }
            } 
            start = end;
            end = max;
            steps ++;
        } 
        return steps;
    }
}

14、输入n，k，输出n的字典序的第k位数字，若n=15，k=7，1 10 11 12 13 14 15 2 3 4 5 6 7 8 9，输出15（dfs、tri树）
15、给定一个升序数组 1，元素有重复，对每个元素算一下平方后得到新的数组 2，问数组 2 中不相同的元素共有多少个？给出时间复杂度和空间复杂度，要求尽量优化。 [-13, -13, -13, 17, 17, 17]
16、给定 m 个不重复字符（如：[a, b, c]），以及一个长度为 n 的字符串 (如：tbbacbctsafsg)，问能否在这个字符串中找到一个长度为 m 的连续子串。要求子串由给定的 m 个字符组成，顺序不要求（如：bac）。
17、有两个表示正整数的字符串，写一个函数求的两个整数相加的结果对应的字符串。（力扣415）

18、单链表的反转，不用递归的方法
19、有序数组存在某个值，查找这个值的下标，有则输出，无则输出-1

20、力扣394：给定一个经过编码的字符串，返回它解码后的字符串（编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次），如s = "3[a]2[bc]", 返回 "aaabcbc".
21、力扣213：打家劫舍求偷窃到的最高金额

22、给你一个整数 n，使得从 n 中删除 k 个数字之后的数字最大。
23、取出数组中第k大的数字
24、求二叉树中和为K的所有路径
25、求一个有序整数数组中和为K的数的对数。
26、递增递减数列（不考虑附近重复），找出最大的数，如int[] arr = {1, 2, 3, 4, 5, 7, 8,10,5,3,2,1};

27、两个单向链表，返回求和后的链表结构，例如2->3->1->5，和3->6，结果返回2->3->5->1
28、两个排序数组找中位数
29、求数字n的平方根
30、跳台阶
31、数组中奇数个元素
32、一栋楼有n层，不知道鸡蛋从第几层扔下去会碎，用最少的次数找出刚好会碎的楼层
33、连续整数求和(leetcode 第 829 题)，要求时间复杂度小于O(N)

34、链表表示的两个数相加。
35、算法题是股票买卖，一次和无限次两种。

36、反转链表：：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
37、三数之和=0
38、链表求和
39、最小覆盖子串
40、最大交换670：给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
41、把一个方程式设计成树以及很多的 follow up
42、LRU缓存

这篇关于面试题目备考的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！