手写深拷贝 | 香蕉，你个卟啦啦

# 手写深拷贝

function deepCopy(obj) {
  if (obj === null || typeof obj !== "object") return obj;
  if (obj instanceof Date) return new Date(obj);
  if (obj instanceof RegExp) return new RegExp(obj);
  let newObj = new obj.constructor();
  for (const key in obj) {
    if (Object.hasOwnProperty.call(obj, key)) {
      newObj[key] = deepCopy(obj[key]);
    }
  }
  return newObj;
}

# 手写防抖、节流

// 防抖
function debounce(fn, wait) {
  let timeouter = null;
  return function () {
    const _this = this;
    const args = arguments;
    if (timeouter) {
      clearTimeout(timeouter);
    }

    timeouter = setTimeout(function () {
      fn.apply(_this, args);
    }, wait);
  };
}

// 节流
function throttle(fn, wait) {
  let timeouter = null;
  return function () {
    const _this = this;
    const args = arguments;
    if (!timeouter) {
      timeouter = setTimeout(function () {
        fn.apply(_this, args);
        timeouter = null;
      }, wait);
    }
  };
}

# 手写拍平数组

Array.prototype.flattenArray = function () {
  const result = [];
  for (let i = 0; i < this.length; i++) {
    if (Array.isArray(this[i])) {
      result = result.concat(flattenArray(this[i]));
    } else {
      result.push(this[i]);
    }
  }
  return result;
};

# 手写冒泡排序

算法思想：判断两个相邻元素，大于则交换位置
算法步骤

从数组中第一个数开始，依次与下一个数比较并次交换比自己小的数，直到最后一个数。如果发生交换，则继续下面的步骤，如果未发生交换，则数组有序，排序结束，此时时间复杂度为 O(n)；每一轮”冒泡”结束后，最大的数将出现在乱序数列的最后一位。重复步骤（1）

算法平均复杂度：n(n^2)

冒泡排序

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        var num = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = num;
      }
    }
  }
  return arr;
}

# 快速排序

算法思想：取一个基准值，比基准值小的在左边，大的在右边；左右在继续这样的操作，最后合并。
算法步骤：

从待排序的 n 个记录中任意选取一个记录（通常选取第一个记录）为分区标准; 把所有小于该排序列的记录移动到左边，把所有大于该排序码的记录移动到右边，中间放所选记录，称之为第一趟排序然后对前后两个子序列分别重复上述过程，直到所有记录都排好序。

算法平均复杂度：n(n log n)

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const left = [];
  const right = [];
  const mid = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < mid) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return [...quickSort(left), mid, ...quickSort(right)];
}

# 选择排序

算法思想：从所有记录中选出最小的一个数据元素与第一个位置的记录交换；然后在剩下的记录当中再找最小的与第二个位置的记录交换，循环到只剩下最后一个数据元素为止。
算法平均复杂度：n(n^2)

function chooseSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] > arr[j]) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
      }
    }
  }
}

# 插入排序

算法思想：从待排序的 n 个记录中的第二个记录开始，依次与前面的记录比较并寻找插入的位置，每次外循环结束后，将当前的数插入到合适的位置。
算法平均复杂度：n(n^2)

Array.prototype.myinsertionSort = function () {
  for (let i = 1; i < this.length; i++) {
    let temp = this[i];
    let j = i;
    for (j; this[j - 1] > temp; j--) {
      this[j] = this[j - 1];
    }
    this[j] = temp;
  }
  console.log(this);
};

# 归并排序

算法思想：将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
算法平均复杂度：n(n log n)

归并排序

function merge(left, right) {
  var result = [];
  while (left.length > 0 && right.length > 0) {
    if (left[0] < right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  return result.concat(left, right);
}

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  var mid = Math.floor(arr.length / 2);
  var left = mergeSort(arr.slice(0, mid));
  var right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

# 上楼梯

一个人上楼梯，可以一次上一阶，也可以一次上两阶，现在一个 10 阶的楼梯，有多少种上法？（@hk）

这是一个典型的斐波那契数列问题。设 f(n) 表示上 n 阶楼梯的上法总数，那么有以下两种情况：

当第一步上了一阶楼梯时，剩下的 n-1 阶楼梯的上法总数为 f(n-1)。
当第一步上了两阶楼梯时，剩下的 n-2 阶楼梯的上法总数为 f(n-2)。
因此，上 n 阶楼梯的上法总数为 f(n) = f(n-1) + f(n-2)。

递归求解斐波那契数列的时间复杂度为 O(2^n)，显然不够高效。可以通过迭代的方式来优化算法，具体实现如下：

function climbStairs(n) {
  if (n <= 2) {
    return n;
  }

  let prev1 = 1,
    prev2 = 2,
    curr = 0;

  for (let i = 3; i <= n; i++) {
    curr = prev1 + prev2;
    prev1 = prev2;
    prev2 = curr;
  }

  return curr;
}

在上述代码中，使用三个变量 prev1、prev2 和 curr 来缓存每一步的计算结果，避免了递归带来的重复计算。时间复杂度为 O(n)，空间复杂度为 O(1)。

因此，上 10 阶楼梯的上法总数为：

console.log(climbStairs(10)); // 输出 89

因为可以一次上一阶或者两阶，所以有 89 种上法。

# 求组合

有一个数组，比如[1, 2, 3, 5, 7, 9, 11, 12, 13, 15, 19, 21, 25, 27]，任意给一个 k 值，找出数组里面任意两个数字相加等于 k 的组合

// 时间复杂度O(n2)
const fin = [];
const k = 8;
const array = [1, 2, 3, 5, 7, 9, 11, 12, 13, 15, 19, 21, 25, 27];
for (let i = 0; i < array.length; i++) {
  for (let j = i + 1; j < array.length - 1 - i; j++) {
    if (array[i] + array[j] === k) {
      fin.push([array[i], array[j]]);
    }
  }
}
console.log(fin);

# 统计字符数

字符串计数，用 map 实现，延伸一下求最多的字符，统计 map 中 value 最大的。

function countChar(str) {
  const charMap = new Map();
  for (const char of str) {
    charMap.set(char, charMap.get(char) + 1 || 1);
  }
  return charMap;
}

← 题库