标签： 算法

想了一个面试题：树的过滤

给候选人做的题，应该好理解，如果讲半天题目，对方都不理解，我都怀疑是不是我的表达能力不行。题目足够简单，我讲解题目也省事，对方不理解或者不能做出来，则淘汰就好，我心里也没有负担。

继续阅读“想了一个面试题：树的过滤”

舞蹈链 – JavaScript 实现

前言

如果想实现一个数独小游戏，可以先了解舞蹈链这个数据结构，还是很有意思的。我不准备再具体讲解 dance link 是什么，因为很难比其它文章写的更好，只提供一个 JavaScript 的实现在下面，如果你感兴趣的话，可以查阅，有问题可以留言讨论。

继续阅读“舞蹈链 – JavaScript 实现”

flex-grow 和 flex-shrink 的计算公式

一直知道的概念是按照比例来计算，今天，朋友问起，仔细验证了一下具体的公式。比如我们先看下面的例子。

flex-grow

<div style="display:flex; width:100px;height:100px">
  <div style="width:10px;flex-grow: 5; background:red;"></div>
  <div style="width:40px;flex-grow: 2; background:blue;"></div>
  <div style="width:30px;flex-grow: 1; background:pink;"></div>
</div>

父元素的宽度是 100px，3 个子元素的宽度是 10、40、30，加起来是 80px，那么还需要剩下 20px 需要填充。每个子元素能分得多少呢？以第一个子元素为例。

5 / (5 + 2 + 1) * 20 + 10 = 22.5。第一个子元素占比 8 分之 5，乘以 20px，再加上原来的 10px，就是 22.5px。可以审查一下元素，验证我们的想法。

flex-shrink

<div style="display:flex; width:60px;height:100px">
  <div style="width:10px;flex-shrink: 5; background:red;"></div>
  <div style="width:40px;flex-shrink: 2; background:blue;"></div>
  <div style="width:30px;flex-shrink: 1; background:pink;"></div>
</div>

再看 flex-shrink。父级元素的宽度是 60px，子元素分别是 10、40、30px，加起来是 80px，那需要收缩 20px。怎么计算第一个子元素的宽度呢？如下：

10 – 5 * 10 / (10 * 5 + 40 * 2 + 30 * 1) * 20，意思是，原来子元素的宽度是 10px，它需要收缩的像素是用自身的宽度，乘以 shrink 这个权重值，再除以整个子元素的宽度乘以 shrink 权重值之和，再乘以整个收缩的 20px。

再审查元素，验证一下结果，也是对的。

我们发现了一点，grow 和 shrink 的计算方式不同，为什么呢？我觉得有 2 点。

  1. grow 这样算，很符合直觉，能够解决问题，心智模型简单。
  2. shrink 的方式更复杂一点，那是为了保证，所有的子元素塌陷后，不会出现负值，按照 grow 的算法的话就会。

以上，感谢阅读。

去 codepen 自己试一试

See the Pen flex-shrink by zeng (@zengxiaoluan) on CodePen.

等额本息的求解之路

房贷计算器

等额本息

年利率：
贷款金额(万元)：
贷款期数：
期数 每月还款 当月还的本金 累计还的本金 还欠的本金 当月还的利息 累计还的利息 累计还的利息 + 累计还的本金
{{n}} {{perMonthMoney}} {{c1.get(n)}} {{c2.get(n)}} {{c5.get(n)}} {{c4.get(n)}} {{c3.get(n)}} {{c6.get(n)}}

等额本息的意思是，本金加利息是等额的，所以每个月的还款额是一样的。等额本金说的是每个月还的本金是一样的，所以随着本金越还越少，则相应的利息部分越来越少。

假设我们借了 12 万块，等额本息，分 12 个月还，那么我们可以列出这样的等式，来理解计算过程，帮助我们求出每个月的还款额。其中 p 表示月利率，月利率等于年利率除以 12 个月，A 是我们要求的每月还款额。在这个例子中，我们假设年利率为百分之 6.

a0 = 12；# 这表示我们借了 12 万的本金

a1 = a0 * (1 + p) - A; # 第一个月的利息加本金，减去还款额 A，表示还款了一个月后，未还的钱

a2 = a1 * (1 + p) - A; # 以此类推

an = an-1 * (1 + p) - A; # 当第 12 月的时候，全部还完，当 n =12 时，则这个等式的左右 2 边都为 0。

怎么根据这些例子来求出 A 值呢，我先编程实现了这样一段代码。

继续阅读“等额本息的求解之路”

求两直线的交点

继续阅读“求两直线的交点”

如何模拟贝塞尔曲线上的点

刚接触觉得贝塞尔还是挺复杂的，n 阶贝塞尔的数学公式都把我吓退了。实现起来还是比较简单的，效果如下，代码可以审查元素获得。