青蛙跳台阶 1. 题目描述 一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 2. 思路分析 跳到 n 阶假设有 f(n)种方法。 往前倒退，如果青蛙最后一次是跳了 2 阶，那么之前有 f(n-2)种跳法; 如果最后一次跳了 1 阶，那么之前有 f(n-1)种跳法。 所以：f(n) = f(n-1) + f(n-2)。就是斐波...

从尾到头打印链表 1. 题目描述 输入一个链表，从尾到头打印链表每个节点的值。 2. 解题思路 可以从头到尾遍历一遍链表，将节点放入栈中，然后依次取出打印（后入先出）。 优化就是借助“递归”，先向下查找再打印输出，也可实现这种“后入先出”。可以类比二叉树的后序遍历。 3. 代码 用 JS 实现了简单实现了链表这种数据结构，这不是重点。 重点在printFromTailToHe...

最小的k个数 1. 题目描述 输入 n 个整数，找出其中最小的 k 个数。例如输入 4、5、1、6、2、7、3、8 这 8 个数字，则最小的 4 个数字是 1、2、3、4。 2. 思路分析 这里创建一个容量为 k 的最大堆。遍历给定数据集合，每次和堆顶元素进行比较，如果小于堆顶元素，则弹出堆顶元素，然后将当前元素放入堆。 由于堆大小为 k，所以弹出、推入操作复杂度为：O(logK)...

丑数 1. 题目描述 把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。例如 6、8 都是丑数，但 14 不是，因为它包含因子 7。习惯上我们把 1 当做是第一个丑数。求按从小到大的顺序的第 1500 个丑数。 2. 解题思路 2.1 思路一 根据定义，将给定的数不断除 2、3、5，看看能不能除尽即可。然后从 1 遍历到 1500。 2.2 思路二 前面速度...

旋转数组最小的数字 1. 题目描述 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为 1。 2. 解题思路 最简单的肯定是从头到尾遍历，复杂度是 $O(N)$。这种方法没有利用“旋转数组”的特性。 借助二分查找的思想，时间...

二进制中1的个数 1. 题目 请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如把 9 表示成二进制是 1001，有 2 位是 1。因此如果输入 9，该函数输出 2。 2. 思路 注意到，如果要判断一个二进制数指定位数是否为 1，比如这个二进制数是 1011。那么只需要构造除了这个位为 1，其他位为 0 的二进制即可，这个例子是 0100。 两者进行&运算...

二维数组中的查找 1. 题目描述 题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数 2. 解题思路 时间复杂度是 $O(N)$，空间复杂度是$O(1)$ 利用数组的排序性质：如果要查找的元素小于当前元素，那么一定不在当前元素左边的列；如果要查找的元素大于当前元素...

介绍 这是笔者在上半年去阿里(蚂蚁)和腾讯面试时候，开始刷的一本书。对于面试过程中的算法和数据结构帮助非常大，所以墙裂推荐。 大概三月份，面试都通过之后，就开始断断续续的阅读、刷题。最近终于刷完了这本书，收货颇丰，把过程中每道题目的想法以及 JavaScript 的解题版本都记录和整理了下来。 由于内容太多，所以划分成了 10 个专题，分别是：位运算、哈希表、堆、字符串、数组、查找、栈...

最近读了 koa2 的源码，理清楚了架构设计与用到的第三方库。本系列将分为 3 篇，分别介绍 koa 的架构设计和 3 个核心库，最终会手动实现一个简易的 koa。这是系列第 3 篇，模拟实现玩具版 koa。 源码和测试代码放在了：dongyuanxin/simple-koa 准备 设计思想和第三方库原理都在前 2 篇详细说明了。这篇主要目的是做一个验证检验，在语法使用 ES6/7 ...

最近读了 koa2 的源码，理清楚了架构设计与用到的第三方库。本系列将分为 3 篇，分别介绍 koa 的架构设计和 3 个核心库，最终会手动实现一个简易的 koa。这是系列第 2 篇，关于 3 个核心库的原理。 is-generator-function：判断 generator koa2 种推荐使用 async 函数，koa1 推荐的是 generator。koa2 为了兼容，在调用...