面试助力，算法 101：JavaScript 描述
搜索文档…
面试助力，算法 101：JavaScript 描述
目录
写在前面
学习指南
开篇——复杂度
字符串
数学
数组
链表
二叉树
最小栈、Shuffle an Array和将有序数组转换为二叉搜索树
对称二叉树、二叉树的最大深度和验证二叉搜索树
二叉树的层次遍历、二叉树的序列化与反序列化和常数时间内插入删除、获得随机数
中序遍历二叉树、从前序与中序遍历序列构造二叉树和二叉搜索树中第 K 小的元素
填充每个节点的下一个右侧节点指针、岛屿数量和二叉树的锯齿形层次遍历
动态规划
回溯算法
排序与搜索
栈和队列
结束篇
由 GitBook 提供支持
最小栈、Shuffle an Array和将有序数组转换为二叉搜索树

最小栈

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
  • push(x) -- 将元素 x 推入栈中。
  • pop() -- 删除栈顶的元素。
  • top() -- 获取栈顶元素。
  • getMin() -- 检索栈中的最小元素。
示例
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.

方法一 最小元素栈

思路
根据数组的性质，push、pop、top都能在常数时间内完成，而此题关键是常数时间内检索最小元素，此解法是开辟一个数组存储，push数据同时，存储当前栈中最小元素，pop数据的同时pop最小元素栈栈顶数据；
详解
  1. 1.
    创建最小元素栈时，开辟 stack 及 minStack 数组，stack 用于存储压栈元素，minStack 用于存储最小元素序列；
  2. 2.
    push操作执行元素 x 压栈：
  3. 3.
    如果 minStack 数组为空时，添加元素 x 到 minStack 数组。
  4. 4.
    否则比较元素 x 与数组末尾元素，取最小值添加到 minStack 数组末尾。表示当前栈中元素的最小值为x。
  5. 5.
    pop操作:
  6. 6.
    删除 stack 数组末尾元素的同时，删除数组 minStack 末尾元素。
  7. 7.
    getMin操作:
  8. 8.
    直接调用 pop 方法，返回 minStack 数据中末尾元素即可。
const MinStack = function () {
this.stack = [];
this.minStack = [];
};
​
/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function (x) {
this.stack.push(x);
if (this.minStack.length === 0) {
this.minStack.push(x);
} else {
const min = Math.min(this.minStack[this.minStack.length - 1], x);
this.minStack.push(min);
}
};
​
/**
* @return {void}
*/
MinStack.prototype.pop = function () {
this.minStack.pop();
return this.stack.pop();
};
​
/**
* @return {number}
*/
MinStack.prototype.top = function () {
return this.stack[this.stack.length - 1];
};
​
/**
* @return {number}
*/
MinStack.prototype.getMin = function () {
return this.minStack[this.minStack.length - 1];
};
复杂度分析
  • 时间复杂度：
    O(1)O(1)
    ​
    push、pop、top、getMin 操作都是基于数组索引，耗费 O(1) 的时间。
  • 空间复杂度：
    O(n)O(n)
    ​
    每次 push 一个元素到 stack 栈的同时将 stack 栈中最小元素 push 到 minStack 栈，耗费
    O(n)O(n)
    的栈空间

方法二 差值存储

思路
用一个min变量保存最小值，每次push操作压栈时,保存的是入栈的值和最小值min的差值，而不是入栈的值；pop出栈时，通过min值和栈顶的值得到；不过此算法有一个缺陷，两数差值有溢出风险。
详解
  1. 1.
    创建最小元素栈时，开辟 stack 数组，用于存储入栈元素x与最小元素 min 的差值；同时定义变量 min，用于存储最小值，初始值为 Number.MAX_VALUE。
  2. 2.
    push 操作执行元素x入栈：：
  3. 3.
    取元素 x 与最小元素 min 的差值，压入stack数组：
  4. 4.
    比较元素x与min值，取其最小值赋值给min变量。
  5. 5.
    pop操作:
  6. 6.
    弹出stack数组末尾元素值 value，如果值value > 0，说明push操作的值大于 min，返回 value + min 值；如果值value <= 0，说明 push 操作的值小于等于原 min 值，恢复最小值min，同时返回 min 值即可。
  7. 7.
    top 操作:
  8. 8.
    取stack数组末尾元素值 value，如果值 value > 0，说明push操作的值大于min，返回 value + min 值；如果值 value <= 0，说明 push 操作的值小于等于原 min 值，返回 min 值即可。
  9. 9.
    getMin 操作:
  10. 10.
    返回 min 元素即可。
