引言

常见的数据结构与算法题目，涵盖了数组、链表、栈、队列、二叉树、哈希表、字符串、图、排序和查找等方面的考察点。每个题目都附带有LeetCode的链接，可以点击链接了解更多题目详情

概述

类型

题目

考察点

难度

LeetCode链接

数组

两数之和

哈希表、查找

简单

LeetCode 1

链表

合并两个有序链表

链表操作、指针

简单

LeetCode 21

栈

有效的括号

栈、字符串处理

简单

LeetCode 20

队列

循环队列设计

队列、数组

中等

LeetCode 622

二叉树

对称二叉树

二叉树递归、对称性判断

简单

LeetCode 101

哈希表

两个数组的交集 II

哈希表、数组

简单

LeetCode 350

字符串

最长公共前缀

字符串处理、前缀判断

简单

LeetCode 14

图

克隆图

图的遍历、深拷贝

中等

LeetCode 133

排序

合并排序的数组

归并排序、数组操作

简单

LeetCode 88

查找

第 K 个数

快速选择、二分查找

中等

LeetCode 215

两数之和（LeetCode 1,Easy）

标签：哈希表|数组

题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9

输出：[0,1]

解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6

输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6

输出：[0,1]

提示：

2 <= nums.length <= 104

-109 <= nums[i] <= 109

-109 <= target <= 109

只会存在一个有效答案

原题：LeetCode 1

思路及实现

方式一：暴力解法（不推荐）

思路

最容易想到的方法是枚举数组中的每一个数 x，寻找数组中是否存在 target - x。 当我们使用遍历整个数组的方式寻找 target - x 时，需要注意到每一个位于 x 之前的元素都已经和 x 匹配过，因此不需要再进行匹配。而每一个元素不能被使用两次，所以我们只需要在 x 后面的元素中寻找 target - x。

代码实现

JAVA版本

import java.util.HashMap;

public int[] twoSum(int[] nums, int target) {

int n = nums.length;

for (int i = 0; i < nums.length; i++) {

// 遍历数组，从第一个元素开始

for (int j = i + 1; j < nums.length; j++) {

// 在当前元素后面的元素中查找与目标值相加等于target的元素

if (nums[i] + nums[j] == target) {

// 如果找到了符合条件的元素对

return new int[]{

i, j}; // 返回这两个元素的下标

}

}

}

return new int[0]; // 如果没有找到符合条件的元素对，则返回空数组

}

C语言版本

#include

#include

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {

int* result = (int*)malloc(2 * sizeof(int)); // 分配保存结果的内存空间

*returnSize = 0; // 初始化返回结果数组的大小为0，表示没有找到满足条件的元素对

for (int i = 0; i < numsSize; i++) {

// 外层循环遍历数组中的每个元素

for (int j = i + 1; j < numsSize; j++) {

// 内层循环遍历当前元素后面的每个元素

if (nums[i] + nums[j] == target) {

// 检查两个元素的和是否等于目标值

result[0] = i; // 将符合条件的第一个元素的下标存入结果数组的第一个位置

result[1] = j; // 将符合条件的第二个元素的下标存入结果数组的第二个位置

*returnSize = 2; // 更新返回结果数组的大小为2

return result; // 返回结果数组

}

}

}

return result; // 返回结果数组，如果没有找到满足条件的元素对，数组中的元素值均为0

// 注意：需要在适当的时候释放result指向的动态分配内存，以避免内存泄漏

}

python3版本

from typing import List

def twoSum(nums: List[int], target: int) -> List[int]:

result = [] # 用于存储结果的列表

n = len(nums)

for i in range(n): # 外层循环遍历列表中的每个元素

for j in range(i+1, n): # 内层循环遍历当前元素后面的每个元素

if nums[i] + nums[j] == target: # 检查两个元素的和是否等于目标值

result.append(i) # 将符合条件的第一个元素的下标添加到结果列表中

result.append(j) # 将符合条件的第二个元素的下标添加到结果列表中

return result # 返回结果列表

return result # 如果没有找到满足条件的元素对，返回空列表

复杂度分析：

