# ac_learning_note

**Repository Path**: qiangge_666/ac_learning_note

## Basic Information

- **Project Name**: ac_learning_note
- **Description**: AC学习笔记
- **Primary Language**: C++
- **License**: CC-BY-4.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 2
- **Forks**: 1
- **Created**: 2020-05-14
- **Last Updated**: 2026-02-07

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# AC Learning Note

> 算法学习笔记与 C++ 编程实践项目

[![License](https://img.shields.io/badge/license-MIT-blue.svg)](LICENSE)
[![Gitee](https://img.shields.io/badge/Gitee-opencode-green.svg)](https://gitee.com/qiangge_666/ac_learning_note)

## 📖 项目简介

本项目是算法学习笔记与 C++ 编程实践的集合，包含：

- **算法实现**：Dijkstra、Bellman-Ford、SPFA、Floyd 等经典算法
- **LeetCode 解法**：Two Sum、Longest Fibonacci Subsequence 等题目解答
- **数据结构**：链表、堆、二分查找等数据结构实现
- **动态规划**：矩阵连乘、数字三角形等动态规划问题
- **测试框架**：基于 Google Test 的完整测试套件

### 博客

- [AC 数的博客](https://www.fogsail.net)

## 🚀 快速开始

### 环境要求

#### 必需依赖

- **GCC**: 15.2.1+ (支持 C++11)
- **CMake**: 4.2.3+
- **Ninja**: 1.13.2+
- **Google Test**: 1.17.0+ (系统包)
- **Python**: 3.14.2+
- **pytest**: 8.4.2+

#### 可选依赖（代码质量工具）

- **cppcheck**: 2.19.1+ (静态代码分析)
- **gcovr**: 8.6+ (代码覆盖率)
- **lcov**: 2.4+ (覆盖率可视化)
- **clang-format**: (代码格式化)

#### 可选构建工具

- **xmake**: 3.0.6+ (跨平台构建工具，替代 CMake)

### 依赖安装

#### Manjaro / Arch Linux

```bash
# 安装所有依赖
sudo pacman -Sy --noconfirm \
    gcc cmake ninja \
    gtest python python-pytest \
    cppcheck gcovr lcov \
    clang-format pre-commit
```

#### Ubuntu / Debian

```bash
# 更新包列表
sudo apt update

# 安装所有依赖
sudo apt install -y \
    build-essential cmake ninja-build \
    libgtest-dev python3 python3-pytest \
    cppcheck gcovr lcov \
    clang-format pre-commit

# 可选：安装 xmake
curl -fsSL https://xmake.io/shget.text | bash
```

### 使用 xmake 构建（推荐新手）

xmake 是一个基于 Lua 的跨平台构建工具，配置更简单：

```bash
# 配置并自动下载依赖（gtest）
xmake f -m debug -y

# 编译
xmake

# 运行测试
xmake run
```

**xmake 优势：**

- 自动下载和管理依赖（无需系统安装 gtest）
- 配置简单，一条命令完成
- 跨平台支持更好

**CMake 优势：**

- 支持代码覆盖率分析
- 支持静态代码检查 (cppcheck)
- 更适合 CI/CD 集成

### 一键构建脚本

项目提供了 `build_run.sh` 脚本，自动完成依赖安装、编译、测试和覆盖率生成：

```bash
# 运行完整构建流程
bash build_run.sh
```

该脚本会自动：

1. 检测操作系统并安装缺失依赖
2. 配置 CMake 项目（启用覆盖率）
3. 执行静态代码分析 (cppcheck)
4. 编译项目
5. 运行所有 C++ 和 Python 测试
6. 生成代码覆盖率报告
7. **覆盖率门禁检查**（最低 90%，不满足则构建失败）

### 手动编译安装

```bash
# 创建构建目录
mkdir build && cd build

# 配置项目（启用覆盖率）
cmake -DENABLE_COVERAGE=ON -DCMAKE_EXPORT_COMPILE_COMMANDS=ON ..

# 编译
make
```

### 运行测试

```bash
# 运行所有测试
./build/my_ac_note

# 运行单个测试
./build/my_ac_note --gtest_filter=MyTest.test_name

# 运行所有测试并生成 XML 报告
./build/my_ac_note --gtest_output=xml:build/report_gtest.xml
```

### 代码格式化

```bash
# 格式化代码
clang-format --style=Google -i src/**/*.cpp src/**/*.h

# 运行所有 pre-commit hooks
pre-commit run --all-files
```

## 📁 项目结构

```
ac_learning_note/
├── .opencode/           # OpenCode AI 编程助手配置
│   └── skills/          # 开发技能包（测试、审查、重构等）
├── src/                 # C++ 源代码
│   ├── algorithms/      # 算法实现
│   │   └── leetcode/    # LeetCode 题目解答
│   ├── data_structures/ # 数据结构定义
│   │   └── list_node.h  # 链表节点定义
│   ├── utils/           # 工具类
│   │   ├── singleton.h
│   │   └── singleton.cpp
│   ├── tests/           # 测试目录
│   ├── other/           # 共享工具函数（Numerical Recipes）
│   ├── main.cpp         # 主程序入口
│   ├── mytest.h/.cpp    # 测试基础设施
│   └── mytest01.cpp     # 额外测试
├── py/                  # Python 实现
├── data/                # 测试数据
├── AGENTS.md            # AI 编程助手使用指南
├── build_run.sh         # 一键构建脚本（含90%覆盖率门禁）
├── CMakeLists.txt       # CMake 构建配置
└── README.md            # 本文件
```

## 📚 算法学习笔记

### 已实现算法

#### 图论

- [Dijkstra 算法](#第一讲-dijkstra-算法)
- Bellman-Ford 算法
- SPFA 算法
- Floyd-Warshall 算法
- Tarjan 强连通分量

#### 动态规划

- 矩阵连乘问题
- 数字三角形（POJ1163）
- 最长斐波那契子序列
- 最大路径和问题

#### 数据结构与算法

- 二分查找
- 链表操作（反转、删除中间节点）
- 数组操作（旋转、去重）
- 位运算与状态压缩

#### LeetCode 题目

- [Two Sum](src/algorithms/leetcode/vector_two_sum.cpp) - 两数之和
- [Add Two Numbers](src/algorithms/leetcode/listnode_two_sum.cpp) - 两数相加
- [Richest Customer Wealth](src/algorithms/leetcode/Richest_Customer_Wealth.cpp) - 最富有客户的资产总量
- [Longest Fibonacci Subsequence](src/algorithms/leetcode/Longest_Fibonacci_Subsequence.cpp) - 最长斐波那契子序列
- [Delete Middle Node](src/algorithms/leetcode/Delete_Middle_Node.cpp) - 删除链表中间节点

### 第一讲-Dijkstra 算法

Dijkstra 算法采用的是一种贪心的策略，声明一个数组 dis 来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把 dis[m]设为 w（s, m）,同时把所有其他（s 不能直接到达的）顶点的路径长度设为无穷大。初始时，集合 T 只有顶点 s。

然后，从 dis 数组选择最小值，则该值就是源点 s 到该值对应的顶点的最短路径，并且把该点加入到 T 中，OK，此时完成一个顶点，然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在 dis 中的值。然后，又从 dis 中找出最小值，重复上述动作，直到 T 中包含了图的所有顶点。

参考链接：[CSDN 博客](https://blog.csdn.net/qq_35644234/article/details/60870719)

### 其他算法章节

更多算法讲解请参考：

- 第二讲-bellman-ford
- 第三讲-spfa
- 第四讲-DFA
- 第五讲-群论思想理解 floyd
- 第六讲-无限猴子定理

## 🛠️ 开发指南

本项目提供了完整的开发工具和规范，请参阅：

- **[AGENTS.md](AGENTS.md)** - AI 编程助手（OpenCode）使用指南
  - 构建命令
  - 代码审查规范
  - 测试框架使用
  - 命名约定和格式化规则
- **OpenCode Skills** - 项目内置的开发技能包
  - `cpp-test-skill` - 自动生成测试用例
  - `cpp-review-skill` - 代码审查
  - `cpp-refactor-skill` - 代码重构
  - `cmake-skill` - CMake 配置管理
  - `cpp-memory-skill` - 内存管理
  - `cpp-performance-skill` - 性能优化

### 代码风格

- **命名规范**：类和函数使用 lowercase snake_case（如 `a_plus_b_no_plus_sym`）
- **格式化**：4 空格缩进，120 列限制，使用 clang-format
- **C++ 标准**：C++11
- **测试框架**：Google Test，所有测试继承 `MyTest` 基类

## 🤝 贡献指南

欢迎贡献代码！请遵循以下步骤：

1. Fork 本仓库
2. 创建特性分支 (`git checkout -b feat/your-feature`)
3. 提交更改 (`git commit -m 'Add some feature'`)
4. 推送到分支 (`git push origin feat/your-feature`)
5. 开启 Pull Request

### 提交规范

提交信息应清晰描述更改内容：

- `feat:` - 新功能
- `fix:` - 修复 bug
- `docs:` - 文档更新
- `style:` - 代码格式（不影响代码功能）
- `refactor:` - 重构
- `test:` - 测试相关
- `chore:` - 构建/工具相关

## 📄 许可证

本项目采用 MIT 许可证 - 详见 [LICENSE](LICENSE) 文件

## 🔗 相关链接

- [博客：AC 数](https://www.fogsail.net)
- [Gitee 仓库](https://gitee.com/qiangge_666/ac_learning_note)
- [Dijkstra 算法详解](https://blog.csdn.net/qq_35644234/article/details/60870719)
- [矩阵连乘问题](https://blog.csdn.net/qq_32919451/article/details/80643118)

## 📝 待完成章节

以下章节待补充内容：

- Bellman-Ford 算法详细讲解
- SPFA 算法详细讲解
- DFA 算法详细讲解
- Floyd-Warshall 算法详细讲解
- 群论思想理解 Floyd
- 无限猴子定理

---

**Happy Coding! 🎉**