HespethornのBlog

222. Count Complete Tree NodesGiven the root of a complete binary tree, return the number of the nodes in the tree. According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h. Design an algorithm that runs in less than O(n) time complexity. Example 1: 12Input: root = [1,2,3,4,5,6]Output: 6 Example 2: 12Input: root...

101. Symmetric TreeGiven the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center). Example 1: 12Input: root = [1,2,2,3,4,4,3]Output: true Example 2: 12Input: root = [1,2,2,null,3,null,3]Output: false 题目大意给定一棵二叉树的根节点 root，判断该二叉树是否是对称的（即围绕中心轴镜像对称）。 例如： 输入二叉树 [1,2,2,3,4,4,3]，其左子树与右子树成镜像，故返回 true； 输入二叉树 [1,2,2,null,3,null,3]，左子树与右子树不镜像，故返回 false。 解题思路判断二叉树是否对称的核心是比较左子树与右子树是否成镜像，即： 左子树的左节点需与右子树的右节点值相等； 左子树的右节点需与右子树的左节点值相等。 1....

226. Invert Binary TreeGiven the root of a binary tree, invert the tree, and return its root. Example 1: 12Input: root = [4,2,7,1,3,6,9]Output: [4,7,2,9,6,3,1] Example 2: 12Input: root = [2,1,3]Output: [2,3,1] Example 3: 12Input: root = []Output: [] 题目大意给定一棵二叉树的根节点 root，翻转这棵二叉树（即交换每个节点的左子树和右子树），并返回翻转后的根节点。 例如： 输入二叉树 [4,2,7,1,3,6,9]，翻转后每个节点的左右子树互换，输出为 [4,7,2,9,6,3,1]。 解题思路翻转二叉树的核心是交换每个节点的左子节点和右子节点，可以通过递归或迭代两种方式实现： 1....

一、remove_if 算法原理与实现细节1.1 核心功能与特性remove_if是 C++ 标准库中用于条件过滤的算法，它能移除容器中满足特定条件的元素。需要特别注意的是： 执行的是逻辑删除而非物理删除 不会改变容器的大小（size） 返回指向新的逻辑末尾的迭代器 1.2 底层实现逻辑123456789101112131415// 模拟标准库remove_if实现逻辑template<class ForwardIt, class UnaryPredicate>ForwardIt remove_if(ForwardIt first, ForwardIt last, UnaryPredicate p) { // 跳过不符合删除条件的元素 first = std::find_if(first, last, p); if (first != last) { // 用后面的元素覆盖需要删除的元素 for (ForwardIt i = std::next(first); i != last; ++i)...

一、基础概念与设计原理在 C++ 开发中，std::unique_ptr与std::vector组合是动态内存管理的常用方案，既灵活又安全。unique_ptr独占所有权的特性，使其与容器存储场景天然适配，容器全权负责指针生命周期。 二、完整实现示例1. 定义基础类定义Point类，包含虚析构函数以支持多态： 123456789101112131415161718#include <iostream>#include <vector>#include <memory> class Point {private: int x_; int y_;public: Point(int x = 0, int y = 0) : x_(x), y_(y) { std::cout << "Point构造: (" << x_ << "," << y_ << ")" <<...

导言LRU（Least Recently Used，最近最少使用）算法是一种常用的缓存淘汰策略，其核心思想是：当缓存空间满时，优先淘汰最近最少使用的元素。在 C++ 中，结合list容器的splice()函数可以高效实现 LRU 算法，因为splice()能以 O (1) 的时间复杂度调整元素位置，非常适合维护元素的访问顺序。 一、LRU 算法的核心需求实现 LRU 算法需要支持以下操作： 访问元素：如果元素存在于缓存中，将其标记为 “最近使用”；如果不存在，需要插入新元素。 插入元素：当缓存未满时直接插入；当缓存已满时，删除 “最近最少使用” 的元素后再插入新元素。 维护顺序：始终保持元素的排列顺序与访问时间相关（最近使用的在前端，最少使用的在末端）。 二、数据结构设计为了高效实现 LRU，我们需要两种数据结构配合： list容器：用于存储缓存元素，最近使用的元素放在链表头部，最少使用的放在尾部。 unordered_map容器：用于快速查找元素在list中的位置（存储元素键与list迭代器的映射），支持 O (1)...

