| java数据结构与算法刷题目录（剑指Offer、LeetCode、ACM）-----主目录-----持续更新(进不去说明我没写完)：https://blog.csdn.net/grd_java/article/details/123063846 |
|---|
文章目录
分治回溯+记忆化搜索
卡特兰数，例如对于n个进栈元素，有多少种出栈顺序，就可以用卡特兰数来求，公式为 1 n + 1 C n m = 1 n + 1 A n m A m m \dfrac{1}{n+1}C_{n}^m =\dfrac{1}{n+1} \dfrac{A_{n}^m}{A_{m}^m} n+11Cnm=n+11AmmAnm,例如n = 3时，有 1 4 ∗ 6 ∗ 5 ∗ 4 3 ∗ 2 ∗ 1 = 5 \dfrac{1}{4}*\dfrac{6*5*4}{3*2*1} = 5 41∗3∗2∗16∗5∗4=5种出栈顺序
- A n m = A_{n}^m = Anm=从n开始从大往小，m个数相乘
- C n m = A n m A m m C_{n}^m = \dfrac{A_{n}^m}{A_{m}^m} Cnm=AmmAnm
- 例如 C 2 n n = A 2 n m A n n C_{2n}^n = \dfrac{A_{2n}^m}{A_{n}^n} C2nn=AnnA2nm
- 例如n = 3时， C 2 n n = C 6 3 = A 6 3 A 3 3 = 6 ∗ 5 ∗ 4 3 ∗ 2 ∗ 1 = 20 C_{2n}^n = C_{6}^3 = \dfrac{A_{6}^3}{A_{3}^3} = \dfrac{6*5*4}{3*2*1} = 20 C2nn=C63=A33A63=3∗2∗16∗5∗4=20
| 解题思路：时间复杂度O( n ∗ n 的卡特兰数 n*n的卡特兰数 n∗n的卡特兰数)，对每一个结点作为根结点的枚举，都需要n的卡特兰数的时间复杂度，因为它的过程和不同出栈顺序一样。空间复杂度O( n ∗ n 的卡特兰数 n*n的卡特兰数 n∗n的卡特兰数) |
|---|
- 先通过分治来划分回溯区域，例如1,2,3, 先让1来分治，然后1和2来分治，然后2和3来分治，最后1,2,3来分治
- 分治划分区域后，开始回溯枚举，枚举用不同数字来当根结点的划分方式
并以当前根结点为中心，左右划分两个区域继续分治
- 因为是升序需要，当我们选择一个数字作为根结点，其左边比它小的都在左子树，比它大的都在右子树。具体可以参考96题，因为这道题是96题的衍生题
标签：right,TreeNode,dfrac,分治,LeetCode95,II,java,卡特兰,left
From： https://blog.csdn.net/grd_java/article/details/137084792
相关文章
|
|---|