const MinStack = function () {
this.stack = [];
this.min = Number.MAX_VALUE;
};
​
/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function (x) {
const min = this.min;
this.stack.push(x - min);
if (x < min) {
this.min = x;
}
};
​
/**
* @return {void}
*/
MinStack.prototype.pop = function () {
const value = this.stack.pop();
const min = this.min;
if (value > 0) {
return value + min;
} else {
this.min = min - value;
return min;
}
};
​
/**
* @return {number}
*/
MinStack.prototype.top = function () {
const value = this.stack[this.stack.length - 1];
if (value > 0) {
return value + this.min;
} else {
return this.min;
}
};
​
/**
* @return {number}
*/
MinStack.prototype.getMin = function () {
return this.min;
};
复杂度分析
  • 时间复杂度：
    O(1)O(1)
    ​
  • 空间复杂度：
    O(1)O(1)
    ​
    每次 push 一个元素到 stack 栈的同时只需要一个元素空间存储最小值，耗费
    O(1)O(1)
    的栈空间

Shuffle an Array

打乱一个没有重复元素的数组。
示例
// 以数字集合 1, 2 和 3 初始化数组。
​
int[] nums = {1,2,3};
​
Solution solution = new Solution(nums);
​
// 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。
​
solution.shuffle();
​
// 重设数组到它的初始状态[1,2,3]。
​
solution.reset();
​
// 随机返回数组[1,2,3]打乱后的结果。
​
solution.shuffle();

方法一

思路
  • reset 函数：缓存传入的原始数据，用于在函数调用时返回。但值得一提的是，进行缓存原始数据时，必须进行浅拷贝，因为原始数据为数组，普通的赋值会导致引用对象传递，一旦变更了 this.nums 的数组内容，缓存的数组也将同步变更
  • shuffle 函数：我们模拟一个这样的场景，有 n 个标着数的球，我们把这 n 个球放入一个看不见的袋子中，每次从中摸一个球出来，并按照摸出的顺序，直到摸空袋子。具体的操作，我们把原始数组复制一份为 nums，每次根据 nums 的长度随机生成一个下标从 nums 中取一个数出来，将其放入新数组 ary 中，并删除 nums 中对应下标的数
详解
  1. 1.
    定义 this.nums 存储传入的数据
  2. 2.
    定义 this.original 存储 nums 的克隆数组
  3. 3.
    定义重置 reset 方法，将 this.nums 重制为 this.original 的克隆数组，并将 this.original 重新克隆一遍（因数组为引用对象，不重新缓存新数组会导致 this.original 和 this.nums 同步变化）
  4. 4.
    定义打乱 shuffle 方法，根据 this.nums 的长度进行循环，每次从根据 this.nums 长度通过 Math.random() 随机生成一个下标
  5. 5.
    根据随机生成的下标，将值存入 ary 数组中
  6. 6.
    最后返回 ary 数组
