综合利用各种数据结构

常用的数据结构

常用的数据结构有数组，hash表，

448. 找到所有数组中消失的数字

题目描述

给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。

找到所有在 [1, n] 范围之间没有出现在数组中的数字。

例子1

Input: [4,3,2,7,8,2,3,1]

output: [5,6]

思考

1 首先想到了使用数组的特性，因为这里1 ≤ a[i] ≤ n，所可以把每个a[i]放到数组中a[i]的位置上，到最后发现数组上没有放置数的位置就是缺失的数字

参考实现1

实现1

/**
 * @param {number[]} nums
 * @return {number[]}
 */

const swap = (nums, i, j) => {
  const temp = nums[j];
  nums[j] = nums[i];
  nums[i] = temp;
};
// Runtime: 204 ms, faster than 29.69% of JavaScript online submissions for Find All Numbers Disappeared in an Array.
// Memory Usage: 47.3 MB, less than 48.68% of JavaScript online submissions for Find All Numbers Disappeared in an Array.
export default (nums) => {
  const len = nums.length;
  const res = new Array(len).fill(0);
  for (let i = 0; i < nums.length; i++) {
    if (res[nums[i] - 1] === 0) {
      res[nums[i] - 1] = nums[i];
    }
  }

  for (let i = 0; i < res.length; i++) {
    if (res[i] === 0) {
      res[i] = i + 1;
    } else {
      res[i] = 0;
    }
  }

  return res.filter((item) => item !== 0);
};

时间复杂度O（n），空间复杂度O（n）

48. 旋转图像

题目描述

给定一个 n × n 的二维矩阵表示一个图像。

将图像顺时针旋转 90 度。

说明:
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

例子1

给定 matrix = 
[
 [1,2,3],
 [4,5,6],
 [7,8,9]
],

原地旋转输入矩阵，使其变为:
[
 [7,4,1],
 [8,5,2],
 [9,6,3]
]

例子2

给定 matrix =
[
 [ 5, 1, 9,11],
 [ 2, 4, 8,10],
 [13, 3, 6, 7],
 [15,14,12,16]
], 

原地旋转输入矩阵，使其变为:
[
 [15,13, 2, 5],
 [14, 3, 4, 1],
 [12, 6, 8, 9],
 [16, 7,10,11]
]

思考

1 这里首先想到了很明显可以递归，首先交换外层的，然后再递归交换里边的

参考实现1

2 第二种是比较通用的方法，是解决类似的顺时针或者逆时针旋转的方法

 * 顺时针旋转
 * 首先上下交换,这里是指第一行和最后一行交换，第二行和倒数第二行，依次类推, 然后交换对角线的数字 
 * 1 2 3     7 8 9     7 4 1
 * 4 5 6  => 4 5 6  => 8 5 2
 * 7 8 9     1 2 3     9 6 3

 * 逆时针旋转
 * 首先左右交换,这里是指第一列和最后一列交换，第二列和倒数第二列，依次类推, 然后交换对角线的数字 
 * 1 2 3     3 2 1     3 6 9
 * 4 5 6  => 6 5 4  => 2 5 8
 * 7 8 9     9 8 7     1 4 7

参考实现2

实现1

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */

const rotate1 = (matrix, begin, end) => {
  const len = end - begin;
  if (begin >= end) {
    return;
  }
  let tempTop = [];
  for (let i = begin; i <= end; i++) {
    tempTop.push(matrix[begin][i]);
  }

  let tempRight = [];
  for (let i = begin; i <= end; i++) {
    tempRight.push(matrix[i][end]);
  }
  let tempBottom = [];
  for (let i = end; i >= begin; i--) {
    tempBottom.push(matrix[end][i]);
  }
  let tempLeft = [];
  for (let i = end; i >= begin; i--) {
    tempLeft.push(matrix[i][begin]);
  }
  // 替换最右边
  for (let i = begin; i <= end; i++) {
    matrix[i][end] = tempTop[i - begin];
  }
  // console.log(temp, matrix);
  for (let i = end; i >= begin; i--) {
    matrix[end][i] = tempRight[end - i];
  }
  for (let i = end; i >= begin; i--) {
    matrix[i][begin] = tempBottom[end - i];
  }
  for (let i = begin; i <= end; i++) {
    // console.log(tempLeft);
    matrix[begin][i] = tempLeft[i - begin];
  }

  rotate1(matrix, begin + 1, end - 1);
};
// Runtime: 76 ms, faster than 82.34% of JavaScript online submissions for Rotate Image.
// Memory Usage: 38.9 MB, less than 23.65% of JavaScript online submissions for Rotate Image.
const rotate = (matrix) => {
  const len = matrix.length;
  rotate1(matrix, 0, len - 1);
  // console.log(matrix);
  // return matrix;
};
export default rotate;

