# 3. 数组中重复的数字
在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
Input: {2, 3, 1, 0, 2, 5}
Output: 2
# 哈希表
时间复杂度为 O(n)，空间复杂度为 O(n)。但使用了额外的空间。
function findRepeatNumber(arr = []) {
if (arr && arr.length) {
const map = {};
for (const val of arr) {
if (map[val]) {
return val;
}
map[val] = true;
}
}
}
# 解法二
要求时间复杂度 O(N)，空间复杂度 O(1)。因此不能使用排序的方法，也不能使用额外的标记数组。对于这种数组元素在 [0, n-1] 范围内的问题，可以将值为 i 的元素调整到第 i 个位置上进行求解。
长度为 n，元素的数值范围也为 n，如果没有重复元素，那么数组每个下标对应的值与下标相等。
从头到尾遍历数组，当扫描到下标 i 的数字 nums[i]：
- 如果等于
i，继续向下扫描； - 如果不等于
i，拿它与第nums[i]个数进行比较，如果相等，说明有重复值，返回nums[i]。如果不相等，就把第i个数 和第nums[i]个数交换。重复这个比较交换的过程。
此算法时间复杂度为 O(n)，因为每个元素最多只要两次交换，就能确定位置(比如把 2 跟 5 交换，此时 2 在正确的位置，而 5 需要再交换一次就能跑到正确的位置)。空间复杂度为 O(1)。
function swap(arr, i, j) {
[arr[i], arr[j]] = [arr[j], arr[i]];
}
function findRepeatNumber(arr = []) {
// 不符合题目条件
if (!arr || arr.length < 2) return -1;
for (let i = 0; i < arr.length; i++) {
// 值超出范围
if (arr[i] < 0 || arr[i] >= arr.length) return -1;
// 每个元素最多交换两次
while (arr[i] != i) {
const val = arr[arr[i]];
if (arr[i] == val) {
return val;
}
swap(arr, i, arr[i]);
}
}
return -1;
}
// 第一种
function duplicate(numbers, duplication) {
for (let i = 0; i < numbers.length; i++) {
while (i !== numbers[i]) {
if (numbers[i] === numbers[numbers[i]]) {
duplication[0] = numbers[i];
return true;
}
let temp = numbers[i];
[numbers[i], numbers[temp]] = [numbers[temp], numbers[i]]; // 交换
}
}
return false;
}
// 第二种
function duplicate2(numbers, duplication) {
for (let i = 0; i < numbers.length; i++) {
let index = numbers[i];
if (index >= numbers.length) {
index -= numbers.length;
}
if (numbers[index] >= numbers.length) {
duplication[0] = index;
return true;
}
numbers[index] = numbers[index] + numbers.length;
}
return false;
}
# 4. 二维数组中的查找
给定一个二维数组，其每一行从左到右递增排序，从上到下也是递增排序。给定一个数，判断这个数是否在该二维数组中。
Consider the following matrix: [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21,
23, 26, 30] ] Given target = 5, return true. Given target = 20, return false.
# 解题思路
要求时间复杂度 O(M + N)，空间复杂度 O(1)。其中 M 为行数，N 为 列数。
该二维数组中的一个数，小于它的数一定在其左边，大于它的数一定在其下边。因此，从右上角开始查找，就可以根据 target 和当前元素的大小关系来缩小查找区间，当前元素的查找区间为左下角的所有元素。
利用数组的排序性质：如果要查找的元素小于当前元素，那么一定不在当前元素左边的列；如果要查找的元素大于当前元素，那么一定在当前元素下面的行。
var findNumberIn2DArray = function(matrix, target) {
if (!matrix.length || !matrix[0].length) return false;
const row = matrix.length - 1;
const col = matrix[0].length - 1;
let i = 0,
j = col;
while (i <= row && j >= 0) {
if (target === matrix[i][j]) {
return true;
} else if (target > matrix[i][j]) {
i++;
} else {
j--;
}
}
return false;
};
const arr = [
[1, 2, 8, 9],
[2, 4, 9, 12],
[4, 7, 10, 13],
[6, 8, 11, 15],
];
console.log(findNumberIn2DArray(arr, 8));
console.log(findNumberIn2DArray(arr, 1));
console.log(findNumberIn2DArray(arr, 145));
# 5. 替换空格
JS 中直接用正则进行替换。
var replaceSpace = function(s) {
return s.replace(/\s/g, '%20');
};
# 6. 从尾到头打印链表
从尾到头反过来打印出每个结点的值。
# 栈(数组)
// 链表节点
function ListNode(val, next) {
this.val = val;
this.next = next || null;
}
function genList(arr = []) {
if (!arr.length) return null;
const [first, ...rest] = arr;
return new ListNode(first, genList(rest));
}
function List(arr = []) {
this.head = genList(arr);
}
var reversePrint = function(head) {
const result = [];
while (head) {
const { val, next } = head;
result.unshift(val);
head = next;
}
return result;
};
const l1 = new List([2, 1, 3]);
console.log(reversePrint(l1.head));
# callback 的形式（链表的翻转）
function traversal(linkedList, callback) {
let currentNode = linkedList.head;
while (currentNode) {
callback(currentNode.value);
currentNode = currentNode.next;
}
}
# 7. 重建二叉树
根据二叉树的前序遍历和中序遍历的结果，重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
# 解题思路
前序遍历的第一个值为根节点的值，使用这个值将中序遍历结果分成两部分，左部分为树的左子树中序遍历结果，右部分为树的右子树中序遍历的结果。
- 前序遍历的第一个元素一定是树的根结点
- 在中序遍历中找到此节点，左边是左子树，右边是右子树
- 根据左右子树的长度，再次划分两个序列，进一步递归
# 代码
function TreeNode(val, left, right) {
this.val = val;
this.left = left || null;
this.right = right || null;
}
/**
* 根据前序遍历和中序遍历重构二叉树
* @param {Array} preorder
* @param {Array} inorder
* @return {Node}
*/
var buildTree = function(preorder, inorder) {
if (!preorder.length || !inorder.length) return null;
// 前序的第一个值为根节点
const headValue = preorder[0];
// 前序第一个是根节点，也是中序左右子树的分割点
// 通过变量 index 可以确定在 前序遍历 / 中序遍历中 确定 左 / 右子树的长度
const index = inorder.findIndex(val => val === headValue);
if (index === -1) return null;
// 递归左右子树的前序、中序
const left = buildTree(preorder.slice(1, index + 1), inorder.slice(0, index));
const right = buildTree(preorder.slice(index + 1), inorder.slice(index + 1));
return new TreeNode(headValue, left, right);
};
const preorder = [1, 2, 4, 7, 3, 5, 6, 8];
const inorder = [4, 7, 2, 1, 5, 3, 8, 6];
console.log(buildTree(preorder, inorder));
# 8. 二叉树的下一个结点
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
# 解题思路
- 如果一个节点的右子树不为空，那么该节点的下一个节点是右子树的最左节点；
- 否则，向上找第一个左链接指向的树包含该节点的祖先节点。
function GetNext(pNode) {
if (pNode === null) {
return null;
}
if (pNode.right !== null) {
// 第1种
pNode = pNode.right;
while (pNode.left !== null) {
pNode = pNode.left;
}
return pNode;
}
while (pNode.next !== null) {
// 第2种
if (pNode === pNode.next.left) {
return pNode.next;
}
pNode = pNode.next;
}
return null;
}
# 9. 用两个栈实现队列
用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。
# 思路
一个栈用来存储插入队列数据，一个栈用来从队列中取出数据。从第一个栈向第二个栈转移数据的过程中：数据的性质已经从后入先出变成了先入先出。
var CQueue = function() {
this.outStack = [];
this.inStack = [];
};
/**
* @param {number} value
* @return {void}
*/
CQueue.prototype.appendTail = function(value) {
if (value) {
// 新插入队列的数据都放在 inStack
this.inStack.push(value);
}
};
/**
* @return {number}
*/
CQueue.prototype.deleteHead = function() {
const { outStack, inStack } = this;
// 如果 outStack 为空，那么将 inStack 中的元素都转移过来
if (!outStack.length) {
while (inStack.length) {
outStack.push(inStack.pop());
}
}
return !outStack.length ? -1 : outStack.pop();
};