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

41次阅读

共计 1648 个字符,预计需要花费 5 分钟才能阅读完成。

引言

最近在换工作,尽管曾经是一个大叔级程序员了,然而三件套还是少不了:更新简历、刷 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
};

总结

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

正文完
 0