手写代码题【基础篇】

一.如何实现一个深比较函数

首先，需要明确一点：HTML 是一种用于创建网页的标记语言，它并不适合用来实现复杂的逻辑功能，如深比较函数。深比较函数通常用于比较两个对象的值是否相等，包括它们的属性和嵌套对象。

如果要在编程中实现深比较函数，通常会选择使用像 JavaScript、Python、Java 或 C# 这样的语言。这里，我将给出一个使用 JavaScript 实现的深比较函数的例子：

function deepCompare(obj1, obj2) {
    // 确保两者都是对象
    if (typeof obj1 !== 'object' || obj1 === null || typeof obj2 !== 'object' || obj2 === null) {
        return obj1 === obj2;
    }

    // 确保两者是同一类型的对象
    if (Array.isArray(obj1) !== Array.isArray(obj2)) {
        return false;
    }

    // 获取对象的键
    const keys1 = Object.keys(obj1);
    const keys2 = Object.keys(obj2);

    // 如果键的数量不同，则对象不相等
    if (keys1.length !== keys2.length) {
        return false;
    }

    // 比较每个键的值
    for (let i = 0; i < keys1.length; i++) {
        const key = keys1[i];

        // 如果值不相等，或者如果键指向的对象不相等（递归调用 deepCompare）
        if (obj1[key] !== obj2[key] || !deepCompare(obj1[key], obj2[key])) {
            return false;
        }
    }

    // 如果所有键的值都相等，则对象相等
    return true;
}

// 使用示例
const obj1 = { a: 1, b: { c: 2 } };
const obj2 = { a: 1, b: { c: 2 } };
const obj3 = { a: 1, b: { c: 3 } };

console.log(deepCompare(obj1, obj2)); // 输出 true
console.log(deepCompare(obj1, obj3)); // 输出 false

这个 deepCompare 函数可以递归地比较两个对象的所有属性和嵌套对象，以确定它们是否相等。如果两个对象在结构和值上都完全相同，则函数返回 true，否则返回 false。

二.实现数组去重要求三种方式

组去重是一个常见的编程问题，下面我将为你提供三种不同的方式来实现数组去重，这里以 JavaScript 为例：

1. 使用 Set 数据结构

JavaScript 的 Set 数据结构是一种特殊的类型，它只允许存储唯一的值。利用这个特性，我们可以很容易地实现数组去重。

function uniqueArrayWithSet(arr) {
  return [...new Set(arr)];
}

const array = [1, 2, 2, 3, 4, 4, 5];
console.log(uniqueArrayWithSet(array)); // [1, 2, 3, 4, 5]

2.使用 filter 方法

我们可以使用数组的 filter 方法来遍历数组，并检查每个元素是否已经在结果数组中出现过。

function uniqueArrayWithFilter(arr) {
  return arr.filter((item, index) => arr.indexOf(item) === index);
}

const array = [1, 2, 2, 3, 4, 4, 5];
console.log(uniqueArrayWithFilter(array)); // [1, 2, 3, 4, 5]

3. 使用 reduce 方法

reduce 方法也可以用来实现数组去重，它会遍历数组，并将结果累积到一个单一的值中。

function uniqueArrayWithReduce(arr) {
  return arr.reduce((accumulator, currentValue) => {
    return accumulator.includes(currentValue) ? accumulator : [...accumulator, currentValue];
  }, []);
}

const array = [1, 2, 2, 3, 4, 4, 5];
console.log(uniqueArrayWithReduce(array)); // [1, 2, 3, 4, 5]

这三种方法各有优缺点，使用 Set 的方法最简单，但在某些情况下可能会改变原始数组的顺序。使用 filter 和 reduce 的方法则能保留原始数组的顺序，但实现起来稍微复杂一些。你可以根据你的具体需求来选择最适合的方法。

三.实现一个方法用于从数组中随机获取一个值

function getRandomValueFromArray(arr) {
  if (!Array.isArray(arr) || arr.length === 0) {
    throw new Error('Input must be a non-empty array.');
  }
  
  // 生成一个随机索引
  const randomIndex = Math.floor(Math.random() * arr.length);
  
  // 返回随机索引对应的元素
  return arr[randomIndex];
}

// 使用示例
const myArray = [1, 2, 3, 4, 5];
const randomValue = getRandomValueFromArray(myArray);
console.log(randomValue); // 可能会输出数组中的任意一个元素，例如 3

在这个getRandomValueFromArray函数中，我们首先检查输入是否是一个非空数组。如果不是，我们抛出一个错误。然后，我们使用Math.random()生成一个0到1之间的随机数，乘以数组的长度，并使用Math.floor()函数向下取整，以确保我们得到一个有效的数组索引。最后，我们返回该索引对应的数组元素。

