关于前端:前端算法关于整理思路的一点启发

引言

最近在换工作，尽管曾经是一个大叔级程序员了，然而三件套还是少不了：更新简历、刷 Boss、刷面试题。往年行情有点寒气逼人，前端人也要开始卷算法了，目前看，难度次要以简略为主，多数中等（大厂多一些）。

我的状况是，三年之前刷过三十来道 leetcode，当初看来数量不够，这次必须再捡起来刷一刷。其中有一道二叉树 medium 题目，题目不算难，然而我感觉对我启发挺大，特地是几轮剖析过程，本文就分享一下我整顿思路的过程，心愿对大家也有所启发。

第一轮

第一轮次要是看题目：

给你一个整数 n，求恰由 n 个节点组成且节点值从 1 到 n 互不雷同的 二叉搜寻树 有多少种？返回满足题意的二叉搜寻树的种数。

第一件事就是题目的浏览了解。我刷题不多，工夫一长，二叉搜寻树 这个概念都有些含糊了，就先从查概念解释开始：二叉搜寻树就是左子树比根小，右子树比根大的二叉树 。再联合示例，就很容易能明确题目意思： 给定数字序列 1-n 能排出多少种二叉搜寻树。

而后就是剖析如何解题了，也就是找到计算排列数量的方法，我很快联想到数学中的排列组合了，排列组合是能够转化成公式的，比方 10 个小学生排队，有多少排法，就能够转化成公式 10 的阶乘。

然而二叉搜寻树的排列又不太一样，根节点有 n 种，但再往下有几种排列，怎么计算？有点没脉络了，思考了几分钟，找不到法则。有点想翻答案了…

第二轮

第二轮就是要害的思路整顿，第一轮遇到困难，差点就去翻答案了，而后被本人摁住了，沉下心来再次整顿思路。

思考的方向就是如何从题目细节，找到排列的法则，第一个想到的就是二叉搜寻树，好好来捋一下它的概念：右边比根小，左边比根大，这不就和有序数组相似么，选定一个数组元素作为根之后，右边的数字就是左子树，左边的就是右子树，其实用数组示意二叉树，在数据结构中有，工夫太久遗记了。

举个例子（有时候用实例去想，更容易了解），给定 n=5，用 2 作为树根，那就左子树就是 1，右子树就是 3-5，1 的排列就 1 种。那右子树的 3-5 呢，怎么排列？如同又卡住了。

要害突破口来了，既然是有序数组，3-5 的排列是否和 1-3 一样？对立减去 2，并不影响排序的程序，所以排序的数量就是一样的！

那么，不论数字是多少，咱们都能够形象成是 1-n 的排列！咱们就能够用迭代去解决问题。

形象之后就是：给定 1-n 的数字序列，入选定一个数字 k(1≤k≤n) 作为根时，f(k) = f(k-1) * f(n-k) . f(1), f(2) 能够间接给出。

第一版代码来了，找到法则之后倒是没写几行代码，提交之后马上就通过了。

var numTrees = function(n) {
    // 留神：n=0 时，须要解决为 1，因为 n=0 示意没有子节点，也是一种排列。if (n < 3) return n || 1

    let nums = 0
    for (let i=1; i<=n; i++) {nums += numTrees(i-1) * numTrees(n-i)
    }

    return nums
};

第三轮

第三轮是优化，第二轮的思路整顿让我最终找出了解题思路，也给了我很大的信念和启发，然而复杂度比拟高，有很大优化空间。

优化思路也是从 3-5 的排列和 1-3 一样去动手，很容易会发现：数组过半之后，数组后半段的排列数量其实和前半段一样的！也就是后半段没必要计算了，间接在前半段根底上翻倍就好了，惟一须要思考的就是数组长度要分奇偶数来解决。

代码也很简略，间接贴一下，供参考。

var numTrees = function(n) {if (n < 3) return n || 1

    let nums = 0
    let mid = Math.ceil(n / 2)

    let i
    for (i=1; i<mid; i++) {nums += numTrees(i-1) * numTrees(n-i)
    }
    // 数据长度分奇偶解决
    if (n&1) {nums = nums * 2 + numTrees(i-1) * numTrees(n-i)
    } else {nums = (nums + numTrees(i-1) * numTrees(n-i)) * 2
    }

    return nums
};

总结

遇到困难，放弃急躁，从细节动手，寻找个别法则。