# 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. 重建二叉树

根据二叉树的前序遍历和中序遍历的结果,重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

# 解题思路

前序遍历的第一个值为根节点的值,使用这个值将中序遍历结果分成两部分,左部分为树的左子树中序遍历结果,右部分为树的右子树中序遍历的结果。

  1. 前序遍历的第一个元素一定是树的根结点
  2. 在中序遍历中找到此节点,左边是左子树,右边是右子树
  3. 根据左右子树的长度,再次划分两个序列,进一步递归

# 代码

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. 二叉树的下一个结点

给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

# 解题思路

  1. 如果一个节点的右子树不为空,那么该节点的下一个节点是右子树的最左节点;
  2. 否则,向上找第一个左链接指向的树包含该节点的祖先节点。
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();
};