代码随想录一刷笔记_哈希表

60+在408的算法考察难度和深度上还是收手了👍）

哈希表理论基础

哈希表用于快速判断一个元素是否出现在集合里，是一种用空间换时间的方法。

当数据通过函数映射到同一位置时，会出现哈希碰撞的现象，一般有线性探测法和拉链法两种办法应对。

数组、set、map三种数据结构的适用情况：

  • 数组：适用于数据量小，数据集中的情况
  • set：适用于数据量大、数据离散的情况
  • map：适用于数据量大，需要存储键值对的情况

有效的字母异位词（242）

这一道题只定义一个数组即可解决。

①遍历两串字母，将遇到的字母填入对应的哈希表序列

②遍历数组，查找是否有异位的字母。

  • tips：相关题目找到字符串中所有字母异位词（438）中，需要考虑避免下标越界的问题。（似乎本题还可以使用滑动窗口的思想）

两个数组的交集（349）

这一题主要是科普了set这类数据结构 & 范围for循环的语法。

  • set

    • 适合使用set的情况：数据很多、数值很分散的情况。（PS：如果需求对重复数据有特别要求需慎重考虑 unordered_set！）

    • 用set这种数据结构存储数据可以实现去重的效果。

      1
      2
      3
      4
      5
      // 定义一个 unordered_set 类型数据结构
      unordered_set<int> result_set;

      // 将num1容器中的数据存入 nums_set 中时，能够实现去重 & 排序 功能
      unordered_set<int> nums_set(num1.begin(), num1.end());

  • 范围for循环

    • 提供了一种简洁的方式遍历容器（数组，vector，list）中的元素

    • 局限：不能提供索引值

      1
      2
      3
      for (declaration: range) {
          ....
      }

快乐数（202）

由于不知道输入的数据大小，所以如果使用数组的话需要留很大的冗余。故，这类题目更适合使用set这种数据结构回答。

set提供了一个成员函数find()，用于在容器中查找特定的元素，返回值取决于查找操作的结果：

  • 如果找到了指定的元素，find()函数会返回一个指向该元素的迭代器；

  • 如果没有找到指定的元素，find()函数会返回容器的end()迭代器。

    • end()迭代器是一个哨兵值，其不指向容器中的任何元素，而是作为一个标记，表示容器的末尾。

    • 在遍历容器时，通常使用end()迭代器来表示何时停止遍历。

      1
      2
      // 判断计算得到的数据是否已经出现过
      set.find(sum) != set.end();

两数之和（1）

这一题的需求是需要存储考虑存储数组index以及数据，所以适用map这种数据结构。

  • auto关键字：

    auto是在c++11标准中引入的，用于自动推导变量的类型。

    1
    2
    3
    // 在这一行代码中，iter的类型应该是 std::map<Key, T>::iterator
    // 在这一行代码中，map.find() 方法寻找的是键为 target - nums[i] 的元素。（关键字是唯一的！）
    auto iter = map.find(target - nums[i]);

  • unordered_map

    • 访问map中value的值

      1
      2
      3
      4
      5
      6
      7
      // 在这里，iter表示指向map的一个有效元素
      // iter->first 表示访问迭代器iter所指向元素的键部分
      // iter->second 表示访问迭代器iter所指向的元素的值部分
      auto iter = map.find(target - nums[i]); 
      if(iter != map.end()) {
      	return {iter->second, i};
      }

    • insert方法

    1
    2
    3
    4
    // insert方法
    // pair<int, int>(a, b) 创建了一个临时的 std::pair 对象
    // insert需要一个pair类型的参数，而不是两个单独的值
    map.insert(pair<int, int>(a + b, c));

四数相加Ⅱ（454）

这一题如果使用暴力解法的话是需要四层for循环，时间复杂度是O(n^4)。故，我们需要对其进行降重操作（采用nums1和nums2，nums3和nums4两两相加的方式）。

接下来的问题是采用哪一种数据结构：

  • 首先在定义里，数组中的值的大小达到了2^28，存在数据量过大以及数据过于分散的问题，故排除使用数组；
  • 然后我们需要计算所有和为0的情况，涉及重复数据的计算，所以需要额外的一个变量来记录有几个重复的值。

故，这一题使用map更合理一些，一个变量用来存储两两相加的结果，另一个变量用来存储这个结果出现的次数。

赎金信（383）

这一题只涉及26个字母，数据量不大，但是涉及到对重复数据的计数，故，可以使用数组和map两种数据结构。

