在软件开发和技术岗位的招聘过程中，数据结构和算法是衡量候选人编程能力和思维逻辑的重要标准之一。许多企业在面试中会设置与数据结构相关的题目，以考察求职者对基本概念的理解以及解决实际问题的能力。以下是一些经典的、常见于技术面试中的数据结构相关问题及其解析。
一、数组与字符串
1. 反转字符串
- 题目描述：给定一个字符串，请将其反转。
- 解法：可以使用双指针法，分别从字符串的两端开始交换字符，直到两个指针相遇或交错。
- 代码示例（Python）：
```python
def reverse_string(s):
s = list(s)
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
return ''.join(s)
```
2. 最长回文子串
- 题目描述：给定一个字符串，找到其中最长的回文子串。
- 解法：可以通过中心扩展法，以每个字符为中心向两边扩展，寻找最长的回文。
- 代码示例（Java）：
```java
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
```
二、链表
1. 删除链表中的倒数第N个节点
- 题目描述：给定一个链表和一个整数 n，请删除链表的倒数第 n 个节点，并返回链表的头结点。
- 解法：使用快慢指针，快指针先走 n 步，然后快慢指针同时移动，当快指针到达末尾时，慢指针所指即为需要删除的节点。
- 代码示例（C++）：
```cpp
ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy->next = head;
ListNode fast = dummy;
ListNode slow = dummy;
for (int i = 0; i < n; ++i) {
fast = fast->next;
}
while (fast && fast->next) {
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
return dummy->next;
}
```
2. 合并两个有序链表
- 题目描述：将两个升序链表合并为一个新的升序链表并返回。
- 解法：使用递归方法，比较两个链表的当前节点值，较小的节点作为新链表的当前节点，然后递归处理剩余部分。
- 代码示例（Python）：
```python
def mergeTwoLists(l1, l2):
if not l1: return l2
if not l2: return l1
if l1.val < l2.val:
l1.next = mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = mergeTwoLists(l1, l2.next)
return l2
```
三、栈与队列
1. 有效的括号
- 题目描述：给定一个只包括 '('，')'，'{'，'}'，'[' 和 ']' 的字符串，判断字符串是否有效。
- 解法：使用栈来匹配括号，遇到左括号入栈，遇到右括号则检查栈顶元素是否匹配。
- 代码示例（Java）：
```java
public boolean isValid(String s) {
Stack
for (char c : s.toCharArray()) {
if (c == '(') stack.push(')');
else if (c == '{') stack.push('}');
else if (c == '[') stack.push(']');
else if (stack.isEmpty() || stack.pop() != c) return false;
}
return stack.isEmpty();
}
```
2. 滑动窗口最大值
- 题目描述：给定一个数组 nums 和一个大小为 k 的滑动窗口，从左到右移动窗口，求出每个窗口内的最大值。
- 解法：使用双端队列存储索引，保持队列中的索引对应的值递减，每次移动窗口时更新最大值。
- 代码示例（Python）：
```python
from collections import deque
def maxSlidingWindow(nums, k):
dq = deque()
res = []
for i in range(len(nums)):
while dq and nums[dq[-1]] <= nums[i]:
dq.pop()
dq.append(i)
if dq[0] == i - k:
dq.popleft()
if i >= k - 1:
res.append(nums[dq[0]])
return res
```
以上只是数据结构面试题的一部分，但它们涵盖了数组、字符串、链表、栈和队列等多个领域。准备这些题目不仅有助于提高技术能力，还能增强解决问题的思维方式。希望这些例子能帮助你在面试中脱颖而出！
