常用算法实现
1. 快速排序（C++）
快速排序是一种高效的分治排序算法，平均时间复杂度为 O(n log n)。
#include <vector>
#include <algorithm>
template<typename T>
void quickSort(std::vector<T>& arr, int left, int right) {
if (left >= right) return;
// 选择中间元素作为基准
int pivot = arr[left + (right - left) / 2];
int i = left, j = right;
while (i <= j) {
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j--;
if (i <= j) {
std::swap(arr[i], arr[j]);
i++;
j--;
}
}
if (left < j) quickSort(arr, left, j);
if (i < right) quickSort(arr, i, right);
}
// 使用示例
void example() {
std::vector<int> data = {64, 34, 25, 12, 22, 11, 90};
quickSort(data, 0, data.size() - 1);
}2. 二分查找（Python）
在有序数组中快速查找目标元素，时间复杂度为 O(log n)。
def binary_search(arr, target):
"""二分查找算法"""
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 # 未找到
# 递归版本
def binary_search_recursive(arr, target, left=0, right=None):
if right is None:
right = len(arr) - 1
if left > right:
return -1
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, right)
else:
return binary_search_recursive(arr, target, left, mid - 1)
# 查找插入位置
def search_insert_position(arr, target):
"""查找目标值应该插入的位置"""
left, right = 0, len(arr)
while left < right:
mid = left + (right - left) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid
return left3. 动态规划 - 最长公共子序列（C++）
使用动态规划解决最长公共子序列问题。
#include <string>
#include <vector>
#include <algorithm>
int longestCommonSubsequence(const std::string& text1, const std::string& text2) {
int m = text1.length(), n = text2.length();
std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1[i-1] == text2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = std::max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[m][n];
}
// 获取实际的LCS字符串
std::string getLCS(const std::string& text1, const std::string& text2) {
int m = text1.length(), n = text2.length();
std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
// 构建DP表
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1[i-1] == text2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = std::max(dp[i-1][j], dp[i][j-1]);
}
}
}
// 回溯构建LCS
std::string lcs;
int i = m, j = n;
while (i > 0 && j > 0) {
if (text1[i-1] == text2[j-1]) {
lcs = text1[i-1] + lcs;
i--; j--;
} else if (dp[i-1][j] > dp[i][j-1]) {
i--;
} else {
j--;
}
}
return lcs;
}4. 图算法 - Dijkstra 最短路径（Python）
使用 Dijkstra 算法计算单源最短路径。
import heapq
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v, weight):
"""添加有向边"""
self.graph[u].append((v, weight))
def dijkstra(self, start):
"""Dijkstra 最短路径算法"""
# 距离字典
distances = {node: float('inf') for node in self.graph}
distances[start] = 0
# 优先队列：(距离, 节点)
pq = [(0, start)]
visited = set()
# 前驱节点，用于重建路径
previous = {}
while pq:
current_dist, current_node = heapq.heappop(pq)
if current_node in visited:
continue
visited.add(current_node)
# 检查所有邻居
for neighbor, weight in self.graph[current_node]:
distance = current_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
previous[neighbor] = current_node
heapq.heappush(pq, (distance, neighbor))
return distances, previous
def get_shortest_path(self, start, end):
"""获取从起点到终点的最短路径"""
distances, previous = self.dijkstra(start)
# 重建路径
path = []
current = end
while current in previous:
path.append(current)
current = previous[current]
path.append(start)
path.reverse()
return path, distances[end]
# 使用示例
g = Graph()
g.add_edge('A', 'B', 4)
g.add_edge('A', 'C', 2)
g.add_edge('B', 'C', 1)
g.add_edge('B', 'D', 5)
g.add_edge('C', 'D', 8)
path, dist = g.get_shortest_path('A', 'D')
print(f"最短路径: {' -> '.join(path)}, 距离: {dist}")设计模式实现
1. 单例模式（C++）
确保一个类只有一个实例，并提供全局访问点。
#include <mutex>
#include <memory>
class Singleton {
private:
static std::unique_ptr<Singleton> instance;
static std::mutex mutex;
// 私有构造函数
Singleton() {}
public:
// 删除拷贝构造和赋值操作
Singleton(const Singleton&) = delete;
Singleton& operator=(const Singleton&) = delete;
static Singleton& getInstance() {
std::lock_guard<std::mutex> lock(mutex);
if (!instance) {
instance.reset(new Singleton());
}
return *instance;
}
void doSomething() {
// 业务逻辑
}
};
// 静态成员初始化
std::unique_ptr<Singleton> Singleton::instance = nullptr;
std::mutex Singleton::mutex;
// C++11 线程安全版本（推荐）
class SingletonMeyers {
private:
SingletonMeyers() {}
public:
SingletonMeyers(const SingletonMeyers&) = delete;
SingletonMeyers& operator=(const SingletonMeyers&) = delete;
static SingletonMeyers& getInstance() {
static SingletonMeyers instance; // C++11保证线程安全
return instance;
}
};2. 观察者模式（Python）
定义对象间的一对多依赖关系，当一个对象状态改变时，所有依赖者都会收到通知。
from abc import ABC, abstractmethod
from typing import List
class Observer(ABC):
"""观察者接口"""
@abstractmethod
def update(self, subject):
pass
class Subject:
"""主题/被观察者"""
def __init__(self):
self._observers: List[Observer] = []
self._state = None
def attach(self, observer: Observer):
"""添加观察者"""
if observer not in self._observers:
self._observers.append(observer)
def detach(self, observer: Observer):
"""移除观察者"""
if observer in self._observers:
self._observers.remove(observer)
def notify(self):
"""通知所有观察者"""
for observer in self._observers:
observer.update(self)
@property
def state(self):
return self._state
@state.setter
def state(self, value):
self._state = value
self.notify()
# 具体观察者
class ConcreteObserverA(Observer):
def update(self, subject):
print(f"ObserverA: 收到状态更新 - {subject.state}")
class ConcreteObserverB(Observer):
def update(self, subject):
print(f"ObserverB: 收到状态更新 - {subject.state}")
# 使用示例
subject = Subject()
observer_a = ConcreteObserverA()
observer_b = ConcreteObserverB()
subject.attach(observer_a)
subject.attach(observer_b)
subject.state = "新状态1"
subject.state = "新状态2"3. 工厂模式（C++）
定义创建对象的接口，让子类决定实例化哪个类。
#include <memory>
#include <string>
// 产品接口
class Shape {
public:
virtual ~Shape() = default;
virtual void draw() const = 0;
virtual double area() const = 0;
};
// 具体产品
class Circle : public Shape {
private:
double radius;
public:
Circle(double r) : radius(r) {}
void draw() const override {
std::cout << "绘制圆形\n";
}
double area() const override {
return 3.14159 * radius * radius;
}
};
class Rectangle : public Shape {
private:
double width, height;
public:
Rectangle(double w, double h) : width(w), height(h) {}
void draw() const override {
std::cout << "绘制矩形\n";
}
double area() const override {
return width * height;
}
};
// 工厂类
class ShapeFactory {
public:
enum class ShapeType { CIRCLE, RECTANGLE };
static std::unique_ptr<Shape> createShape(ShapeType type,
double param1,
double param2 = 0) {
switch (type) {
case ShapeType::CIRCLE:
return std::make_unique<Circle>(param1);
case ShapeType::RECTANGLE:
return std::make_unique<Rectangle>(param1, param2);
default:
return nullptr;
}
}
};
// 使用
void factoryExample() {
auto circle = ShapeFactory::createShape(
ShapeFactory::ShapeType::CIRCLE, 5.0
);
circle->draw();
auto rect = ShapeFactory::createShape(
ShapeFactory::ShapeType::RECTANGLE, 4.0, 6.0
);
rect->draw();
}4. 策略模式（Python）
定义一系列算法，将每个算法封装起来，使它们可以相互替换。
from abc import ABC, abstractmethod
class Strategy(ABC):
"""策略接口"""
@abstractmethod
def execute(self, data):
pass
class BubbleSortStrategy(Strategy):
"""冒泡排序策略"""
def execute(self, data):
arr = data.copy()
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
class QuickSortStrategy(Strategy):
"""快速排序策略"""
def execute(self, data):
if len(data) <= 1:
return data
pivot = data[len(data) // 2]
left = [x for x in data if x < pivot]
middle = [x for x in data if x == pivot]
right = [x for x in data if x > pivot]
return self.execute(left) + middle + self.execute(right)
class SortContext:
"""上下文类"""
def __init__(self, strategy: Strategy):
self._strategy = strategy
@property
def strategy(self):
return self._strategy
@strategy.setter
def strategy(self, strategy: Strategy):
self._strategy = strategy
def sort(self, data):
return self._strategy.execute(data)
# 使用示例
data = [64, 34, 25, 12, 22, 11, 90]
context = SortContext(BubbleSortStrategy())
result1 = context.sort(data)
print(f"冒泡排序: {result1}")
context.strategy = QuickSortStrategy()
result2 = context.sort(data)
print(f"快速排序: {result2}")实用工具函数
1. 字符串处理工具（C++）
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
namespace StringUtils {
// 字符串分割
std::vector<std::string> split(const std::string& str, char delimiter) {
std::vector<std::string> tokens;
std::stringstream ss(str);
std::string token;
while (std::getline(ss, token, delimiter)) {
if (!token.empty()) {
tokens.push_back(token);
}
}
return tokens;
}
// 字符串trim
std::string trim(const std::string& str) {
auto start = std::find_if_not(str.begin(), str.end(),
[](unsigned char ch) { return std::isspace(ch); });
auto end = std::find_if_not(str.rbegin(), str.rend(),
[](unsigned char ch) { return std::isspace(ch); }).base();
return (start < end) ? std::string(start, end) : std::string();
}
// 字符串替换
std::string replace(std::string str, const std::string& from, const std::string& to) {
size_t pos = 0;
while ((pos = str.find(from, pos)) != std::string::npos) {
str.replace(pos, from.length(), to);
pos += to.length();
}
return str;
}
// 大小写转换
std::string toUpper(std::string str) {
std::transform(str.begin(), str.end(), str.begin(), ::toupper);
return str;
}
std::string toLower(std::string str) {
std::transform(str.begin(), str.end(), str.begin(), ::tolower);
return str;
}
// 判断是否以某个前缀开始
bool startsWith(const std::string& str, const std::string& prefix) {
return str.size() >= prefix.size() &&
str.compare(0, prefix.size(), prefix) == 0;
}
// 判断是否以某个后缀结束
bool endsWith(const std::string& str, const std::string& suffix) {
return str.size() >= suffix.size() &&
str.compare(str.size() - suffix.size(), suffix.size(), suffix) == 0;
}
} // namespace StringUtils2. 文件操作工具（Python）
import os
import json
import csv
from pathlib import Path
from typing import List, Dict, Any
class FileUtils:
"""文件操作工具类"""
@staticmethod
def read_json(filepath: str) -> Dict[str, Any]:
"""读取 JSON 文件"""
with open(filepath, 'r', encoding='utf-8') as f:
return json.load(f)
@staticmethod
def write_json(filepath: str, data: Dict[str, Any], indent: int = 2):
"""写入 JSON 文件"""
with open(filepath, 'w', encoding='utf-8') as f:
json.dump(data, f, indent=indent, ensure_ascii=False)
@staticmethod
def read_csv(filepath: str) -> List[Dict[str, str]]:
"""读取 CSV 文件"""
with open(filepath, 'r', encoding='utf-8') as f:
reader = csv.DictReader(f)
return list(reader)
@staticmethod
def write_csv(filepath: str, data: List[Dict[str, Any]],
fieldnames: List[str] = None):
"""写入 CSV 文件"""
if not data:
return
if fieldnames is None:
fieldnames = list(data[0].keys())
with open(filepath, 'w', encoding='utf-8', newline='') as f:
writer = csv.DictWriter(f, fieldnames=fieldnames)
writer.writeheader()
writer.writerows(data)
@staticmethod
def ensure_dir(directory: str):
"""确保目录存在"""
Path(directory).mkdir(parents=True, exist_ok=True)
@staticmethod
def get_file_size(filepath: str) -> int:
"""获取文件大小（字节）"""
return os.path.getsize(filepath)
@staticmethod
def list_files(directory: str, extension: str = None) -> List[str]:
"""列出目录中的所有文件"""
path = Path(directory)
if extension:
return [str(f) for f in path.glob(f"*.{extension}")]
return [str(f) for f in path.glob("*") if f.is_file()]
@staticmethod
def copy_file(src: str, dst: str):
"""复制文件"""
import shutil
shutil.copy2(src, dst)
@staticmethod
def move_file(src: str, dst: str):
"""移动文件"""
import shutil
shutil.move(src, dst)3. 日期时间工具（Python）
from datetime import datetime, timedelta
from typing import Optional
class DateTimeUtils:
"""日期时间工具类"""
@staticmethod
def now() -> datetime:
"""获取当前时间"""
return datetime.now()
@staticmethod
def format_datetime(dt: datetime, fmt: str = "%Y-%m-%d %H:%M:%S") -> str:
"""格式化日期时间"""
return dt.strftime(fmt)
@staticmethod
def parse_datetime(date_string: str, fmt: str = "%Y-%m-%d %H:%M:%S") -> datetime:
"""解析日期时间字符串"""
return datetime.strptime(date_string, fmt)
@staticmethod
def add_days(dt: datetime, days: int) -> datetime:
"""增加天数"""
return dt + timedelta(days=days)
@staticmethod
def add_hours(dt: datetime, hours: int) -> datetime:
"""增加小时"""
return dt + timedelta(hours=hours)
@staticmethod
def diff_days(dt1: datetime, dt2: datetime) -> int:
"""计算两个日期的天数差"""
return abs((dt2 - dt1).days)
@staticmethod
def is_weekend(dt: datetime) -> bool:
"""判断是否为周末"""
return dt.weekday() >= 5
@staticmethod
def get_month_range(year: int, month: int) -> tuple:
"""获取某月的开始和结束日期"""
start = datetime(year, month, 1)
if month == 12:
end = datetime(year + 1, 1, 1) - timedelta(days=1)
else:
end = datetime(year, month + 1, 1) - timedelta(days=1)
return start, end
@staticmethod
def timestamp_to_datetime(timestamp: float) -> datetime:
"""时间戳转日期时间"""
return datetime.fromtimestamp(timestamp)
@staticmethod
def datetime_to_timestamp(dt: datetime) -> float:
"""日期时间转时间戳"""
return dt.timestamp()4. 数据验证工具（Python）
import re
from typing import Any
class ValidationUtils:
"""数据验证工具类"""
@staticmethod
def is_email(email: str) -> bool:
"""验证电子邮件格式"""
pattern = r'^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$'
return bool(re.match(pattern, email))
@staticmethod
def is_phone(phone: str) -> bool:
"""验证手机号码（中国）"""
pattern = r'^1[3-9]\d{9}$'
return bool(re.match(pattern, phone))
@staticmethod
def is_url(url: str) -> bool:
"""验证URL格式"""
pattern = r'^https?://[^\s/$.?#].[^\s]*$'
return bool(re.match(pattern, url))
@staticmethod
def is_ip_address(ip: str) -> bool:
"""验证IP地址"""
pattern = r'^(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)$'
return bool(re.match(pattern, ip))
@staticmethod
def is_strong_password(password: str) -> bool:
"""验证强密码（至少8位，包含大小写字母、数字和特殊字符）"""
if len(password) < 8:
return False
has_upper = bool(re.search(r'[A-Z]', password))
has_lower = bool(re.search(r'[a-z]', password))
has_digit = bool(re.search(r'\d', password))
has_special = bool(re.search(r'[!@#$%^&*(),.?":{}|<>]', password))
return all([has_upper, has_lower, has_digit, has_special])
@staticmethod
def is_number(value: Any) -> bool:
"""判断是否为数字"""
try:
float(value)
return True
except (ValueError, TypeError):
return False
@staticmethod
def is_positive_integer(value: Any) -> bool:
"""判断是否为正整数"""
try:
num = int(value)
return num > 0
except (ValueError, TypeError):
return False
@staticmethod
def sanitize_filename(filename: str) -> str:
"""清理文件名，移除非法字符"""
return re.sub(r'[<>:"/\\|?*]', '_', filename)自定义数据结构
1. LRU 缓存（C++）
实现最近最少使用（Least Recently Used）缓存。
#include <unordered_map>
#include <list>
template<typename K, typename V>
class LRUCache {
private:
size_t capacity;
std::list<std::pair<K, V>> cache_list;
std::unordered_map<K, typename std::list<std::pair<K, V>>::iterator> cache_map;
public:
LRUCache(size_t cap) : capacity(cap) {}
V get(const K& key) {
auto it = cache_map.find(key);
if (it == cache_map.end()) {
throw std::runtime_error("Key not found");
}
// 移动到列表前端
cache_list.splice(cache_list.begin(), cache_list, it->second);
return it->second->second;
}
void put(const K& key, const V& value) {
auto it = cache_map.find(key);
if (it != cache_map.end()) {
// 更新已存在的键
it->second->second = value;
cache_list.splice(cache_list.begin(), cache_list, it->second);
} else {
// 添加新键
if (cache_list.size() == capacity) {
// 移除最久未使用的元素
auto last = cache_list.back();
cache_map.erase(last.first);
cache_list.pop_back();
}
cache_list.emplace_front(key, value);
cache_map[key] = cache_list.begin();
}
}
bool contains(const K& key) const {
return cache_map.find(key) != cache_map.end();
}
size_t size() const {
return cache_list.size();
}
};2. 前缀树/字典树（Python）
高效存储和检索字符串集合的数据结构。
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
self.word_count = 0
class Trie:
"""前缀树实现"""
def __init__(self):
self.root = TrieNode()
def insert(self, word: str):
"""插入单词"""
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
node.word_count += 1
def search(self, word: str) -> bool:
"""搜索完整单词"""
node = self._find_node(word)
return node is not None and node.is_end_of_word
def starts_with(self, prefix: str) -> bool:
"""检查是否存在以prefix开头的单词"""
return self._find_node(prefix) is not None
def _find_node(self, prefix: str) -> TrieNode:
"""查找前缀对应的节点"""
node = self.root
for char in prefix:
if char not in node.children:
return None
node = node.children[char]
return node
def get_words_with_prefix(self, prefix: str) -> list:
"""获取所有以prefix开头的单词"""
node = self._find_node(prefix)
if node is None:
return []
words = []
self._dfs(node, prefix, words)
return words
def _dfs(self, node: TrieNode, current_word: str, words: list):
"""深度优先搜索收集单词"""
if node.is_end_of_word:
words.append(current_word)
for char, child_node in node.children.items():
self._dfs(child_node, current_word + char, words)
def delete(self, word: str) -> bool:
"""删除单词"""
def _delete(node, word, index):
if index == len(word):
if not node.is_end_of_word:
return False
node.is_end_of_word = False
return len(node.children) == 0
char = word[index]
if char not in node.children:
return False
should_delete = _delete(node.children[char], word, index + 1)
if should_delete:
del node.children[char]
return len(node.children) == 0 and not node.is_end_of_word
return False
return _delete(self.root, word, 0)
# 使用示例
trie = Trie()
words = ["apple", "app", "application", "apply", "banana"]
for word in words:
trie.insert(word)
print(trie.search("app")) # True
print(trie.starts_with("app")) # True
print(trie.get_words_with_prefix("app")) # ['app', 'apple', 'application', 'apply']