我一直在发布关于数据结构和算法的各类面试例题，诸如数组（Array）、队列（Queue）、堆栈（Stack）、二进制树（Binary tree）、链表（LinkedList）、字符串（String）、数字（Number）、动态数组（ArrayList）等等。本文是对我过去发布的这些例题的一份汇总和索引，将来再出新例题时我也会添加到这里。这些题目都是关于数据结构和算法常见的面试问题。

如果你想练习、提升数据结构和算法程序的水平，这篇汇总文章就很值得收藏了。练习这些题目时，我建议读者先自己做一遍再检查答案。

我知道面试中一般不会直接问这些问题，其中有很多题目也很老了，但毕竟它们都是精选出来的好题，可以帮助大家提升编程、算法和解决问题的能力。

堆栈

问题1：使用数组来实现堆栈

编写进栈（push）和出栈（pop）方法来演示堆栈行为（后进先出，Last In First Out）。

解决方案：使用数组实现堆栈的Java程序

问题2：使用链表实现堆栈

编写进栈和出栈方法来演示堆栈行为（后进先出）。

解决方案：使用链表实现堆栈的Java程序

问题3：使用两个队列实现堆栈

本题需要使用两个队列来实现堆栈行为。编写进栈和出栈方法来演示Stack行为（后进先出）。

解决方案：使用两个队列实现堆栈的Java程序

问题4：使用另一个堆栈排序指定堆栈

本题需要使用另一个堆栈排序指定堆栈。本题可以使用堆栈的进栈和出栈操作来完成任务。

解决方案：使用另一个堆栈排序指定堆栈

队列

问题5：在Java中使用数组实现队列

本题需要使用数组来实现队列

解决方案：在Java中使用数组实现队列

问题6：使用两个队列实现堆栈

本题需要使用链表来实现队列。

解决方案：使用链表实现队列的程序

链表

问题7：在Java中实现单链表

本题需要实现单链表数据结构。编写一个简单的程序来演示插入和删除操作。

解决方案：在Java中实现单链表的程序

问题8：如何使用Java反转链表。

本题需要编写一个迭代和递归的方案来反转链表。

解决方案：使用Java反转链表的程序

问题9：如何查找链表的中间元素。

本题需要编写一个Java程序以最优化的方式查找链表的中间元素。

解决方案：查找链表中间元素的Java程序

问题10：如何从链表中找到倒数第n个元素。

本题需要编写Java程序以最优化的方式查找链表的倒数第n个元素。

在问题9中，节点7就是链表中倒数第3个元素。

解决方案：如何从链表中查找倒数第n个元素

问题11：如何检测链表中的循环。如果链表有循环，请找到循环的起始节点。

本题需要编写一个Java程序来检测链表中是否存在循环，如果找到循环则需要找到它的起始节点。

解决方案：如何检测链表中的循环

问题12：如何检查链表是否是回文？

回文是一个单词、短语、数字或其它符号或元素序列，它们正序和倒序读起来是一样的。例如12121就是一个回文，因为它正读反读都一样。“madam”也是一个回文。我们需要编写Java程序来检查链表是否是回文。

解决方案：用于检查链表是否为回文的Java程序

问题13：找到两个链表的交集？

给定两个单链表，检查两个链表是否相交；如果它们相交就找出交集。

解决方案：两个链表的交集

问题14：如何反转成对链表？

本题需要编写一个Java程序来反转成对链表。

解决方案：反转成对链表的Java程序

问题15：如何使用Java实现双链表？

本题需要编写一个Java程序实现双链表。

解决方案：Java中的双链表

数组

问题16：编写Java程序以查找数组中最小和最大的元素。

本题中会给定一个包含许多数字的数组，需要找出其中最小和最大的元素

解决方案：查找数组中最小和最大元素的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）

解决方案：查找数组中第二大数字的Java程序

问题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）

解决方案：查找数组中出现奇数次数字的Java程序

问题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）

解决方案：使用Java在数组中找出和最接近零的元素对

问题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}

解决方案：在数组中分离0和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}

解决方案：在数组中分离0和1

问题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]

解决方案：对只有0、1和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

解决方案：使用Java找到滑动窗口的最大值

问题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元素）

