Tag: 递归
组合数学入门（2）：卡特兰数 卡特兰数是组合数学中最重要的数列之一。它们出现在许多表面上看起来完全不同的计数问题中，但实际上这些问题都具有相同的内在结构：平衡性、递归性以及“不交叉”约束。 在本文中，我们将介绍卡特兰数/Catalan，展示几个重要公式，并解释一些经典应用场景，特别是路径不能越过对角线的网格行走问题。 什么是卡特兰数？ 卡特兰数列如下： 第 n 个卡特兰数的一般公式为： 一个等价形式为： 这两个公式完全等价，在组合数学中都经常出现。 为什么卡特兰数很重要 卡特兰数用于计数许多具有递归结构或平衡结构的问题。它们通常出现在以下情形中： 对象必须以平衡方式构造， 路径必须保持在某个边界之内， 配对之间不能交叉， 结构可以被拆分为独立的左右部分。 因此，它们广泛出现在括号、树、网格、多边形以及栈操作等问题中。 一些重要的卡特兰公式 闭式公式 差分等价形式 递推公式 这个递推公式非常重要。它说明：如果一个规模为 n 的结构可以拆分为左侧大小为 i、右侧大小为 n-1-i 的两个部分，那么总数就是对所有可能拆分方式求和。 生成函数 渐近增长 …
组合简介（组合数学入门） 视频：油管/Youtube | B站/小破站 | 微博视频 | 西瓜视频 | 微信视频号 | X/推特 | 小红书 | Facebook 组合计数是在顺序不重要时选择项目的方式。我们从一个简单的格子行走示例出发建立直觉，介绍二项式记号，推导公式，解释递推关系 ，并把所有内容联系到帕斯卡三角。 格子行走示例 — 从左下到右上路径 想象你只能向右（R）或向上（U）移动。要从左下走到需要三次向右和两次向上的点，每一条最短路径都是由五步组成的序列，其中包含三个 R 和两个 U。 每条有效路径只是从五个位置中选择两个放 U（其余为 R）。所以这样的路径数就是“从 5 …
数学中的迭代幂运算/重幂是什么？ 迭代幂运算（重幂）是数学中的一种运算，涉及到反复进行幂次运算。它是超运算序列的一部分，该序列延伸了加法、乘法和幂运算。在迭代幂运算中，一个数自乘多次，直到达到指定的次数。 一个数a迭代幂的高度n通常表示为：，也就是把n写在a的左上角，（也可以记作：a↑↑n）这表示a被迭代n次。 例如： （简单恒等式） （a自乘一次） （a的幂次为a自乘） ，依此类推。 在迭代幂运算的上下文中， 通常未定义或没有普遍共识。然而，一些数学惯例建议对于任何 ，，类似于在幂运算中对任何非零的 有 的情况。 迭代幂运算示例 让我们评估 （读作“2迭代到高度3”）： 因此 迭代幂/重幂运算的通用性质 非交换性：迭代幂运算不是交换的，这意味着 增长速度非常快：迭代幂运算增长非常快。即使是小数也会因为幂运算的快速增长而导致非常大的结果。 迭代幂运算/重幂在基础数学中较少见，但在某些高级数学领域中发挥作用，特别是在涉及极大数的领域，如大数理论和计算机科学中。 用 Python 计算迭代幂运算 以下是两个计算迭代幂运算的Python函数。第一个使用递归，第二个使用迭代。 在两个函数中，我们在开始时添加了对 n = 0 …
这题比较有意思, 拿来分享一下: 在二叉树中, 根节点在深度0处, 并且每个深度k节点的子节点在深度k + 1处. 如果二元树的两个节点具有相同的深度但具有不同的父节点, 则它们是堂/表兄弟. 我们给出了具有唯一值的二叉树的根, 以及树中两个不同节点的值x和y. 当且仅当对应于值x和y的节点是同类时, 才返回true. 例如: 1 2 3 2和3的父母是同一个, 所以不是表兄弟(妹) 1 2 3 4 5 4和5是, 因为来自不同的父母, 并且所以树的高度是一样的. 深度优先+递归 二叉树(或者图)的一些算法大多数都可以用深度优先DFS来实现, …
题意: 给定一个二分查找树 BST, Binary Search Tree, 查找指定的元素, 返回该节点开始的子树. 如果没找到就返回NULL. 给定 4 / \ 2 7 / \ 1 3 如果我们要查找 2, 则返回子树: 2 / \ 1 3 二叉树在C/C++中的定义 二叉树可以用结构体来定义, …
题意: 合并两个二叉树, 没有说不可以改变原来的二叉树. 合并的时候把结点求合. C/C++ 中二叉树的定义 在C或者C++中, 二叉树的定义可以很方便的用结构体来表征. 其中左右子树都是递归定义. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) …
题意: 给定一个字符串, 输出所有字符大小写都可以组成的字符串. 如: “ab1” 能成生 DFS 深度优先 – 递归 我们可以从字符串的开头递归的把当前字符给添加到最终的字符串中, 当当前字符是字母的时候, 就有两种可能了. 当到达字符串尾部的时候我们把当前字符串添加到结果数组中即可. class Solution { public: vector<string> letterCasePermutation(string S) { search("", S, 0, S.length() - 1); return …
