复杂链表的复制
1. 题目描述请实现函数ComplexListNode *Clone（ComplexListNode* pHead），复制一个复杂链表。在复杂链表中，每个结点除了有一个 next 指针指向下一个结点外，还有一个 sibling 指向链表中的任意结点或者 NULL。
2. 思路分析按照正常的思路，首先从头到尾遍历链表，拷贝每个节点的 value 和 next 指针。然后从头再次遍历，第二次遍历的目的在于拷贝每个节点的 sibling 指针。
然而即使找到原节点的 sibling 指针，还是得为了找到复制节点对应的 sibling 指针而再遍历一遍。那么对于 n 个要寻找 sibling 指针的节点，复杂度就是 O(N*N)。
显然，为了降低复杂度，必须从第二次遍历着手。这里采用的方法是，在第一次遍历的时候，把 (原节点, 复制节点) 作为映射保存在表中。那么第二次遍历的时候，就能在 O(1) 的复杂度下立即找到原链上 sibling 指针在复制链上对应的映射。
3. 代码分析123456789101112131415161718192021222324252627282930313233 ...
两个链表中的第一个公共节点
1. 题目描述输入两个链表，找出它们的第一个公共结点。
2. 思路分析2.1 思路一：栈实现在第一个公共节点前的节点都是不相同的，因此只要倒序遍历两个链表，找出最后一个出现的相同节点即可。
因为链表不能倒序遍历，所以借助栈实现。
2.2 思路二：快慢指针假设链表 A 长度大于链表 B 长度，它们的长度差为 diff。
让 A 的指针先移动 diff 的位移，然后 A 和 B 的指针再同时向后移动，每次比较节点，选出第一个出现的相同节点。
3. 代码实现为了方便，先简单实现节点数据结构：
123456class Node { constructor(value, next) { this.value = value this.next = next }}
3.1 思路一：栈实现1234567891011121314151617181920212223242526272829303132333435/** * 思路一：利用栈实现 * * @param {Node} list1 * @par ...
二维数组中的查找
1. 题目描述题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数
2. 解题思路时间复杂度是 $O(N)$，空间复杂度是$O(1)$
利用数组的排序性质：如果要查找的元素小于当前元素，那么一定不在当前元素左边的列；如果要查找的元素大于当前元素，那么一定在当前元素下面的行。
3. 代码1234567891011121314151617181920212223242526272829303132333435363738394041/** * 题目答案 * @param {Array} arr * @param {Number} elem */function findElem(arr, elem) { let row = arr.length - 1, col = arr[0].length - 1 let i = 0, j = col while (i <= row & ...
数组顺序调整
1. 题目描述输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
2. 思路描述这题进一步抽象就是满足一定条件的元素都移动到数组的前面，不满足的移动到后面。所以，需要有一个参数用来传递判断函数。
最优解法就是数组两头分别有一个指针，然后向中间靠拢。符合条件，就一直向中间移动；不符合条件，就停下来指针，交换两个元素；然后继续移动，直到两个指针相遇。
3. 代码实现函数change运用了设计模式中的“桥接模式”，判断条件由用户自己定义。
1234567891011121314151617181920212223242526272829303132333435363738/** * 交换数组元素 * @param {Array} arr * @param {Number} i * @param {Number} j */const swap = (arr, i, j) => ([arr[i], arr[j]] = [arr[j], arr[i]])/** * 将 ...
把数组排成最小的数
1. 题目描述输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为 321323。
2. 思路分析因为涉及拼接，所以可以将其看做字符串，同时规避了大数溢出的问题，而且字符串的比较规则和数字相同。
借助自定义排序，可以快速比较两个数的大小。比如只看{3, 32}这两个数字。它们可以拼接成 332 和 323，按照题目要求，这里应该取 323。也就是说，此处自定义函数应该返回-1。
3. 代码实现12345678910111213141516171819202122/** * * @param {Array} numbers */function printMinNumber(numbers) { numbers.sort((x, y) => { const s1 = x + '' + y, s2 = y + '' + x if (s1 &l ...
数组中的逆序对
1. 题目描述输入一个数组,求出这个数组中的逆序对的总数。
例如在数组{7，5，6，4}中，一共存在 5 个逆序对，分别是(7,6), (7, 5), (7,4), (6,4), (5,4)。
2. 思路分析暴力法的时间复杂度是 O(N^2)。利用归并排序的思路，可以将时间复杂度降低到 O(NlogN)。
比如对于 7、5、6、4 来说，会被分成 5、7 和 4、6 两组。
准备两个指针指向两组最后元素，当左边数组指针的对应元素小于右边指针对应元素，结果可以加上从左指针到右指针之间的元素个数（都是逆序的）。
依次移动指针，直到达到边界。
3. 代码实现代码最后输出了数组，经过归并，数组已经是有序的了。
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758/** * * @param {Array} arr * @param {Number} start * @param {Nu ...
用两个栈实现队列
1. 题目描述用两个栈实现一个队列。队列的声明如下:
请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入结点和在队列头部删除结点的功能。
2. 解题思路一个栈用来存储插入队列数据，一个栈用来从队列中取出数据。
从第一个栈向第二个栈转移数据的过程中：数据的性质已经从后入先出变成了先入先出。
3. 代码1234567891011121314151617181920212223242526272829303132333435363738394041class Queue { constructor() { this.stack1 = [] this.stack2 = [] } appendTail(value) { // 新插入队列的数据都放在 stack1 this.stack1.splice(0, 0, value) } deleteHead() { // 将要取出的值都从stack2中取 ...
包含min函数的栈
1. 题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数。在该栈中，调用 min、push 及 pop 的时间复杂度都是 O（1）。
2. 思路分析有关栈的题目，可以考虑使用“辅助栈”，即利用空间换时间的方法。
这道题就是借助“辅助栈”来实现。当有新元素被 push 进普通栈的时候，程序比较新元素和辅助栈中的原有元素，选出最小的元素，将其放入辅助栈。
根据栈的特点和操作思路，辅助栈顶的元素就是最小元素。并且辅助栈的元素和普通栈的元素是“一一对应”的。
3. 代码实现1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162/** * 包含Min函数的栈 */class MinStack { constructor() { this.stack = [] // 数据栈 this.minStack = [] // 辅助栈 ...
栈的压入弹出序列
1. 题目描述输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。
例如序列 1、2、3、4、5 是某栈的压栈序列，序列 4、5、3、2、1 是该压栈序列对应的一个弹出序列，但 4、3、5、1、2 就不可能是该压栈序列的弹出序列。
2. 思路分析栈的题目还是借助“辅助栈”。大体思路如下：
将入栈序列的元素依次入辅助栈
检查辅助栈顶元素和弹栈序列栈顶元素是否一致：
元素一致，弹出辅助栈元素，弹栈序列指针后移
不一致，回到第一步
需要注意的是，过程中的边界条件检查（多试试几种情况）。除此之外，由于 js 不提供指针运算，所以用标记下标的方法代替指针。
3. 代码实现1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556/** * 获得栈顶元素 * @param {Array} stack */function getStackTop(stack ...
青蛙跳台阶
1. 题目描述一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
2. 思路分析跳到 n 阶假设有 f(n)种方法。
往前倒退，如果青蛙最后一次是跳了 2 阶，那么之前有 f(n-2)种跳法; 如果最后一次跳了 1 阶，那么之前有 f(n-1)种跳法。
所以：f(n) = f(n-1) + f(n-2)。就是斐波那契数列。
3. 代码这里利用缓存模式（又称备忘录模式）实现了代码。
123456789101112131415161718192021222324252627282930313233343536const fibonacci = (() => { let mem = new Map() mem.set(1, 1) mem.set(2, 1) const _fibonacci = (n) => { if (n <= 0) { throw new Error('Unvalid param') ...