解决方案：在数组中查找leader

问题35：在已排序的二进制数组中找出数字1的数量。

在给定的已排序二进制数组中打印数字1的数量。

例如：

Input:
int[] arr = {0,0,0,1,1,1,1};
output: 4
int[] arr = {0,0,1};
output: 1

解决方案：在已排序的二进制数组中对数字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]

解决方案：Java中数组的排列

问题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”。

解决方案：使用Java找出字符串数组中最长的公共前缀

问题46：使用Java查找集合的所有子集（幂集）。

给定一组不同整数的集合，返回所有可能的子集（幂集）。

例如：

Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

解决方案：使用Java查找集合的所有子集

字符串

问题47：如何使用Java反转字符串？可以在不使用任何Java内置方法的前提下编写方案吗？

解决方案：有很多方法，例如

使用for循环
使用递归
使用字符串Buffer

参考”使用Java反向字符串“

问题48：编写一个Java程序来检查两个字符串是否是变位词（Anagram）。

解决方案：如果两个字符串有相同的字符但顺序不同，它们就是变位词，如Angel和Angle。

有几种方法，如

使用字符串方法
使用array.sort

参考“使用Java检查两个字符串是否是变位词”

问题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方法。

参考“使用Java查找字符串中第一个非重复字符”

问题53：使用Java查找字符串的所有子字符串。

解决方案：

例如，如果输入为“abb”，则输出应为“a”，“b”，“b”，“ab”，“bb”，“abb”

我们使用字符串类的subString方法来查找所有子字符串。

参考“查找字符串的所有子字符串”

问题54：不使用任何Java内置方法查找字符串的长度。

解决方案：本题可以使用try catch块来捕获StringIndexOutOfBoundException，出现此异常时可以简单地返回i（出现异常的索引）

参考“不使用任何Java内置方法查找字符串的长度”

问题55：使用Java打印字符串的所有排列。

解决方案：取出字符串的第一个字符插入字符串剩余排列的每个位置，做递归。

参考“使用Java打印字符串的所有排列”

二叉树

问题56：如何遍历二叉树？

遍历二叉树有三种方法。

问题57：编写一个算法做二叉树的层序遍历。

可以使用队列数据结构。

解决方案：二叉树的层序遍历

问题58：二叉树的螺旋顺序遍历。

解决方案：二叉树的螺旋顺序遍历

问题59：如何打印二叉树的叶节点？

上图中二叉树的叶节点是5、30、55、70

解决方案：打印二叉树的叶节点

问题60：如何对二叉树的叶节点计数

问题59中使用的二叉树的叶节点数为4。

解决方案：对二叉树的叶节点计数

问题61：如何打印二叉树中从根到叶的所有路径。

解决方案：打印二叉树中从根到叶的所有路径

问题62：如何在二叉树中查找节点级别。

给定一个节点，需要找到节点的级别。例如：问题61中节点70的级别为3。

解决方案：在二叉树中查找节点级别

问题63：如何在二叉树中找到最大元素。

解决方案：在二叉树中查找最大元素

问题64：如何在二叉树中找到最低公共祖先（LCA）。

解决方案：在二叉树中查找LCA

问题65：如何对二叉树做边界遍历。

如下图所示。

解决方案：二叉树的边界遍历

问题66：如何打印二叉树的垂直和？

本题需要找到位于同一列中的节点之和。

解决方案：如何打印二叉树的垂直和

问题67：在二叉树中找出和等于给定值的子树数量。

给定二叉树和整数。本题需要找到所有节点和等于给定整数的子树数量。

解决方案：在二叉树中计算和等于给定值的子树数量

&nbsp

二叉搜索树

问题68：什么是二叉搜索树？

二叉搜索树是一种特殊类型的二叉树，具有以下属性。

小于根的节点在左子树中。
大于根的节点在右子树中。
没有重复节点
左右子树也是二叉搜索树。

问题69：编写算法，在二叉搜索树中插入一个节点。

解决方案：在二叉搜索树中插入节点

问题70：编写算法，删除二叉搜索树中的节点。

解决方案：删除二叉搜索树中的节点

问题71：如何在二叉搜索树中找到最小和最大元素？

解决方案：二叉搜索树的最左侧和最右侧节点分别是最小和最大节点

