工厂模式有三个版本： simple factory（不能被称为模式） factory method abstract factory 本文的披萨店例子参考《Head First 设计模式》的 Java 示例 问题场景 假设我们现在有一个披萨店，菜单上有三种披萨，根据顾客的实时订单选择创建相应的披萨实例： // 披萨的超类 class Pizza { ...

观察者模式允许对象（订阅者）被通知订阅对象（发布者）的变化，并且根据订阅对象（发布者）的变化更新自身状态。 问题场景 假设有一个发布者 A，A 的状态经常改变；另有一个订阅者 B，B 想要实时获知 A 的当前状态。A 可能有多个订阅者，即 A <-> B1, A <-> B2, A <-> B3, ……, A <-> Bn，形成一对多关系。...

策略模式将不同的算法封装到各自的策略类中，使得它们可以互相替换，以达到动态改变对象的行为的目的。 问题场景 例子引自参考视频。 策略模式是为了解决以下类型的问题而提出的： 假设我们有一个超类鸭子，鸭子有两种行为：叫和飞。 // 超类鸭子 class Duck { quack() { // 叫 console.log('呱呱叫'); } ...

Morris 中序遍历 例题：剑指 Offer II 054. 所有大于等于节点的值之和 本例题是反序中序遍历（即下面引文中的“左”<->“右”要反着看），其官解是这样解释 Morris 遍历的： Morris 遍历的核心思想是利用树的大量空闲指针，实现空间开销的极限缩减。其反序中序遍历规则总结如下： 如果当前节点的右子节点为空，处理当前节点，并遍历当...

本文是我搭建博客的过程记录笔记。如果你想要搭建与我同样主题的博客，建议直接阅读 Chirpy getting-started。 环境准备 我的环境：MacOS, zsh, homebrew 如果还未在 github 建立 xxx.github.io 仓库，则先根据 GitHub: Creating a GitHub Pages site，把仓库建好后，再按下面执行。 检查环境 参考...

搞清递归的关键：清楚递归函数的定义 + 递归函数返回值的含义。 递归函数返回值不一定是题目要求的目标结果。 例题 1：最长同值路径 687. 最长同值路径。 题目要求：root 中的最长同值路径，此路径无需穿过 root。 var longestUnivaluePath = function(root) { let ans = 0; // 结果辅助变量 co...

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。 LSD 示意图 基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，...

计数排序是一种空间换时间的非比较方法。 开辟一个长度为数组数值跨度（最大值-最小值+1）的辅助数组（桶） 遍历数组元素，将元素放置到各自应去的桶中 全部元素放置完后，遍历桶内的元素，重新整合得到的新数组就是排好序的 function countSort(nums) { const len = nums.length, max = Math.m...

堆的概念 属性 堆是一颗完全二叉树（complete binary tree)。这个前提非常重要，记住这一点才能理解父子结点的索引值关系以及判断叶子结点的原理。 注意：分清完全二叉树和满二叉树。对于满二叉树，国内外定义不同（本文跟随国际定义）： 国内，仅下图(a)才能叫做满二叉树，满二叉树是完全二叉树的特殊形态。满二叉树必定是完全二叉树；反之不一定。 国际...

排序算法之归并排序 将整个数组对半分，直到每个子数组只剩1个元素；然后回溯往上合并，合并时按升序将合并前的子数组元素排列，最终得到整个数组的升序。 对半分操作会进行logn次，一次对半分操作对应一次合并操作，每次合并都需要遍历两个子数组的所有元素，因此时间复杂度为o(n * logn) 空间浪费的归并排序 以下为空间较浪费的非原地修改归并排序算法： function mergeSo...