标签： 算法

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

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 阶贝塞尔的数学公式都把我吓退了。实现起来还是比较简单的，效果如下，代码可以审查元素获得。

从 18 年到 22 年，第一次知道 svg 中其实已经存在矩阵相关的 API，我们先来看一下通过矩阵运算实现的一个例子。

See the Pen transform ellipse by zeng (@zengxiaoluan) on CodePen.

继续阅读“svg 中的矩阵”

看懂这篇文章需要会矩阵相乘的运算，以及矩阵相乘在图形学里的意义。大学线性代数这门课，学过矩阵的乘法，没有学过也没事，也能体会得到。我在文章里提供了 codepen 的示例，可以清晰的了解到。

继续阅读“图形变换与矩阵相乘”

朋友面试腾讯，遇到了一个算法题，挺有意思的，特此记录一下。题目是这样的，给定一个数组如下：

let arr = [
  ["a", "aa", "aaa", "aaaa"],
  ["b", "bb", "bbb"],
  ["a", "ab", "aba"],
  ["a", "aa", "aab"]
]

将其转化成一个树状的子结构，如下：

[
  {
    name: "a",
    child: [
      {
        name: "aa",
        child: [
          {
            name: "aaa",
            child: [
              {
                name: "aaaa",
                child: [],
              },
            ],
          },
          {
            name: "aab",
            child: [],
          },
        ],
      },
      {
        name: "ab",
        child: [
          {
            name: "aba",
            child: [],
          },
        ],
      },
    ],
  },
  {
    name: "b",
    child: [
      {
        name: "bb",
        child: [
          {
            name: "bbb",
            child: [],
          },
        ],
      },
    ],
  },
];

继续阅读“记一个朋友遇到的腾讯面试题”

Trie 能解决什么问题？

假设我们有一个数组：['tiger', 'monkey', 'elephant', 'dog']，我们想要查找里面有没有 dog，最简单的方法是遍历数组，如果要查 10000 次，则遍历数组的次数是 1w * 4 = 4w；如果我们用 trie 来解决这个问题，则会大大的提升我们的速度。构建 trie 的遍历次数是 5 + 6 + 7 + 3 = 21，再查询 10000 次，则是 10000 * 3 + 21 = 30021。很明显，查询次数越多，trie 的性能优势就越明显。

上面的计算可能并不专业，仅供参考。

继续阅读“Trie 的简易版 js 实现”

Segment tree 可以用来解决一些区间的问题。比如说有 100 个元素的整数数组，想要求其中索引位置在 a - b 之间所有数字的和，那怎么求呢？一种方式是遍历，从 a 到 b，这样的时间复杂度是 O(n) 级别的；第二种是使用线段树，则可以把时间复杂度优化到 O(logn)。

继续阅读“线段树的 js 实现”

这个优先队列使用数组存储。下面的代码是一个最大堆的实现。

继续阅读“简易优先队列 js 版”