问题72：如何在二叉搜索树中找到最低共同祖先（LCA）？

解决方案：在二叉搜索树中查找LCA

问题73：在二叉搜索树中查找中序后继

解决方案：二叉搜索树的中序后继

问题74：将已排序数组转换为平衡二叉搜索树

解决方案：将已排序的排序数组转换为平衡二叉搜索树

问题75：将已排序的链表转换为平衡二叉搜索树

解决方案：将已排序的链表转换为平衡二叉搜索树

问题76：使用Java检查二叉树是否为二叉搜索树

解决方案：使用Java检查二叉树是否为二叉搜索树

排序

问题77：编写一个算法来实现冒泡排序。

解决方案：Java中的冒泡排序

问题78：编写一个算法来实现插入排序。

解决方案：Java的插入排序

问题79：编写一个算法来实现选择排序。

解决方案：Java的选择排序

问题80：编写合并排序算法，计算其复杂度。

解决方案：Java的合并排序

问题81：实现堆排序。

解决方案：Java的堆排序

问题82：使用Java实现快速排序。

解决方案：使用Java实现快速排序

问题83：使用Java实现希尔排序。

解决方案：使用Java实现希尔排序

问题84：使用Java实现计数排序。

解决方案：使用Java实现计数排序

问题85：什么是二分搜索？写一个算法来使用二分搜索在排序数组中找到一个元素。

解决方案：Java中的二分搜索算法

图

问题86：编写一个算法在图中实现深度优先搜索。

解决方案：Java中的深度优先搜索

问题87：编写算法在图中实现广度优先搜索。

解决方案：Java中的广度优先搜索

问题88：从源到所有其他顶点解释Dijkstra算法

解决方案：Java中的Dijkstra算法

问题89：解释Bellman Ford算法（最短路径算法）以找到最短距离

解决方案：Java中的Bellman ford算法

问题90：解释Kruskal查找最小生成树算法

解决方案：Kruskal算法

动态编程

问题91：给定两个字符串，找到最长的公共子串。

解决方案：使用Java查找最长公共子字符串

问题92：给定字符串A和B。找出它们的最长公共子序列（LCS）。

解决方案：Java中的最长公共子序列

问题93：给定矩阵，我们需要计算MxN矩阵从左上到右下的所有路径。可以向下或向右移动。

解决方案：计算矩阵中的所有路径

问题94：Java中的编辑距离问题

给定两个字符串String1和String2，用给定操作以最小步数将String1转换为String2。使用任何一个给定操作都会增加步数。

给定操作有：

删除：此操作允许从字符串中删除任何一个字符。
插入：此操作允许在字符串中的任何位置插入一个字符。
替换：此操作允许用字符替换字符串中的任何一个字符

解决方案：Java中的编辑距离问题

问题95：Java中的找零问题

给定要支付的金额和支付币种。每种币值无限供应。为了支付给定的金额，打印所有可能的货币组合。

解决方案：Java中的找零问题

问题96：到达最后一个索引的最小跳转次数。

解决方案：到达最后一个索引的最小跳转次数

其它

问题97：什么是算法以及如何计算算法的复杂度？

解决方案：如何计算算法的复杂度

问题98：使用Java实现trie数据结构。

解决方案：使用Java实现trie数据结构

问题99：使用Java计算n阶乘末尾0的个数。

解决方案：使用Java计算n阶乘末尾0的个数

问题100：直方图中最大的矩形区域。

解决方案：计算直方图中的最大矩形区域

问题101：检查Java中表达式的平衡括号。

解决方案：检查Java中表达式的平衡括号

问题102：什么是记忆化（Memoization）。

解：

记忆化是将结果存储在数据结构中（通常是Hashtable或HashMap或数组），确保方法不会对同一输入执行多次。

Java中的记忆化示例

这都是关于数据结构和算法面试问题的问题。读者可能还喜欢下列文章：

查看英文原文：https://hackernoon.com/top-100-data-structure-and-algorithms-interview-questions-for-practice-d5071e92321e

作者介绍：

Arpit Mandliya是一位Java博主、极客、梦想家！网站Java2blog.com的作者

创作场景

Java 数据结构和算法百大面试题