四.实现一个方法用于解析 URL 查询字符串

在JavaScript中，解析URL查询字符串通常可以使用内置的URLSearchParams API来实现。但如果你想要一个自定义的函数，以下是一个简单的实现方法，它将查询字符串转换为一个对象，其中键是参数名，值是参数值。

function parseQueryString(queryString) {
  const queryParams = {};
  const pairs = queryString.split("&");

  for (const pair of pairs) {
    const [key, value] = pair.split("=");
    // 如果值存在，则解码
    const decodedValue = value ? decodeURIComponent(value) : "";
    // 如果键存在，则解码
    const decodedKey = key ? decodeURIComponent(key) : "";
    queryParams[decodedKey] = decodedValue;
  }

  return queryParams;
}

// 使用示例
const queryString = "key1=value1&key2=value2&key3=value3";
const parsedParams = parseQueryString(queryString);
console.log(parsedParams);
// 输出: { key1: 'value1', key2: 'value2', key3: 'value3' }

这个函数首先根据&字符将查询字符串分割成多个键值对。然后，它遍历这些键值对，使用split("=")将每个键值对分割成键和值。使用decodeURIComponent函数对键和值进行解码，以处理可能存在的URL编码字符。最后，它将这些键值对存储在一个对象中，并返回这个对象。

请注意，这个函数假定查询字符串是正确格式化的，并且不包含重复的键。如果查询字符串中存在重复的键，这个函数只会保留最后一个键值对。如果你需要处理重复的键，你可以将queryParams的值初始化为一个数组，并在遇到重复的键时将值推入数组中。

五.实现一个无限累加的 sum 函数

实现一个无限累加的 sum 函数在数学上是不可能的，因为无限序列的总和可能是有限的（例如，几何级数 1, 1/2, 1/4, ... 的和是 2），也可能是无限的（例如，算术级数 1, 2, 3, ... 的和是无限大的）。

不过，我们可以实现一个函数，它接受一个函数作为参数，并不断地调用这个函数来累加结果，直到达到某个条件为止。这样的函数在编程中是很常见的，通常用于处理一些需要迭代计算的情况。

下面是一个使用 JavaScript 实现的例子，该函数接受一个返回数字的函数作为参数，并累加该函数返回的值，直到累加值超过某个阈值或者迭代次数超过限制：

function infiniteSum(generator, threshold = Infinity, limit = Infinity) {
  let sum = 0;
  let count = 0;
  
  while (sum < threshold && count < limit) {
    const nextValue = generator();
    sum += nextValue;
    count++;
    
    // 如果累加值超过了阈值或者迭代次数达到了限制，跳出循环
    if (sum >= threshold || count >= limit) {
      break;
    }
  }
  
  return sum;
}

// 使用示例：累加从 1 开始的自然数，直到累加值超过 1000
const sumUpToThreshold = infiniteSum(() => {
  let count = 1;
  return () => count++;
}, 1000);

console.log(sumUpToThreshold); // 输出累加的结果，可能是 1 + 2 + 3 + ... + n 的和，其中 n 的值使得累加和刚好小于或等于 1000

在这个例子中，infiniteSum 函数接受三个参数：

generator 是一个函数，每次调用时返回要累加的下一个值。
threshold 是一个阈值，当累加和超过这个值时，函数将停止累加并返回结果。默认值为 Infinity，表示没有阈值限制。
limit 是一个限制迭代次数的值，当达到这个次数时，函数也会停止累加并返回结果。默认值为 Infinity，表示没有迭代次数限制。

请注意，这个函数并不是真正的“无限累加”，因为它会在达到某个条件时停止。在实际应用中，你需要根据具体需求来确定何时停止累加。

六.实现一个方法用于拍平多维数组

拍平多维数组（也称为将数组展平或扁平化）是将一个包含任意嵌套级别的数组转换为一维数组的过程。在JavaScript中，你可以使用递归或Array.prototype.flat()方法来实现这一功能。以下是两种方法的实现：

1. 使用`Array.prototype.flat()`方法

Array.prototype.flat()方法可以接受一个可选的参数来指定要提取的嵌套数组的最大深度。如果省略该参数或将其设置为Infinity，则会提取所有嵌套数组。

function flattenArray(arr) {
  return arr.flat(Infinity);
}

// 使用示例
const multiDimensionalArray = [1, [2, [3, [4]]]];
const flattenedArray = flattenArray(multiDimensionalArray);
console.log(flattenedArray); // 输出: [1, 2, 3, 4]

2. 使用递归方法

如果你想要一个不使用内置flat()方法的解决方案，你可以使用递归来实现。

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

