保存成功
保存失败,请重试
提交成功

数据结构算法常见的 100 道面试题全解析:2019 版

作者/分享人:攻城狮
参加过国有交通部门的相关语音识别,轨迹,面部识别分析等项目。从事人工智能多年,有着丰富的经验,最近沉迷数据结构算法中

最近由于工作需要接触了不少关于数据结构算法的面试题目,从中总结了一些知识,也从网上筛过一些面试题,但是不是无法运行就是版本过低,让大家很是懊恼。所以我借此机会对大多数的数据结构算法的题目进行了一次总结,有大家见到过的也有没见到过的,并以实战的形式直接列出跑通的代码,有些题目我会给出多语言的版本,并列出详细的解题思路。虽然在大数据领域大家碰到复杂度特别高的数据结构不是特别的多,但是往往公司的面试都是很华丽的,所以还是好好准备一手,锻炼一下自己的逻辑思维。面试不会出很多原题,但是原理不会变,希望大家举一反三,能够彻底消化吸收。

通过本场 Chat,你将获得如下知识点:

  • 掌握 Java 的基础语法
  • 掌握数据结构算法的常见应用场景
  • 提升逻辑思维能力
  • 应对大部分随机面试题目

所有题目简单描述

难度系数:30%

1.统计所有小于非负整数 n 的质数的数量 。
2.给定一个仅包含大小写字母和空格 ' ' 的字符串,返回其最后一个单词的长度。
3.给定一个非负整数 c ,你要判断是否存在两个整数 a 和 b,使得 a2 + b2 = c。
4.统计字符串中的单词个数,这里的单词指的是连续的不是空格的字符。
5.给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是 O(n)。
6.在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...中找到第 n 个数字。
7.给定一个整数类型的数组 nums,请编写一个能够返回数组“中心索引”的方法。
8.实现 int sqrt(int x) 函数。计算并返回 x 的平方根,其中 x 是非负整数。
9.给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。
10.给出平面上三个点组成的列表,判断这些点是否可以构成回旋镖。
11.统计所有小于非负整数 n 的质数的数量。
12.给定一个正整数,返回它在 Excel 表中相对应的列名称。
13.给定一个整数 n,返回 n! 结果尾数中零的数量。
14.给定一个有相同值的二叉搜索树BST,找出 BST 中的所有众数(出现频率最高的元素)。
例如:

1
  \
   2
  /
 2

15.给定一个整数,写一个函数来判断它是否是 3 的幂次方。
16.给定一个二叉树,找出其最小深度。
17.不使用运算符 + 和 - ​​​​​​​,计算两整数 ​​​​​​​a 、b ​​​​​​​之和。
18.给定一个 N 叉树,返回其节点值的层序遍历。 (即从左到右,逐层遍历)。
19.给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
20.给定一个非负整数 num,反复将各个位上的数字相加,直到结果为一位数。
21.给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。
22.翻转一棵二叉树。
23.给你一个有效的 IPv4 地址 address,返回这个 IP 地址的无效化版本。
24.实现函数 ToLowerCase(),该函数接收一个字符串参数 str,并将该字符串中的大写字母转换成小写字母,之后返回新的字符串。
25.给定二叉搜索树的根结点 root,返回 L 和 R(含)之间的所有结点的值的和。

难度系数:60%

26.给定一个字符串,逐个翻转字符串中的每个单词。
27.比较两个版本号 version1 和 version2。
如果 version1 > version2 返回 1,如果 version1 < version2 返回 -1, 除此之外返回 0。

28.一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?

29.给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。
30.给定一组非负整数,重新排列它们的顺序使之组成一个最大的整数。

31.你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。

32.给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。

33.给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
34.以 Unix 风格给出一个文件的绝对路径,你需要简化它。或者换句话说,将其转换为规范路径。
35.给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。

36.给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是 O(log n) 级别。 如果数组中不存在目标值,返回 [-1, -1]。

