HespethornのBlog

108. Convert Sorted Array to Binary Search TreeGiven an integer array nums where the elements are sorted in ascending order, convert it to a *height-balanced* binary search tree. Example 1: 123Input: nums = [-10,-3,0,5,9]Output: [0,-3,9,-10,null,5]Explanation: [0,-10,5,null,-3,null,9] is also accepted: Example 2: 123Input: nums = [1,3]Output: [3,1]Explanation: [1,null,3] and [3,1] are both height-balanced BSTs. 题目大意给定一个升序排列的整数数组 nums，将其转换为一棵高度平衡的二叉搜索树（BST）。高度平衡的定义是：二叉树的左右两个子树的高度差的绝对值不超过...

106. Construct Binary Tree from Inorder and Postorder TraversalGiven two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree. Example 1: 12Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]Output: [3,9,20,null,null,15,7] Example 2: 12Input: inorder = [-1], postorder = [-1]Output: [-1] 题目大意给定一棵二叉树的中序遍历数组 inorder 和后序遍历数组...

一、类图设计方法论：构建稳健的面向对象模型类图建模的本质是将现实世界的业务概念转化为计算机可理解的面向对象结构。遵循科学的方法论是确保模型质量的基础，核心包含四大环节：元素识别、关系构建、属性定义与模型优化。 1.1 元素识别：精准定位核心建模单元元素识别是类图设计的起点，需从业务需求中提取关键概念并转化为 UML 元素。识别过程需遵循 "单一职责原则"，确保每个元素职责清晰、边界明确。 核心元素类型及识别方法 元素类型 识别特征 表示符号 应用场景 类 (Class) 具有相同属性和行为的对象集合 矩形（分三层：类名 / 属性 / 方法） 业务实体（如 User、Order）、控制逻辑（如 OrderService）、工具组件（如 DateUtils） 接口 (Interface) 定义行为契约，无具体实现 棒棒糖形状或矩形（标注 <>） 服务契约（如 PaymentGateway）、模块边界（如 UserRepository） 抽象类 (Abstract...

一、面向对象分析（OOA）：需求提取与实体识别1.1 核心业务需求本系统旨在实现以下关键功能： 支持对多种基础几何图形，包括矩形、圆形和三角形的面积计算； 以统一的方式展示不同类型图形的名称及其对应的面积计算结果； 构建具有高度扩展性的系统架构，确保在新增图形类型时，现有计算逻辑无需进行任何修改。 1.2 核心实体识别（3 个以上核心实体）经过严谨的需求分析，本研究确定了以下核心业务实体，并对各实体的属性、行为及业务约束进行了详细定义： 实体名称 核心属性 核心行为 业务约束 图形（Figure） 无直接属性（抽象概念） 获取名称、计算面积 作为抽象基类，不可实例化，需由具体图形类继承 矩形（Rectangle） 长度（length）、宽度（width） 计算面积、返回名称 长度和宽度必须为正数 圆形（Circle） 半径（radius） 计算面积、返回名称 半径必须为正数 三角形（Triangle） 三边长度（a、b、c） 计算面积、返回名称 三边长度需满足三角不等式（a+b>c...

导言在 C++ 开发中，频繁使用 new/delete 会导致内存碎片、系统调用开销大等问题，尤其在多线程场景下性能损耗显著。内存池作为一种高效的内存管理方案，通过预先申请大块内存、重复利用空闲内存的方式，能有效解决这些问题。 一、内存池核心设计思路1.1 解决的核心问题 内存碎片：原生 new/delete 分配的内存大小随机，长期使用会产生大量无法利用的小块内存（碎片）； 系统调用开销：每次 new 都会触发系统调用（如 brk/mmap），频繁调用会严重影响性能； 多线程安全：原生内存分配器的锁竞争会导致多线程场景下性能下降。 1.2 核心设计方案我们的内存池采用 “多池分治 + 无锁空闲链表 + 内存块复用” 的设计，具体如下： 多池分治：按内存大小划分 64 个内存池，分别管理 8~512 字节的内存（步长 8 字节），超过 512 字节的内存直接使用原生 new/delete； 无锁空闲链表：用原子操作（CAS）实现空闲内存的入队 / 出队，避免多线程锁竞争； 内存块复用：预先申请 4096...

一、STL 算法调用成员函数的典型错误在开始解决方案前，我们先明确最常见的错误模式，理解问题本质才能避免重复踩坑。 1.1 错误代码示例1234567891011121314151617181920212223242526#include <vector>#include <algorithm>#include <iostream>class NumberProcessor {private: int value;public: NumberProcessor(int v) : value(v) {} bool isEven() const { return value % 2 == 0; } // 筛选条件成员函数 void printValue() const { std::cout << value << " "; } // 操作成员函数 void add(int num) {...

一、Vector 整体结构与 allocator 定位1.1 Vector 核心数据成员构成std::vector 作为动态数组容器，其核心数据结构由三个指针（或类似指针的迭代器）构成，分别指向： 数据区起始位置（begin）：指向已分配内存块的起始地址 有效数据结束位置（end）：指向当前已存储元素的下一个位置 内存块结束位置（capacity_end）：指向已分配内存块的末尾位置 1.2 allocator 在 Vector 中的核心定位std::allocator 作为 Vector 的内存分配器组件，承担以下核心职责： 提供类型安全的内存分配 / 释放接口 解耦容器逻辑与底层内存管理实现 实现元素构造与内存分配的分离操作 支持自定义内存分配策略的扩展接口 二、std::allocator 核心接口与内存分配流程2.1 allocator 核心成员函数 allocate(size_t n)：分配能够存储 n 个元素的未初始化内存块，返回指向内存块起始位置的指针，内存大小为 n * sizeof (T) deallocate(T p, size_t...

一、核心概念辨析在开始代码实现前，需先明确三个核心概念的区别： 概念 定义 典型示例 可调用实体 (Callable Entity) 所有可以通过()语法调用的对象或表达式的统称 函数指针、lambda 表达式、仿函数、bind返回对象 函数对象 (Function Object) 具有operator()成员函数的类实例（仿函数） 自定义struct Add { int operator()(int a, int b); } 可调用对象 (Callable Object) 除函数指针外的可调用实体，强调 "对象" 属性 lambda 表达式、std::bind返回值、std::mem_fn返回值 二、完整代码实现以下代码基于 C++11...

103. Binary Tree Zigzag Level Order Traversal Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between). Example 1: 12Input: root = [3,9,20,null,null,15,7]Output: [[3],[20,9],[15,7]] Example 2: 12Input: root = [1]Output: [[1]] Example 3: 12Input: root = []Output: [] 题目大意给定一棵二叉树的根节点，返回其节点值的锯齿形层序遍历。即：第一层从左到右，第二层从右到左，第三层再从左到右，以此类推，交替进行。 例如： 输入 root =...

99. Recover Binary Search TreeYou are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure. Example 1: 123Input: root = [1,3,null,null,2]Output: [3,1,null,null,2]Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid. Example 2: 123Input: root = [3,1,4,null,null,2]Output: [2,1,4,null,null,3]Explanation: 2 cannot be in the right...

98. Validate Binary Search TreeGiven the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: The left subtree of a node contains only nodes with keys strictly less than the node's key. The right subtree of a node contains only nodes with keys strictly greater than the node's key. Both the left and right subtrees must also be binary search trees. Example 1: 12Input: root = [2,1,3]Output: true Example 2: 123Input: root =...

引言在传统的 C++...

一、文件读取核心概念与基础流程1.1 文件操作的三要素文件读取本质是 "数据在外部存储与内存间的传输过程"，需关注三个核心要素： 流对象：C++ 标准库通过std::ifstream（输入文件流）提供文件读取接口，是连接程序与外部文件的桥梁 流状态：通过good()/eof()/fail()/bad()四个状态标志判断操作有效性 数据缓冲区：操作系统与标准库均会维护缓冲区，减少磁盘 IO 次数（默认缓冲区大小通常为 4KB 或 8KB） 1.2 基础文件读取流程（标准范式）所有文件读取操作都遵循 "打开 - 读取 - 关闭" 的核心流程，标准实现代码如下： 123456789101112131415161718192021222324252627282930313233343536373839#include <fstream>#include <iostream>#include <string>int main() { // 1....

一、std::function —— 可调用对象的 "万能容器"1.1 概念解析：什么是 std::function？std::function 是 C++11 标准库 头文件中引入的通用可调用对象封装器，其核心作用是将各种不同类型的可调用实体（函数指针、成员函数指针、lambda 表达式、函数对象）统一到一个类型安全的容器中。 可以将其类比为 "函数的通用接口转换器"—— 无论原始可调用对象的类型如何，只要签名（返回值类型 + 参数类型列表）匹配，就能被 std::function 封装并统一调用。 1.2 实现原理：类型擦除（Type Erasure）std::function 本质是通过类型擦除技术实现的多态封装，核心流程如下： 定义一个抽象基类（如 function_base），包含纯虚函数 operator()（对应目标签名）和析构函数； 为每个具体的可调用对象类型，实现一个模板派生类（如 function_impl），继承自 function_base，并在 operator()...

一、工具链安装（环境准备阶段）代码覆盖率分析依赖 lcov（数据处理）、gcov（数据生成）、genhtml（报告可视化）三款核心工具，需根据操作系统选择对应安装方式。 1.1 Debian/Ubuntu 系统通过 apt 包管理器一键安装，命令如下： 1sudo apt update && sudo apt install -y lcov gcov genhtml lcov：负责收集、过滤、合并覆盖率原始数据 gcov：编译器内置组件（GCC 默认自带，Clang 需确保版本 ≥9.0） genhtml：将 lcov 数据转换为带代码标注的 HTML 报告 1.2 工具版本验证安装完成后需确认工具可用性与版本兼容性，避免因版本过低导致功能异常： 1234# 验证 lcov 版本（需 ≥1.16，支持现代 CMake 路径映射）lcov --version# 验证编译器覆盖率组件（GCC ≥7.0，Clang ≥9.0）gcov --version 二、CMake 配置（编译配置阶段）在项目根目录的 CMakeLists.txt...

导言在软件开发过程中，代码覆盖率是衡量测试质量的关键指标之一。它能够帮助开发和测试团队识别未被测试覆盖的代码区域，从而提升软件质量和稳定性。Lcov（Linux Test Project Coverage Tool）作为一款强大的代码覆盖率分析工具，基于 GCC 的覆盖测试功能，能够生成直观的 HTML 报告，广泛应用于 Linux 环境下的软件开发流程。本文将从基础概念入手，带您逐步掌握 Lcov 的安装、配置、使用及数据分析，轻松入门代码覆盖率分析。 一、Lcov 基础概念：你需要了解的核心术语在使用 Lcov 之前，首先需要理解代码覆盖率的基本概念，这将帮助你更好地解读 Lcov 生成的报告。 术语 定义 作用 代码覆盖率（Code Coverage） 衡量测试用例执行时覆盖代码比例的指标，反映测试的充分性 评估测试质量，识别未测试代码 行覆盖（Line Coverage） 被测试执行过的代码行数占总代码行数的比例 最基础的覆盖率指标，直观反映代码执行情况 分支覆盖（Branch Coverage） 被测试执行过的代码分支（如...

96. Unique Binary Search TreesGiven an integer n, return *the number of structurally unique **BST'*s (binary search trees) which has exactly n nodes of unique values from 1 to n. Example 1: 12Input: n = 3Output: 5 Example 2: 12Input: n = 1Output: 1 题目大意给定一个整数 n，计算由 1 到 n 为节点所组成的结构独特的二叉搜索树（BST）的数量。 例如： 输入 n = 3，存在 5 种结构独特的 BST，返回 5； 输入 n = 1，只有 1 种 BST，返回 1。 解题思路计算独特 BST 的数量可以通过动态规划（DP） 实现，核心思路基于以下观察： 若选择 i 作为根节点，则左子树由 1~i-1 构成，右子树由 i+1~n 构成； 左子树的独特结构数量为 dp[i-1]，右子树的独特结构数量为...

95. Unique Binary Search Trees IIGiven an integer n, return *all the structurally unique **BST'*s (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order. Example 1: 12Input: n = 3Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]] Example 2: 12Input: n = 1Output: [[1]] 题目大意给定一个整数 n，生成所有由 1 到 n 为节点所组成的结构独特的二叉搜索树（BST）。返回这些二叉搜索树的根节点列表。 二叉搜索树的特性是：对于任意节点，其左子树中的所有节点值都小于该节点值，右子树中的所有节点值都大于该节点值。 例如： 输入 n =...

112. Path SumGiven the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum. A leaf is a node with no children. Example 1: 123Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22Output: trueExplanation: The root-to-leaf path with the target sum is shown. Example 2: 123456Input: root = [1,2,3], targetSum = 5Output: falseExplanation: There are two root-to-leaf...

导言在掌握 CMake 基础用法后，本文将通过一个完整的多文件计算项目案例，深入讲解 CMake 在实际开发中的应用。该案例包含加减乘除四个运算模块，通过 CMake 实现自动化构建，同时覆盖源文件搜索、头文件路径配置、变量使用等核心技巧，帮助你将 CMake 知识落地到实际项目中。 一、项目整体概览1.1 项目功能该项目实现了整数的加减乘除基本运算，通过main.cpp中的test()函数调用各运算模块，最终在控制台输出计算结果。项目结构清晰，将不同运算逻辑拆分到独立的源文件和头文件中，符合模块化开发思想。 1.2 完整文件结构1234567891011calc_project/├── add.cpp # 加法运算实现├── add.h # 加法运算声明├── CMakeLists.txt # CMake配置文件├── divi.cpp # 除法运算实现├── divi.h # 除法运算声明├── main.cpp # 主程序（测试入口）├── mult.cpp # 乘法运算实现├──...