面试大厂必刷：LeetCode算法90题

1. 买股票的最佳时机

难度级别：简单

题目： 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。 注意：你不能在买入股票前卖出股票。

2. 跳跃游戏

难度级别：中等

题目：

给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。

3. 场景题：发红包

题目：

让你设计一个微信发红包的api，你会怎么设计，不能有人领到的红包里面没钱，红包数值精确到分。

4. 合并排序的数组

难度级别：简单

题目：

给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。 初始化 A 和 B 的元素数量分别为 m 和 n。

5. 剪绳子

难度级别：中等

题目：

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问k[0]*k[1]*...*k[m-1]可能的最大乘积是多少？例如，当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18。

6. 有序数组中不重复元素的个数

题目：

给定一个有序数组，请算出平方后的结果可能的个数。

7. 找出不重复的元素个数

题目：

一个数据先递增再递减，找出数组不重复的个数。不能使用额外空间，复杂度o(n)

8. 找范围

题目：

高考成绩2000万数据，分数0-750，如何快速知道你的排名，如何知道任一分数排名？

9. 测时间

题目：

两根香，一根烧完1小时，如何测量15分钟

10. 链表相交

难度级别：简单

题目：

给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第 k 个节点与另一个链表的第 j 个节点是同一节点（引用完全相同），则这两个链表相交。

11. 求平方根

题目：

（这道题目跟 leetcode 上的不一样，leetcode 上只要求整数，这个还有精度） 写一个函数，求平方根，函数参数为目标数字和精度，测试案例 fn(4.1,0.001) fn(501.1,0.001) fn(0.045,0.001)

12. 场景题：互相关注表设计

题目：

场景题：需求：谁关注了我，我关注了谁，谁与我互相关注。表该如何设计，索引怎么建。查询语句怎么写

13. 找 K 个最小值

题目：

10亿个数字，取最小的100个数

14. 找出重复元素

题目：

1亿个正整数,范围是0-42亿。求出现次数是2的数字，空间复杂度

15. 二叉树层次遍历

难度级别：中等

题目：

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

16. 蛇形遍历二叉树

难度级别：中等

题目：

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

17. 链表求和

难度级别：中等

题目：

给定两个用链表表示的整数，每个节点包含一个数位。 这些数位是反向存放的，也就是个位排在链表首部。 编写函数对这两个整数求和，并用链表形式返回结果。

18. 生成随机数

题目:

给定一个 0-4 随机数生成器 如何生成 0-6 随机数

19. 二叉树的最近公共祖先

难度级别：中等

题目：

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

20. 二叉树中的最大路径和

难度级别：困难

题目：

给定一个非空二叉树，返回其最大路径和。 本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

21. 快速排序

手写快排。 快排其实是分治思想的一种，通过找一个基准点，使得该基准点左边的数字都小于等于该基准，基准点右边的数字都大于等于该基准，然后将左右两部分再进行排序，使得总体有序。实现方法通常使用头尾指针。

22. 二叉树的前序遍历非递归

难度级别：中等

题目：

给定一个二叉树，返回它的 前序 遍历。

23. 二叉树的后序遍历

难度级别：困难

题目：

给定一个二叉树，返回它的 后序 遍历。

24. 最长连续递增数列

难度级别：困难

题目：

给定一个未排序的整数数组，找出最长连续序列的长度。 要求算法的时间复杂度为 O(n)。

25. （智力题）海盗分金币

题目：

有5个海盗，获得了100枚金币，于是他们要商量一个方法来分配金币。商议方式如下：

• (1) 由5个海盗轮流提出分配方案。
• (2) 如果超过半数海盗（包括提出者）同意该方案，则按照该方案分配。
• (3) 如果同意该方案的人数（包括提出者）小于等于半数，则提出者要被扔到海里喂鱼，剩下的海盗继续商议分配。
• (4) 海盗们都是绝对理性的，以自己尽可能多获得金币为目的。但是在收益相等的情况下，会倾向把提出者扔到海里。

问：第一个海盗应该提出怎样的分配方案，才能保证自己既不被扔到海里，又能使自己利益最大化？

26. 接雨水

难度级别：困难

题目：

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

27. ip 判断

题目：

有一个IP地址库，假设有几十万条ip，如何判断某个ip地址是否在这个库中

28. 二叉树的路径和

题目：

给定一棵二叉树，求根节点到叶子节点的最小路径和。

29. 反转链表 + 每 k 个反转链表

难度级别：简单

题目：

反转一个单链表。

30. 25. K 个一组翻转链表

