看懂这篇文章需要会矩阵相乘的运算,以及矩阵相乘在图形学里的意义。大学线性代数这门课,学过矩阵的乘法,没有学过也没事,也能体会得到。我在文章里提供了 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 的简易版 js 实现
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 实现”线段树的 js 实现
Segment tree 可以用来解决一些区间的问题。比如说有 100
个元素的整数数组,想要求其中索引位置在 a - b
之间所有数字的和,那怎么求呢?一种方式是遍历,从 a 到 b,这样的时间复杂度是 O(n) 级别的;第二种是使用线段树,则可以把时间复杂度优化到 O(logn)。
简易优先队列 js 版
这个优先队列使用数组存储。下面的代码是一个最大堆的实现。
继续阅读“简易优先队列 js 版”动画展示插入排序全过程
计划把学习的系列排序算法做个简单的动画,坚持做到 timsort 为止。
动画展示快速排序全过程
动画展示选择排序全过程
动画展示冒泡排序全过程
就这么一简单玩意儿,花了我一晚上时间,我怎么变得聪明起来呢。
继续阅读“动画展示冒泡排序全过程”汉诺塔游戏
近期一直在玩的游戏是汉诺塔,我倒是觉得这个游戏挺解乏的,但是我女票子却不喜欢,我让她玩 5 层,她讨价还价成 4 层,我再坚持一次,她就说不玩了不玩了,那就陪她玩 4 层咯。下面,我们来看看 js 制作的简单动画展示,这个游戏应该怎么玩。
继续阅读“汉诺塔游戏”