104. Maximum Depth of Binary TreeGiven the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Example 1: 12Input: root = [3,9,20,null,null,15,7]Output: 3 Example 2: 12Input: root = [1,null,2]Output: 2 题目大意给定一棵二叉树的根节点 root，返回该二叉树的最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数量。 例如： 输入二叉树 [3,9,20,null,null,15,7]，其最大深度为 3（路径：3 → 20 → 15 或 3 → 20 → 7，均包含 3...

116. Populating Next Right Pointers in Each NodeYou are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition: 123456struct Node { int val; Node *left; Node *right; Node *next;} Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL. Example 1: 123Input: root =...

515. Find Largest Value in Each Tree RowGiven the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed). Example 1: 12Input: root = [1,3,2,5,3,null,9]Output: [1,3,9] Example 2: 12Input: root = [1,2,3]Output: [1,3] 题目大意给定一棵二叉树的根节点 root，返回一个数组，其中每个元素是二叉树对应行（从 0 开始索引）中的最大值。 例如： 输入二叉树 [1,3,2,5,3,null,9]，第 0 行最大值为 1，第 1 行最大值为 3，第 2 行最大值为 9，因此返回...

一、sort ()：容器元素的排序利器sort()是 C++ 标准库中用于排序的函数，其核心功能是对容器中的元素进行升序或自定义规则排序。不过，并非所有容器都支持sort()，它仅适用于随机访问迭代器的容器（如vector、deque、array等），而像list、set等容器则有自己的排序方式。 1. 基本用法sort()的函数原型如下（以vector为例）： 1234567#include <algorithm> // 需包含算法库// 升序排序（默认）sort(begin_iterator, end_iterator);// 自定义排序规则sort(begin_iterator, end_iterator, comparator); 其中，begin_iterator和end_iterator指定排序的范围（左闭右开），comparator是一个自定义的比较函数或 lambda 表达式，用于定义排序规则。 2. 实战示例 默认升序排序： 12345678910111213#include <vector>#include...

