wehub-skill-sync
469 lines
9.8 KiB
Markdown
469 lines
9.8 KiB
Markdown
# 数组与字符串参考
|
||
|
||
## 数组
|
||
|
||
### 核心概念
|
||
|
||
**数组（array）** 是存储在连续内存位置上的元素集合。数组提供 O(1) 的随机访问，但插入/删除操作（末尾除外）为 O(n)。
|
||
|
||
**关键属性**：
|
||
- 固定或动态大小（取决于语言）
|
||
- 同质元素（相同类型）
|
||
- 多数语言中从零开始索引
|
||
- 连续内存分配
|
||
|
||
### 常见操作
|
||
|
||
| 操作 | 时间复杂度 | 说明 |
|
||
|-----------|----------------|-------|
|
||
| 访问 | O(1) | 直接索引查找 |
|
||
| 搜索 | O(n) | 若已排序则 O(log n) + 二分查找 |
|
||
| 插入（末尾） | O(1) 均摊 | 可能触发扩容 |
|
||
| 插入（任意位置） | O(n) | 移动元素 |
|
||
| 删除（末尾） | O(1) | Pop 操作 |
|
||
| 删除（任意位置） | O(n) | 移动元素 |
|
||
|
||
### Python 实现
|
||
|
||
```python
|
||
# Array/List operations
|
||
arr = [1, 2, 3, 4, 5]
|
||
|
||
# Access
|
||
element = arr[2] # O(1)
|
||
|
||
# Search
|
||
index = arr.index(3) # O(n)
|
||
exists = 3 in arr # O(n)
|
||
|
||
# Insert
|
||
arr.append(6) # O(1) at end
|
||
arr.insert(2, 10) # O(n) at arbitrary position
|
||
|
||
# Delete
|
||
arr.pop() # O(1) from end
|
||
arr.pop(2) # O(n) from arbitrary position
|
||
arr.remove(10) # O(n) - finds and removes
|
||
|
||
# Slicing
|
||
subarray = arr[1:4] # O(k) where k is slice size
|
||
|
||
# Common patterns
|
||
reversed_arr = arr[::-1]
|
||
sorted_arr = sorted(arr) # O(n log n)
|
||
```
|
||
|
||
### JavaScript 实现
|
||
|
||
```javascript
|
||
// Array operations
|
||
const arr = [1, 2, 3, 4, 5];
|
||
|
||
// Access
|
||
const element = arr[2]; // O(1)
|
||
|
||
// Search
|
||
const index = arr.indexOf(3); // O(n)
|
||
const exists = arr.includes(3); // O(n)
|
||
|
||
// Insert
|
||
arr.push(6); // O(1) at end
|
||
arr.splice(2, 0, 10); // O(n) at arbitrary position
|
||
|
||
// Delete
|
||
arr.pop(); // O(1) from end
|
||
arr.splice(2, 1); // O(n) from arbitrary position
|
||
|
||
// Slicing
|
||
const subarray = arr.slice(1, 4); // O(k)
|
||
|
||
// Common patterns
|
||
const reversedArr = arr.reverse();
|
||
const sortedArr = arr.sort((a, b) => a - b); // O(n log n)
|
||
```
|
||
|
||
---
|
||
|
||
## 字符串
|
||
|
||
### 核心概念
|
||
|
||
**字符串（string）** 是字符序列。在大多数语言中，字符串是不可变的（Python、Java），或被视为字符数组（C++，JavaScript 在某些情况下允许修改）。
|
||
|
||
**关键属性**：
|
||
- 在 Python、Java、JavaScript（基本类型）中不可变
|
||
- 在 C++ 中是字符数组
|
||
- 需考虑 UTF-8/UTF-16 编码
|
||
- 拼接操作可能代价高昂
|
||
|
||
### 常见操作
|
||
|
||
| 操作 | 时间复杂度 | 说明 |
|
||
|-----------|----------------|-------|
|
||
| 访问 | O(1) | 直接索引查找 |
|
||
| 拼接 | O(n + m) | 若不可变则创建新字符串 |
|
||
| 子串 | O(k) | k = 子串长度 |
|
||
| 搜索 | O(n * m) | 朴素算法；使用 KMP 为 O(n + m) |
|
||
| 替换 | O(n) | 不可变语言中创建新字符串 |
|
||
|
||
### Python 实现
|
||
|
||
```python
|
||
s = "hello world"
|
||
|
||
# Access
|
||
char = s[0] # O(1)
|
||
|
||
# Slicing
|
||
substring = s[0:5] # O(k)
|
||
substring = s[::-1] # Reverse O(n)
|
||
|
||
# Search
|
||
index = s.find("world") # O(n), returns -1 if not found
|
||
index = s.index("world") # O(n), raises error if not found
|
||
exists = "world" in s # O(n)
|
||
|
||
# Modification (creates new string)
|
||
s_upper = s.upper()
|
||
s_lower = s.lower()
|
||
s_replaced = s.replace("world", "python")
|
||
|
||
# Split and join
|
||
words = s.split() # O(n)
|
||
joined = " ".join(words) # O(n)
|
||
|
||
# Common patterns
|
||
is_alpha = s.isalpha()
|
||
is_digit = s.isdigit()
|
||
stripped = s.strip() # Remove whitespace
|
||
```
|
||
|
||
### JavaScript 实现
|
||
|
||
```javascript
|
||
let s = "hello world";
|
||
|
||
// Access
|
||
const char = s[0]; // O(1)
|
||
|
||
// Slicing
|
||
const substring = s.slice(0, 5); // O(k)
|
||
const reversed = s.split('').reverse().join(''); // O(n)
|
||
|
||
// Search
|
||
const index = s.indexOf("world"); // O(n), returns -1 if not found
|
||
const exists = s.includes("world"); // O(n)
|
||
|
||
// Modification (creates new string)
|
||
const sUpper = s.toUpperCase();
|
||
const sLower = s.toLowerCase();
|
||
const sReplaced = s.replace("world", "javascript");
|
||
|
||
// Split and join
|
||
const words = s.split(' '); // O(n)
|
||
const joined = words.join(' '); // O(n)
|
||
|
||
// Common methods
|
||
const trimmed = s.trim();
|
||
const startsWithHello = s.startsWith("hello");
|
||
const endsWithWorld = s.endsWith("world");
|
||
```
|
||
|
||
---
|
||
|
||
## 常见数组/字符串模式
|
||
|
||
### 1. 双指针
|
||
|
||
**问题**：检查字符串是否为回文
|
||
```python
|
||
def is_palindrome(s):
|
||
left, right = 0, len(s) - 1
|
||
|
||
while left < right:
|
||
if s[left] != s[right]:
|
||
return False
|
||
left += 1
|
||
right -= 1
|
||
|
||
return True
|
||
```
|
||
|
||
### 2. 滑动窗口
|
||
|
||
**问题**：大小为 k 的最大子数组和
|
||
```python
|
||
def max_sum_subarray(arr, k):
|
||
if len(arr) < k:
|
||
return None
|
||
|
||
window_sum = sum(arr[:k])
|
||
max_sum = window_sum
|
||
|
||
for i in range(k, len(arr)):
|
||
window_sum = window_sum - arr[i - k] + arr[i]
|
||
max_sum = max(max_sum, window_sum)
|
||
|
||
return max_sum
|
||
```
|
||
|
||
### 3. 前缀和
|
||
|
||
**问题**：区间和查询
|
||
```python
|
||
class RangeSumQuery:
|
||
def __init__(self, nums):
|
||
self.prefix = [0]
|
||
for num in nums:
|
||
self.prefix.append(self.prefix[-1] + num)
|
||
|
||
def sum_range(self, left, right):
|
||
return self.prefix[right + 1] - self.prefix[left]
|
||
```
|
||
|
||
### 4. 哈希表统计频率
|
||
|
||
**问题**：字符串中第一个不重复的字符
|
||
```python
|
||
def first_unique_char(s):
|
||
from collections import Counter
|
||
|
||
freq = Counter(s)
|
||
|
||
for i, char in enumerate(s):
|
||
if freq[char] == 1:
|
||
return i
|
||
|
||
return -1
|
||
```
|
||
|
||
### 5. 字符串构建器（性能优化）
|
||
|
||
**问题**：高效字符串拼接
|
||
```python
|
||
# BAD: O(n²) due to immutability
|
||
result = ""
|
||
for i in range(n):
|
||
result += str(i) # Creates new string each time
|
||
|
||
# GOOD: O(n) using list
|
||
result = []
|
||
for i in range(n):
|
||
result.append(str(i))
|
||
final_result = "".join(result)
|
||
```
|
||
|
||
---
|
||
|
||
## 进阶技巧
|
||
|
||
### 1. Kadane 算法（最大子数组和）
|
||
|
||
```python
|
||
def max_subarray_sum(nums):
|
||
"""Find maximum sum of contiguous subarray."""
|
||
max_current = max_global = nums[0]
|
||
|
||
for i in range(1, len(nums)):
|
||
max_current = max(nums[i], max_current + nums[i])
|
||
max_global = max(max_global, max_current)
|
||
|
||
return max_global
|
||
```
|
||
|
||
**时间复杂度**：O(n)，**空间复杂度**：O(1)
|
||
|
||
### 2. KMP 字符串匹配
|
||
|
||
```python
|
||
def kmp_search(text, pattern):
|
||
"""Knuth-Morris-Pratt string matching."""
|
||
def compute_lps(pattern):
|
||
lps = [0] * len(pattern)
|
||
length = 0
|
||
i = 1
|
||
|
||
while i < len(pattern):
|
||
if pattern[i] == pattern[length]:
|
||
length += 1
|
||
lps[i] = length
|
||
i += 1
|
||
else:
|
||
if length != 0:
|
||
length = lps[length - 1]
|
||
else:
|
||
lps[i] = 0
|
||
i += 1
|
||
|
||
return lps
|
||
|
||
lps = compute_lps(pattern)
|
||
i = j = 0
|
||
|
||
while i < len(text):
|
||
if pattern[j] == text[i]:
|
||
i += 1
|
||
j += 1
|
||
|
||
if j == len(pattern):
|
||
return i - j # Pattern found
|
||
elif i < len(text) and pattern[j] != text[i]:
|
||
if j != 0:
|
||
j = lps[j - 1]
|
||
else:
|
||
i += 1
|
||
|
||
return -1 # Not found
|
||
```
|
||
|
||
**时间复杂度**：O(n + m)，**空间复杂度**：O(m)
|
||
|
||
### 3. Rabin-Karp（滚动哈希）
|
||
|
||
```python
|
||
def rabin_karp(text, pattern):
|
||
"""Rolling hash string matching."""
|
||
d = 256 # Number of characters
|
||
q = 101 # Prime number
|
||
m = len(pattern)
|
||
n = len(text)
|
||
p = 0 # Hash value for pattern
|
||
t = 0 # Hash value for text
|
||
h = 1
|
||
|
||
# Calculate h = pow(d, m-1) % q
|
||
for i in range(m - 1):
|
||
h = (h * d) % q
|
||
|
||
# Calculate initial hash values
|
||
for i in range(m):
|
||
p = (d * p + ord(pattern[i])) % q
|
||
t = (d * t + ord(text[i])) % q
|
||
|
||
# Slide pattern over text
|
||
for i in range(n - m + 1):
|
||
if p == t:
|
||
# Check characters one by one
|
||
if text[i:i + m] == pattern:
|
||
return i
|
||
|
||
# Calculate hash for next window
|
||
if i < n - m:
|
||
t = (d * (t - ord(text[i]) * h) + ord(text[i + m])) % q
|
||
if t < 0:
|
||
t += q
|
||
|
||
return -1
|
||
```
|
||
|
||
**平均时间复杂度**：O(n + m)，**最坏情况**：O(n * m)
|
||
|
||
---
|
||
|
||
## 常见陷阱与最佳实践
|
||
|
||
### 陷阱 1：差一错误
|
||
```python
|
||
# WRONG
|
||
for i in range(len(arr) - 1): # Misses last element
|
||
print(arr[i])
|
||
|
||
# CORRECT
|
||
for i in range(len(arr)):
|
||
print(arr[i])
|
||
```
|
||
|
||
### 陷阱 2：遍历时修改
|
||
```python
|
||
# WRONG
|
||
for item in arr:
|
||
if item % 2 == 0:
|
||
arr.remove(item) # Can skip elements
|
||
|
||
# CORRECT
|
||
arr = [item for item in arr if item % 2 != 0]
|
||
# Or iterate backwards
|
||
for i in range(len(arr) - 1, -1, -1):
|
||
if arr[i] % 2 == 0:
|
||
arr.pop(i)
|
||
```
|
||
|
||
### 陷阱 3：循环中拼接字符串
|
||
```python
|
||
# INEFFICIENT: O(n²)
|
||
result = ""
|
||
for i in range(n):
|
||
result += str(i)
|
||
|
||
# EFFICIENT: O(n)
|
||
result = "".join(str(i) for i in range(n))
|
||
```
|
||
|
||
### 最佳实践 1：使用内置函数
|
||
```python
|
||
# Manual max finding
|
||
max_val = arr[0]
|
||
for val in arr:
|
||
if val > max_val:
|
||
max_val = val
|
||
|
||
# Better
|
||
max_val = max(arr)
|
||
```
|
||
|
||
### 最佳实践 2：列表推导式
|
||
```python
|
||
# Traditional loop
|
||
squares = []
|
||
for x in range(10):
|
||
squares.append(x ** 2)
|
||
|
||
# List comprehension (more Pythonic)
|
||
squares = [x ** 2 for x in range(10)]
|
||
```
|
||
|
||
### 最佳实践 3：使用 Enumerate 获取索引与值
|
||
```python
|
||
# Manual indexing
|
||
for i in range(len(arr)):
|
||
print(f"Index {i}: {arr[i]}")
|
||
|
||
# Better
|
||
for i, val in enumerate(arr):
|
||
print(f"Index {i}: {val}")
|
||
```
|
||
|
||
---
|
||
|
||
## 面试问题检查清单
|
||
|
||
在解决数组/字符串问题时：
|
||
|
||
1. **明确约束条件**：
|
||
- 数组大小限制？
|
||
- 数组能否为空？
|
||
- 取值范围？
|
||
- 是否允许原地修改？
|
||
|
||
2. **考虑边界情况**：
|
||
- 空数组/空字符串
|
||
- 单个元素
|
||
- 所有元素相同
|
||
- 已排序
|
||
- 负数（针对数组）
|
||
|
||
3. **选择方法**：
|
||
- 先暴力求解（验证逻辑）
|
||
- 优化（双指针、哈希表、滑动窗口）
|
||
- 考虑时间/空间权衡
|
||
|
||
4. **用示例测试**：
|
||
- 常规情况
|
||
- 边界情况
|
||
- 大量输入
|
||
|
||
5. **分析复杂度**：
|
||
- 时间复杂度
|
||
- 空间复杂度
|
||
- 能否进一步优化？
|