标签: 算法

归并排序

排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。
归并排序采用的是分治思想。

分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。

const mergeSort = (arr) => {
  let len = arr.length;
  if (len < 2) {
    return arr;
  }
  let middle = Math.floor(len / 2);
  let left = arr.slice(0, middle);
  let right = arr.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
};
//
const merge = (left, right) => {
  const result = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  while (left.length) {
    result.push(left.shift());
  }
  while (right.length) {
    result.push(right.shift());
  }
  return result;
};
const arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.time("归并排序耗时");
console.log("arr :", mergeSort(arr));
console.timeEnd("归并排序耗时"); // 大约 8ms

ZiHao...大约 2 分钟

数字转罗马数字

罗马数字由 777 个不同的单字母符号组成，每个符号对应一个具体的数值。此外，减法规则（如问题描述中所述）给出了额外的 666 个复合符号。这给了我们总共 131313 个独特的符号（每个符号由 111 个或 222 个字母组成），如下图所示。

我们用来确定罗马数字的规则是：对于罗马数字从左到右的每一位，选择尽可能大的符号值。对于 140，最大可以选择的符号值为 C=100。接下来，对于剩余的数字 140，最大可以选择的符号值为 XL=40。因此，140 的对应的罗马数字为 C+XL=CXL。

ZiHao...小于 1 分钟

回溯算法题

输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
输入：s = "abc" 输出：["abc","acb","bac","bca","cab","cba"]

/**
 * @param {string} s
 * @return {string[]}
 * 全排列算法:
 *   固定位置依次递归交换位置穷举出所有的可能性。
 */
var permutation = function (s) {
  const char = s.split("");
  const res = [];
  const dsf = function (n) {
    // 递归的出口,如果是遍历到最后一个位置此方法就解了
    if (n === char.length) {
      res.push(char.join(""));
      return;
    }
    const catSet = new Set();
    for (let i = n; i < char.length; i++) {
      //如果有相同的交换，则不需要处理枝减。
      if (catSet.has(char[i])) continue;
      catSet.add(char[i]);
      // 被固定的位置和其他位置依次交换位置
      {
        const t = char[n];
        char[n] = char[i];
        char[i] = t;
      }
      // 递归下一个位置
      dsf(n + 1);
      // 被交换的位置需要回溯归位。
      {
        const t = char[n];
        char[n] = char[i];
        char[i] = t;
      }
    }
  };
  dsf(0);
  return res.sort();
};

ZiHao...小于 1 分钟

图的深度与广度优先遍历

深度优先遍历算法口诀

访问根节点
对根节点的没访问过相邻节点挨个进行深度优先遍历
code

const graph = {
  0: [1, 2],
  1: [2],
  2: [0, 3],
  3: [3],
};
const dfs = (n) => {
  console.log(n); //访问根节点
  visted.add(n); //访问过的做一个记录
  graph[n].forEach((item) => {
    if (!visted.has(item)) {
      dfs(item); //递归调用
    }
  });
};
dfs(2);
//结果为   2  0  1  3

ZiHao...大约 1 分钟

顺时针打印矩阵JS版

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function (matrix) {
  if (matrix.length == 0) {
    return [];
  }
  if (matrix[0].length == 0) {
    return [];
  }
  //向右  获取长和宽
  let height = matrix.length;
  let width = matrix[0].length;
  let result = [];
  //向右打印
  for (let i = 0; i < width; i++) {
    result.push(matrix[0][i]);
  }
  //如果有向下的，则向下 不能则返回结果
  if (height > 1) {
    for (let k = 1; k < height; k++) {
      result.push(matrix[k][width - 1]);
    }
  } else {
    return result;
  }

  //如果能向左就向左 不能则返回结果
  if (width > 1) {
    for (let i = width - 2; i >= 0; i--) {
      result.push(matrix[height - 1][i]);
    }
  } else {
    return result;
  }
  //如果能向上 则向上，不能则返回结果
  if (height > 2) {
    for (let i = height - 2; i >= 1; i--) {
      result.push(matrix[i][0]);
    }
  } else {
    return result;
  }
  //剥除里面的矩阵  (循环一次减掉两层高度)
  let inner = new Array(height - 2);
  for (let i = 0; i < height - 2; i++) {
    inner[i] = matrix[i + 1].slice(1, width - 1);
  }
  //递归
  result = result.concat(spiralOrder(inner));
  return result;
};

ZiHao...小于 1 分钟