一、erase 方法的功能定位vector 的 erase 方法是 STL 中用于从容器中移除元素的核心函数，其主要功能是： 从 vector 中删除单个元素或一段连续范围内的元素 调整容器大小以反映元素数量的变化 维护剩余元素的连续性和内存布局 返回一个迭代器，指向被删除元素的下一个元素 erase 方法是破坏性操作，会改变容器的状态和内部布局，同时可能影响现有迭代器的有效性。 二、迭代器参数的语法特征与使用场景vector 的 erase 方法有两种重载形式，分别适用于不同的删除场景： 2.1 单个元素删除1iterator erase(iterator position); 参数：指向要删除元素的迭代器 返回值：指向被删除元素下一个元素的有效迭代器 使用场景：已知要删除元素的确切位置时 2.2 范围元素删除1iterator erase(iterator first, iterator...

一、内部实现机制 vector：基于动态数组实现，元素存储在连续的内存空间中，通过单一指针管理内存块 list：基于双向链表实现，每个元素包含数据域和两个指针域（前驱和后继），元素分散存储在内存中 二、核心性能差异 操作 vector list 随机访问（按索引访问） O (1)，高效支持 O (n)，不支持直接索引访问 头部插入 / 删除 O (n)，需移动所有元素 O (1)，只需调整指针 尾部插入 / 删除 O (1)（平均） O(1) 中间插入 / 删除 O (n)，需移动插入点后的所有元素 O (1)，只需调整附近元素的指针 内存分配 可能需要整体扩容（复制所有元素） 每次插入新元素单独分配内存 迭代器类型 随机访问迭代器 双向迭代器 缓存利用率 高（连续内存，缓存局部性好） 低（元素分散，容易缓存失效） 三、功能差异 vector： 支持[]运算符和at()方法进行随机访问 提供reserve()方法预分配内存 元素在内存中连续存储，可直接获取数据指针（data()方法） 适合与 C API...

导言deque（双端队列）是另一种常用的序列容器，与 vector 相比，它在两端的插入删除操作上有独特优势。以下是 deque 高效操作的策略和特性： 一、deque 的特性与优势deque 与 vector 的核心区别在于内存布局： deque 采用分段连续内存结构，由多个固定大小的内存块组成 支持 O (1) 时间复杂度的两端插入和删除操作 不需要像 vector 那样在扩容时复制所有元素 二、高效插入元素 两端插入效率最高deque 在头部和尾部的插入操作都是 O (1) 时间复杂度，这是它相比 vector 的主要优势： 123456789std::deque<int> dq;// 尾部插入dq.push_back(10);dq.emplace_back(20); // 更高效，直接构造// 头部插入（vector不擅长的操作）dq.push_front(5);dq.emplace_front(3); // 直接在头部构造 中间插入的特点与 vector 类似，deque 的中间插入仍需移动元素，时间复杂度为 O (n)，但实际性能可能略优于...

一、vector 容器概述vector 是 C++ 标准模板库（STL）中 最用的序列容器之一，它基于动态数组实现，能够存储同类型元素并支持高效的随机访问。自 C++98 标准首次引入以来，vector 凭借其灵活的内存管理和优秀的性能表现，成为了 C++ 开发者处理动态数据集合的首选工具。 与静态数组相比，vector 的核心优势在于自动内存管理—— 它会根据元素数量动态调整内部存储空间，无需开发者手动分配和释放内存。这种特性使得 vector 在处理元素数量不确定的场景时尤为便捷，同时保持了数组的随机访问效率。 vector 的核心特性可以概括为： 连续的内存空间分配，支持随机访问 动态扩容机制，自动管理内存 尾部插入 / 删除操作效率高 中间插入 / 删除操作可能导致大量元素移动 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include...

一、智能指针循环引用问题的处理1.1 循环引用的产生与危害循环引用是shared_ptr使用过程中最常见的问题之一，当两个或多个shared_ptr形成引用闭环时就会产生循环引用。这种情况下，每个shared_ptr的引用计数都无法降到 0，导致其所管理的对象无法被释放，最终造成内存泄漏。 典型的循环引用场景： 双向链表节点相互引用 父对象持有子对象的shared_ptr，子对象同时持有父对象的shared_ptr 观察者模式中，观察者与被观察者相互持有shared_ptr 1.2 循环引用示例12345678910111213141516171819202122232425262728293031#include <memory>#include <iostream>class B; // 前向声明class A {public: std::shared_ptr<B> b_ptr; A() { std::cout << "A constructed\n";...

一、引言引入智能指针（Smart Pointer）是 C++ 为解决动态内存管理问题而设计的工具，其核心目的是自动管理动态分配的内存（堆内存），避免手动管理内存时常见的错误（如内存泄漏、野指针、二次释放等），提高代码的安全性和健壮性。 二、智能指针基础2.1 具体解决的问题手动使用new分配内存和delete释放内存时，容易出现以下问题，而智能指针通过自动化机制解决了这些问题： 内存泄漏 手动管理时，若忘记调用delete释放已分配的内存，或因异常、分支跳转等导致delete未执行，会造成内存泄漏（内存被占用且无法回收）。 智能指针通过RAII（资源获取即初始化）...

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980#ifndef SMART_PTR_H#define SMART_PTR_H// 基于RAII的智能指针实现，模拟unique_ptrtemplate <typename T>class SmartPtr {private: T* m_ptr; // 指向管理的资源public: // 构造函数：获取资源 explicit SmartPtr(T* ptr = nullptr) : m_ptr(ptr) {} // 析构函数：释放资源（RAII核心） ~SmartPtr() { delete m_ptr; // 自动释放资源 m_ptr = nullptr; ...

429. N-ary Tree Level Order TraversalGiven an n-ary tree, return the level order traversal of its nodes' values. Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples). Example 1: 12Input: root = [1,null,3,2,4,null,5,6]Output: [[1],[3,2,4],[5,6]] Example 2: 12Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]Output:...

637. Average of Levels in Binary TreeGiven the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted. Example 1: 1234Input: root = [3,9,20,null,null,15,7]Output: [3.00000,14.50000,11.00000]Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.Hence return [3, 14.5, 11]. Example 2: 12Input: root = [3,9,20,15,7]Output:...

199. Binary Tree Right Side ViewGiven the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom. Example 1: Input: root = [1,2,3,null,5,null,4] Output: [1,3,4] Explanation: Example 2: Input: root = [1,2,3,4,null,null,null,5] Output: [1,3,4,5] Explanation: Example 3: Input: root = [1,null,3] Output: [1,3] Example 4: Input: root = [] Output: [] 题目大意给定一棵二叉树的根节点...