37.给出一个区间的集合,请合并所有重叠的区间。
38.给定一个含有 M x N 个元素的矩阵(M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素。
39.给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。
40.峰值元素是指其值大于左右相邻值的元素。
给定一个输入数组 nums,其中 nums[i] ≠ nums[i+1],找到峰值元素并返回其索引。
41.给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
42.给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
43.给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
44.运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。
45.给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。
46.给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
47.给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。
48.给定一个经过编码的字符串,返回它解码后的字符串。
49.反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
50.打乱一个没有重复元素的数组。
51.给定一个二叉树,根节点为第1层,深度为 1。在其第 d 层追加一行值为 v 的节点。

添加规则:给定一个深度值 d (正整数),针对深度为 d-1 层的每一非空节点 N,为 N 创建两个值为 v 的左子树和右子树。

52.给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
53.给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。​
设计一个算法计算出最大利润。 54.给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。 55.给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

56.给出二叉树的根节点 root,树上每个节点都有一个不同的值。如果节点值在 to_delete 中出现,我们就把该节点从树上删去,最后得到一个森林(一些不相交的树构成的集合)。返回森林中的每棵树。你可以按任意顺序组织答案。

57.给定一个可包含重复数字的序列,返回所有不重复的全排列。
58.给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。
59.给出一个完全二叉树,求出该树的节点个数。
60.给定一个目录信息列表,包括目录路径,以及该目录中的所有包含内容的文件,您需要找到文件系统中的所有重复文件组的路径。一组重复的文件至少包括二个具有完全相同内容的文件。
61.给定一个方形整数数组 A,我们想要得到通过 A 的下降路径的最小和。
62.给定一个非空数组,数组中元素为 a0, a1, a2, … , an-1,其中 0 ≤ ai < 231 。找到 ai 和aj 最大的异或 (XOR) 运算结果,其中0 ≤ i, j < n 你能在O(n)的时间解决这个问题吗?

63.给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。
64.对链表进行插入排序。
65.给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
66.给定一个字符串,请将字符串里的字符按照出现的频率降序排列。
67.给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
68.给定一个非空的整数数组,返回其中出现频率前 k 高的元素。
69.给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。
70.给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。
71.给定长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积
72.给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素 。
73.字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段,同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表 。
74.给定一个二叉树,返回它的中序 遍历。
75.给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合 。
76.给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

77.给定一个正整数 n,你可以做如下操作:

  1. 如果 n 是偶数,则用 n / 2替换 n。 2.如果 n 是奇数,则可以用 n + 1或n - 1替换 n。 n 变为 1 所需的最小替换次数是多少?

78.有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好 z升 的水?
79.给定一个二叉树,判断其是否是一个有效的二叉搜索树。
80.给定一个以字符串表示的非负整数 num,移除这个数中的 k 位数字,使得剩下的数字最小。

难度系数:90%

81.现在题目中给定的是两个数组,首先想到的应该是先将两个数组进行合并并且排序,继而再根据奇偶数直接返回中位数就可以
82.给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '' 的正则表达式匹配。'.' 匹配任意单个字符'' 匹配零个或多个前面的那一个元素
83.给定一个字符串 (s) 和一个字符模式 (p) ,实现一个支持 '?' 和 '*' 的通配符匹配。
84.验证给定的字符串是否可以解释为十进制数字。
85.二叉搜索树中的两个节点被错误地交换。请在不改变其结构的情况下,恢复这棵树。

输入: [1,3,null,null,2]
输出: [3,1,null,null,2]
   1     3
  /     /
 3   →  1
  \     \
   2     2

86.给定一个二维平面,平面上有 n 个点,求最多有多少个点在同一条直线上。
87.给定一个无序的数组,找出数组在排序之后,相邻元素之间最大的差值。如果数组元素个数小于 2,则返回 0。
88.给定一个整数 n,计算所有小于等于 n 的非负整数中数字 1 出现的个数。
89.将非负整数转换为其对应的英文表示。
90.给定一个仅包含数字 0-9 的字符串和一个目标值,在数字之间添加二元运算符(不是一元)+、- 或 * ,返回所有能够得到目标值的表达式。
91.删除最小数量的无效括号,使得输入的字符串有效,返回所有可能的结果。
92.给定一个仅包含小写字母的字符串,去除字符串中重复的字母,使得每个字母只出现一次。需保证返回结果的字典序最小(要求不能打乱其他字符的相对位置)。
93.给定一个非负整数数组和一个整数 m,你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。

94.给出一些不同颜色的盒子,盒子的颜色由数字表示,即不同的数字表示不同的颜色。你将经过若干轮操作去去掉盒子,直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子(k >= 1),这样一轮之后你将得到 k*k 个积分。当你将所有盒子都去掉之后,求你能获得的最大积分和。

95.给定一个正整数 n,找出小于或等于 n 的非负整数中,其二进制表示不包含 连续的1 的个数。
96.给定两个单词 word1 和 word2,计算出将 word1 转换成 word2 所使用的最少操作数 。

输入: word1 = "horse", word2 = "ros"
输出: 3
horse -> rorse (将 'h' 替换为 'r') → rorse -> rose (删除 'r') → rose -> ros (删除 'e')

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

98.有 1000 只水桶,其中有且只有一桶装的含有毒药,其余装的都是水。它们从外观看起来都一样。如果小猪喝了毒药,它会在 15 分钟内死去。 问题来了,如果需要你在一小时内,弄清楚哪只水桶含有毒药,你最少需要多少只猪?

99.在二维地图上, 0代表海洋, 1代表陆地,我们最多只能将一格 0 海洋变成 1变成陆地。
进行填海之后,地图上最大的岛屿面积是多少?(上、下、左、右四个方向相连的 1 可形成岛屿)
100.实现一个基本的计算器来计算一个简单的字符串表达式的值。

会员免费订阅
已有412人预订
预订达标
文章出炉
     
08月17日
11月14日
本场 Chat 文章已出炉,购买后即可阅读文章并获得一张攻城狮的读者圈Pass
请务必添加GitChat服务号以查看活动进度及获取活动通知。
退款保证:
• 08月21日前,预订人数未达标,您将获得全额退款。
• 作者未按时完成文章,您将获得全额退款。
你可能还喜欢
机器学习必备的数学知识,一次学会
白朔天
程序员的数学修养
李烨
数据结构算法常见的 100 道面试题全解析:2019 版
攻城狮
程序员的核心竞争力
李烨
程序员如何专注和管理时间
程序员的三门课
微服务架构深度解析与最佳实践
kimmking
多线程,设计模式,Netty 实战,带你手写一个分布式消息队列
当年明月
如何设计一个注册中心
star
深入 JVM 字节码,一步一图解析类的加载、链接、初始化、创建对象、程序执行的流程
CSDM
高效学习的途径
程序员的三门课
靠着这份 Java 核心面试知识整理(PDF),稳拿头条/菜鸟/字节 offer
一只Tomcat
程序员必须懂的架构入门课
IT老兵哥
程序员眼中后端技术点总结
技术征程
实战:Redis 高并发秒杀和分布式锁技术应用及项目剖析
朱学超
从 Vue 3 源码切入,全面掌握前端编译原理
修言
微信扫描登录
关注提示×
扫码关注公众号,获得 Chat 最新进展通知!
入群与作者交流×
扫码后回复关键字 入群
Chat·作者交流群
入群码
该二维码永久有效