万能开头

#include<bits/stdc++.h>
using namespace std;

在 C++ 中，using namespace std;指令允许用户使用 std 命名空间中的所有标识符，而无需在它们前面加上 std::。

leetcode hot 100

hash

1. 两数之和

   题目描述：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

   方法：找数 x，寻找数组中是否存在 target - x。

   使用哈希表，可以将寻找 target - x的时间复杂度降低到从 O(N) 降低到 O(1) —— 创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x插入到哈希表中，即可保证不会让 x和自己匹配。

   class Solution {
   public:
       vector<int> twoSum(vector<int>& nums, int target) {
           unordered_map<int, int> hashtable;
           for (int i = 0; i < nums.size(); ++i) {
               auto it = hashtable.find(target - nums[i]);
               if (it != hashtable.end()) {
                   return {it->second, i};
               }
               hashtable[nums[i]] = i;
           }
           return {};
       }
   };

1. find 方法

   find 是哈希表的一个成员函数，用于查找指定的键（key）。它的作用是：

   • 如果哈希表中存在该键，则返回一个指向该键值对的迭代器。
   • 如果哈希表中不存在该键，则返回 hashtable.end()，表示未找到。

2. auto it

   • auto 是 C++11 引入的关键字，用于自动推导变量的类型。

     在这里，it 的类型会被推导为哈希表迭代器的类型（例如 std::unordered_map<int, int>::iterator）。

   • it 是一个迭代器，指向哈希表中找到的键值对（如果找到的话）。

3. return {it->second, i};

  C++11 引入的一种语法特性，称为**初始化列表**（initializer list）。它用于**返回一个包含多个值的对象**。

  1. **`it->second`** 表示迭代器指向的键值对中的值（value）。

     在哈希表中，键值对的形式是 `{key, value}`，`it->second` 就是 `value`。

  2. **`{it->second, i}`**是一个初始化列表，用于构造一个包含两个值的对象。

  3. **`return`**
     - 返回单个值时，直接写值。
     - 返回容器或对象时，可以使用 `{}` 构造返回值。
     - 返回空容器时，使用 `{}`。

2. 字母异位词分组

   题目描述：给定一个字符串数组，请将 字母异位词 组合在一起。可以按任意顺序返回结果列表。（字母异位词 是由重新排列源单词的所有字母得到的一个新单词）

   方法：模式识别 - 一旦根据特征排序，想到散列表。

   排序。由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。

   class Solution {
   public:
       vector <vector<string>> groupAnagrams(vector<string>& strs) {
           unordered_map<string, vector<string>> mp;
           for (string& str: strs) {
               string key = str;
               sort(key.begin(), key.end());
               mp[key].emplace_back(str);
           }
           vector<vector<string>> ans;
           for (auto it = mp.begin(); it != mp.end(); ++it) {
               ans.emplace_back(it->second);
           }
           return ans;
       }
   };
   

   1. *和& 分别用于表示指针和引用

      • \*：
        1. 用于声明指针，例如 int* p; 表示 p 是一个指向 int 的指针。
        2. 用于解引用指针，例如 *p 表示 p 指向的 int 值。
      • &：
        1. 用于声明引用，例如 int& r = x; 表示 r 是 x 的引用。
        2. 用于取地址，例如 int* p = &x; 表示 p 是 x 的地址。
      • vector<string>：
        1. vector<string>& strs 表示一个存储 string 对象的向量的引用。避免不必要的拷贝，并且可以直接修改原始数据。
        2. vector<string*>& strs 表示一个存储 string 指针的向量的引用。

   2. sort(key.begin(), key.end());

      • key.begin() 和 key.end()：

        1. key.begin() 返回一个指向 key 第一个字符的迭代器。
        2. key.end() 返回一个指向 key 末尾（最后一个字符的下一个位置）的迭代器。
        3. 这两个迭代器定义了排序的范围，即从 key 的第一个字符到最后一个字符。

      • sort 函数：

        1. sort 是C++标准库 <algorithm> 中的一个函数，用于对范围内的元素进行排序。
        2. 它的默认行为是将元素按升序排列（从小到大）。
        3. 对于字符串 key，sort 会将其中的字符按ASCII值从小到大重新排列。

      • 举个例子

        假设 key 的初始值是 "cba"，那么：

        string key = "cba";
        sort(key.begin(), key.end());
        

        执行 sort 后，key 的值会变成 "abc"，因为字符按字典序重新排列了。

   3. mp[key].emplace_back(str);

      将字符串 str 添加到 unordered_map 中键为 key 的 vector 中。

      • emplace_back(str) 的作用

        • emplace_back 用于在 vector 的末尾添加一个新元素。

        • 与 push_back 类似，但 emplace_back 更高效，因为它直接在 vector 的内存中构造元素，避免了不必要的拷贝或移动操作。