实现2

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */

// Runtime: 72 ms, faster than 93.88% of JavaScript online submissions for Rotate Image.
// Memory Usage: 38.9 MB, less than 32.93% of JavaScript online submissions for Rotate Image.
const rotate = (matrix) => {
  const len = matrix.length;
  let low = 0;
  let high = len - 1;
  while (low < high) {
    for (let i = 0; i < len; i++) {
      const temp = matrix[low][i];
      matrix[low][i] = matrix[high][i];
      matrix[high][i] = temp;
    }
    low++;
    high--;
  }
  for (let i = 1; i < len; i++) {
    for (let j = 0; j < i; j++) {
      const temp = matrix[i][j];
      matrix[i][j] = matrix[j][i];
      matrix[j][i] = temp;
    }
  }
};
export default rotate;

时间复杂度O(n * n) 空间复杂度O（1）

240. 搜索二维矩阵 II

题目描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

例子1

input: 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]], target = 5
output: true

思考

1 刚开始想使用二分搜索，可是后来发现不行，后来看了下题解很容易，只是特别不容易想到

参考实现1

实现1

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
// Runtime: 296 ms, faster than 64.11% of JavaScript online submissions for Search a 2D Matrix II.
// Memory Usage: 41.8 MB, less than 58.69% of JavaScript online submissions for Search a 2D Matrix II.
export default (matrix, target) => {
  if (matrix.length === 0) {
    return false;
  }
  let row = 0;
  let col = matrix[0].length - 1;
  while (col >= 0 && row < matrix.length) {
    if (target === matrix[row][col]) {
      return true;
    } else if (target < matrix[row][col]) {
      col--;
    } else {
      row++;
    }
  }
  return false;
};

时间复杂度O（max（m,n））, 空间复杂度O（1）

769. 最多能完成排序的块

题目描述

数组arr是[0, 1, ..., arr.length - 1]的一种排列，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。

我们最多能将数组分成多少块？

例子1
input: arr = [4,3,2,1,0]
output: 1
解释: 将数组分成2块或者更多块，都无法得到所需的结果。 例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。

例子2
input: arr = [1,0,2,3,4]
output: 4
解释: 我们可以把它分成两块，例如 [1, 0], [2, 3, 4]。 然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数。

注意：

1 arr 的长度在 [1, 10] 之间。
2 arr[i]是 [0, 1, ..., arr.length - 1]的一种排列。

思考

1 刚开始想遇到最大值就拆开，可是发现不行，比如输入[1,2,0,5]的时候，就不能按照这种策略来执行，后来发现如果我们遇到想要拆开的时候，必须在max前面的所有数字必须都已经在前面的数组中使用过了。所以可以设置一个hasUsed数组来记录数字是否使用过

参考实现1

2 还有特别简单的方法，当然这里的简单是指解法，但是并不是指可以很简单的思考出来。

我们可以遍历数组，记录遇到的最大数字max，如果发现max等于我们遍历数组的下标，就可以拆开了。

这里主要是因为输入数组的里边的数组刚好等于数组的长度减1，所以当遇到max等于数组下标的时候，这时候就可以拆分为一个子数组，因为这时候前面的肯定都排好序了或者都在目前拆分的数组中

参考实现2

实现1

/**
 * @param {number[]} arr
 * @return {number}
 */
// Runtime: 68 ms, faster than 98.04% of JavaScript online submissions for Max Chunks To Make Sorted.
// Memory Usage: 38.5 MB, less than 50.98% of JavaScript online submissions for Max Chunks To Make Sorted.
export default (arr) => {
  const hasUsed = new Array(arr.length).fill(0);
  let res = 1;
  let max = arr[0];
  hasUsed[max] = 1;
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      let flag = hasUsed[0];
      for (let j = 1; j < max; j++) {
        flag &= hasUsed[j];
      }
      if (flag) {
        res++;
      }
      max = arr[i];
    }
    hasUsed[arr[i]] = 1;
  }
  return res;
};

实现2

/**
 * @param {number[]} arr
 * @return {number}
 */
// Runtime: 64 ms, faster than 100.00% of JavaScript online submissions for Max Chunks To Make Sorted.
// Memory Usage: 38.5 MB, less than 50.98% of JavaScript online submissions for Max Chunks To Make Sorted.
export default (arr) => {
  let res = 0;
  let max = arr[0];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
    if (max === i) {
      res++;
    }
  }
  return res;
};