我一直在发布关于数据结构和算法的各类面试例题，诸如数组（Array）、队列（Queue）、堆栈（Stack）、二进制树（Binary tree）、链表（LinkedList）、字符串（String）、数字（Number）、动态数组（ArrayList）等等。本文是对我过去发布的这些例题的一份汇总和索引，将来再出新例题时我也会添加到这里。这些题目都是关于数据结构和算法常见的面试问题。
如果你想练习、提升数据结构和算法程序的水平，这篇汇总文章就很值得收藏了。练习这些题目时，我建议读者先自己做一遍再检查答案。
我知道面试中一般不会直接问这些问题，其中有很多题目也很老了，但毕竟它们都是精选出来的好题，可以帮助大家提升编程、算法和解决问题的能力。
堆栈
问题 1：使用数组来实现堆栈
编写进栈（push）和出栈（pop）方法来演示堆栈行为（后进先出，Last In First Out）。
问题 2：使用链表实现堆栈
编写进栈和出栈方法来演示堆栈行为（后进先出）。
问题 3：使用两个队列实现堆栈
本题需要使用两个队列来实现堆栈行为。编写进栈和出栈方法来演示 Stack 行为（后进先出）。
问题 4：使用另一个堆栈排序指定堆栈
本题需要使用另一个堆栈排序指定堆栈。本题可以使用堆栈的进栈和出栈操作来完成任务。
队列
问题 5：在 Java 中使用数组实现队列
本题需要使用数组来实现队列
问题 6：使用两个队列实现堆栈
本题需要使用链表来实现队列。
链表
问题 7：在 Java 中实现单链表
本题需要实现单链表数据结构。编写一个简单的程序来演示插入和删除操作。
问题 8：如何使用 Java 反转链表 。
本题需要编写一个迭代和递归的方案来反转链表。
问题 9：如何查找链表的中间元素 。
本题需要编写一个 Java 程序以最优化的方式查找链表的中间元素。
问题 10：如何从链表中找到倒数第 n 个元素 。
本题需要编写 Java 程序以最优化的方式查找链表的倒数第 n 个元素。
在问题 9 中，节点 7 就是链表中倒数第 3 个元素。
问题 11：如何检测链表中的循环。如果链表有循环，请找到循环的起始节点 。
本题需要编写一个 Java 程序来检测链表中是否存在循环，如果找到循环则需要找到它的起始节点。
问题 12：如何检查链表是否是回文？
回文是一个单词、短语、数字或其它符号或元素序列，它们正序和倒序读起来是一样的。例如 12121 就是一个回文，因为它正读反读都一样。“madam”也是一个回文。我们需要编写 Java 程序来检查链表是否是回文。
问题 13：找到两个链表的交集？
给定两个单链表，检查两个链表是否相交；如果它们相交就找出交集。
问题 14：如何反转成对链表？
本题需要编写一个 Java 程序来反转成对链表。
问题 15：如何使用 Java 实现双链表？
本题需要编写一个 Java 程序实现双链表。
数组
问题 16：编写 Java 程序以查找数组中最小和最大的元素 。
本题中会给定一个包含许多数字的数组，需要找出其中最小和最大的元素
问题 17：找出数组中缺少的数字 。
本题会给定一个包含 1 到 n 的整数数组，但少了 1 到 n 中的某个数字。需要提供找到丢失数字的最佳方案。数组中的数字不能重复。
例如：
int[] arr1={7,5,6,1,4,2};
Missing number: 3（缺少的数字是 3）
int[] arr2={5,3,1,2};
Missing number: 4（缺少的数字是 4）
问题 18：在已旋转和排序的数组中搜索元素 。
本题会给定一个排序和旋转过的数组，如下所示：
int arr[]={16,19,21,25,3,5,8,10};
如果你发现数组已做过排序和旋转，就要在 o(log n) 的时间复杂度内搜索上述数组中的元素。
问题 19：找到已排序和旋转的数组中的最小元素 。
本题会给定一个已排序和旋转的数组，如下所示：
int arr[]={16,19,21,25,3,5,8,10};
Minimum element in the array: 3（数组中最小的元素是 3）
如果你发现数组已做过排序和旋转，就要在 o(log n) 的时间复杂度内找出数组中的最小元素。
问题 20：找到数组中的第二大数字
本题会给定一个已排序和旋转过的数组，如下所示：
例如 ：
int[] arr1={7,5,6,1,4,2};
Second largest element in the array: 6（数组中第二大的元素是 6）
问题 21：查找数组中出现奇数次数的数字
本题会给定一个整数数组，其中所有数字都会出现偶数次，只有一个例外。本题需要找到出现奇数次数的数字，方案限定在 o(n) 的时间复杂度和 o(1) 的空间复杂度内。
例如 ：
int array[] = new int[]{20, 40, 50, 40, 50, 20, 30, 30, 50, 20, 40, 40, 20};
Number which occurs odd number of times is: 50（出现奇数次的数字是 50）
问题 22：找到火车站所需的最少站台数量
本题会给定前往特定车站列车的到达和离开时间。需要找到在任意时间点上车站所需的最小站台数量。
例如 ：
arrival[] = {1:00, 1:40, 1:50, 2:00, 2:15, 4:00}
departure[] = {1:10, 3:00, 2:20, 2:30, 3:15, 6:00}
No. of platforms required in above scenario = 4（上述情况下需要的最少站台数为 4）
请注意，列车到达时间按时间顺序排列。
问题 23：在数组中找到一个和最接近零的元素对
给定一个包含正负整数的数组，需要找出数组中和最接近零的整数对。
例如 ：
array[]={1,3,-5,7,8,20,-40,6};
The pair whose sum is closest to zero: -5 and 6（和最接近零的整数对是 -5 和 6）
问题 24：给定一个已排序的数组和一个数字 x，找到数组中和最接近 x 的元素对
给定一个已排序数组，我们需要找到数组中和最接近数字 X 的元素对。
例如 ：
array[]={-40,-5,1,3,6,7,8,20};
The pair whose sum is closest to 5: 1 and 3（这里和最接近 5 的元素对是 1 和 3）
解决方案：使用 Java 在数组中找到和最接近 X 的元素对
问题 25：查找数组中和等于给定数字的所有元素对
给定一个数组，我们需要找到和等于数 X 的所有元素对。
例如 ：
array[]={ -40, -5, 1, 3, 6, 7, 8, 20 };
Pair of elements whose sum is equal to 15: 7, 8 and -5, 20（和等于 15 的元素对有 7 和 8、-5 和 20）
问题 26：给定一个数字 0 和 1 随机排序的数组，需要把 0 和 1 分开 。
例如 ：
arr[] = {0,1,0,0,1,1,1,0,1}
Array after separating 0 and 1 numbers（将 0 和 1 分开后数组变为）:
{0,0,0,0,1,1,1,1,1}
问题 27：在数组中分离奇数和偶数
给定一个整数数组，需要在数组中分离奇数和偶数。
请注意，元素顺序可以改动。
例如 ：
arr[] = {12, 17, 70, 15, 22, 65, 21, 90}
Array after separating odd and even numbers（分离奇偶数后数组变为）:
{12, 90, 70, 22, 15, 65, 21, 17}
问题 28：给定一个只有 0、1 和 2 的数组。编写一个函数，以 O(n) 的时间复杂度排序给定数组 。
例如 ：
Input:
[1, 2, 2, 0, 0, 1, 2, 2, 1]
Output:
[0, 0, 1, 1, 1, 2, 2, 2, 2]
问题 29：在数组中查找局部最小元素
局部最小元素比其旁边的元素都小
例如 ：
Input:
int [] arr = {10, 5, 3, 6, 13, 16, 7};
Output: 3
int []arr = {11,12,13,14};
Output: 11
int []arr = {10};
Output: 10
int []arr = {8,6};
Output: 6
问题 30：使用 Java 找到滑动窗口的最大值
给定一个整数数组和一个整数 k，从所有大小为 K 的连续子数组中找出最大元素。
例如 ：
Input:
Input: int[] arr = {2,6,-1,2,4,1,-6,5}
int k = 3
output: 6,6,4,4,4,5
问题 31：计算已排序数组中每个元素的出现次数（或频率）
给定包含重复项的整数排序数组。找出数组中存在的每个元素的频率。
频率定义为数组中元素的出现次数。
例如：
Input:
Input:
int[] arr = {1, 1, 1, 3, 3, 4, 5, 5, 6, 6};
Output:
Frequency of 1 is: 3（数字 1 的频率为 3）
Frequency of 3 is: 2
Frequency of 4 is: 1
Frequency of 5 is: 2
Frequency of 6 is: 2
问题 32：在数组中查找等于给定和的子数组 。
给定一个非负整数数组和一个数字。需要打印和等于给定整数的子数组的所有起始和结束索引。
例如 ：
Input:
Input-int[] arr = {2, 3, 6, 4, 9, 0, 11};
int num = 9
Output-
starting index: 1, Ending index: 2
starting index: 5, Ending index: 5
starting index: 5, Ending index: 6
问题 33：找到数组中的峰值元素 。
数组中的峰值元素大于等于邻近元素，即对于索引中 i 处的元素，索引 i-1 和 i+1 处的邻近元素必须小于等于前者。
问题 34：找到数组中的 leader 。
我们需要打印数组中的所有 leader。Leader 元素大于它右侧的所有元素。
例如 ：
arr[]={14, 12, 70, 15, 99, 65, 21, 90}
Here 99 and 90 are leader elements（99 和 90 是 leader 元素）
问题 35：在已排序的二进制数组中找出数字 1 的数量 。
在给定的已排序二进制数组中打印数字 1 的数量。
例如 ：
Input:
int[] arr = {0,0,0,1,1,1,1};
output: 4
int[] arr = {0,0,1};
output: 1
问题 36：在整数数组中查找第一个重复元素 。
找到整数数组中的第一个重复元素。
例如：
Input:
Input: array[] = {10, 7, 8, 1, 8, 7, 6}
Output: 7 [7 is the first element actually repeats（7 是第一个重复元素）]
问题 37：检查数组元素是否连续 。
给定一个数组，我们需要检查数组是否是连续元素。
例如 ：
Input: array[] = {5, 3, 4, 1, 2}
Output: true
As array contains consecutive elements from 1 to 5（数组中有 1 到 5 的连续元素）
Input: array[] = {47, 43, 45, 44, 46}
Output: true
As array contains consecutive elements from 43 to 47
Input: array[] = {6, 7, 5, 6}
Output: false
As array does not contain consecutive elements.（数组中没有连续元素）
问题 38：Java 中数组的排列 。
给定包含不同整数的数组，打印数组的所有排列。
例如 ：
array: [10, 20, 30]
Permuations are:
[10, 20, 30]
[10, 30, 20]
[20, 10, 30]
[20, 30, 10]
[30, 10, 20]
[30, 20, 10]
问题 39：在 K 位置旋转数组。
例如 ：
N=6 and k=2
If Arr[] = {1, 2, 3, 4, 5, 6} and k=2
then rotated array will be {5, 6, 1, 2, 3, 4}
[解决方案：按 K 位置旋转数组 ( https://java2blog.com/rotate-array-by-k-positions/ )
问题 40：股票买卖策略 。
给定整数数组，元素代表某日股价，找出一次交易可获得的最大利润。
所以需要找出（买入日，卖出日）的元素对，买入日值小于等于卖出日值，并最大化利润。
例如 ：
int arr[]={14, 12, 70, 15, 99, 65, 21, 90};
Max profit can be gain by buying at 1th day(0 based indexing) and sell at 4th day.(第一天买入第四天卖出利润最大）
Max profit = 99-12 =87
问题 41：找出数组中后面较大元素与前面较小元素的最大差值
给定整数数组，找出后面较大元素与前面较小元素的最大差值
例如 ：
int arr[]={14, 12, 70, 15, 95, 65, 22, 30};
Max Difference =95-12 = 83
问题 42：在按行和按列排序的矩阵中搜索
给定按行和按列排序的矩阵，需要以最小的时间复杂度搜索元素。
问题 43：和最大的连续子数组 。
在一维数字数组内找到和最大的连续子数组。
例如 ：
for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6
问题 44：在数组中找到和为给定值的连续子数组 。
给定正整数数组和值 X，找到其和等于 X 的连续子数组。
例如 ：
arr[]={14, 12, 70, 15, 99, 65, 21, 90};
X =97.
Sum found between index 1 to 3
Elements are 12, 17 and 15
问题 45：使用 Java 找出字符串数组中最长的公共前缀 。
给定字符串数组，找出最长的公共前缀。
例如 ：
字符串 [] strArr={"java2blog","javaworld","javabean","javatemp"};
So Longest common prefix in above 字符串 array will be “java” as all above string starts with “java”. 最长的公共前缀是“java”。
问题 46：使用 Java 查找集合的所有子集（幂集） 。
给定一组不同整数的集合，返回所有可能的子集（幂集）。
例如 ：
Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
字符串
问题 47：如何使用 Java 反转字符串？ 可以在不使用任何 Java 内置方法的前提下编写方案吗？
解决方案 ：有很多方法，例如
- 使用 for 循环
- 使用递归
- 使用字符串 Buffer
参考”使用 Java 反向字符串“
问题 48：编写一个 Java 程序来检查两个字符串是否是变位词（Anagram） 。
解决方案 ：如果两个字符串有相同的字符但顺序不同，它们就是变位词，如 Angel 和 Angle。
有几种方法，如
- 使用字符串方法
- 使用 array.sort
问题 49：使用 Java 检查字符串是否只有独立字符 。
解决方案 ：可以用以下方法
- 使用 HashSet
- 使用字符串的 indexOf 和 lastIndexOf 方法
- 使用 ascii 值的字符。
完整解决方案参考“检查字符串是否只包含独立字符”
问题 50：如何用 Java 检查一个字符串是否是另一个的旋转？
解决方案：假设 要检查 str1 和 str2 是否相互旋转。
- 使用 str3=str1 + str1 创建一个新字符串
- 检查 str3 是否包含 str2
- 如果 str3 包含 str2，那么 str2 是 str1 的旋转，否则就不是
完整方案参考“使用 Java 检查一个字符串是否是另一个的旋转”
问题 51：如何使用 Java 中找到字符串中的重复字符？
解决方案 ：
- 创建一个 HashMap ，字符串的字符作为键插入，字符计数就是值。
- 如果 Hashamap 已经包含某字符，则将其计数增加 1，否则将该字符放在 HashMap 中。
- 如果某字符的值大于 1，则表示它是该字符串中的重复字符。
参阅“查找字符串中的重复字符”
问题 52：使用 Java 查找字符串中的第一个非重复字符 。
解决方案 ：方法有
- 使用 LinkedHashMap
- 使用 indexOf 和 lastIndexOf 方法。
问题 53：使用 Java 查找字符串的所有子字符串 。
解决方案 ：
例如，如果输入为“abb”，则输出应为“a”，“b”，“b”，“ab”，“bb”，“abb”
我们使用字符串类的 subString 方法来查找所有子字符串。
参考“查找字符串的所有子字符串”
问题 54：不使用任何 Java 内置方法查找字符串的长度 。
解决方案 ：本题可以使用 try catch 块来捕获 StringIndexOutOfBoundException，出现此异常时可以简单地返回 i（出现异常的索引）
问题 55：使用 Java 打印字符串的所有排列 。
解决方案 ：取出字符串的第一个字符插入字符串剩余排列的每个位置，做递归。
二叉树
问题 56：如何遍历二叉树？
遍历二叉树有三种方法。
问题 57：编写一个算法做二叉树的层序遍历 。
可以使用队列数据结构。
问题 58：二叉树的螺旋顺序遍历 。
问题 59：如何打印二叉树的叶节点？
上图中二叉树的叶节点是 5、30、55、70
问题 60：如何对二叉树的叶节点计数
问题 59 中使用的二叉树的叶节点数为 4。
问题 61：如何打印二叉树中从根到叶的所有路径 。
问题 62：如何在二叉树中查找节点级别 。
给定一个节点，需要找到节点的级别。例如：问题 61 中节点 70 的级别为 3。
问题 63：如何在二叉树中找到最大元素 。
问题 64：如何在二叉树中找到最低公共祖先（LCA） 。
问题 65：如何对二叉树做边界遍历 。
如下图所示。
问题 66：如何打印二叉树的垂直和？
本题需要找到位于同一列中的节点之和。
问题 67：在二叉树中找出和等于给定值的子树数量 。
给定二叉树和整数。本题需要找到所有节点和等于给定整数的子树数量。
 
二叉搜索树
问题 68：什么是二叉搜索树？
二叉搜索树是一种特殊类型的二叉树，具有以下属性。
- 小于根的节点在左子树中。
- 大于根的节点在右子树中。
- 没有重复节点
- 左右子树也是二叉搜索树。
问题 69：编写算法，在二叉搜索树中插入一个节点 。
问题 70：编写算法，删除二叉搜索树中的节点 。
问题 71：如何在二叉搜索树中找到最小和最大元素？
解决方案：二叉搜索树的最左侧和最右侧节点分别是最小和最大节点
问题 72：如何在二叉搜索树中找到最低共同祖先（LCA）？
问题 73：在二叉搜索树中查找中序后继
问题 74：将已排序数组转换为平衡二叉搜索树
问题 75：将已排序的链表转换为平衡二叉搜索树
问题 76：使用 Java 检查二叉树是否为二叉搜索树
排序
问题 77：编写一个算法来实现冒泡排序 。
问题 78：编写一个算法来实现插入排序 。
问题 79：编写一个算法来实现选择排序 。
问题 80：编写合并排序算法，计算其复杂度 。
问题 81：实现堆排序 。
问题 82：使用 Java 实现快速排序 。
问题 83：使用 Java 实现希尔排序 。
问题 84：使用 Java 实现计数排序 。
问题 85：什么是二分搜索？ 写一个算法来使用二分搜索在排序数组中找到一个元素 。
图
问题 86：编写一个算法在图中实现深度优先搜索 。
问题 87：编写算法在图中实现广度优先搜索 。
问题 88：从源到所有其他顶点解释 Dijkstra 算法
问题 89：解释 Bellman Ford 算法（最短路径算法）以找到最短距离
问题 90：解释 Kruskal 查找最小生成树算法
动态编程
问题 91：给定两个字符串，找到最长的公共子串 。
问题 92：给定字符串 A 和 B。找出它们的最长公共子序列（LCS） 。
问题 93：给定矩阵，我们需要计算 MxN 矩阵从左上到右下的所有路径。可以向下或向右移动 。
问题 94：Java 中的编辑距离问题
给定两个字符串 String1 和 String2，用给定操作以最小步数将 String1 转换为 String2。使用任何一个给定操作都会增加步数。
给定操作有：
- 删除：此操作允许从字符串中删除任何一个字符。
- 插入：此操作允许在字符串中的任何位置插入一个字符。
- 替换：此操作允许用字符替换字符串中的任何一个字符
问题 95：Java 中的找零问题
给定要支付的金额和支付币种。每种币值无限供应。为了支付给定的金额，打印所有可能的货币组合 。
问题 96：到达最后一个索引的最小跳转次数 。
其它
问题 97：什么是算法以及如何计算算法的复杂度？
问题 98：使用 Java 实现 trie 数据结构 。
问题 99：使用 Java 计算 n 阶乘末尾 0 的个数 。
问题 100：直方图中最大的矩形区域 。
问题 101：检查 Java 中表达式的平衡括号 。
问题 102：什么是记忆化（Memoization） 。
解 ：
记忆化是将结果存储在数据结构中（通常是 Hashtable 或 HashMap 或数组），确保方法不会对同一输入执行多次。
这都是关于数据结构和算法面试问题的问题。读者可能还喜欢下列文章：
- Java 核心面试问题
- Java Collections 面试问题
- Java 字符串面试问题
- Java 中的 OOP 面试问题
- Java 多线程面试问题
- Java 中的异常处理面试问题
- Java 序列化面试问题
- Web 服务面试问题
- Restful 网络服务面试问题
- Spring 面试问题
- Hibernate 面试问题
作者介绍 ：
Arpit Mandliya 是一位 Java 博主、极客、梦想家！ 网站 Java2blog.com 的作者