难度级别：困难

题目：

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。 k 是一个正整数，它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

31. 场景题：求中位数

题目：

2g内存，要求一个10g文件的中位数

32. 螺旋矩阵

难度级别：中等

题目：

给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

33. 数据结构 heap

题目：

讲一讲 heap 是什么？手写一个 heap

34. 中文数字转阿拉伯数字

问题：

给定一个中文字符串，将其转换成对应的阿拉伯数字

35. 重建二叉树

难度级别：中等

题目：

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 例如，给出：

前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

1. 3

2. / \

3. 9 20

4. / \

5. 15 7

限制：

0 <= 节点个数 <= 5000

36. 路径总和

难度级别：简单

题目：

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

37. 路径总和-2

难度级别：中等

题目：

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例: 给定如下二叉树，以及目标和 sum = 22，

1. 5

2. / \

3. 4 8

4. / / \

5. 11 13 4

6. / \ / \

7. 7 2 5 1

返回

1. [

2. [5,4,11,2],

3. [5,8,4,5]

4. ]

38. 单例模式

题目：

手写单例模式

39. 合并区间

难度级别：中等

题目：

给出一个区间的集合，请合并所有重叠的区间。

40. 翻转字符串中的单词

难度级别：中等

题目：

给定一个字符串，逐个翻转字符串中的每个单词。

41. 和为s的连续正整数序列

难度级别：简单

题目：

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

42. 二分查找

题目：

介绍下二分查找，如果我想在链表中使用二分查找，怎么做比较好？

43. 归并排序

题目：

介绍一下归并排序，时间复杂度多少？

44. LRU 算法

难度级别：中等

题目：

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。 写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：

你是否可以在 O(1) 时间复杂度内完成这两种操作？

45. 数据库连接池

题目：

数据库连接池怎么设计？

46. 版本数字比较

题目：

版本数字比较，比如"1.10.0"版本比"1.8.1"版本新，不允许使用 split 等函数

47. 文件拷贝

题目：

某一个大文件被拆成了 N 个小文件，每个小文件编号从 0 至 N-1，相应大小分别记为 S(i)。给定磁盘空间为 C ，试实现一个函数从 N 个文件中连续选出若干个文件拷贝到磁盘中，使得磁盘剩余空间最小。

48. 场景题：redis 高并发

问题：

redis 设置高并发抢单一的东西，如何避免高并发对一个键进行访问？

49. 最大栈

难度级别：简单

题目：

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最大元素的栈。

• push(x) —— 将元素 x 推入栈中。
• pop() —— 删除栈顶的元素。
• top() —— 获取栈顶元素。
• getMax() —— 检索栈中的最大元素。

50. 场景题：分布式生成数据

题目：

分布式多个机器生成id，如何保证不重复

51. B+树和红黑树

题目：

B+树和红黑树， 红黑树和一般的平衡二叉树，增、删、改、查的过程和效率、时间复杂度

52. 找出和为 k 的数对

难度级别：简单

题目：

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

53. 二叉树各层节点数

题目：

返回二叉树各层节点数，使用递归和非递归方法，并说明时间复杂度和空间复杂度

54. 输出下一个更大的数字

难度级别：中等

题目：

给定一个 32 位正整数 n，你需要找到最小的 32 位整数，其与 n 中存在的位数完全相同，并且其值大于n。如果不存在这样的 32 位整数，则返回 -1。

55. 输出字符串数组？

题目：

（这是原博的描述） 算法：输入List<String>，删除当中形如”1_”的，返回原来的List (2)

56. 缺失的第一个正数

难度级别：困难

题目：

给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。

57. 场景题：抛硬币问题

题目：

一个硬币，正面概率0.7，反面概率0.3，现在有一瓶水，怎么掷能让两个人公平的喝到水

58. 两个栈实现队列

难度级别：简单

题目：

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

59. 二叉树右视图

题目：

二叉树右视图

60. 概率题：扑克牌

题目：

54张扑克牌，平均分成3份，大小王在一份的概率

61. 有序有重复数组查找范围

难度级别：中等

题目：

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

62. 三数之和

难度级别：中等

题目：

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

63. 扫码登录

题目：

扫码登录是如何实现的？

64. 思考题：赛马

题目：

64匹马，8个跑道，选跑最快的4匹马需要比赛多少次

65. 思考题：抛硬币

题目：

两个人轮流抛硬币，先抛到正面的赢，问先抛的人赢的概率

66. 三个线程循环打印ABC

题目：

三个线程循环打印ABC

