前言
在面试中，数据结构和算法常常是被面试官重点考察的内容。掌握好常见的数据结构和算法，并能够灵活运用，对于通过面试来说至关重要。本文将对一些常见的数据结构和算法问题进行解析，并提供相应的解题思路。
数据结构
数组
数组是一种线性数据结构，具有固定大小和连续内存空间的特点。常见的数组问题有两数之和、三数之和等。
问题：两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值 target 的两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，但是你不能重复利用这个数组中同样的元素。
public int[] twoSum(int[] nums, int target) {
Map<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};
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
解题思路：使用哈希表（HashMap）来存储每个元素及其对应的索引值，遍历数组时，先检查哈希表中是否存在 complement（差值），存在则返回结果，不存在则将当前元素加入哈希表中。时间复杂度为 O(n)。
链表
链表是一种非连续存储的线性数据结构，由一系列节点组成，每个节点包含指向下一个节点的指针。常见的链表问题有反转链表、合并两个有序链表等。
问题：反转链表
反转一个单链表。
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
解题思路：使用两个指针 prev 和 curr，将当前节点的 next 指针指向前一个节点，然后更新 prev 和 curr 的指针，直到遍历完整个链表。时间复杂度为 O(n)。
栈和队列
栈和队列是两种常见的数据结构，栈是一种后进先出（LIFO）的数据结构，而队列是一种先进先出（FIFO）的数据结构。
问题：有效的括号
给定一个只包括 '('、')'、'{'、'}'、'['、']' 的字符串 s，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else if (c == ')' && !stack.isEmpty() && stack.peek() == '(') {
stack.pop();
} else if (c == ']' && !stack.isEmpty() && stack.peek() == '[') {
stack.pop();
} else if (c == '}' && !stack.isEmpty() && stack.peek() == '{') {
stack.pop();
} else {
return false;
}
}
return stack.isEmpty();
}
解题思路：使用栈来检查括号的闭合情况，遍历字符串，如果是左括号，则将其入栈；如果是右括号，则需要检查栈顶的元素是否与其对应，对应则将栈顶元素出栈，否则返回 false。遍历完字符串后，检查栈是否为空，为空则表示所有括号都闭合。时间复杂度为 O(n)。
树
树是一种非线性数据结构，每个节点最多有两个子节点。常见的树问题有二叉树的遍历（前序、中序、后序）、判断二叉搜索树等。
问题：二叉树的层序遍历
给定一个二叉树，返回其层序遍历结果。
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
result.add(level);
}
return result;
}
解题思路：使用队列来进行广度优先搜索（BFS），依次将每一层的节点入队，然后遍历每层节点并将其子节点入队。时间复杂度为 O(n)。
算法
排序算法
排序算法是将一组数据按照特定规则进行重新排列的算法。常见的排序算法有冒泡排序、插入排序、选择排序、快速排序、归并排序等。
问题：快速排序
给定一个整数数组 nums，使用快速排序算法对数组进行排序。
public void quickSort(int[] nums, int left, int right) {
if (left < right) {
int pivotIndex = partition(nums, left, right);
quickSort(nums, left, pivotIndex - 1);
quickSort(nums, pivotIndex + 1, right);
}
}
public int partition(int[] nums, int left, int right) {
int pivot = nums[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (nums[j] < pivot) {
i++;
swap(nums, i, j);
}
}
swap(nums, i + 1, right);
return i + 1;
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
解题思路：选择数组中的一个元素作为枢轴（通常选择最后一个元素），将小于枢轴的数放到左边，大于枢轴的数放到右边，然后递归地对左右两部分进行快速排序。时间复杂度最好情况为 O(nlogn)，最坏情况为 O(n^2)。
搜索算法
搜索算法是在给定的数据集合中查找特定元素或满足特定条件的元素的算法。常见的搜索算法有线性搜索、二分搜索、深度优先搜索（DFS）、广度优先搜索（BFS）等。
问题：二分搜索
给定一个有序（非降序）数组 nums 和一个目标值 target，使用二分搜索算法在数组中查找目标值，并返回其下标。
public int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
解题思路：在有序数组中进行二分查找，每次取中间元素与目标值进行比较，如果中间元素等于目标值，则返回其下标；如果中间元素小于目标值，则在右半部分查找；如果中间元素大于目标值，则在左半部分查找。时间复杂度为 O(logn)。
总结
本文对一些常见的数据结构和算法问题进行了解析，并提供相应的解题思路。在面试中，掌握好常见的数据结构和算法，并能够灵活运用，对于通过面试来说非常重要。希望本文能对大家在准备面试过程中有所帮助。
本文来自极简博客，作者：梦里花落，转载请注明原文链接：数据结构和算法常见面试题解析
