Tag: 数据结构
组合数学入门（2）：卡特兰数 卡特兰数是组合数学中最重要的数列之一。它们出现在许多表面上看起来完全不同的计数问题中，但实际上这些问题都具有相同的内在结构：平衡性、递归性以及“不交叉”约束。 在本文中，我们将介绍卡特兰数/Catalan，展示几个重要公式，并解释一些经典应用场景，特别是路径不能越过对角线的网格行走问题。 什么是卡特兰数？ 卡特兰数列如下： 第 n 个卡特兰数的一般公式为： 一个等价形式为： 这两个公式完全等价，在组合数学中都经常出现。 为什么卡特兰数很重要 卡特兰数用于计数许多具有递归结构或平衡结构的问题。它们通常出现在以下情形中： 对象必须以平衡方式构造， 路径必须保持在某个边界之内， 配对之间不能交叉， 结构可以被拆分为独立的左右部分。 因此，它们广泛出现在括号、树、网格、多边形以及栈操作等问题中。 一些重要的卡特兰公式 闭式公式 差分等价形式 递推公式 这个递推公式非常重要。它说明：如果一个规模为 n 的结构可以拆分为左侧大小为 i、右侧大小为 n-1-i 的两个部分，那么总数就是对所有可能拆分方式求和。 生成函数 渐近增长 …
Python 基础排序算法：基数排序详解与示例 Python Radix Sort 教程：整数、负数和浮点数排序 Python 数字排序指南：从整数到浮点的基数排序实现 高效排序算法讲解：Python 中的基数排序应用 Python 排序算法全解析：Radix Sort 的用法与实例 Python 基数排序简介 基数排序是一种非比较型排序算法，它通过按位对数字进行排序来完成排序。与直接比较整个数字（如快速排序或归并排序）不同，基数排序将元素根据其数字或字符分配到“桶”中，然后逐位处理。 对于整数，基数排序通常从最低有效位（LSD）到最高有效位（MSD）进行排序。这样可以保证稳定性，在处理完所有位后得到有序数组。 — 基数排序的工作原理 找到数组中的最大值，以确定需要处理的位数。 对每一位（个位、十位、百位等）使用稳定排序（如计数排序）。 重复此过程直到处理完所有位。 示例：对数组 进行排序： 按个位排序 → 按十位排序 → …
有序数据结构在编程中（尤其是算法竞赛和竞技编程）非常实用。在 Python 中，主要由 Sorted Containers 库提供三种有序数据结构：SortedDict、SortedSet 和 SortedList。 深入理解 Python 有序数据结构：从内置到 SortedContainers Python 有序数据结构完整指南 Python 中的有序列表、字典与集合实战解析 带你玩转 Python SortedContainers 与内置排序结构 Python 开发者必读：SortedContainers 与内置数据结构对比 Python 有序数据结构教程 排序是编程中最常见的操作之一。Python 提供了多种方式来维护有序数据，从内置的列表、集合、堆，到第三方库 sortedcontainers。 本教程将介绍 …
操作给定的二叉树, 将其变换为源二叉树的镜像. 反转给定的二叉树 输入描述: 二叉树的镜像定义: 源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 / \ / \ …
题意: 给出一个数组, 求第三大的数字是多少, 重复的数字并不算在内, 比如 第3大的数字是1 而不是 2. Using std::set set 是集合, 是有序的(从小到大), 集合中不包含重复的元素, 所以我们可以遍历数组并把数字添加到集合中. 在这过程中, 如果集合大小大于三个, 就把最小的元素删除. 我们不能直接按照索引的访问集合中的元素, 但是我们可以用迭代器 rbegin() 和 begin() 来访问集合中最大和最小的元素. class Solution { public: int …
这题难度中等, 原因就是在实现的时候细节很多, 不容易一次性搞对. 还好这两个列表表示的整数是反过来的, 所以实现上可以边遍历边相加, 只需要在累加每一位的时候记得记住进位即可. C++单向列表定义如下: struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; 当然, 还有更笨的方法, 就是先把每个列表转换成数字, 然后想加再把结果换成列表. 我们需要创建一个dummy结点, 记住, 在函数返回的时候返回 dummy.next …
没事刷刷题能防止老年痴呆, 而且也能让你随时处于最佳状态, 随时都可以炒老板鱿鱼另谋高就. 题目: 设计一个堆栈(Stack)使 push, pop, 和取最小 min 操作时间复杂度都是 O(1). 这题的难点就是在于怎么样用O(1)常数时间复杂度来取得堆栈里的最小值. class MinStack { public: MinStack() { // write your code here } /* * @param number: An …
