HespethornのBlog

102. Binary Tree Level Order TraversalGiven the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level). Example 1: 12Input: root = [3,9,20,null,null,15,7]Output: [[3],[9,20],[15,7]] Example 2: 12Input: root = [1]Output: [[1]] Example 3: 12Input: root = []Output: [] 题目大意给定一棵二叉树的根节点 root，返回其节点值的层序遍历结果（即从左到右、逐层遍历）。结果需以二维数组形式呈现，每一层的节点值构成一个子数组（例如，第一层 [根节点]，第二层 [左子节点,...

一、概念C++ 的多态机制主要通过三个核心概念实现，它们在编译和运行时有着截然不同的处理方式： 概念 定义 绑定时机 核心特征 函数重载 同一作用域内，函数名相同但参数列表不同的函数 编译时 静态多态，基于参数列表区分 函数重写 派生类中重新定义基类中的虚函数，函数签名完全相同 运行时 动态多态，基于对象实际类型调用 函数隐藏 派生类中定义的函数遮蔽基类中同名函数，无论参数是否相同 编译时 名称遮蔽，基类函数被隐藏 注：函数签名包括函数名、参数类型和顺序，不包括返回值类型 二、函数重载解析函数重载是 C++ 实现静态多态的基础机制，允许在同一作用域内定义多个同名函数，通过参数列表的差异进行区分。 重载的实现原理编译器在编译阶段会对重载函数进行名称修饰（Name Mangling），根据函数名和参数列表生成唯一的内部名称，因此重载函数在底层实际上拥有不同的标识符。 重载示例代码123456789101112131415161718192021222324252627282930313233343536373839#include...

一、复制控制的核心概念与场景复制控制机制是C++中处理对象创建、复制和销毁的核心手段。在继承体系中，当派生类对象被复制时，需要特别关注以下关键点： 复制场景 拷贝构造函数调用：当用已存在的对象初始化新对象时 赋值操作符调用：当用一个对象赋值给另一个对象时 析构函数调用：当对象生命周期结束时 典型问题 浅拷贝导致的指针悬挂（dangling pointer） 资源泄漏（resource leak） 自赋值（self-assignment）引发的异常 二、派生类复制的构造函数调用链12345678910111213class Base {public: Base() { /* 基类构造 */ } Base(const Base& other) { /* 基类拷贝构造 */ } ~Base() { /* 基类析构 */ }};class Derived : public Base {public: Derived() : Base() {...

一、对象赋值的双向可行性分析1.1 基类到派生类的转换 隐式转换: 不允许直接赋值（如 Base b = d;） 显式转换: 需使用构造函数或类型转换运算符 123456789101112class Base {public: Base() {} explicit Base(int val) : data(val) {}private: int data;};class Derived : public Base {public: Derived(int val) : Base(val) {}}; 内存影响: 派生类对象包含基类数据成员，赋值操作不会改变大小，但会丢失派生类特有数据 1.2 派生类到基类的转换 隐式转换: 允许（如 Base b = d;） 显式转换: 可使用static_cast或构造函数 123Derived d;Base b = d; // 隐式转换Base& br =...

一、virtual 继承的核心作用在C++中，virtual关键字用于解决多重继承时的菱形继承问题。当多个派生类共享同一基类时，如果不使用虚继承，会导致基类对象被多次实例化，造成内存浪费和指针混淆。 1.1 问题场景考虑经典菱形继承结构： 12345678910111213141516class A {public: int a;};class B : virtual public A {public: int b;};class C : virtual public A {public: int c;};class D : public B, public C {}; 在这种情况下，D对象会包含两个A子对象（一个来自B，一个来自C），导致： 内存重复占用（每个A子对象占用相同内存空间） 指针访问歧义（需要明确使用B::a或C::a） 1.2...

一、关联容器的底层数据结构特性C++ 标准库中的map和set均属于关联容器，其底层实现基于红黑树（Red-Black Tree）—— 一种自平衡的二叉搜索树。这种数据结构具有以下核心特性： 有序性：元素按照键值的比较规则进行排序存储 自平衡性：通过特定的旋转和着色操作，保证树的高度始终保持在 O (log n) 级别 迭代效率：支持高效的顺序访问和范围查询 红黑树的平衡机制确保了所有基本操作（插入、删除、查找）都能在O(log n) 的时间复杂度内完成，这使得关联容器在需要频繁查找和有序遍历的场景中表现优异。 二、map 与 set 的存储机制差异虽然map和set共享相同的底层实现机制，但它们的存储方式存在本质区别： 特性 set map 存储内容 仅存储键（key） 存储键值对（key-value） 元素唯一性 键值唯一，不允许重复 键值唯一，不允许重复 访问方式 只能通过键访问元素 可通过键访问对应的值 模板参数 std::set<Key, Compare, Allocator> std::map<Key,...

一、核心数据结构：红黑树C++ 标准库中std::map的底层实现采用红黑树（Red-Black Tree），这是一种自平衡的二叉搜索树（BST）。红黑树通过特定的规则保证树的高度始终维持在 O (log n) 级别，从而确保各种操作的高效性。 1具体见前一篇 C++ 标准库中的 set 容器 二、map 容器的核心组件2.1 迭代器实现std::map的迭代器是双向迭代器，其实现本质上是红黑树节点的指针封装，并提供了遍历树的操作。 2.2 内存管理机制std::map通常使用内存池（memory pool）或分配器（allocator）管理节点内存，而非频繁调用new和delete： 采用 slab 分配策略，预先分配一批节点内存 节点释放时不直接归还给系统，而是放入空闲列表 下次分配时优先从空闲列表获取，减少系统调用开销 三、核心操作实现3.1...

一、set 容器的本质与底层数据结构C++ 标准库中的std::set是一种关联式容器，其核心特性是自动排序和唯一性。与序列式容器（如 vector、list）不同，set 中的元素是按照特定的排序规则进行存储的，这使得 set 具有高效的查找、插入和删除操作。 std::set的底层实现采用了红黑树（Red-Black Tree） 这一自平衡二叉搜索树数据结构。红黑树通过一系列规则保证了树的平衡性，从而确保了基本操作（插入、删除、查找）的时间复杂度均为 O (logN)，其中 N 为树中元素的数量。 在 C++ 标准库中，红黑树的实现通常被封装在_Rb_tree类模板中，而 set 则是该类模板的一个特化应用，专门用于存储键值对中的键（在 set 中，键和值是同一个概念） 二、红黑树的结构解析2.1 红黑树节点的构成红黑树的每个节点通常包含以下几个部分： 键（key）：即存储的元素值，用于节点间的比较 左孩子指针（left child）：指向当前节点的左子节点 右孩子指针（right...

20. Valid ParenthesesGiven a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Every close bracket has a corresponding open bracket of the same type. 题目大意给定一个只包含 '('、')'、'{'、'}'、'[' 和...

1047. Remove All Adjacent Duplicates In StringYou are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them. We repeatedly make duplicate removals on s until we no longer can. Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique. Example 1: 1234Input: s = "abbaca"Output: "ca"Explanation: For example, in...

155. Min StackDesign a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the MinStack class: MinStack() initializes the stack object. void push(int val) pushes the element val onto the stack. void pop() removes the element on the top of the stack. int top() gets the top element of the stack. int getMin() retrieves the minimum element in the stack. You must implement a solution with O(1) time complexity for each function. 题目大意设计一个支持...

一、pair 的模板定义与类型参数设计1.1 基本模板定义C++ 标准库中的std::pair是一个模板类，用于存储两个异构对象作为一个单元。其基本定义如下： 123456789101112namespace std { template <class T1, class T2> struct pair { typedef T1 first_type; typedef T2 second_type; T1 first; T2 second; // 构造函数及其他成员函数... };} 这个定义展示了pair的核心特征： 两个模板类型参数T1和T2，分别指定了两个成员的类型 公开的成员变量first和second，分别存储第一个和第二个元素 类型别名first_type和second_type，用于获取元素类型 1.2 类型推导机制在 C++11...

引言：字符串性能的关键挑战在 C++ 开发中，std::string作为最常用的容器之一，其性能直接影响整体程序效率。传统字符串实现采用动态内存分配策略，无论字符串长度如何，都需要在堆上分配空间，这会带来： 内存分配 / 释放的开销 缓存局部性不佳 小字符串场景下的效率低下 短字符串优化（Short String Optimization, SSO）正是为解决这些问题而生的关键技术，已成为现代 C++ 标准库（如 libstdc++、libc++）的标配实现策略。 一、SSO 的核心原理1.1 传统字符串实现的缺陷传统std::string（C++11 之前）通常采用 "胖指针" 结构： 123456// 传统字符串实现（概念模型）struct String { char* data; // 指向堆内存的指针 size_t length; // 字符串长度 size_t capacity; // 已分配容量}; 这种结构对短字符串极不友好，例如存储 "hello"...

一、写时复制核心概念写时复制 (简称 COW) 是一种资源管理优化技术，其核心思想是：当多个对象需要共享同一资源时，直到其中一个对象需要修改资源前，都不需要真正复制资源，仅在修改时才创建资源的私有副本。 这种机制通过延迟复制操作，减少了不必要的内存分配和数据拷贝，从而提高程序性能，尤其适用于： 频繁复制但很少修改的场景 内存资源宝贵的环境 大型数据结构的共享访问 二、写时复制实现三要素1. 共享数据存储需要一个独立的共享数据结构，存储实际的数据内容。 1234567template <typename T>struct SharedData { T* data; // 实际数据指针 size_t size; // 数据大小 size_t ref_count; // 引用计数 // 其他元数据...}; 2. 引用计数机制通过引用计数跟踪当前有多少对象共享该资源： 当新对象共享资源时，引用计数 + 1 当对象销毁或不再共享时，引用计数 - 1 当引用计数为 0...

227. Basic Calculator IIGiven a string s which represents an expression, evaluate this expression and return its value. The integer division should truncate toward zero. You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1]. Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval(). 题目大意给定一个字符串 s 表示一个算术表达式，要求计算该表达式的值并返回。表达式仅包含非负整数、+、-、*、/...

150. Evaluate Reverse Polish NotationYou are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation. Evaluate the expression. Return an integer that represents the value of the expression. Note that: The valid operators are '+', '-', '*', and '/'. Each operand may be an integer or another expression. The division between two integers always truncates toward zero. There will not be any division by zero. The input...

71. Simplify PathYou are given an absolute path for a Unix-style file system, which always begins with a slash '/'. Your task is to transform this absolute path into its simplified canonical path. The rules of a Unix-style file system are as follows: A single period '.' represents the current directory. A double period '..' represents the previous/parent directory. Multiple consecutive slashes such as '//' and '///' are treated as a single slash...

引言在 C++ 编程中，->和*运算符最初设计用于指针操作。然而，通过运算符重载机制，我们可以让自定义类型也支持这些操作，从而实现类似指针的行为，同时添加额外功能。 一、为什么需要重载->和*运算符1. 扩展指针功能的核心需求原生指针 (T*) 虽然简洁高效，但存在明显局限： 无法自动管理资源生命周期 缺乏访问控制机制 不支持额外的调试信息 不能实现代理或间接访问模式 通过重载->和*，我们可以创建 "智能指针" 或 "代理对象"，在保持指针操作语法的同时，添加所需功能。 2. 关键应用场景资源自动管理智能指针通过运算符重载实现自动内存管理： 1234567891011121314151617181920// 简化的shared_ptr实现思路template<typename T>class SharedPtr {private: T* ptr; int* ref_count; void release() { if...

一、什么是 Pimpl 模式？Pimpl 模式（Pointer to Implementation）通过私有指针隔离类的接口与实现，是 C++ 封装原则的高级应用。其核心目标为：隐藏实现细节、提升编译效率、保障二进制兼容及简化接口。 二、Pimpl 模式的实现机制传统类设计将接口与实现混在头文件，Pimpl 模式则通过以下方式分离： 头文件声明含私有指针的公共接口类 源文件定义包含实现细节的实现类 接口类借指针间接访问实现类成员 传统设计 Pimpl 模式设计 接口与实现一体 接口类仅含指针 头文件暴露所有细节 头文件隐藏实现 实现变更需重编译所有依赖 仅需重编译源文件 三、Pimpl 模式的代码实现3.1 头文件（widget.h）123456789101112131415161718192021222324252627#include <memory>#include <string>// Widget 类是对外暴露的公共接口类class Widget {public: // 构造函数，用于创建...

导言单例模式的自动释放是解决资源泄漏问题的关键，不同场景下可以选择不同的实现方式。下面详细解析四种典型的自动释放机制，包括其实现原理、代码示例及适用场景。 一、方式一：利用栈对象的生命周期进行管理实现原理利用栈对象 "出作用域自动析构" 的特性，将单例指针存储在栈对象中，当栈对象被销毁时，自动释放单例资源。 代码实现12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include <iostream>class Singleton {private: // 私有构造函数 Singleton() { std::cout << "Singleton 构造函数被调用" << std::endl; } // 私有析构函数 ~Singleton() { ...