时间复杂度分析：O(n^2)，其中n为数组nums的长度。这是由于代码使用了两层循环来遍历数组。外层循环将执行n次，而内层循环则将执行(n-1)次、(n-2)次、…、2次、1次，总的执行次数为n * (n-1) / 2，即O(n^2)。

空间复杂度分析：O(1)，即常数级别的空间复杂度。因为代码只使用了常数个额外变量来存储元素的下标和存储结果的数组。

方式二：哈希表（推荐）

思路

注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。

使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。

这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

下图以[2,7,11,15]为例

代码实现

JAVA版本

import java.util.HashMap;

class Solution {

public int[] twoSum(int[] nums, int target) {

//key为当前值，value为当前值的位置

HashMap map = new HashMap<>();

for (int i = 0; i < nums.length; i++) {

int complement = target - nums[i]; // 计算差值，即目标值与当前元素的差值

if (map.containsKey(complement)) {

return new int[]{

map.get(complement), i}; // 返回HashMap中保存的差值元素的下标和当前元素的下标

}

map.put(nums[i], i); // 将当前元素添加到HashMap中

}

return new int[0]; // 如果没有找到满足条件的元素对，返回空数组

}

}

C语言版本

#include

#include

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {

int* result = (int*)malloc(2 * sizeof(int));

*returnSize = 0;

// 创建哈希表

int hashtable[20001] = {

0};

for (int i = 0; i < numsSize; ++i) {

int complement = target - nums[i]; // 计算差值，即目标值与当前元素的差值

// 检查哈希表中是否存在差值

if (complement >= -10000 && complement <= 10000 && hashtable[complement + 10000] != 0) {

result[0] = hashtable[complement + 10000] - 1; // 返回哈希表中保存的差值元素的下标

result[1] = i; // 返回当前元素的下标

*returnSize = 2; // 更新返回结果数组的大小为2

return result;

}

// 将当前元素添加到哈希表中

hashtable[nums[i] + 10000] = i + 1;

}

return result;

}

python3版本

from typing import List

from collections import defaultdict

class Solution:

def twoSum(self, nums: List[int], target: int) -> List[int]:

hashtable = defaultdict(int) # 使用defaultdict来容纳哈希表

for i in range(len(nums)):

complement = target - nums[i] # 计算差值，即目标值与当前元素的差值

if complement in hashtable:

return [hashtable[complement], i] # 返回哈希表中保存的差值元素的下标和当前元素的下标

hashtable[nums[i]] = i # 将当前元素添加到哈希表中

return [] # 如果没有找到满足条件的元素对，返回空列表

复杂度分析：

时间复杂度：O(N)，其中 N 是数组中的元素数量。对于每一个元素 x，我们可以 O(1) 地寻找 target - x。

空间复杂度：O(N)，其中 N 是数组中的元素数量。主要为哈希表的开销。

合并两个有序链表（LeetCode 21,Easy）

标签：哈希表|数组

题目

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1： > 输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4] 示例 2：

输入：l1 = [], l2 = [] 输出：[]

示例 3：

输入：l1 = [], l2 = [0] 输出：[0] 提示：

两个链表的节点数目范围是 [0, 50] -100 <= Node.val <= 100 l1 和 l2 均按 非递减顺序 排列

原题： LeetCode 21

思路及实现

方式一：迭代（推荐）

思路

我们可以用迭代的方法来实现上述算法。当 l1 和 l2 都不是空链表时，判断 l1 和 l2 哪一个链表的头节点的值更小，将较小值的节点添加到结果里，当一个节点被添加到结果里之后，将对应链表中的节点向后移一位

代码实现

Java版本

/**

* Definition for singly-linked list.

* class ListNode {

* int val;

* ListNode next;

* ListNode(int val) {

* this.val = val;

* }

* }

*/

class Solution {

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

ListNode node = new ListNode(-1); // 创建一个临时节点作为结果链表的头节点

ListNode cur = node;

while (list1 != null && list2 != null) {

if (list1.val < list2.val) {

cur.next = list1; // 将较小节点连接到结果链表

list1 = list1.next; // 移动指针到下一个节点

} else {

cur.next = list2;

list2 = list2.next;

}

cur = cur.next; // 移动当前节点指针到下一个节点

}

if (list1 != null) {

cur.next = list1; // 将剩下的节点连接到结果链表

}

if (list2 != null) {

cur.next = list2;

}

return node.next; // 返回结果链表的头节点

}

}