1
2
3
4
5
6
7
8
9
// 范围for循环中的问题
// 在这一题中，遍历的是String类型的字符串，使用char类型进行遍历后，在循环体中c赋值得到的是magazine中每一个的字符。
	string magazine='xxx';
	for (char c: magazine)
    {
        // ....
        // 进行 c-'a'操作时，会直接转换为asall码计算。
        num[c - 'a']++;
    }

三数之和（15）

这一题有两个需要注意的点：

  1. 降低时间复杂度。使用暴力枚举的话需要n^3的时间复杂度，修改思路是降成两重循环 + 查找需要的第三个数是否存在
  2. 去重。数组中是可能存在重复的数字的，所以需要考虑如何去除重复的数据。

①暴力方法：三重循环

（使用这种方法，就没有想过能通过力ToT。）

时间复杂度先不谈，使用这种方法主要考虑如何去重。 => 先对数组进行排序，然后在遍历时，如果遍历到的数据（除了当前循环的第一个数据）和前一个数据相同，就跳过处理。

②使用模板进行降重

由暴力方法，已经成功实现了去重的工作，接下来需要考虑的就是如何降低复杂度。 => 使用set和map进行处理。

  1. 在我实现的方法中，使用了双重循环 & map 方法。对于map中存储的第三个数需要注意这一个点：

    • 第三个数的index是否是在前两个之后（之前已排序）。

    针对这一个点，需要判定：

    • map中是否能够查询到需要的第三个数

    • map中该值的value值是否为0

      • 如果第三个数和第二个数相同，value >1

    用时有点高，仅击败5.01%….

  2. 在讲解的方法中，对更多的细节进行了判断，降低了时间。

    • 因为数组已排序，如果第一个数大于0，则表明已经g了
    • 使用了 set 方法，具体操作是
      • 两层for循环遍历的是第一个数和第三个数，将第二个数据存在set中，进行遍历，若使用过则删除
      • 需要考虑去除重复的三元组
    • 这种方法效率也不是很高

③使用双指针（nb👈(ﾟヮﾟ👈)）

题解推荐使用双指针的方法，将三重for循环降到了一重，并且需要考虑的条件也少了许多。具体如下：

  • 首先，也是需要对数组进行排序操作。
  • 遍历的是最左边的数（就是三元组中最小的数，序号为i），并且令left指针指向i+1，right指针指向nums.size() - 1。
  • 如果三个数相加和>0,则对right指针进行操作；如果三个数相加小于0，则对left指针进行操作；直到left=right。
    • 在这个过程中，也需要考虑指针指到的数值是否存在重复的情况。

四数之和（18）

处理n数之和的问题，解决方法大体是进行 n - 2 重 for 循环，然后最后两个数据使用双指针法进行遍历。

遇到的一些问题：

  1. 剪枝处理方法：（令第一个数为i，第二个数为j）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    // 第一重剪枝
    // 确保nums[i] 以及 nums[i] + nums[j] 满足大于等于0是因为
    // 如果是负数，会导致单个数大于target，但是最终相加结果可能等于target的情况
    // ! 两个负数相加，可能会变得更小！！
    if (nums[i] > target && nums[i] >= 0) break;

    // 第二重剪枝
    // 其中，nums[i] + nums[j] >= 0 的条件可以优化为 => nums[j] >= 0
    if (nums[i] + nums[j] > target && nums[i] + nums[j] >= 0) break;

  2. 越界问题：

    这题中有些用例的数值是超过了int的界限的，所以需要用long类型的数据接收四个数的和。

    此处，需要注意类型转化的时机和方式：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    // 方式1
    // 由于四个数为int类型，所以等式右边的求和类型为int类型的，然后将这个值转化为long类型的数据
    // 显然，右边求和的结果存在越界的情况，需要注意一下
    long sum = nums[i] + nums[j] + nums[left] + nums[right];

    // 方式2
    // 这里使用了显式类型转换 (long)，将 nums[i] 转换为 long 类型
    // 由于 nums[i] 已经被转换为 long 类型，后续的加法操作也会在 long 类型上进行，因此整个表达式的结果会被自动提升为 long 类型
    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
LeetCode > 代码随想录
#Notes #LeetCode #Data structure #Algorithm #C++
代码随想录一刷笔记_哈希表
http://example.com/2024/09/08/code-3-hashtable/
作者
Poivre
发布于
2024年9月8日
许可协议