面试题目备考
2021/8/1 23:07:32
本文主要是介绍面试题目备考,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
面试题目准备
〇、面经链接
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基础
- 变量
- 静态变量
- 存放位置
- 什么时候初始化?
- 如何初始化?
- 静态变量
- 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模式
- 基于事件和回调机制实现
- BIO(Blocking 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
- HashMap是线程安全的吗,为什么?
3、多线程
- 进程与线程
- 概念:运行过程、执行单位
- Java内存区域-线程共享★和独占
- 线程切换的代价为什么小:
- 时间片轮转切换保存执行现场,线程中共享进程中的资源无需切换【不切换资源】
- 切换线程不会影响TLB(负责缓存内存中的逻辑地址和物理地址的映射信息)【不清空缓存】
- 进程的挂起:
- wait和notify用于挂起和唤醒,用于暂停线程的运行,也可通过休眠方式挂起
- 等待资源时,释放锁,避免资源浪费,资源就绪后再唤醒
- 进程间通信的方式:*IPC方式*包括:管道、系统IPC(信号量、消息队列、共享内存)和套接字(socket)。
- 多线程与死锁
- 线程的生命周期和状态
- 多线程引发的问题:上下文切换(时间片)、死锁(等待临界资源)
- 死锁的产生条件与避免
- sleep和wait、start和run
- synchronized关键字
- 使用:修饰静态方法、实例方法、代码块
- 底层原理:代码块monitorenter和修饰方法的ACC_SYNCHRONIZED标识
- ReentranLock:API+高级功能(等待可中断、公平锁、选择性通知)
- volatile关键字
- Java内存模型中线程保存至本地内存(寄存器)而非主存,易导致数据不一致---volatile保证变量可见性+防止指令重排序
- 并发编程:原子性(synchronized)、可见性、有序性
- synchronized保证同步性,同时保证可见性和原子性,性能不如volatile
- ThreadLocal关键字
- 修饰变量,每个线程有该变量的私有值,可通过get/set修改
- 包含~Map,该类是对Map的封装,key是Thread,value是set的值
- key是弱引用,value是强引用,会出现key为null的Entry,无法被GC回收,产生内存泄露。
- 解决:增删改时,手动调用remove()
- 线程池
- 好处:降低消耗,提高利用率,便于管理
- Runnable不返回结果,Callable可以,Executors可以实现互转
- execute提交无返回值任务到线程池,submit提交有返回值任务(内部调用execute),返回Future对象取返回值get()
- 创建:ThreadPoolExecutor构造选参/Executors的newXXThreadPool--定量、单个、cache
- 饱和策略:池满&队列满--抛异常、加Q容量、丢弃(线程/未处理任务)
- 原理:获取线程池状态,判断核心线程池min是否已满且处于RUNNING,满则判断队列可否加入任务,再判断线程池max是否满,如果执行失败,拒绝命令并执行饱和策略
- 线程池的选型,为什么,底层实现原理
- 线程池的核心参数,如何确定线程池的大小
- Atomic原子类
- 基本类型、数组类型、引用类型、对象的属性修改类型
- 无需加锁也能保证线程安全,get/lazySet/compareAndSet(e,u)
- CAS:现有值等于预期则更新为输入值
- AQS
- JUC.locks.AbstractQueueSynchronizer,构建锁和同步器的框架
- 自定义同步器需要继承并调用模板方法(tryAcquire/tryRelease Shared)
- 可重入锁ReentranLock和CountDownLatch的state分别为1和n
- 三大组件=Semaphore、CountDownLatch(控制线程等待的倒计时器)、CycliBarrier(循环栅栏,阻塞一组线程同时放开)
4、JVM
- 内存模型
- Java中堆和栈的区别
- java 实例放在哪个区,常量放在哪个区;
- 优化
- 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
- 常用数据结构
- zet的结构及插入时间复杂度
- redis 的 zset 怎么实现的?
- redis数据结构的底层实现
- zset 延时队列怎么实现的
- redis 数据结构有哪些?分别怎么实现的?
- Redis 的 ZSET 怎么实现的?尽量介绍的全一点,跳跃表加哈希表以及压缩链表
- Redis 的 ZSET 做排行榜时,如果要实现分数相同时按时间顺序排序怎么实现
- 持久化与缓存
- Redis持久化方式
- redis缓存过期策略,准备同步,哨兵机制和集群的区别
- redis持久化原理
- 执行
- Redis单进程还是多进程??我印象挺深的,为什么面试官要说单进程而不是单线程
- Redis读写分离
- 场景题:Redis主从部署,在写请求特别多的场景下,如何保证在从节点读到的数据不是脏数据
- Redis是单进程单线程,那为什么RDB时候不会阻塞
- redis key 的过期策略
- redis如何实现高可用
- 集群
- Redis集群策略、分槽
- Redistribution集群中不同节点如何通信
- 延迟双删解决主从Redis节点的数据一致性
- redis 主从同步是怎样的过程?
- redis 哨兵和集群
- redis 的跳表知道吗,为什么不用红黑树。我回答了因为红黑树实现比跳表复杂。但是面试官不是很满意,后来查了一下是有这部分原因的。
- redis 集群是怎么实现的,说一下一致性 hash。
3、MongoDB
4. 其他
- 用过什么数据库,各数据库的应用场景。
- binlog 日志和 redolog 日志清楚吗?说了两个日志的作用以及两阶段提交
(三)计算机网络、操作系统、数据结构
- HTTP和HTTPS
- Https的过程讲一下。先是说了http+ssl,dns之后,准备讲ssl的原理时,他示意我说回答一下传输层相关的。然后我就回答了tcp三次握手,对着服务器端指定端口,比如80端口发起连接,之后就是正常的数据请求了。
- HTTP 和 HTTPS 的区别
- 详细描述一下 HTTPS 的加密过程,需要几次通信
- http常用方法
- HTTP 包结构。
- https原理
- http各种返回码,401和406啥区别?
- 一个完整的 HTTP 请求会涉及到哪些协议
- Https的过程讲一下。先是说了http+ssl,dns之后,准备讲ssl的原理时,他示意我说回答一下传输层相关的。然后我就回答了tcp三次握手,对着服务器端指定端口,比如80端口发起连接,之后就是正常的数据请求了
- 详细描述一下 HTTPS 的加密过程,需要几次通信
- TCP和IP
- TCP四次挥手,结合CS两端点的TCP栈和上层应用的交互来解释四次挥手,以及为何需要中间那个FIN-WAIT-2这个过程,最后由被动关闭一方的上层应用通过调用socket.closed()来结束数据传输,进入最终的FIN模式;
- TCP 三次握手和四次挥手,说一下 time_wait。
- TCP流量控制、拥塞控制
- 详细描述一下 HTTPS 的加密过程,需要几次通信
- http keepalive、tcp keepalive
- TCP流量控制是通过接收端发送带有接受窗口剩余大小的ACK来实现的,那么如果接收端的TCP没有CPU调度会发送ACK吗,会不会因为接受窗口满了并且不能及时发送ACK导致数据丢失
- TIME_WAIT 是什么?TIME_WAIT 为什么是 2MSL 而不是 1MSL 或者 3MSL?
- TCP 的包怎么保证有序性?
- TCP和UDP的区别和各自的应用
- linux中管道的底层原理
- OSI七层或者TCP/IP四层模型
- ICMP协议
- OSI七层模型
- OS的内存模型
- 操作系统分页和分段的区别
- 对于进程管理这一块,你有什么可以说的?如果一个进程占用了过多时间,怎么办?
- 对于内存管理这一块,你有什么可以说的?虚拟内存怎么优化?
- Socket 编程用了哪些系统调用?
- 操作系统内存模型
- 进程
- 进程的调度
- 令牌桶原理、数据结构??数据结构这个我是真的懵了,后来想可以用一个volatile自增字段+阻塞队列实现
- 你提到了 Unix Domain Socket,那 Unix Domain Socket 和绑定 localhost 的 Socket 有什么区别?哪个性能更高?
- 锁
- 用过哪些锁,自旋锁和互斥锁有什么区别
- 用过哪些分布式锁
- 分布式锁的实现、原理
- 数据结构
- 跳表结构
- 动态规划与贪心有什么区别
- B 树 和 B+ 树的区别,为什么 mysql 要用 B+ 树,mongodb 要用 B 树。
- 相关操作
- Linux查看具体端口是否被占用
- 查看 CPU 的命令和磁盘 IO 的命令
- 加密
- 对称加密、非对称加密
- MD5是对称加密么
- 管道
- linux中管道的底层原理
- 其他
- select 和 epoll
(四)Java EE
- Netty
- 说一下Netty的IO原理,答:Reactor反应模型,Linux那边叫做IO多路复用。一个线程用来接收请求,将读写事件交给背后的worker线程。Redis、Nginx、Netty都是用到了这种模型。Redis其实也是多线程,只不过是用单线程来接收请求,在客户端看起来是串行接收执行,所以效果上就是单线程。但是IO多路复用才是Redis能高并发的底层保证。
- Jsp & Servlet
- post请求返回的100状态码是协议规定的还是浏览器规定的
- 知道 Cookie 吗?
- 知道 Cookie 吗?
- 列举 HTTP 状态码。
(五)框架
(六)Kafka
- Kafka 选主怎么做的?
- kafka 与 rabbitmq区别
- kafka 分区怎么同步的
- kafka 怎么保证不丢消息的
- kafka 为什么可以扛住这么高的qps
- kafka partition broker consumer consumer group topic 等都是啥关系?
(七)大数据
- zookeeper
- 为什么用zookeeper做服务发现
- zookeeper如何维护长连接的状态
- zookeeper主从架构怎么保证数据同步
(八)其他中间件
- MQ
- MQ作用、原理以及主要组件
- kafka了解吗,各个MQ的对比
- RocketMQ中topic、queue的具体含义
- 集群消费、广播消费
- 队列泄洪
- 项目中怎么用MQ的
- rabbitmq 的工作原理。我只是用过,但是没有具体研究过,凉凉。。。
- kafka 的工作原理,如何保证顺序等
- 微服务
- 集群消费、广播消费
- 为什么项目里要用protobuf,protobuf 的好处
- 市面主流的RPC框架了解多少
- 为什么要实现一个RPC框架
- 微服务的好处
- 问什么不用本地调用,而要用微服务
- 项目中RPC框架中怎么定义协议的
- dubbo服务发现
- 注册中心服务判活
- 项目中限流怎么做的
- dubbo的好处
- 微服务网关模块的具体逻辑,为什么要用网关
- 网关模块怎么可以保证整个系统的安全性
- 微服务的业务模块拆分,为什么要这样拆分
- Dubbo原理介绍
- 微服务的特点,如何实现服务发现和负载均衡
- 秒杀
- 秒杀项目中缓存预热
- 秒杀优化,压测QPS
- 服务发现是怎么实现的
- 熔断是怎么实现的
- 其他概念
- 负载均衡策略
- 哈希一致性
- 负载均衡策略
- Netty
- 说一下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<>(); - 区别:元素顺序不同
- Stack
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缓存
这篇关于面试题目备考的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南