代码
/**
* @param {number[]} nums
*/
const Solution = (nums) => {
this.nums = nums;
this.original = nums.slice(0);
};
/**
* 重置数组并返回
* @return {number[]}
*/
Solution.prototype.reset = () => {
this.nums = this.original;
this.original = this.original.slice(0);
return this.original;
};
/**
* 返回一个随机重排的数组
* @return {number[]}
*/
Solution.prototype.shuffle = () => {
const ary = [];
const nums = this.nums.slice(0);
const len = nums.length;
for (let i = 0; i < len; i += 1) {
const targetIndex = Math.floor(Math.random() * nums.length);
ary[i] = nums[targetIndex];
nums.splice(targetIndex, 1);
}
return ary;
};
复杂度分析
  • 时间复杂度：
    O(n2)O(n^2)
    ​
    js 中 splice 方法的时间复杂度为
    O(n)O(n)
    ，因为当你在中间删除一个元素后，在此位置之后的所有元素都需要整体向前移动一个位置，因此导致遍历所有
    nn
     个元素，又因为 splice 方法于 for 循环中需执行
    nn
     遍，因此为
    O(n2)O(n^2)
    。
  • 空间复杂度：
    O(n)O(n)
    ​
    为实现重置功能，原始数组需保存一份，因此为
    O(n)O(n)
    。

方法二

思路
  • reset 函数：同方法一
  • shuffle 函数：为降低方法一中的时间复杂度，我们可以让数组中的元素进行互换，从而减少 splice 方法所需执行的时间。具体的操作，我们从数组的最后往前迭代，生成一个范围在 0 到当前遍历下标之间的随机整数，和当前遍历下标的元素进行互换。这跟方法一中的模拟摸球是一样的，每次被摸出的球便不能再被摸出来。
详解
  1. 1.
    定义 this.nums 存储传入的数据
  2. 2.
    定义 this.original 存储 nums 的克隆数组
  3. 3.
    定义重置 reset 方法，将 this.nums 重制为 this.original 的克隆数组，并将 this.original 重新克隆一遍（因数组为引用对象，不重新缓存新数组会导致 this.original 和 this.nums 同步变化）
  4. 4.
    定义打乱 shuffle 方法，根据 this.nums 的长度进行倒序循环，每次从根据当前下标 i 通过 Math.floor(Math.random() * (i + 1)) 随机生成一个下标（Knuth-Durstenfeld Shuffle算法）
  5. 5.
    根据随机生成的下标，和当前下标，进行数据互换
  6. 6.
    最后返回 nums 数组
代码
/**
* @param {number[]} nums
*/
const Solution = (nums) => {
this.nums = nums;
this.original = nums.slice(0);
};
/**
* 重置数组并返回
* @return {number[]}
*/
Solution.prototype.reset = () => {
this.nums = this.original;
this.original = this.original.slice(0);
return this.original;
};
/**
* 返回一个随机重排的数组
* @return {number[]}
*/
Solution.prototype.shuffle = () => {
const nums = this.nums.slice(0);
const len = nums.length;
for (let i = len - 1; i > 0; i -= 1) {
const targetIndex = Math.floor(Math.random() * (i + 1));
const tmp = nums[i];
nums[i] = nums[targetIndex];
nums[targetIndex] = tmp;
}
return nums;
};
复杂度分析
  • 时间复杂度：
    O(n)O(n)
    ​
    上述算法中，for 循环内操作都是常数时间复杂度，因此为
    O(n)O(n)
    。
  • 空间复杂度：
    O(n)O(n)
    ​
    为实现重置功能，原始数组需保存一份，因此为
    O(n)O(n)
    。

将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ \ / \
-10 null 5 null

方法一 二分 + 递归法

思路
由于数组是按照递增有序排列的，并且高度平衡二叉搜索树（一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1），可以使用二分法从数组的中间开始查找数据。
详解
  1. 1.
    找出数组的中间坐标（mid）对应元素，作为当前二叉树节点（root）的 value
  2. 2.
    root 的左节点 是 0 -> mid 的中间坐标对应元素
  3. 3.
    root 的右节点 是 mid -> (arr.length - 1) 的中间坐标对应元素
  4. 4.
    root 的左右节点 按照 1 - 3 步骤生成新的左右节点，直到数组遍历完，算法终止