67. 数组中第K大的数

难度级别：中等

题目：

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

68. top k

题目：

返回一个数组中前 k 个大的或者小的数字

69. 狼和羊的故事

题目：

一个农场中有狼和羊，现在要将他们用围栏分开，问最少需要多少围栏。

70. 二叉排序树找第k大的元素

题目：

利用二叉排序树的性质找第k大的元素

71. 链表求和

难度级别：中等

题目：

给定两个用链表表示的整数，每个节点包含一个数位。 这些数位是反向存放的，也就是个位排在链表首部。 编写函数对这两个整数求和，并用链表形式返回结果。

72. 场景题：定时任务

题目：

系统中有几万个任务需要在各自的特定时刻触发执行，怎么做？

73. 二叉树的最近公共祖先 + 搜索二维矩阵 II + 最长不含重复字符的子字符串

(1) 二叉树的最近公共祖先(同题 19)

难度级别：中等

题目：

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

(2) 搜索二维矩阵 II

难度级别：中等

题目：

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

(3) 最长不含重复字符的子字符串

难度级别：中等

题目：

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

74. 场景题：微博关注列表

题目：

一个很复杂的场景，大概是微博用户有个关注列表，以及知道各种大V的动态，设计数据结构啥的，到最后在用户这边显示一个更新微博列表

75. 场景题：游戏中的 debuff

题目：

游戏里，一个玩家可能吃到很多种debuff，每个debuff有一定持续时间。给你一个定时器，怎么设计数据结构，来维护玩家的debuff状态？

76. 场景题：红黑树，B+树，跳表应用场景

题目：

红黑树，B+树，跳表应用场景

77. “马”在棋盘上的概率

难度级别：中等

题目：

已知一个 NxN 的国际象棋棋盘，棋盘的行号和列号都是从 0 开始。即最左上角的格子记为 (0, 0)，最右下角的记为 (N-1, N-1)。

现有一个 “马”（也译作 “骑士”）位于 (r, c) ，并打算进行 K 次移动。

如下图所示，国际象棋的 “马” 每一步先沿水平或垂直方向移动 2 个格子，然后向与之相垂直的方向再移动 1 个格子，共有 8 个可选的位置。

现在 “马” 每一步都从可选的位置（包括棋盘外部的）中独立随机地选择一个进行移动，直到移动了 K 次或跳到了棋盘外面。

求移动结束后，“马” 仍留在棋盘上的概率。

78. 场景题：大文件中的 id 计算

题目：

一个5T的文件，里面全是id，1-10^9 ，如何计算不同id的个数

79. 求中位数

题目：

一个有序数组，从随即一位截断，把前段放在后边，如 4 5 6 7 1 2 3求中位数

80. 输出第 n 个字符

题目：

一个形如 123456789101112…… 的字符串，输入一个 n（很大很大），输出字符串第 n 个字符

81. 公交车超载

题目：

一辆公交车，有 m 站，最多坐 n 人，输入一路上票的信息（即上车下车站），输出会不会超载。

82. 场景题：台球入洞

题目：

坐标系中有一个球桌，四个角坐标：(0,0), (0,4), (2,4), (2,0)，一颗球在 (1,1)，请问从哪些角度可以射入洞内（可无限次碰撞）？

83. 完全二叉树的节点个数

题目：

求完全二叉树的节点个数，小于O(n)，并分析复杂度

84. 链表实现一个栈

题目：

链表实现一个栈

85. 加油站 + 柠檬水找零

(1) 加油站

难度级别：中等

题目：

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

(2) 柠檬水找零

难度级别：简单

题目：

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。

顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

86. 堆

题目：

手写jdk中的优先级队列 PriorityQueue（最小堆）

87. 圆圈剩下的数字（约瑟夫环）

难度级别：简单

题目：

0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

88. 和为K的子数组

难度级别：中等

题目：

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

89. 设计模式

题目：

说说你知道的设计模式，说说项目里用到的设计模式，说说策略模式，设计一个下棋的场景问如何结合设计模式使用，设计模式什么时候继承，什么时候委托？

90. 代码输出

题目：

以下代码题输出什么？

1. Map<Short, String> map = new HashMap<>();

2. for(short i = 0; i <100; i++) {

3. map.put(i, String.valueOf(i));

4. map.remove(i-1);

5. }

6. System.out.println(map.size());

由于文章篇幅原因，全部90题答案和解析思路不能全部上传，有需要的朋友一键三连+评论，然后添加我的VX（tkzl6666）即可免费领取。