// 使用示例
const multiDimensionalArray = [1, [2, [3, [4]]]];
const flattenedArray = flattenArrayRecursively(multiDimensionalArray);
console.log(flattenedArray); // 输出: [1, 2, 3, 4]

在这个递归函数中，我们遍历输入的数组。如果遇到一个元素仍然是数组，我们递归调用flattenArrayRecursively函数来拍平这个子数组，并使用concat方法将其结果添加到result数组中。如果元素不是数组，我们直接将其添加到result数组中。

两种方法都可以实现拍平多维数组的目的，你可以根据你的需求和环境来选择最适合的方法。使用Array.prototype.flat()方法通常更简洁，但如果你需要兼容不支持该方法的旧浏览器环境，递归方法会是一个备选方案。

七.实现一个方法用于限制 Promise 的并发数量

要实现一个限制 Promise 并发数量的方法，你可以使用 JavaScript 中的 Promise.all 与 Array.prototype.slice 来结合控制并发数量。以下是一个示例，演示如何创建一个函数，该函数接收一个 Promise 数组和一个并发限制数，然后依次执行这些 Promise，确保在任何时候并发执行的数量不超过限制。

function limitConcurrency(promises, limit) {
  let executingPromises = 0; // 当前正在执行的 Promise 数量
  const pendingPromises = []; // 等待执行的 Promise 数组
  const results = []; // 存储所有 Promise 的结果

  // 执行 Promise 的函数
  function executePromise(promise) {
    return promise.then(result => {
      executingPromises--; // Promise 执行完毕，减少并发数
      results.push(result); // 存储结果
      if (pendingPromises.length > 0) {
        // 如果有等待的 Promise，则继续执行
        executePromise(pendingPromises.shift());
      }
    });
  }

  // 添加 Promise 到等待队列，并尝试执行
  function addPromise(promise) {
    pendingPromises.push(promise);
    if (executingPromises < limit && pendingPromises.length > 0) {
      // 如果并发数未达限制且有等待的 Promise，则执行
      executePromise(pendingPromises.shift());
    }
  }

  // 遍历所有 Promise，添加到等待队列
  promises.forEach(addPromise);

  // 返回一个 Promise，在所有 Promise 都执行完毕后 resolve
  return Promise.all(results);
}

// 使用示例
const promises = [
  new Promise(resolve => setTimeout(resolve, 1000, 'result 1')),
  new Promise(resolve => setTimeout(resolve, 500, 'result 2')),
  new Promise(resolve => setTimeout(resolve, 800, 'result 3')),
  // 更多 Promise...
];

const limit = 2; // 限制并发数量为 2

limitConcurrency(promises, limit)
  .then(results => {
    console.log(results); // ['result 2', 'result 3', 'result 1']
  })
  .catch(error => {
    console.error('An error occurred:', error);
  });

在这个示例中，limitConcurrency 函数接收一个 Promise 数组和一个并发限制数。它维护了一个 executingPromises 计数器来跟踪当前正在执行的 Promise 数量，一个 pendingPromises 数组来存储等待执行的 Promise，以及一个 results 数组来存储所有 Promise 的结果。

当一个新的 Promise 被添加到等待队列时，它会检查当前是否有未达到并发限制并且还有等待的 Promise。如果是，则它会从等待队列中取出一个 Promise 来执行，并更新 executingPromises 计数器。当 Promise 执行完毕时，它会减少 executingPromises 计数器，并检查是否有更多的等待 Promise 可以执行。

最后，limitConcurrency 函数返回一个 Promise.all(results)，这样调用者可以等待所有 Promise 完成并获得结果数组。

八.手写 bind 方法用于模拟 JavaScript 中的 bind 方法

在JavaScript中，Function.prototype.bind() 方法创建一个新的函数，当这个新函数被调用时，bind() 的第一个参数将作为它运行时的 this，之后的一序列参数将会在传递的实参前传入作为它的参数。

下面是一个简单的手写 bind() 方法的实现：

Function.prototype.myBind = function(context) {
    var self = this; // 保存原函数
    // 获取bind()第二个及以后的参数
    var args = Array.prototype.slice.call(arguments, 1); 
    // 返回一个新函数
    return function() {
        // 获取bind返回的函数传入的参数
        var bindArgs = Array.prototype.slice.call(arguments);
        // 执行原函数，并返回结果
        return self.apply(context, args.concat(bindArgs));
    }
}

九.使用二分法对数组排序

二分法通常用于搜索而不是排序。在排序数组中，二分法可以高效地找到某个元素的位置。然而，如果你想使用二分法来排序一个数组，你可能是指使用类似快速排序的分而治之策略，而不是简单的二分搜索。

