LeetCode 刷题笔记（2）

一、前言

LeetCode - JavaScript 专栏刷题笔记第二篇。

第一篇刷题笔记详见：LeetCode 刷题笔记（1）

二、算法题目

1. 复合函数

LeetCode地址：2629. 复合函数

请你编写一个函数，它接收一个函数数组 [f1, f2, f3，…， fn] ，并返回一个新的函数 fn ，它是函数数组的 复合函数 。

[f(x)， g(x)， h(x)] 的 复合函数 为 fn(x) = f(g(h(x))) 。

一个空函数列表的 复合函数 是 恒等函数 f(x) = x 。

你可以假设数组中的每个函数接受一个整型参数作为输入，并返回一个整型作为输出。

思路

这道题并不难，但是有一个用的比较少的 API 可以直接实现，所以拿出来讲一讲。

这道题乍一看有点难以理解，实际就是给你一个初始值 x, 然后从右至左以此执行。

那么我们从数组末尾往前遍历，每次将最新的值更新到 x ，用于下次执行传入即可。

类似 Array#reduce 的 API 是 Array#reduceRight 。与 reduce 的遍历顺序相反，是从右至左累计和的一个 API ，这道题可以直接使用 reduceRight 解决。

具体实现

方法一：遍历

/**
 * @param {Function[]} functions
 * @return {Function}
 */
var compose = function(functions) {
 return function(x) {
      for(let i = functions.length - 1; i >= 0; i--) {
          x = functions[i](x)
      }
      return x;
    }
};

方法二：reduceRight

/**
 * @param {Function[]} functions
 * @return {Function}
 */
var compose = function(functions) {
 return function(x) {
      return functions.reduceRight((total, fn) => fn(total), x);
    }
};

2. 分组

LeetCode地址：2631. 分组

请你编写一段可应用于所有数组的代码，使任何数组调用 array.groupBy(fn) 方法时，它返回对该数组 分组后 的结果。

数组分组是一个对象，其中的每个键都是 fn(arr[i]) 的输出的一个数组，该数组中含有原数组中具有该键的所有项。

提供的回调函数 fn 将接受数组中的项并返回一个字符串类型的键。

每个值列表的顺序应该与元素在数组中出现的顺序相同。任何顺序的键都是可以接受的。

请在不使用 lodash 的 _.groupBy 函数的前提下解决这个问题。

思路

比较初级的题，实际开发中会遇到类似功能比较多，仅仅考察了一下哈希表的使用。

这道题的要求是，根据传入的 fn 函数的结果进行分组，图中示例给的已经很清楚了，不在多解释。

我们直接根据 fn(item) 的不同结果的存入数组就可以了。

具体实现

/**
 * @param {Function} fn
 * @return {Array}
 */
Array.prototype.groupBy = function(fn) {
    const map = {};
    this.forEach( item =>{
      const key = fn(item);
      if(!map[key]) {
          map[key] = [item];
      }else{
          map[key].push(item)
      }
    })
 return map
};

/**
 * [1,2,3].groupBy(String) // {"1":[1],"2":[2],"3":[3]}
 */

3. 柯里化

LeetCode地址：2632. 柯里化

请你编写一个函数，它接收一个其他的函数，并返回该函数的 柯里化 后的形式。

柯里化 函数的定义是接受与原函数相同数量或更少数量的参数，并返回另一个 柯里化 后的函数或与原函数相同的值。

实际上，当你调用原函数，如 sum(1,2,3) 时，它将调用 柯里化 函数的某个形式，如 csum(1)(2)(3)， csum(1)(2,3)， csum(1,2)(3)，或 csum(1,2,3) 。所有调用 柯里化 函数的方法都应该返回与原始函数相同的值。

思路

柯里化是一种关于函数的高阶技术，他不仅被用于 Javascript，还被用于其他编程语言。

柯里化可以将一个函数从可调用的 sum(1,2,3) 转换成可调用的 f(1)(2)(3)。

也就是说：柯里化将原本一个一次性接受多参数的函数，转换为多次接受部分参数的函数，这种转换过程涉及到将原始函数的参数拆分为多个部分，并返回一个新的函数，每次接受一些参数，直到接受完所有参数并执行原始函数。

实现该方法的关键点是一个不常用的属性：fn.length , 在 JS 中函数自带的 length 属性返回的该函数的参数个数。

解释完柯里化的作用及关键的 fn.length 属性，想实现就不难了。

既然柯里化是需要等到接受完所有的参数再返回结果，那么我们维护一个数组，将每次传入的参数存入数组中，直到 参数各数 === fn.length 再将 fn(参数列表) 的执行结果返回即可。

具体实现

/**
 * @param {Function} fn
 * @return {Function}
 */
var curry = function(fn) {
 // 缓存已经传入的参数列表
    const argList = [];
    return function curried(...args) {
      argList.push(...args);
      // 判断参数个数是否满足要求
      if(argList.length === fn.length) {
        return fn(...argList);
      }
      // 不满足要求再次返回柯里化函数
      return curried;
    };
};

/**
 * function sum(a, b) { return a + b; }
 * const csum = curry(sum);
 * csum(1)(2) // 3
 */

4. 将对象转换为 JSON 字符串

LeetCode地址：2633. 将对象转换为 JSON 字符串