滑动窗口

数组

1. 最大子数组

   • 题目：

     给定一个整数数组 nums ，请找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。（子数组 是数组中的一个连续部分）

   • 题解 - 动态规划：假设 nums 数组的长度是 n，下标从 0 到 n−1。用 f(i) 代表以第 i 个数结尾的「连续子数组的最大和」，则答案是：$max_{0≤i≤n−1}{f(i)}$。因此只需要求出每个位置的 f(i)，返回 f 数组中的最大值即可。

     求 f(i)：考虑 nums[i] 单独成为一段还是加入 f(i−1) 对应的那一段，这取决于 nums[i] 和 f(i−1)+nums[i] 的大小，我们希望获得一个比较大的，于是可以写出的动态规划转移方程：

     $$ f(i)=max(f(i−1)+nums[i] , nums[i]) $$

     用变量 pre 来维护对于当前 f(i) 的 f(i−1) 的值是多少。

   class Solution {
   public:
       int maxSubArray(vector<int>& nums) {
           int pre = 0, maxAns = nums[0];
           for (const auto &x: nums) {
               pre = max(pre + x, x);
               maxAns = max(maxAns, pre);
           }
           return maxAns;
       }
   };
   

树

1. 二叉树的最小深度 - D/BFS

   最小深度是从根节点到最近叶子节点的最短路径上的节点数量 —— 本质上是求最短距离。

   **说明：**叶子节点是指没有子节点的节点。

   1. if-else大法

      class Solution {
      public:
      	int minDepth(TreeNode root) {
      		if (root == null) return 0;
      		else if (root.left == null) return minDepth(root.right) + 1;
      		else if (root.right == null) return minDepth(root.left) + 1;
      		else return min(minDepth(root.left), minDepth(root.right)) + 1;
      	}
      }
      

      min 函数比较了两个整数a和b，并返回较小的那个值。

   2. DFS 深度遍历的解法

      每当遍历到一条树枝的叶子节点，就会更新最小深度，当遍历完整棵树后，就能算出整棵树的最小深度。

      class Solution {
      private:
          // 记录最小深度（根节点到最近的叶子节点的距离）
          int minDepthValue = INT_MAX;
          // 记录当前遍历到的节点深度
          int currentDepth = 0;
      
      public:
          int minDepth(TreeNode* root) {
              if (root == nullptr) {
                  return 0;
              }
      
              // 从根节点开始 DFS 遍历
              traverse(root);
              return minDepthValue;
          }
      
          void traverse(TreeNode* root) {
              if (root == nullptr) {
                  return;
              }
      
              // 前序位置进入节点时增加当前深度
              currentDepth++;
      
              // 如果当前节点是叶子节点，更新最小深度
              if (root->left == nullptr && root->right == nullptr) {
                  minDepthValue = min(minDepthValue, currentDepth);
              }
      
              traverse(root->left);
              traverse(root->right);
      
              // 后序位置离开节点时减少当前深度
              currentDepth--;
          }
      };
      

   3. BFS 层序遍历的解法

      按照 BFS 从上到下逐层遍历二叉树的特点，当遍历到第一个叶子节点时，就能得到最小深度。

      class Solution {
      public:
          int minDepth(TreeNode* root) {
              if (root == nullptr) return 0;
              queue<TreeNode*> q;
              q.push(root);
              // root 本身就是一层，depth 初始化为 1
              int depth = 1;
      
              while (!q.empty()) {
                  int sz = q.size();
                  // 遍历当前层的节点
                  for (int i = 0; i < sz; i++) {
                      TreeNode* cur = q.front();
                      q.pop();
                      // 判断是否到达叶子结点
                      if (cur->left == nullptr && cur->right == nullptr)
                          return depth;
                      // 将下一层节点加入队列
                      if (cur->left != nullptr)
                          q.push(cur->left);
                      if (cur->right != nullptr)
                          q.push(cur->right);
                  }
                  // 这里增加步数
                  depth++;
              }
              return depth;
          }
      };
      

      1. pop() 函数

         该函数没有参数，也没有返回值。它仅用于删除栈顶元素。

      2. front() 函数

         返回对容器中第一个元素的引用。

3. 最大子序和

• Algorithm