说明： 创建了一个临时节点作为结果链表的头节点。然后使用cur引用指向当前节点，通过遍历两个链表，比较节点的值，将较小节点连接到结果链表中，并将指针移向下一个节点。最后，将剩下的节点连接到结果链表的末尾。

需要注意的是，最后返回的是结果链表的头节点

C语言版本

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {

struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));

node->val = -1; // 创建一个临时节点作为结果链表的头节点

node->next = NULL;

struct ListNode* cur = node;

while (list1 != NULL && list2 != NULL) {

if (list1->val < list2->val) {

cur->next = list1; // 将较小节点连接到结果链表

list1 = list1->next; // 移动指针到下一个节点

} else {

cur->next = list2;

list2 = list2->next;

}

cur = cur->next; // 移动当前节点指针到下一个节点

}

if (list1 != NULL) {

cur->next = list1; // 将剩下的节点连接到结果链表

}

if (list2 != NULL) {

cur->next = list2;

}

struct ListNode* result = node->next; // 指向结果链表的头节点

free(node); // 释放临时节点的内存

return result;

}

说明： 在C语言中使用了头节点，并使用了指针操作来完成。

在算法中，我们创建了一个临时节点作为结果链表的头节点。然后使用cur指针指向当前节点，通过遍历两个链表，比较节点的值，将较小节点连接到结果链表中，并将指针移向下一个节点。最后，将剩下的节点连接到结果链表的末尾。

需要注意的是，最后返回的是结果链表的头节点，使用一个临时节点来保存结果链表的头节点可以简化操作。

在末尾，我们释放了临时节点的内存，以防止内存泄漏。

Python3版本

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, val=0, next=None):

# self.val = val

# self.next = next

class Solution:

def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:

node = ListNode(-1) # 创建临时节点作为结果链表的头节点

cur = node

while list1 and list2:

if list1.val < list2.val:

cur.next = list1 # 将较小节点连接到结果链表

list1 = list1.next

else:

cur.next = list2

list2 = list2.next

cur = cur.next

cur.next = list1 or list2 # 将剩下的节点连接到结果链表

return node.next # 返回结果链表的头节点

说明： Python 三元表达式写法 A if x else B ，代表当 x=True 时执行 A ，否则执行 B 。

复杂度分析

时间复杂度：O(M+N)，M, N分别标识list1和list2的长度

空间复杂度: O(1), 节点引用cur，常量级的额外空间

方式二：递归（不推荐）

思路

我们可以如下递归地定义两个链表里的 merge 操作（忽略边界情况，比如空链表等）：

情况一 ：list1[0]

其他情况 ：list2[0]+merge(list1,list2[1:])

也就是说，两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并。

我们直接将以上递归过程建模，同时需要考虑边界情况。 如果 l1 或者 l2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束

代码实现

Java版本

/**

* Definition for singly-linked list.

* public class ListNode {

* int val;

* ListNode next;

* ListNode() {}

* ListNode(int val) { this.val = val; }

* ListNode(int val, ListNode next) { this.val = val; this.next = next; }

* }

*/

class Solution {

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

// 如果l1为空，则直接返回l2作为合并后的链表

if (l1 == null) {

return l2;

}

// 如果l2为空，则直接返回l1作为合并后的链表

else if (l2 == null) {

return l1;

}

// 如果l1的值小于l2的值

else if (l1.val < l2.val) {

// 将l1的下一个节点与l2递归地合并

l1.next = mergeTwoLists(l1.next, l2);

return l1; // 返回合并后的链表头节点l1

}

// 如果l2的值小于等于l1的值

else {

// 将l2的下一个节点与l1递归地合并

l2.next = mergeTwoLists(l1, l2.next);

return l2; // 返回合并后的链表头节点l2

}

}

}

