【12.30】转行小白历险记-刷算法06

发布时间:2023年12月30日

01补充一下:哈希表的基础知识

1. 创建哈希表

在 JavaScript 中,您可以使用对象或 Map 来创建一个哈希表。

  • 使用对象:
let hashTable = {};
  • 使用 Map 对象:
let hashMap = new Map();

2. 插入键值对(Add / Set)

向哈希表中添加键值对。

  • 使用对象:
hashTable[key] = value;
  • 使用 Map 对象:
hashMap.set(key, value);

3. 搜索键值(Get)

根据键获取哈希表中的值。

  • 使用对象:
let value = hashTable[key];
  • 使用 Map 对象:
let value = hashMap.get(key);

4. 检查键是否存在(Check for Key)

检查哈希表中是否存在某个键。

  • 使用对象:
let exists = key in hashTable;
  • 使用 Map 对象:
let exists = hashMap.has(key);

5. 删除键值对(Delete)

从哈希表中删除一个键值对。

  • 使用对象:
delete hashTable[key];
  • 使用 Map 对象:
hashMap.delete(key);

6. 遍历哈希表(Iterate)

遍历哈希表中的所有键值对。

  • 使用对象:
for (let key in hashTable) {
    if (hashTable.hasOwnProperty(key)) {
        console.log(key, hashTable[key]);
    }
}
  • 使用 Map 对象
hashMap.forEach((value, key) => {
    console.log(key, value);
});

7. 获取哈希表大小(Size)

获取哈希表中的键值对数量。

  • 使用对象:需要手动计算。
let size = Object.keys(hashTable).length;
  • 使用 Map 对象:
let size = hashMap.size;

02JS常见数据结构

在 JavaScript 中,数组(Array)、集合(Set)和映射(Map)都是用于存储数据的常见数据结构,但它们各自有不同的特性和用途:

数组(Array)

  1. 有序集合:数组是元素的有序集合,其中每个元素都有一个数字索引。

  2. 重复元素:数组可以包含重复的元素。

  3. 元素类型:数组中的元素可以是任意类型,包括不同类型的混合。

  4. 使用场景:适用于需要顺序访问或快速访问特定索引元素的场景。

  5. 基本操作:添加、删除、访问元素等,以及一系列数组特有的方法(如 mapfilterreduce 等)。

集合(Set)

  1. 无序集合:Set 是无序的集合,不保证元素的顺序。

  2. 唯一元素:Set 中的元素是唯一的,不允许重复。

  3. 元素类型:Set 中的元素可以是任意类型。

  4. 使用场景:适用于需要存储不重复元素、快速检查元素是否存在的场景。

  5. 基本操作:添加、删除元素,以及检查元素是否存在。

映射(Map)

  1. 键值对:Map 存储键值对集合,其中键和值可以是任意类型。

  2. 有序集合:Map 保持键值对的插入顺序。

  3. 唯一键:Map 中的键是唯一的。

  4. 使用场景:适用于需要快速访问、更新或删除键值对的场景。

  5. 基本操作:添加、删除键值对,访问或更新值,以及遍历键值对。

总结

  • 数组(Array):有序集合,可包含重复元素,通过数字索引访问元素。
  • 集合(Set):无序集合,元素唯一,不包含重复元素,常用于去重和快速查找。
  • 映射(Map):键值对集合,保持插入顺序,键唯一,适用于存储和处理相关联的数据。

?03Leetcode:350. 两个数组的交集

下面的代码逻辑是用set实现的,set创建的数据结构是没有重复元素的,所以一旦数组中有重复的元素,会导致输出的结果只有一个比如

输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2]

这个和题意不太符合

在选择数据结构的时候可以选择Map

函数逻辑,适合349的题号

  1. 数组交换(如果需要)

    • 首先,代码检查两个数组的长度。如果 nums1 的长度小于 nums2 的长度,则交换这两个数组。这样做的目的是优化性能,减少后续在较大的数组上进行的查找操作。
  2. 创建 Set 对象

    • nums1Set 是使用 nums1 创建的 Set 对象。由于 Set 中的元素是唯一的,这样可以快速检查一个元素是否存在于 nums1 中。
    • resSet 是一个用来存储最终交集结果的空 Set 对象。
  3. 查找交集

    • 遍历 nums2 中的每个元素。对于 nums2 中的每个元素,检查它是否存在于 nums1Set 中(即是否也是 nums1 的元素)。
    • 如果存在,则将该元素添加到结果集 resSet 中。由于 Set 自动处理重复值,因此即使 nums2 中有重复元素,结果集中也不会有重复
  4. 返回结果

    • 使用 Array.from(resSet) 将结果集 resSet 转换为数组形式,并返回。这是因为 Set 对象不是数组,而题目要求返回数组形式的结果。

示例

假设调用 intersection([1, 2, 2, 1], [2, 2]),函数将执行如下:

  • 由于 [1, 2, 2, 1] 的长度不小于 [2, 2] 的长度,因此不交换数组。
  • 创建 nums1Set{1, 2}
  • 遍历数组 [2, 2],并检查每个元素是否在 nums1Set 中。
  • 2nums1Set 中,因此被添加到 resSet 中。
  • 返回 [2] 作为交集结果。

?正确解法用

用map和数组相结合

04 快乐数

示例 1:检测 19 是否是快乐数

  1. 初始化

    • n = 19
    • seen 集合为空。
  2. 第一次循环

    • 19 不等于 1,且 19 不在 seen 集合中,因此继续执行。
    • 19 添加到 seen 集合中。
    • 计算 19 的各位数的平方和:1*1 + 9*9 = 1 + 81 = 82
    • 更新 n = 82
  3. 第二次循环

    • 82 不等于 1,且 82 不在 seen 集合中。
    • 82 添加到 seen 集合中。
    • 计算 82 的各位数的平方和:8*8 + 2*2 = 64 + 4 = 68
    • 更新 n = 68
  4. 后续几次循环

    • 类似地,计算 68 的各位数平方和得到 100,然后计算 100 的各位数平方和得到 1
    • 更新 n = 1
  5. 结束循环

    • n 等于 1,跳出循环。
  6. 返回结果

    • n === 1true,因此函数返回 true,表示 19 是快乐数。

示例 2:检测 2 是否是快乐数

  1. 初始化

    • n = 2
    • seen 集合为空。
  2. 循环

    • 重复计算 n 的各位数的平方和,并更新 n
    • 每次迭代后检查 n 是否变为 1 或 n 是否已存在于 seen 中。
    • 在计算的过程中,您会发现 n 开始循环(例如,变为之前已经出现过的数字),但永远不会变为 1。
  3. 结束循环

    • 检测到循环,因为 n 的值已经在 seen 集合中出现过。
  4. 返回结果

    • 因为 n 不等于 1,所以函数返回 false,表示 2 不是快乐数。
文章来源:https://blog.csdn.net/TTTT2222111/article/details/135306010
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。