现给定一个对象，返回该对象的有效 JSON 字符串。你可以假设这个对象只包括字符串、整数、数组、对象、布尔值和 null。返回的字符串不能包含额外的空格。键的返回顺序应该与 Object.keys() 的顺序相同。

请你在不使用内置方法 JSON.stringify 的前提下解决这个问题。

思路

前端基本功：手写 JSON.stringify

手写简化版的 JSON.stringify 并不难，只要将题目要求中的几个不同类型的数据考虑到，分类处理好即可。

根据题目要求，转换成 JSON 字符串有主要有 5 类不同的数据需要分别判断

null 值：需要手动转换成 null 字符串，否则会在处理数组或对象中遇到会直接成为空，同时 null 会被判定为 object 类型。
字符串类型：字符串需要手动拼接 \", 否则在拼接字符串时不会保留双引号
基本类型：如 boolean, number 直接保持原值即可。
数组：考虑到数组中可能包含对象、数组，所以需要递归遍历每一项处理好后进行拼接
对象：同样，也需要考虑对象中包含数组及对象，也需要进行递归处理

为了简化拼接字符串的代码量，我们直接通过模板字符串进行拼接即可。

具体实现

/**
 * @param {any} object
 * @return {string}
 */
var jsonStringify = function(object) {
 // 处理 null 值
    if(object === null) return "null"
    // 处理基本类型
    if(typeof object !== 'object') {
        return typeof object === 'string' ?  `\"${object}\"` : object;
    }
    // 处理数组类型
    if(Array.isArray(object)) {
        return `[${object.map(jsonStringify)}]`
    }
    // 处理对象类型
    return `{${Object.keys(object).map((key)=> `\"${key}\":${jsonStringify(object[key])}`)}}`
};

5. 两个对象之间的差异

LeetCode地址：2700. 两个对象之间的差异

请你编写一个函数，它接收两个深度嵌套的对象或数组 obj1 和 obj2 ，并返回一个新对象表示它们之间差异。

该函数应该比较这两个对象的属性，并识别任何变化。返回的对象应仅包含从 obj1 到 obj2 的值不同的键。对于每个变化的键，值应表示为一个数组 [obj1 value, obj2 value] 。不存在于一个对象中但存在于另一个对象中的键不应包含在返回的对象中。在比较两个数组时，数组的索引被视为它们的键。最终结果应是一个深度嵌套的对象，其中每个叶子的值都是一个差异数组。

你可以假设这两个对象都是 JSON.parse 的输出结果。

思路

该题要求比对两个对象，并将原值与修改后的值作为一个数组返回，如果是新增或者删除的属性，直接忽略不做处理。

假设有以下两个对象：

1 2	`o1 = { a: 1, b: 2} o2 = { a: 3, b: 2}`

我们根据上面两个对象可以比对出属性 a 发生了变化，那么我们返回 {a:[1, 3]} 即可。

处理 JSON 的题，基本类似，无非考察递归的掌握与数据类型的控制，我们根据一下几个特征进行判断即可。

如果 obj1 和 obj2 不是同一类型，直接返回 [obj1,obj2]
如果 obj1 和 obj2 是都是基本类型时，直接判断结果，如果不一致则返回[obj1, obj2]
如果二者都是引用类型，则调用 objDiff(obj1[key], obj2[key]) 递归校验。

具体实现

/**
 * @param {object} obj1
 * @param {object} obj2
 * @return {object}
 */
function objDiff(obj1, obj2) {
  // 如果 key 已经被删除，不做处理
  if(obj2 === void 0) return void 0;
  // 如果是基本类型，或者两个对象的类型不一样，则直接返回比对后的结果
  // 注：对象类型不一样，值一定不一样
  if(typeof obj1 !== 'object' || obj1 === null || isNotEqualsType(obj1, obj2)) {
    return obj1 === obj2 ? void 0 : [ obj1, obj2 ];
  }
  // 保存比对后的结果
  const diffMap = {};
  for(const key of Object.keys(obj1)){
 // 递归比对当前 key 是否一致
    const diff = objDiff(obj1[key], obj2[key]);
    // 如果是 undefined 或者 对象是空的，则说明对象是一致的
    if(diff !== void 0 && Object.keys(diff).length) {
      diffMap[key] = diff;
    }
  }
  return diffMap;
};
const getType = (val) => Object.prototype.toString.apply(val);
const isNotEqualsType = (val1 , val2) => getType(val1) !== getType(val2);

三、结语

由于算法讲解本身就很难通过少量的语言就能表述清除，让文字通俗易懂更是难上加难，为了避免篇幅太长而导致放弃或者直接丢到收藏夹中吃灰，所以本篇只提取了 5 道题进行讲解。

算法的实现本身就多种多样的，我的个人见解未必是最优解，我非常欢迎读者对我在文章中提出的观点、方法或示例进行评价和反馈。这对于我个人的成长和进步非常重要，也有助于确保我传达的信息准确无误。所以，请不要犹豫，如果你有任何想法或建议，请在阅读文章后留下你的评论。

编程素养相关 > 数据结构与算法 > JavaScript 专栏

#JavaScript #LeetCode

LeetCode 刷题笔记（2）

https://blog.pangcy.cn/2023/07/12/编程素养相关/数据结构与算法/JavaScript 专栏/LeetCode 刷题笔记（2）/

作者

子洋

发布于

2023年7月12日

许可协议

CSS 实现 3D 书本动效上一篇

LeetCode 刷题笔记（1）下一篇