大家好，欢迎来到IT知识分享网。
引言
常见的数据结构与算法题目，涵盖了数组、链表、栈、队列、二叉树、哈希表、字符串、图、排序和查找等方面的考察点。每个题目都附带有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
思路及实现
方式一：暴力解法（不推荐）
思路
代码实现
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 <stdio.h> #include <stdlib.h> 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 和自己匹配。
代码实现
JAVA版本
import java.util.HashMap; class Solution {
public int[] twoSum(int[] nums, int target) {
//key为当前值，value为当前值的位置 HashMap<Integer, Integer> 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 <stdio.h> #include <stdlib.h> 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）
- 标签：哈希表|数组
题目
输入：l1 = [], l2 = [] 输出：[]
示例 3：
输入：l1 = [], l2 = [0] 输出：[0] 提示：
原题： 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; // 返回结果链表的头节点 } } 需要注意的是，最后返回的是结果链表的头节点
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]，则 list1[0]+merge(list1[1:],list2) 其他情况 ：list2[0]+merge(list1,list2[1:]) 也就是说，两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并。
代码实现
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 } } } C语言版本
#include <stdio.h> #include <stdlib.h> 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 } } 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 = “(]” 输出：false
提示：
1 <= s.length <= 104 s 仅由括号 ‘()[]{}’ 组成
原题：LeetCode 20 有效的括号
思路及实现
方式一：栈（推荐）
思路
判断括号的有效性可以使用「栈」这一数据结构来解决。
代码实现
Java版本
import java.util.Stack; // leetcode submit region begin(Prohibit modification and deletion) class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>(); // 创建一个栈用于存储左括号字符 for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i); if (c == '(' || c == '[' || c == '{') {
stack.push(c); // 如果是左括号字符，将其压入栈中 } else {
if (stack.isEmpty()) {
return false; // 如果栈为空，说明缺少左括号，返回false } char top = stack.pop(); // 弹出栈顶元素 if (c == ')' && top != '(') {
return false; // 如果当前字符是右括号且与栈顶元素不匹配，返回false } if (c == ']' && top != '[') {
return false; } if (c == '}' && top != '{') {
return false; } } } return stack.isEmpty(); // 最后判断栈是否为空，如果为空说明每个左括号都有匹配的右括号，则返回true，否则返回false } } // leetcode submit region end(Prohibit modification and deletion) C++版本(由于C语言需要自己实现栈较为繁琐，此处使用C++)
#include <iostream> #include <stack> #include <string> using namespace std; bool isValid(string s) {
stack<char> stk; // 创建一个栈用于存储左括号字符 for (char c : s) {
if (c == '(' || c == '[' || c == '{') {
stk.push(c); // 如果是左括号字符，将其压入栈中 } else {
if (stk.empty()) {
return false; // 如果栈为空，说明缺少左括号，返回false } char top = stk.top(); /* 获取栈顶元素 */ stk.pop(); // 弹出栈顶元素 if (c == ')' && top != '(') {
return false; // 如果当前字符是右括号且与栈顶元素不匹配，返回false } if (c == ']' && top != '[') {
return false; } if (c == '}' && top != '{') {
return false; } } } return stk.empty(); // 最后判断栈是否为空，如果为空说明每个左括号都有匹配的右括号，则返回true，否则返回false } Python3版本
class Solution: def isValid(self, s: str) -> bool: stack = [] # 创建一个栈用于存储左括号字符 brackets = {
'(': ')', '[': ']', '{': '}'} for char in s: if char in brackets.keys(): # 如果是左括号字符，将其压入栈中 stack.append(char) elif char in brackets.values(): # 如果是右括号字符 if not stack: # 如果栈为空，说明缺少左括号，返回False return False top = stack.pop() # 弹出栈顶元素 if char != brackets[top]: # 如果当前字符与栈顶元素不匹配，返回False return False return len(stack) == 0 # 判断栈是否为空，为空说明每个左括号都有匹配的右括号 复杂度分析
- 时间复杂度：O(n)，其中 n 是字符串 s 的长度。
- 空间复杂度：O(n)，其中n为字符串的长度。在最坏情况下，所有的字符都是左括号，需要将其全部入栈，占用了O(n) 的空间。
这个算法具有线性时间复杂度和线性空间复杂度。
循环队列设计（LeetCode 622,Medium）
- 标签：队列、数组
题目
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。 你的实现应该支持如下操作： MyCircularQueue(k): 构造器，设置队列长度为 k 。 Front: 从队首获取元素。如果队列为空，返回 -1 。 Rear: 获取队尾元素。如果队列为空，返回 -1 。 enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。 deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。 isEmpty(): 检查循环队列是否为空。 isFull(): 检查循环队列是否已满。 示例： MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3 circularQueue.enQueue(1); // 返回 true circularQueue.enQueue(2); // 返回 true circularQueue.enQueue(3); // 返回 true circularQueue.enQueue(4); // 返回 false，队列已满 circularQueue.Rear(); // 返回 3 circularQueue.isFull(); // 返回 true circularQueue.deQueue(); // 返回 true circularQueue.enQueue(4); // 返回 true circularQueue.Rear(); // 返回 4 提示： 所有的值都在 0 至 1000 的范围内； 操作数将在 1 至 1000 的范围内； 请不要使用内置的队列库。 原题：[LeetCode 622](https://leetcode-cn.com/problems/design-circular-queue/) 思路及实现
方式一：数组（不推荐）
思路
为了区别这两种情况，假设队列使用的数组有 capacity 个存储空间，则此时规定循环队列最多只能有capacity−1 个队列元素，当循环队列中只剩下一个空存储单元时，则表示队列已满。
- elements：一个固定大小的数组，用于保存循环队列的元素。
- capacity：循环队列的容量，即队列中最多可以容纳的元素数量。
- front：队列首元素对应的数组的索引。
- rear：队列尾元素对应的索引的下一个索引。
循环队列的接口方法如下： MyCircularQueue(int k): 初始化队列，同时base 数组的空间初始化大小为 k+1。front,rear 全部初始化为 0。 enQueue(int value)：在队列的尾部插入一个元素，并同时将队尾的索引 rear 更新为 (rear+1)modcapacity。 deQueue()：从队首取出一个元素，并同时将队首的索引 front 更新为 (front+1)modcapacity。 Front()：返回队首的元素，需要检测队列是否为空。 Rear()：返回队尾的元素，需要检测队列是否为空。 isEmpty()：检测队列是否为空，根据之前的定义只需判断 rear 是否等于 front。 isFull()：检测队列是否已满，根据之前的定义只需判断 front 是否等于 (rear+1)modcapacity。 代码实现
Java版本
class MyCircularQueue {
private int front; // 队头指针 private int rear; // 队尾指针 private int capacity; // 队列容量 private int[] elements; // 存储队列元素的数组 public MyCircularQueue(int k) {
capacity = k + 1; // 设置队列容量，需要额外留一个空位用于判断队满的条件 elements = new int[capacity]; // 创建存储队列元素的数组 rear = front = 0; // 初始化队头和队尾指针 } public boolean enQueue(int value) {
if (isFull()) {
return false; // 如果队列已满，无法入队，返回false } elements[rear] = value; // 将元素放入队尾 rear = (rear + 1) % capacity; // 队尾指针后移一位，通过取模实现循环 return true; } public boolean deQueue() {
if (isEmpty()) {
return false; // 如果队列为空，无法出队，返回false } front = (front + 1) % capacity; // 队头指针后移一位，通过取模实现循环 return true; } public int Front() {
if (isEmpty()) {
return -1; // 如果队列为空，返回-1 } return elements[front]; // 返回队头元素 } public int Rear() {
if (isEmpty()) {
return -1; // 如果队列为空，返回-1 } return elements[(rear - 1 + capacity) % capacity]; // 返回队尾元素，通过(rear-1+capacity)%capacity实现循环 } public boolean isEmpty() {
return rear == front; // 队头指针等于队尾指针时，队列为空 } public boolean isFull() {
return (rear + 1) % capacity == front; // 队头指针的下一个位置等于队尾指针时，队列为满 } } 这个代码中使用成员变量来存储队列的状态和数据，方法通过操作这些成员变量来实现对队列的操作。方法的返回值为布尔型，用于表示操作是否成功，而不是抛出异常来处理异常情况。
C语言版本
typedef struct {
int front; // 队头指针 int rear; // 队尾指针 int capacity; // 队列容量 int* elements; // 存储队列元素的数组 } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); // 分配队列结构体的内存空间 obj->capacity = k + 1; // 设置队列容量，需要额外留一个空位用于判断队满的条件 obj->front = obj->rear = 0; // 初始化队头和队尾指针为0 obj->elements = (int*)malloc(sizeof(int) * obj->capacity); // 创建存储队列元素的数组 return obj; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if ((obj->rear + 1) % obj->capacity == obj->front) {
return false; // 如果队列已满，无法入队，返回false } obj->elements[obj->rear] = value; // 将元素放入队尾 obj->rear = (obj->rear + 1) % obj->capacity; // 队尾指针后移一位，通过取模实现循环 return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if (obj->rear == obj->front) {
return false; // 如果队列为空，无法出队，返回false } obj->front = (obj->front + 1) % obj->capacity; // 队头指针后移一位，通过取模实现循环 return true; } int myCircularQueueFront(MyCircularQueue* obj) {
if (obj->rear == obj->front) {
return -1; // 如果队列为空，返回-1 } return obj->elements[obj->front]; // 返回队头元素 } int myCircularQueueRear(MyCircularQueue* obj) {
if (obj->rear == obj->front) {
return -1; // 如果队列为空，返回-1 } return obj->elements[(obj->rear - 1 + obj->capacity) % obj->capacity]; // 返回队尾元素，通过(rear-1+capacity)%capacity实现循环 } bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->rear == obj->front; // 队头指针等于队尾指针时，队列为空 } bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->rear + 1) % obj->capacity == obj->front; // 队头指针的下一个位置等于队尾指针时，队列为满 } void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->elements); // 释放存储队列元素的数组内存空间 free(obj); // 释放队列结构体内存空间 } 说明：使用结构体MyCircularQueue来存储队列的状态和数据。结构体中包括front和rear两个指针，capacity队列容量，以及存储队列元素的elements数组。
Python3版本
class MyCircularQueue: def __init__(self, k: int): self.front = self.rear = 0 # 初始化队头和队尾指针 self.elements = [0] * (k + 1) # 创建一个长度为k+1的数组来存储元素，留出一个空位作为判断队满的条件 def enQueue(self, value: int) -> bool: if self.isFull(): # 如果队满，无法入队，返回False return False self.elements[self.rear] = value # 将元素放入队尾 self.rear = (self.rear + 1) % len(self.elements) # 队尾指针后移一位 return True def deQueue(self) -> bool: if self.isEmpty(): # 如果队空，无法出队，返回False return False self.front = (self.front + 1) % len(self.elements) # 队头指针后移一位 return True def Front(self) -> int: return -1 if self.isEmpty() else self.elements[self.front] # 如果队空，返回-1；否则返回队头元素 def Rear(self) -> int: return -1 if self.isEmpty() else self.elements[(self.rear - 1) % len(self.elements)] # 如果队空，返回-1；否则返回队尾元素 def isEmpty(self) -> bool: return self.rear == self.front # 队头指针等于队尾指针时，队列为空 def isFull(self) -> bool: return (self.rear + 1) % len(self.elements) == self.front # 队头指针的下一位等于队尾指针时，队列为满 复杂度分析
- 时间复杂度：初始化和每项操作的时间复杂度均为 O(1)。
- 空间复杂度：O(k)，其中 k 为给定的队列元素数目。
方式二：链表（推荐）
思路
我们同样可以用链表实现队列，用链表实现队列则较为简单，因为链表可以在 O(1) 时间复杂度完成插入与删除。入队列时，将新的元素插入到链表的尾部；出队列时，将链表的头节点返回，并将头节点指向下一个节点。
循环队列的属性如下:
- head：链表的头节点，队列的头节点。
- tail：链表的尾节点，队列的尾节点。
- capacity：队列的容量，即队列可以存储的最大元素数量。
- size：队列当前的元素的数量。
代码实现
Java
class MyCircularQueue {
private ListNode head; // 队头节点 private ListNode tail; // 队尾节点 private int capacity; // 队列容量 private int size; // 当前队列的元素个数 public MyCircularQueue(int k) {
capacity = k; size = 0; } public boolean enQueue(int value) {
if (isFull()) {
return false; // 如果队列已满，无法入队，返回false } ListNode node = new ListNode(value); if (head == null) {
head = tail = node; // 如果队列为空，设置头部和尾部节点为新节点 } else {
tail.next = node; // 将新节点添加到尾部 tail = node; // 更新尾部节点 } size++; // 元素个数加1 return true; } public boolean deQueue() {
if (isEmpty()) {
return false; // 如果队列为空，无法出队，返回false } head = head.next; // 将头部节点后移一位，实现出队操作 size--; // 元素个数减1 return true; } public int Front() {
if (isEmpty()) {
return -1; // 如果队列为空，返回-1 } return head.val; // 返回头部节点的值 } public int Rear() {
if (isEmpty()) {
return -1; // 如果队列为空，返回-1 } return tail.val; // 返回尾部节点的值 } public boolean isEmpty() {
return size == 0; // 如果元素个数为0，队列为空 } public boolean isFull() {
return size == capacity; // 如果元素个数等于队列容量，队列已满 } } class ListNode {
int val; ListNode next; public ListNode(int val) {
this.val = val; } } C语言
typedef struct {
struct ListNode *head; // 队头指针 struct ListNode *tail; // 队尾指针 int capacity; // 队列容量 int size; // 当前队列的元素个数 } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue *obj = (MyCircularQueue *)malloc(sizeof(MyCircularQueue)); // 创建队列结构体并分配内存空间 obj->capacity = k; // 设置队列容量 obj->size = 0; // 当前队列元素个数为0 obj->head = obj->tail = NULL; // 初始化队头和队尾指针为 NULL return obj; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if (obj->size >= obj->capacity) {
return false; // 如果队列已满，无法入队，返回 false } struct ListNode *node = (struct ListNode *)malloc(sizeof(struct ListNode)); // 创建新节点并分配内存空间 node->val = value; // 设置节点的值 node->next = NULL; // 初始化节点的下一个指针为 NULL if (!obj->head) {
obj->head = obj->tail = node; // 如果队列为空，设置头部和尾部指针为新节点 } else {
obj->tail->next = node; // 将新节点添加到尾部 obj->tail = node; // 更新尾部指针 } obj->size++; // 当前队列元素个数加1 return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if (obj->size == 0) {
return false; // 如果队列为空，无法出队，返回 false } struct ListNode *node = obj->head; // 保存当前头部节点 obj->head = obj->head->next; // 头部指针后移一位，实现出队操作 obj->size--; // 当前队列元素个数减1 free(node); // 释放出队节点的内存 return true; } int myCircularQueueFront(MyCircularQueue* obj) {
if (obj->size == 0) {
return -1; // 如果队列为空，返回 -1 } return obj->head->val; // 返回头部节点的值 } int myCircularQueueRear(MyCircularQueue* obj) {
if (obj->size == 0) {
return -1; // 如果队列为空，返回 -1 } return obj->tail->val; // 返回尾部节点的值 } bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->size == 0; // 如果当前队列元素个数为0，队列为空 } bool myCircularQueueIsFull(MyCircularQueue* obj) {
return obj->size == obj->capacity; // 如果当前队列元素个数等于队列容量，队列已满 } void myCircularQueueFree(MyCircularQueue* obj) {
for (struct ListNode *curr = obj->head; curr;) {
// 遍历整个队列，从头部开始 struct ListNode *node = curr; // 保存当前节点 curr = curr->next; // 移动到下一个节点 free(node); // 释放当前节点的内存 } free(obj); // 释放队列结构体的内存 } Python3
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class MyCircularQueue: def __init__(self, k: int): self.head = self.tail = None # 队头和队尾指针，用于指向队列的头部和尾部 self.capacity = k # 队列容量 self.size = 0 # 当前队列中的元素个数 def enQueue(self, value: int) -> bool: if self.isFull(): # 如果队列已满，无法入队，返回False return False node = ListNode(value) # 创建一个新节点 if self.head is None: # 如果队列为空，设置头部和尾部指针为新节点 self.head = node self.tail = node else: self.tail.next = node # 将新节点添加到尾部 self.tail = node # 更新尾部指针 self.size += 1 # 元素个数加1 return True def deQueue(self) -> bool: if self.isEmpty(): # 如果队列为空，无法出队，返回False return False self.head = self.head.next # 将头部指针后移一位，实现出队操作 self.size -= 1 # 元素个数减1 return True def Front(self) -> int: return -1 if self.isEmpty() else self.head.val # 如果队列为空，返回-1；否则返回头部节点的值 def Rear(self) -> int: return -1 if self.isEmpty() else self.tail.val # 如果队列为空，返回-1；否则返回尾部节点的值 def isEmpty(self) -> bool: return self.size == 0 # 如果元素个数为0，队列为空 def isFull(self) -> bool: return self.size == self.capacity # 如果元素个数等于队列容量，队列已满 说明： 使用链表来存储队列的元素。ListNode是节点结构体，用于表示队列中的每个节点。
MyCircularQueue类的初始化方法__init__中，初始化队头和队尾指针为None，队列容量为k，当前队列的元素个数为0。
复杂度分析
- 时间复杂度：初始化和每项操作的时间复杂度均为 O(1)。
- 空间复杂度：O(k)，其中 k 为给定的队列元素数目。
数组VS链表
| 方面 | 数组 | 链表 |
|---|---|---|
| 存储方式 | 连续的内存空间 | 非连续的内存空间 |
| 插入和删除操作 | O(n) | O(1) |
| 随机访问 | O(1) | O(n) |
| 内存效率 | 较高（不需要额外指针空间） | 较低（需要额外指针空间） |
| 大小变化 | 需要重新分配内存空间 | 可以动态变化 |
| 实现复杂性 | 相对简单 | 相对复杂 |
对称二叉树（LeetCode 101,Easy）
- 标签：二叉树递归、对称性判断
题目
给你一个二叉树的根节点 root ， 检查它是否轴对称。
输入：root = [1,2,2,null,3,null,3] 输出：false
提示：
思路及实现
方式一：递归（推荐）
思路
根据上面信息可以总结出递归函数的两个终止条件：
- left 和 right 不等，或者 left 和 right 都为空
- 递归的比较 left，left 和 right.right，递归比较
left，right 和 right.left
代码实现
Java版本
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true; // 如果根节点为null，即空树，视为对称二叉树，返回true } return isMirror(root.left, root.right); // 调用isMirror方法判断左子树和右子树是否对称 } private boolean isMirror(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true; // 如果左子树和右子树都为null，也视为对称，返回true } if (left == null || right == null) {
return false; // 如果左子树和右子树只有一个为null，视为不对称，返回false } return left.val == right.val && isMirror(left.left, right.right) && isMirror(left.right, right.left); // 如果左子树和右子树的值相等，且同时满足左子树的左子树和右子树的右子树对称， // 以及左子树的右子树和右子树的左子树对称，则视为对称，返回true；否则，返回false } } isMirror方法是递归判断左右子树是否对称的函数。首先判断左子树和右子树是否都为null，如果是，即均为空树，视为对称，返回true。然后判断左子树和右子树中只有一个为null的情况，即一个为空树一个不为空树，视为不对称，返回false。最后，判断左子树的值和右子树的值是否相等，并且同时递归判断左子树的左子树和右子树的右子树是否对称，以及递归判断左子树的右子树和右子树的左子树是否对称。只有全部满足才视为对称，返回true；否则，返回false。
C语言版本
#include <stdbool.h> /*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; */ bool isMirror(struct TreeNode *left, struct TreeNode *right); bool isSymmetric(struct TreeNode *root) {
if (root == NULL) {
return true; // 如果根节点为NULL，即空树，视为对称二叉树，返回true } return isMirror(root->left, root->right); // 调用isMirror函数判断左子树和右子树是否对称 } bool isMirror(struct TreeNode *left, struct TreeNode *right) {
if (left == NULL && right == NULL) {
return true; // 如果左子树和右子树都为NULL，也视为对称，返回true } if (left == NULL || right == NULL) {
return false; // 如果左子树和右子树只有一个为NULL，视为不对称，返回false } return (left->val == right->val) && isMirror(left->left, right->right) && isMirror(left->right, right->left); // 如果左子树和右子树的值相等，并且同时满足左子树的左子树和右子树的右子树对称， // 以及左子树的右子树和右子树的左子树对称，则视为对称，返回true；否则，返回false } Python3版本
class Solution: def isSymmetric(self, root: TreeNode) -> bool: if root is None: return True # 如果根节点为空，返回True，空树被认为是对称的 return self.isMirror(root.left, root.right) def isMirror(self, left: TreeNode, right: TreeNode) -> bool: if left is None and right is None: return True # 如果左子树和右子树都为空，认为是对称的 if left is None or right is None: return False # 如果左子树和右子树只有一个为空，不对称 return left.val == right.val and self.isMirror(left.left, right.right) and self.isMirror(left.right, right.left) # 比较左子树的左子树和右子树的右子树，以及左子树的右子树和右子树的左子树，满足条件才认为是对称的 # 假设定义了TreeNode类，包含val、left和right属性 class TreeNode: def __init__(self, val: int = 0, left: TreeNode = None, right: TreeNode = None): self.val = val self.left = left self.right = right 复杂度分析
- 时间复杂度：O(n)，其中 n 表示树的节点数。
- 空间复杂度：O(n)，递归调用的栈空间最多为树的高度。
方式二：队列（迭代）
思路
代码实现
Java版本
//leetcode submit region begin(Prohibit modification and deletion) import java.util.LinkedList; class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return false; // 根节点为空，不算对称 } if (root.left == null && root.right == null) {
return true; // 左右子树都为空，算对称 } LinkedList<TreeNode> queue = new LinkedList(); // 使用队列来保存待比较的节点 queue.add(root.left); queue.add(root.right); while (queue.size() > 0) {
TreeNode left = queue.removeFirst(); TreeNode right = queue.removeFirst(); // 只要两个节点都为空，继续循环；两者有一个为空，返回false if (left == null && right == null) {
continue; } if (left == null || right == null) {
return false; } // 判断两个节点的值是否相等 if (left.val != right.val) {
return false; } // 将左节点的左子节点和右节点的右子节点放入队列 queue.add(left.left); queue.add(right.right); // 将左节点的右子节点和右节点的左子节点放入队列 queue.add(left.right); queue.add(right.left); } return true; } } //leetcode submit region end(Prohibit modification and deletion) 在 isSymmetric 方法中，首先判断根节点是否为空，如果为空，返回 false，表示不对称。然后，如果根节点的左右子树都为空，返回 true，表示对称（只有一个元素的case）。
将左节点的左子节点和右节点的右子节点放入队列，用于后续比较。同时，将左节点的右子节点和右节点的左子节点放入队列，也用于后续比较。
当队列为空时，表示所有节点都已比较完毕，没有发现不对称的情况，返回 true，表示对称。
这段代码使用了迭代方法，利用队列存储待比较的节点，逐层按顺序比较，避免了递归方法的额外栈空间开销。
C语言版本
// leetcode submit region begin(Prohibit modification and deletion) #include <stdbool.h> struct TreeNode {
int val; struct TreeNode *left; struct TreeNode *right; }; bool isSymmetric(struct TreeNode* root) {
if (root == NULL) {
return false; // 根节点为空，不算对称 } struct TreeNode* queue[10000]; // 使用队列来保存待比较的节点 int front = 0, rear = 0; queue[rear++] = root->left; queue[rear++] = root->right; while (rear != front) {
struct TreeNode* left = queue[front++]; struct TreeNode* right = queue[front++]; // 只要两个节点都为空，继续循环；两者有一个为空，返回false if (left == NULL && right == NULL) {
continue; } if (left == NULL || right == NULL) {
return false; } // 判断两个节点的值是否相等 if (left->val != right->val) {
return false; } // 将左节点的左子节点和右节点的右子节点放入队列 queue[rear++] = left->left; queue[rear++] = right->right; // 将左节点的右子节点和右节点的左子节点放入队列 queue[rear++] = left->right; queue[rear++] = right->left; } return true; } //leetcode submit region end(Prohibit modification and deletion) 在 isSymmetric 函数中，首先判断根节点是否为空，如果为空，返回 false，表示不对称。
创建一个队列 queue，使用数组来保存待比较的节点。使用 front 和 rear 变量分别表示队首和队尾的索引。
将根节点的左子节点和右子节点依次加入队列 queue。
然后进入循环，每次从队列中取出两个节点进行比较。
将左节点的左子节点和右节点的右子节点放入队列，用于后续比较。同时，将左节点的右子节点和右节点的左子节点放入队列，也用于后续比较。
当队列为空时，表示所有节点都已比较完毕，没有发现不对称的情况，返回 true，表示对称。
这段代码使用了迭代方法，利用数组队列方式存储待比较的节点，逐个按序比较，避免了递归方法的额外栈空间开销。
Python3版本
class Solution: def isSymmetric(self, root: TreeNode) -> bool: if root is None: return False # 根节点为空，不算对称 queue = [] queue.append(root.left) queue.append(root.right) while queue: left = queue.pop(0) right = queue.pop(0) if left is None and right is None: continue # 只要两个节点都为空，继续循环 if left is None or right is None: return False # 两者有一个为空，返回False，不对称 if left.val != right.val: return False # 节点值不相等，不对称 queue.append(left.left) # 左节点的左子节点入队列 queue.append(right.right) # 右节点的右子节点入队列 queue.append(left.right) # 左节点的右子节点入队列 queue.append(right.left) # 右节点的左子节点入队列 return True # 队列为空，所有节点比较完毕，对称 说明：（基础说明可查看java或者c的实现）
- 在函数参数的类型注解中，使用了 TreeNode 类型来标注 root 参数的类型。
- 使用了 is 运算符来判断节点是否为 None。is 运算符比较的是对象的身份标识，用于判断对象是否是同一个对象。这里用它来判断节点是否为None。
- 使用了列表 queue 来实现队列的功能，通过 append() 方法将节点加入队列的尾部，通过 pop(0)
方法来从队列的头部取出节点。Python的列表可以很方便地实现队列的功能。
复杂度分析
- 时间复杂度：O(n)，其中 n 表示树的节点数。在最坏情况下，需要遍历树的所有节点。
- 空间复杂度：O(n)，最坏情况下，队列中需要存储树的一层节点，所以空间复杂度与树的高度有关。在最坏情况下，树的高度为 n/2，因此空间复杂度为 O(n)。
综合来看，这个算法的时间复杂度和空间复杂度都是 O(n)，其中 n 表示树的节点数。算法的性能随着节点数的增加而线性增长。
两个数组的交集 II（LeetCode 350,Easy）
- 标签：哈希表、数组
题目
给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数， 应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。 示例 1： 输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2,2] 示例 2: 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[4,9] 提示： 1 <= nums1.length, nums2.length <= 1000 0 <= nums1[i], nums2[i] <= 1000 进阶： 如果给定的数组已经排好序呢？你将如何优化你的算法？ 如果 nums1 的大小比 nums2 小，哪种方法更优？ 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？ 思路及实现
方式一：哈希表
思路
由于同一个数字在两个数组中都可能出现多次，因此需要用哈希表存储每个数字出现的次数。对于一个数字，其在交集中出现的次数等于该数字在两个数组中出现次数的最小值。
首先遍历第一个数组，并在哈希表中记录第一个数组中的每个数字以及对应出现的次数，然后遍历第二个数组，对于第二个数组中的每个数字，如果在哈希表中存在这个数字，则将该数字添加到答案，并减少哈希表中该数字出现的次数。
为了降低空间复杂度，首先遍历较短的数组并在哈希表中记录每个数字以及对应出现的次数，然后遍历较长的数组得到交集。
代码实现
Java版本
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Map<Integer, Integer> numMap = new HashMap<>(); List<Integer> res = new ArrayList<>(); // 遍历 nums1 数组，将元素及其出现次数存储在哈希表中 for (int num : nums1) {
numMap.put(num, numMap.getOrDefault(num, 0) + 1); } // 遍历 nums2 数组，检查每个元素是否在哈希表中出现 // 如果出现，将该元素添加到结果集中，并将哈希表中的对应出现次数减1 for (int num : nums2) {
if (numMap.containsKey(num) && numMap.get(num) > 0) {
res.add(num); numMap.put(num, numMap.get(num) - 1); } } // 将结果集转换为数组输出 int[] result = new int[res.size()]; for (int i = 0; i < res.size(); i++) {
result[i] = res.get(i); } return result; } } C语言版本
#include <stdio.h> #include <stdlib.h> / * 返回两个整数中的较小值 */ int min(int a, int b) {
return a < b ? a : b; } int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
// 使用哈希表来存储nums1中每个元素及其出现的次数 int* numMap = (int*) malloc(sizeof(int) * 1001); for (int i = 0; i < nums1Size; i++) {
numMap[nums1[i]]++; } int* res = (int*) malloc(sizeof(int) * min(nums1Size, nums2Size)); // 结果集使用动态分配的数组来存储 int resSize = 0; // 结果集的大小 // 遍历nums2数组，检查每个元素在哈希表中是否存在 // 如果存在且对应出现次数大于0，则加入结果集，并将对应出现次数减1 for (int i = 0; i < nums2Size; i++) {
if (numMap[nums2[i]] > 0) {
res[resSize++] = nums2[i]; numMap[nums2[i]]--; } } *returnSize = resSize; // 将结果集的大小赋给返回值 free(numMap); // 释放动态分配的内存 return res; // 返回结果集数组的指针 } Python3版本
class Solution: def intersect(self, nums1, nums2): # 使用哈希表来存储nums1中每个元素及其出现的次数 numMap = {
} for num in nums1: numMap[num] = numMap.get(num, 0) + 1 res = [] # 遍历nums2数组，检查每个元素在哈希表中是否存在 # 如果存在且对应出现次数大于0，则加入结果集，并将对应出现次数减1 for num in nums2: if num in numMap and numMap[num] > 0: res.append(num) numMap[num] -= 1 return res 复杂度分析
- 时间复杂度：O(max(m, n))，其中 m 和 n 分别表示两个输入数组的长度。需要遍历两个数组并对哈希表进行操作，哈希表操作的时间复杂度是 O(1)，因此总时间复杂度与两个数组的长度和呈线性关系。
- 空间复杂度：O(min(m, n))，表示两个输入数组中较小的那个数组的长度
方式二：排序 + 双指针
思路
如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集。
首先对两个数组进行排序，然后使用两个指针遍历两个数组。
初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，将该数字添加到答案，并将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。
代码实现
Java版本
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
// 对两个数组进行排序 Arrays.sort(nums1); Arrays.sort(nums2); // 获取两个数组的长度 int length1 = nums1.length, length2 = nums2.length; // 创建结果数组，长度为两个数组中较小的长度 int[] intersection = new int[Math.min(length1, length2)]; // 初始化指针和结果数组的索引 int index1 = 0, index2 = 0, index = 0; // 双指针法求交集 while (index1 < length1 && index2 < length2) {
if (nums1[index1] < nums2[index2]) {
index1++; // nums1的元素较小，移动nums1的指针 } else if (nums1[index1] > nums2[index2]) {
index2++; // nums2的元素较小，移动nums2的指针 } else {
// 相等，加入结果数组，同时移动两个指针和结果数组的索引 intersection[index] = nums1[index1]; index1++; index2++; index++; } } // 返回交集结果数组，利用Arrays.copyOfRange()截取结果数组的有效部分 return Arrays.copyOfRange(intersection, 0, index); } } C语言版本
#include <stdlib.h> int cmp(const void *a, const void *b) {
return (*(int *)a - *(int *)b); } int *intersect(int *nums1, int nums1Size, int *nums2, int nums2Size, int *returnSize) {
// 对两个数组进行排序 qsort(nums1, nums1Size, sizeof(int), cmp); qsort(nums2, nums2Size, sizeof(int), cmp); // 创建结果数组，长度为两个数组中较小的大小 int *intersection = (int *)malloc(sizeof(int) * (nums1Size < nums2Size ? nums1Size : nums2Size)); // 初始化指针和结果数组索引 int index1 = 0, index2 = 0, index = 0; // 双指针法求交集 while (index1 < nums1Size && index2 < nums2Size) {
if (nums1[index1] < nums2[index2]) {
index1++; // nums1的元素较小，移动nums1的指针 } else if (nums1[index1] > nums2[index2]) {
index2++; // nums2的元素较小，移动nums2的指针 } else {
// 相等，加入结果数组，同时移动两个指针和结果数组的索引 intersection[index] = nums1[index1]; index1++; index2++; index++; } } // 返回交集结果数组的大小 *returnSize = index; return intersection; } Python3版本
class Solution: def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]: # 对两个数组进行排序 nums1.sort() nums2.sort() # 获取两个数组的长度 length1, length2 = len(nums1), len(nums2) # 创建一个空列表来存储交集结果 intersection = list() # 初始化两个指针 index1 = index2 = 0 # 双指针法求交集 while index1 < length1 and index2 < length2: if nums1[index1] < nums2[index2]: index1 += 1 elif nums1[index1] > nums2[index2]: index2 += 1 else: # 相等，加入结果列表，同时移动两个指针 intersection.append(nums1[index1]) index1 += 1 index2 += 1 # 返回交集结果列表 return intersection 复杂度分析
- 时间复杂度：O(mlogm+nlogn)，其中 m 和 n 分别是两个数组的长度。对两个数组进行排序的时间复杂度是 O(mlogm+nlogn)，遍历两个数组的时间复杂度是 O(m+n)，因此总时间复杂度是 O(mlogm+nlogn)。
- 空间复杂度：O(min(m,n))，其中 m 和 n 分别是两个数组的长度。为返回值创建一个数组 intersection，其长度为较短的数组的长度。不过在 C++ 中，我们可以直接创建一个 vector，不需要把答案临时存放在一个额外的数组中，所以这种实现的空间复杂度为 O(1)。
最长公共前缀（LeetCode 14,Easy）
- 标签：字符串处理、前缀判断
题目
编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 ""。 示例 1： 输入：strs = ["flower","flow","flight"] 输出："fl" 示例 2： 输入：strs = ["dog","racecar","car"] 输出："" 解释：输入不存在公共前缀。 提示： 1 <= strs.length <= 200 0 <= strs[i].length <= 200 strs[i] 仅由小写英文字母组成 原题：LeetCode 14
思路及实现
方式一：横向扫描
思路
代码实现
Java
class Solution {
public String longestCommonPrefix(String[] strs) {
// 如果字符串数组为空或者长度为0，则返回空字符串 if (strs == null || strs.length == 0) {
return ""; } // 将第一个字符串作为前缀进行初始化 String prefix = strs[0]; // 数组中字符串的数量 int count = strs.length; // 遍历字符串数组，依次求取最长公共前缀 for (int i = 1; i < count; i++) {
prefix = longestCommonPrefix(prefix, strs[i]); // 如果最长公共前缀为空，则可以提前结束循环 if (prefix.length() == 0) {
break; } } // 返回最长公共前缀 return prefix; } // 求取两个字符串的最长公共前缀 public String longestCommonPrefix(String str1, String str2) {
// 获取两个字符串的最小长度 int length = Math.min(str1.length(), str2.length()); // 初始化索引 int index = 0; // 遍历两个字符串，找到最长公共前缀的结束索引 while (index < length && str1.charAt(index) == str2.charAt(index)) {
index++; } // 返回最长公共前缀 return str1.substring(0, index); } } C语言版本
#include <stdio.h> #include <stdlib.h> #include <string.h> char* longestCommonPrefix(char** strs, int strsSize) {
// 如果字符串数组为空或者长度为0，则返回空字符串 if (strs == NULL || strsSize == 0) return ""; // 将第一个字符串作为初始的最长公共前缀 char* prefix = strs[0]; // 遍历数组剩余的字符串，更新最长公共前缀 for (int i = 1; i < strsSize; i++) {
prefix = lcp(prefix, strs[i]); // 如果最长公共前缀为空，则跳出循环 if (prefix[0] == '\0') break; } return prefix; } Python3版本
class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: # 如果字符串数组为空，则返回空字符串 if not strs: return "" # 将数组的第一个字符串作为初始的最长公共前缀 prefix, count = strs[0], len(strs) # 遍历数组剩余的字符串，更新最长公共前缀 for i in range(1, count): prefix = self.lcp(prefix, strs[i]) # 如果最长公共前缀为空，则跳出循环 if not prefix: break return prefix # 求取两个字符串的最长公共前缀 def lcp(self, str1, str2): # 获取两个字符串的最小长度 length, index = min(len(str1), len(str2)), 0 # 遍历两个字符串，找到最长公共前缀的结束索引 while index < length and str1[index] == str2[index]: index += 1 # 返回最长公共前缀 return str1[:index] 复杂度分析
- 时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
- 空间复杂度：O(1)。使用的额外空间复杂度为常数。
方式二：纵向扫描
思路
代码实现
Java
class Solution {
public String longestCommonPrefix(String[] strs) {
// 如果字符串数组为空或者长度为0，直接返回空字符串 if (strs == null || strs.length == 0) {
return ""; } // 获取第一个字符串的长度和数组的长度 int length = strs[0].length(); int count = strs.length; // 遍历第一个字符串的每个字符 for (int i = 0; i < length; i++) {
char c = strs[0].charAt(i); // 遍历剩余的字符串进行比较 for (int j = 1; j < count; j++) {
// 如果当前字符已经超过了某个字符串的长度，或者当前字符不等于其他字符串对应位置的字符，返回前缀部分 if (i == strs[j].length() || strs[j].charAt(i) != c) {
return strs[0].substring(0, i); } } } // 返回第一个字符串作为最长公共前缀 return strs[0]; } } C语言版本
在这里插入代码片 Python
在这里插入代码片 复杂度分析
- 时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
- 空间复杂度：O(1)。使用的额外空间复杂度为常数。
方式三：纵向扫描
思路
代码实现
Java版本
class Solution {
public String longestCommonPrefix(String[] strs) {
// 如果字符串数组为空或者长度为0，直接返回空字符串 if (strs == null || strs.length == 0) {
return ""; } else {
return longestCommonPrefix(strs, 0, strs.length - 1); } } // 递归函数，用于求取指定范围内字符串数组的最长公共前缀 public String longestCommonPrefix(String[] strs, int start, int end) {
// 如果范围内只有一个字符串，则直接返回该字符串作为最长公共前缀 if (start == end) {
return strs[start]; } else {
// 计算范围中间索引 int mid = (end - start) / 2 + start; // 求取左半部分和右半部分的最长公共前缀 String lcpLeft = longestCommonPrefix(strs, start, mid); String lcpRight = longestCommonPrefix(strs, mid + 1, end); // 返回左半部分和右半部分的最长公共前缀的公共前缀 return commonPrefix(lcpLeft, lcpRight); } } // 求取两个字符串的最长公共前缀的公共前缀 public String commonPrefix(String lcpLeft, String lcpRight) {
// 获取最小长度 int minLength = Math.min(lcpLeft.length(), lcpRight.length()); // 对比两个字符串的字符，找到不相等的位置，返回前缀部分 for (int i = 0; i < minLength; i++) {
if (lcpLeft.charAt(i) != lcpRight.charAt(i)) {
return lcpLeft.substring(0, i); } } // 返回最小长度范围内的字符串，即最长公共前缀 return lcpLeft.substring(0, minLength); } } C语言版本
#include <stdio.h> #include <string.h> // 函数声明 char* longestCommonPrefix(char** strs, int strsSize); /* * 获取两个字符串的最长公共前缀 * 参数: str1 - 字符串1, str2 - 字符串2 * 返回值: 最长公共前缀的指针 */ char* commonPrefix(char* str1, char* str2); /* * 获取字符串数组中的最长公共前缀 * 参数: strs - 字符串数组, strsSize - 字符串数组的长度 * 返回值: 最长公共前缀的指针 */ char* longestCommonPrefix(char** strs, int strsSize) {
// 如果字符串数组为空或者长度为0，直接返回空字符串 if (strs == NULL || strsSize == 0) {
return ""; } // 将第一个字符串作为初始的最长公共前缀 char* prefix = strs[0]; // 遍历剩余的字符串 for (int i = 1; i < strsSize; i++) {
// 更新最长公共前缀为当前遍历的字符串与最长公共前缀的公共前缀 prefix = commonPrefix(prefix, strs[i]); // 如果最长公共前缀为空，说明不存在公共前缀，直接跳出循环 if (strlen(prefix) == 0) {
break; } } return prefix; } /* * 获取两个字符串的最长公共前缀的公共前缀 * 参数: str1 - 字符串1, str2 - 字符串2 * 返回值: 最长公共前缀的指针 */ char* commonPrefix(char* str1, char* str2) {
int length1 = strlen(str1); int length2 = strlen(str2); int index = 0; while (index < length1 && index < length2 && str1[index] == str2[index]) {
index++; } // 创建新的字符串，存储公共前缀 char* result = (char*)malloc((index + 1) * sizeof(char)); strncpy(result, str1, index); result[index] = '\0'; // 末尾添加结束符 return result; } Python3版本
class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: # 定义递归函数，用于求取字符串数组中指定范围内的最长公共前缀 def lcp(start, end): # 如果范围中只有一个字符串，则直接返回该字符串作为最长公共前缀 if start == end: return strs[start] # 分治法，将范围划分为两部分，分别求取左右两部分的最长公共前缀 mid = (start + end) // 2 lcpLeft, lcpRight = lcp(start, mid), lcp(mid + 1, end) # 找到左右两部分最长公共前缀的最小长度 minLength = min(len(lcpLeft), len(lcpRight)) # 在最小长度范围内逐个字符比较 for i in range(minLength): if lcpLeft[i] != lcpRight[i]: # 遇到第一个不相等的字符，返回前缀部分 return lcpLeft[:i] # 返回最小长度范围内的最长公共前缀 return lcpLeft[:minLength] # 如果字符串数组为空，则返回空字符串 return "" if not strs else lcp(0, len(strs) - 1) 复杂度分析
- 时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。时间复杂度的递推式是 T(n)=2⋅T(2n )+O(m)，通过计算可得 T(n)=O(mn)。
- 空间复杂度：O(mlogn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。空间复杂度主要取决于递归调用的层数，层数最大为 logn，每层需要 m 的空间存储返回结果。
方式四：二分查找
代码实现
Java版本
class Solution {
public String longestCommonPrefix(String[] strs) {
// 如果字符串数组为空或长度为0，直接返回空字符串 if (strs == null || strs.length == 0) {
return ""; } // 获取字符串数组中最短字符串的长度 int minLength = Integer.MAX_VALUE; for (String str : strs) {
minLength = Math.min(minLength, str.length()); } // 使用二分查找的思路来查找最长公共前缀 int low = 0, high = minLength; while (low < high) {
// 取中间位置 int mid = (high - low + 1) / 2 + low; // 判断中间位置的前缀是否是公共前缀 if (isCommonPrefix(strs, mid)) {
// 如果是，更新 low，继续查找右半部分 low = mid; } else {
// 如果不是，更新 high，继续查找左半部分 high = mid - 1; } } // 返回最长公共前缀 return strs[0].substring(0, low); } // 判断指定长度前缀是否是字符串数组的公共前缀 public boolean isCommonPrefix(String[] strs, int length) {
// 获取第一个字符串的指定长度前缀 String str0 = strs[0].substring(0, length); int count = strs.length; // 遍历剩余的字符串，逐个比较前缀字符 for (int i = 1; i < count; i++) {
String str = strs[i]; for (int j = 0; j < length; j++) {
if (str0.charAt(j) != str.charAt(j)) {
return false; } } } // 返回是否是公共前缀的结果 return true; } } C语言版本
#include <stdio.h> #include <stdlib.h> #include <string.h> // 函数声明 char* longestCommonPrefix(char** strs, int strsSize); int isCommonPrefix(char** strs, int strsSize, int len); / int main() { // 测试数据 char* strs[] = {"flower", "flow", "flight"}; int strsSize = 3; // 调用函数并打印结果 char* result = longestCommonPrefix(strs, strsSize); printf("Longest Common Prefix: %s\n", result); return 0; } / /* * 获取字符串数组中的最长公共前缀 * 参数: strs - 字符串数组, strsSize - 字符串数组的长度 * 返回值: 最长公共前缀的指针 */ char* longestCommonPrefix(char** strs, int strsSize) {
// 如果字符串数组为空或长度为0，直接返回空字符串 if (strs == NULL || strsSize == 0) {
return ""; } // 找出最短字符串的长度 int minLength = INT_MAX; for (int i = 0; i < strsSize; i++) {
int len = strlen(strs[i]); if (len < minLength) {
minLength = len; } } // 使用二分法查找最长公共前缀 int low = 1; int high = minLength; int mid = 0; while (low <= high) {
mid = (low + high) / 2; if (isCommonPrefix(strs, strsSize, mid)) {
low = mid + 1; } else {
high = mid - 1; } } // 根据最长公共前缀的长度，创建并返回结果字符串 char* result = (char*)malloc((mid + 1) * sizeof(char)); strncpy(result, strs[0], mid); result[mid] = '\0'; return result; } /* * 判断指定长度前缀是否是字符串数组的公共前缀 * 参数: strs - 字符串数组, strsSize - 字符串数组的长度, len - 前缀长度 * 返回值: 是否是公共前缀的整数值，1为是，0为否 */ int isCommonPrefix(char** strs, int strsSize, int len) {
for (int i = 0; i < len; i++) {
char ch = strs[0][i]; for (int j = 1; j < strsSize; j++) {
if (strs[j][i] != ch) {
return 0; } } } return 1; } Python3版本
def longestCommonPrefix(strs): # 如果字符串数组为空或长度为0，直接返回空字符串 if not strs: return "" # 找出最短字符串的长度 minLength = min(len(s) for s in strs) # 使用二分法查找最长公共前缀 low = 1 high = minLength while low <= high: mid = (low + high) // 2 if isCommonPrefix(strs, mid): low = mid + 1 else: high = mid - 1 # 根据最长公共前缀的长度，返回结果字符串 return strs[0][:low] def isCommonPrefix(strs, length): for i in range(length): ch = strs[0][i] for j in range(1, len(strs)): if strs[j][i] != ch: return False return True # 调用函数并打印结果 #strs = ["flower", "flow", "flight"] #result = longestCommonPrefix(strs) #print("Longest Common Prefix:", result) 复杂度分析
- 时间复杂度：O(mnlogm)，其中 m 是字符串数组中的字符串的最小长度，n 是字符串的数量。二分查找的迭代执行次数是 O(logm)，每次迭代最多需要比较 mn 个字符，因此总时间复杂度是 O(mnlogm)。
- 空间复杂度：O(1)。使用的额外空间复杂度为常数。
克隆图（LeetCode 133,Medium）
- 标签：图的遍历、深拷贝
题目
在这里插入代码片 思路及实现
方式一：暴力解法（不推荐）
思路
代码实现
Java
在这里插入代码片 C
在这里插入代码片 Python
在这里插入代码片 复杂度分析
- 时间复杂度
- 空间复杂度
方式二：暴力解法（不推荐）
思路
代码实现
Java
在这里插入代码片 C
在这里插入代码片 Python
在这里插入代码片 复杂度分析
- 时间复杂度
- 空间复杂度
合并排序的数组（LeetCode 88,Easy）
- 标签：归并排序、数组操作
题目
在这里插入代码片 思路及实现
方式一：暴力解法（不推荐）
思路
代码实现
Java
在这里插入代码片 C
在这里插入代码片 Python
在这里插入代码片 复杂度分析
- 时间复杂度
- 空间复杂度
方式二：暴力解法（不推荐）
思路
代码实现
Java
在这里插入代码片 C
在这里插入代码片 Python
在这里插入代码片 复杂度分析
- 时间复杂度
- 空间复杂度
第 K 个数（LeetCode 215,Medium）
- 标签：快速选择、二分查找
题目
在这里插入代码片 思路及实现
方式一：暴力解法（不推荐）
思路
代码实现
Java
在这里插入代码片 C
在这里插入代码片 Python
在这里插入代码片 复杂度分析
- 时间复杂度
- 空间复杂度
方式二：暴力解法（不推荐）
思路
代码实现
Java
在这里插入代码片 C
在这里插入代码片 Python
在这里插入代码片 复杂度分析
- 时间复杂度
- 空间复杂度
结语
经典的数据结构与算法题目不仅考察我们的解题思路和编程能力，更重要的是让我们深入理解各种数据结构和算法的原理和应用。通过解题，我们可以不断提高自己的编程能力，锻炼思维的敏捷性。同时，也能够给我们带来一些乐趣和满足感。
希望这些有趣的题目能够给你带来启发和帮助，让你更加热爱并深入学习数据结构与算法。加油，继续挑战，我们一起做个优秀的开发者！
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/121705.html
