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

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

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

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

通过本场 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.实现一个基本的计算器来计算一个简单的字符串表达式的值。

已有212人预订
预订达标
文章出炉
     
08月17日
09月19日
预订后,您将在09月19日之前获得一篇专享文章,您还将获得一张攻城狮的读者圈Pass
请务必添加GitChat服务号以查看活动进度及获取活动通知。
退款保证:
• 08月21日前,预订人数未达标,您将获得全额退款。
• 作者未按时完成文章,您将获得全额退款。
你可能还喜欢
被动收入 101 :使用云开发和 Taro 开发一个小程序
白宦成
深入浅出用户认证鉴权
hucheng
支付宝支付流程与服务端实现
江水
10 个代码细节助你培养大牛思维
zaqweb
快速成长:大学期间 0 到 100000 + 、拿到阿里 offer,我都做了什么?
latent
不把握好这 3 个原则,你的简历就是废纸
白朔天
深入浅出华为鸿蒙操作系统
闪客sun
Zookeeper 详解与实践,你面试工作都绕不开的必考题!
latent
Java 编程(程序可靠性的 30 点建议)
OverWrite
带你手写一个 Mybatis 框架,全面了解 Mybatis 实现原理
当年明月
轻松 TDD 之旅 2.0
张晓龙
快速搭建 Spring Boot 后台管理系统框架
JohnDeng
Vue 实操指南
Fengy
如何雅致地处理代码中的异常
Fearless
使用批处理 bat 脚本提高工作效率
login
微信扫描登录
关注提示×
扫码关注公众号,获得 Chat 最新进展通知!
入群与作者交流×
扫码后回复关键字 入群
Chat·作者交流群
入群码
该二维码永久有效