快速排序是一个使用分而治之策略的排序算法。其基本思想是选择一个“基准”元素，然后将数组分为两部分：一部分是小于基准的元素，另一部分是大于基准的元素。然后，对这两部分分别进行快速排序。

以下是一个使用 JavaScript 实现的快速排序算法：

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pivotIndex = partition(arr, low, high);
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
  }
  return arr;
}

function partition(arr, low, high) {
  const pivot = arr[high];
  let i = low - 1;
  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

const array = [3, 7, 2, 5, 6, 4, 1];
console.log(quickSort(array)); // 输出 [1, 2, 3, 4, 5, 6, 7]

在这个例子中，quickSort 函数是主要的排序函数，它使用 partition 函数来选择一个基准，并将数组分为两部分。然后，它递归地对这两部分进行排序。partition 函数选择最后一个元素作为基准，然后将所有小于基准的元素移到基准的左边，所有大于基准的元素移到基准的右边。最后，它返回基准的新位置。

需要注意的是，虽然快速排序在最坏的情况下（当输入数组已经排序或逆序时）的时间复杂度为 O(n^2)，但在平均情况下，它的时间复杂度为 O(n log n)，这使它成为非常高效的排序算法之一。

十.给定一个数组它的第 i 个元素是一支给定的股票在第 i 天的价格

要求：设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。示例 1: 输入：prices = [3,3,5,0,0,3,1,4] 输出：6 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天（股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。示例 2：输入：prices = [1,2,3,4,5] 输出：4 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。示例 3：输入：prices = [7,6,4,3,1] 输出：0 解释：在这个情况下, 没有交易完成, 所以最大利润为 0。示例 4：输入：prices = [1] 输出：0 提示: 1 <= prices.length <= 105 0 <= prices[i] <= 105

要计算可以进行最多两笔交易的最大利润，我们可以使用动态规划的方法。我们可以定义四个变量来跟踪四个关键状态：

buy1：第一次买入股票后的最大利润
sell1：第一次卖出股票后的最大利润
buy2：第二次买入股票后的最大利润
sell2：第二次卖出股票后的最大利润

接下来，我们可以根据这些状态之间的关系来更新它们：

buy1[i] 是在第 i 天买入股票后的最大利润，这取决于前一天的最大利润和当天是否选择买入（即 buy1[i] = Math.max(buy1[i-1], sell1[i-1] - prices[i])）
sell1[i] 是在第 i 天卖出股票后的最大利润，这取决于前一天的最大利润和当天是否选择卖出（即 sell1[i] = Math.max(sell1[i-1], buy1[i-1] + prices[i])）
buy2[i] 是在第 i 天第二次买入股票后的最大利润，这取决于前一天的最大利润和当天是否选择买入（即 buy2[i] = Math.max(buy2[i-1], sell1[i-1] - prices[i])）
sell2[i] 是在第 i 天第二次卖出股票后的最大利润，这取决于前一天的最大利润和当天是否选择卖出（即 sell2[i] = Math.max(sell2[i-1], buy2[i-1] + prices[i])）

最后，最大利润即为 sell2[prices.length - 1]，即最后一次卖出股票后的最大利润。

下面是相应的 JavaScript 实现：

function maxProfit(prices) {
  const n = prices.length;
  if (n < 2) return 0; // 如果数组长度小于2，则无法进行交易，返回0

  let buy1 = -prices[0]; // 第一次买入股票后的最大利润
  let sell1 = 0; // 第一次卖出股票后的最大利润
  let buy2 = -prices[0]; // 第二次买入股票后的最大利润
  let sell2 = 0; // 第二次卖出股票后的最大利润

  for (let i = 1; i < n; i++) {
    // 更新第一次买入和卖出的最大利润
    buy1 = Math.max(buy1, sell1 - prices[i]);
    sell1 = Math.max(sell1, buy1 + prices[i]);

    // 更新第二次买入和卖出的最大利润
    buy2 = Math.max(buy2, sell1 - prices[i]);
    sell2 = Math.max(sell2, buy2 + prices[i]);
  }

  return sell2; // 返回最终的最大利润
}

// 示例测试
console.log(maxProfit([3, 3, 5, 0, 0, 3, 1, 4])); // 输出 6
console.log(maxProfit([1, 2, 3, 4, 5])); // 输出 4
console.log(maxProfit([7, 6, 4, 3, 1])); // 输出 0
console.log(maxProfit([1])); // 输出 0

这个算法的时间复杂度是 O(n)，其中 n 是数组的长度，因为只需要遍历一次数组。空间复杂度也是 O(1)，因为我们只需要存储四个变量来跟踪状态。