Puxuan's Blog

STL 的核心底层结构之一：红黑树 (RB Tree)。std::map、std::set、std::multimap、std::multiset 都是基于它实现的。我们来一步步构建出自己的 MyRBTree。 红黑树特性回顾红黑树是一种 自平衡二叉搜索树，满足以下条件： 每个节点是红色或黑色； 根节点是黑色； 叶子节点（NIL）是黑色； 如果一个节点是红的，那么它的两个子节点都是黑的； 从任意节点到其叶子节点的所有路径上，黑色节点数量相同。 这些规则保证树的高度在 O(log n)。 代码实现RBTreeNode & Iterator 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697// ===================// rbtree no...

在 C++ 的 STL（Standard Template Library，标准模板库） 中，queue 和 stack 都属于 容器适配器（Container Adapters），它们并不是独立的数据结构，而是基于其他底层容器（如 deque 或 list）封装出来的特定用途的数据结构。 两者的区别对比 特性 queue stack 数据访问模式 FIFO（先进先出） LIFO（后进先出） 插入位置 队尾（back） 栈顶（top） 删除位置 队首（front） 栈顶（top） 底层默认容器 deque deque 常用场景 BFS（广度优先搜索）、任务队列等 DFS（深度优先搜索）、函数调用栈等 queue（队列）queue 是先进先出（FIFO, First In First Out） 的数据结构。元素只能从队尾（back）插入，从队首（front）移出。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152...

题目描述(Medium) Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value. If target is not found in the array, return [-1, -1]. You must write an algorithm with O(log n) runtime complexity. Example 1: 12Input: nums = [5,7,7,8,8,10], target = 8Output: [3,4] Example 2: 12Input: nums = [5,7,7,8,8,10], target = 6Output: [-1,-1] Example 3: 12Input: nums = [], target = 0Output: [-1,-1] 思路1 二分查找代码1234567891011121314151617181920212223...

在 C++ STL（标准模板库）中，std::deque 是一种 双端队列（double-ended queue），它是一种支持在 序列两端高效插入和删除 的序列式容器。 一、deque 的基本概念 deque 是 “double-ended queue” 的缩写。它类似于 std::vector，但有一个关键区别： 特性 vector deque 随机访问 ✅ O(1) ✅ O(1) 在末尾插入/删除 ✅ O(1) ✅ O(1) 在开头插入/删除 ❌ O(n) ✅ O(1) 连续内存 ✅ ❌ （分段存储） 因此： 如果你只在尾部操作，用 vector； 如果你需要频繁在两端插入或删除，用 deque。 二、deque 的底层结构 deque 并不是像 vector 一样存放在一整块连续内存中，而是： 由一系列固定大小的内存块（buffer）组成，再由一个中央的“map（指针数组）”来管理这些块。 大致结构如下： [block1] → [block2] → [block3] → … ↑ ↑ | ...

题目描述[HARD] For an integer array nums, an inverse pair is a pair of integers [i, j] where 0 <= i < j < nums.length and nums[i] > nums[j]. Given two integers n and k, return the number of different arrays consisting of numbers from 1 to n such that there are exactly k inverse pairs. Since the answer can be huge, return it modulo 10^9 + 7. Example 1: 123Input: n = 3, k = 0Output: 1Explanation: Only the array [1,2,3] which consists of numbers from 1 to 3 has exactly 0 inverse pai...

记录自己在 LeetCode 上的刷题节奏、思路沉淀与反思，方便复盘和查缺补漏。 刷题目标 每周至少完成 5 道不同类型的题目，关注题型覆盖面而非刷题数量 优先补齐弱项（图论、动态规划、数据结构设计等） 输出简洁题解与时间 / 空间复杂度分析 2025 Week 1 题目 难度 题型 思路小结 复盘 链接 629 K Inverse Pairs Array Hard 动态规划 通过动态规划 ✅ 完成 https://leetcode.com/problems/k-inverse-pairs-array 34 irst and Last Position of Element in Sorted Array Medium 二分查找 通过二分查找 ✅ 完成 https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/ 46 Permutations Medium 回溯 通过回溯 ✅ 完成 https://leetcode.com/problem...

Gravity Falls[] 题目描述F. Gravity Falls time limit per test2 secondsmemory limit per test256 megabytes Farmer John has narrays a1,a2,…,an that may have different lengths. He will stack the arrays on top of each other, resulting in a grid with n rows. The arrays are left-aligned and can be stacked in any order he desires. Then, gravity will take place. Any cell that is not on the bottom row and does not have an element beneath it will fall down a row. This process will be repeated until there are...

Monocarp’s String

一个简单的算法模板库： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155#ifndef MY_ALGORITHM_H#define MY_ALGORITHM_H#include "my_iterator.h"#include "my_utility.h"namespace mystl&#...