说明： 解法提供了递归方式来合并两个有序链表的操作。在算法中，首先处理特殊情况：如果l1为空，则直接返回l2作为合并后的链表；如果l2为空，则直接返回l1作为合并后的链表。接下来，判断l1和l2的值大小关系：如果l1的值小于l2的值，将l1的下一个节点与l2递归地合并，将合并结果作为l1的下一个节点，并返回l1作为合并后的链表头节点；如果l2的值小于等于l1的值，将l2的下一个节点与l1递归地合并，将合并结果作为l2的下一个节点，并返回l2作为合并后的链表头节点。最终，返回合并后的链表头节点。

C语言版本

#include

#include

struct ListNode {

int val;

struct ListNode *next;

};

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {

// 如果l1为空，则直接返回l2作为合并后的链表

if (l1 == NULL) {

return l2;

}

// 如果l2为空，则直接返回l1作为合并后的链表

else if (l2 == NULL) {

return l1;

}

// 如果l1的值小于l2的值

else if (l1->val < l2->val) {

// 将l1的下一个节点与l2递归地合并

l1->next = mergeTwoLists(l1->next, l2);

return l1; // 返回合并后的链表头节点l1

}

// 如果l2的值小于等于l1的值

else {

// 将l2的下一个节点与l1递归地合并

l2->next = mergeTwoLists(l1, l2->next);

return l2; // 返回合并后的链表头节点l2

}

}

说明： 在算法中，首先处理特殊情况：如果l1为空，则直接返回l2作为合并后的链表；如果l2为空，则直接返回l1作为合并后的链表。接下来，判断l1和l2的值的大小关系：如果l1的值小于l2的值，将l1的下一个节点与l2递归地合并，将合并结果作为l1的下一个节点，并返回l1作为合并后的链表头节点；如果l2的值小于等于l1的值，将l2的下一个节点与l1递归地合并，将合并结果作为l2的下一个节点，并返回l2作为合并后的链表头节点。最终，返回合并后的链表头节点。

Python3版本

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, val=0, next=None):

# self.val = val

# self.next = next

class Solution:

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:

if not l1: # 如果l1为空，则直接返回l2

return l2

elif not l2: # 如果l2为空，则直接返回l1

return l1

elif l1.val < l2.val: # 如果l1的值小于l2的值

l1.next = self.mergeTwoLists(l1.next, l2) # 递归地将l1的下一个节点与l2合并

return l1

else:

l2.next = self.mergeTwoLists(l1, l2.next) # 递归地将l2的下一个节点与l1合并

return l2

复杂度分析

时间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点（直到至少有一个链表为空），函数 mergeTwoList 至多只会递归调用每个节点一次。因此，时间复杂度取决于合并后的链表长度，即 O(n+m)。

空间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。递归调用 mergeTwoLists 函数时需要消耗栈空间，栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n+m 次，因此空间复杂度为 O(n+m)。

小结

递归和迭代都可以用来解决将两个有序链表合并的问题。下面对比一下递归和迭代的解法特点：

递归解法

迭代解法

优点

简洁，易于理解和实现

不涉及函数递归调用，避免递归开销和栈溢出问题

缺点

可能产生多个函数调用，涉及函数调用开销和栈溢出问题

需要使用额外变量保存当前节点，增加代码复杂性

时间复杂度

O(m+n)，其中m和n分别是两个链表的长度

O(m+n)，其中m和n分别是两个链表的长度

空间复杂度

O(m+n)，其中m和n分别是两个链表的长度

O(1)

在实际应用中，如果链表较长，特别是超过系统栈的容量，采用迭代解法更为安全。而对于简短的链表，递归解法更为简洁和直观。

有效的括号（LeetCode 20,Easy）

标签：栈、字符串处理

题目

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = “()” 输出：true 示例 2：

输入：s = “()[]{}” 输出：true 示例 3：

输入：s = “(]” 输出：false

提示：

1 <= s.length <= 104 s 仅由括号 ‘()[]{}’ 组成

原题：LeetCode 20 有效的括号

思路及实现

方式一：栈（推荐）

思路

判断括号的有效性可以使用「栈」这一数据结构来解决。

代码实现

Java版本

import java.util.Stack;

// leetcode submit region begin(Prohibit modification and deletion)

class Solution {

pub