代码
const sortedArrayToBST = (arr) => {
return initTreeNodes(arr, arr.length - 1, 0);
};
​
const initTreeNodes = (arr, end, start) => {
if (start <= end) {
const mid = start + parseInt((end - start) / 2, 10);
const root = Node(arr[mid]);
root.left = initTreeNodes(arr, mid - 1, start);
root.right = initTreeNodes(arr, end, mid + 1);
return root;
} else {
return null;
}
};
复杂度分析
  • 时间复杂度：
    O(n)O(n)
    ​
    每次调用需要遍历数组，因此，时间复杂度是
    O(n)O(n)
    。
  • 空间复杂度：
    O(1)O(1)
    ​
    算法在运行过程中，只申请了常量大小内存，因此，空间复杂度是
    O(1)O(1)
    。

方法二 数组模拟队列

思路
可以先将提示数组按照二分法的查找顺数，一次推入数组中。然后，按照数组顺序通过生成二叉树的一般算法生成目标树。由于在题目的二叉树中，节点的左子节点的值要小于节点的值，节点的右子节点的值要大于节点的值。因此，数组从中点按照 [root, 左, 右, 左, 右...] 接收节点的值，并按照生成二叉树的一般算法，即可生成目标树。
详解
  1. 1.
    首先，使用二分法，先找到数组中间位置（mid）元素，将该元素 push 进目标数组 queue（模拟队列）
  2. 2.
    将数组分成两部分 0 -> mid, (mid + 1) -> arr.length
  3. 3.
    将获得两个新数组，按照 1、2 步骤重复，直到数组元素全部遍历完成
  4. 4.
    然后，按顺序遍历数组，arr[0]为 根节点值
  5. 5.
    当 queue[i]， 小于 arr[0] 时会被分配到左子节点，大于 arr[0] 时会被分配到右子节点
  6. 6.
    当左子节点已经有值时，会比较左子节点的值与 queue[i]，按照值得大小 分配到 左子节点的 左子节点或者 右子节点
  7. 7.
    当右子节点已经有值时，会比较右子节点的值与 queue[i]，按照值得大小 分配到 左子节点的 左子节点或者 右子节点
  8. 8.
    遍历 queue， 重复执行 6、7 步骤， 直到 queue 被全部遍历
代码
const sortedArrayToBST = (arr) => {
if (!arr.length) {
return null;
}
const queue = [];
// 二分法重新排列数组 queue
initNodeValueArr(arr, 0, arr.length, queue);
// 根节点
const root = new TreeNode(queue[0]);
for (let i = 1; i < queue.length; i += 1) {
// 插入节点数据
insertNode(root, queue[i]);
}
return root;
};
​
const insertNode = (node, value) => {
// 生成左子节点
if (value < node.val) {
if (!node.left) {
node.left = new TreeNode(value);
} else {
insertNode(node.left, value);
}
// 生成右子节点
} else if (!node.right) {
node.right = new TreeNode(value);
} else {
insertNode(node.right, value);
}
};
​
const initNodeValueArr = (arr, start, end, queue) => {
const mid = start + parseInt((end - start) / 2, 10);
queue.push(arr[mid]);
// 左节点数值
if (start < mid) {
initNodeValueArr(arr, start, mid, queue);
}
// 右节点数值
if (mid + 1 < end) {
initNodeValueArr(arr, mid + 1, end, queue);
}
};
复杂度分析
  • 时间复杂度：
    O(n)O(n)
    ​
    每次调用需要遍历数组，因此，时间复杂度是
    O(n)O(n)
    。
  • 空间复杂度：
    O(n)O(n)
    ​
    算法在运行过程中，申请了 n 长度的数组 queue，因此，空间复杂度是
    O(n)O(n)
    ​
以前
二叉树
下一个
对称二叉树、二叉树的最大深度和验证二叉搜索树
最近更新 2yr ago
复制链接
大纲
最小栈
Shuffle an Array
将有序数组转换为二叉搜索树