题目一：leetcode 136. 只出现一次的数字

一、题目

leetcode 136. 只出现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

二、题解

2.1 哈希表法？

初步思考，这个问题，可以借助hashmap来处理

C++ 知识卡片1——std::unordered_map

简介

• std::unordered_map 是 C++11 中引入的一种关联容器，它存储的是键值对，其中每个键都是唯一的，并且每个键都映射到一个值。与 std::map 不同的是，std::unordered_map 内部使用哈希表实现，因此它可以提供平均情况下对于元素的插入、访问和删除操作的常数时间复杂度（O(1)），但最坏情况下会退化到线性时间（O(n)）。

头文件

• 需要包含头文件 <unordered_map>

常用方法

• insert(): 插入键值对，如果键已经存在，则插入不会发生。
• emplace(): 尝试就地构造元素，这通常比 insert 更高效。
• erase(): 通过键来删除元素。
• clear() ：移除容器中的所有元素，但保留内存分配和哈希表的结构。这允许快速清空容器而不影响其容量或性能特性。
• find(key): 通过键查找元素，如果找到，则返回一个指向该元素的迭代器；如果未找到，则返回 end() 迭代器。
• count(key) ：返回某个键存在于容器中的次数。由于 unordered_map 中每个键都是唯一的，此方法只能返回 0（键不存在）或 1（键存在）。
• `operator[]: 访问给定键对应的值。如果该键不存在，会插入一个新元素并返回其值的引用。
• at(): 访问给定键对应的值，如果键不存在，则抛出 std::out_of_range 异常。
• empty(): 检查容器是否为空。
• size(): 返回容器中元素的数量。
• begin() 和 end(): 分别返回一个迭代器，这些迭代器支持前向遍历，但由于 unordered_map 是一个无序容器，遍历的顺序并不代表元素插入的顺序或任何特定排序。
• 可以使用 for(auto xxx : xxx_unordered_map) 遍历 unordered_map，并且可以使用 xxx.first和 xxx.second 访问每个元素的 key 和 value。

相关示代码示例

#include <iostream>
#include <string>
#include <unordered_map>

int main() 
{
    // 创建一个 unordered_map，键为 std::string 类型，值为 int 类型
    std::unordered_map<std::string, int> myMap;

    // 插入键值对
    myMap["apple"] = 1;
    myMap.insert({"banana", 2});
    myMap.emplace("cherry", 3);

    // 访问元素
    std::cout << "apple has value " << myMap["apple"] << std::endl;

    // 检查元素是否存在
    if (myMap.find("banana") != myMap.end()) {
        std::cout << "Found banana in the map." << std::endl;
    }

    // 更新元素的值
    myMap["apple"] = 10;

    // 遍历 unordered_map
    for (const auto& pair : myMap) {
        std::cout << pair.first << " has value " << pair.second << std::endl;
    }

    // 删除元素
    myMap.erase("banana");

    return 0;
}

先看一下这这种方式的代码

class Solution {
        public:
            int singleNumber(vector<int>& nums) {
                unordered_map<int, int> nums_count_map;
                for(int i = 0; i < nums.size(); i++)
                {
                    if(nums_count_map.count(nums[i]) > 0)
                    {
                        nums_count_map[nums[i]]++;
                    }
                    else
                    {
                        nums_count_map.insert(make_pair(nums[i], 1));
                    }
                }
                int result = 0;
                for(auto iter = nums_count_map.begin(); iter != nums_count_map.end(); iter++)
                {
                     if(iter->second == 1)
                     {
                         result = iter->first;
                         break;
                     }
                }
                return result;
            }
        };

但显然这个算法的空间复杂度不符合要求，运行速度也不是很快。那么接下来就是位运算：按位异或出场的时候了。

2.2 位运算法

使用异或运算（^）来实现，那么我们先来看看异或运算是什么？异或运算有什么性质吧？

异或运算（^）具有以下性质：

（1）任何数和 0 异或得到它本身，即 a ^ 0 = a
（2）任何数和自身异或得到 0，即 a ^ a = 0
（3）异或运算满足交换律和结合律，即 a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b

通过上面的性质， a ^ a = 0，我们可以想到 nums 数组中两个相同的数值进行异或运算结果为0，并且异或运算满足交换律和结合律，所以无论两个相同的数相隔多远都可以消掉，最后留下只出现一次的元素，下面就是代码了。

    class Solution {
    public:
        int singleNumber(vector<int>& nums) {
            int result = 0;
            for(int i = 0; i < nums.size(); i++)
            {
               result ^= nums[i];
            }
            return result;
        }
    };

结果还不错，我就不追求更卓越了，更高效的方法，也欢迎 jym 甩在评论区，供大家一起欣赏，一起讨论哦～

题目二：leetcode 128. 最长连续序列

一、题目

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) **的算法解决此问题。

示例 1：

输入： nums = [100,4,200,1,3,2]
输出： 4
解释： 最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

输入： nums = [0,3,7,2,5,8,4,6,0,1]
输出： 9

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

二、题解

C++ 知识卡片2——unordered_set

简介

• unordered_set 是一个基于哈希表的容器，用于存储唯一元素的集合。

头文件

• 需要包含头文件 <unordered_set>

常用方法

• insert(element) ：向 unordered_set 中插入元素。如果元素已经存在，则操作不会改变容器。
• emplace(args...) ：直接在 unordered_set 中构造元素，避免了临时对象的创建和复制。其参数是用于构造元素的参数。
• erase(key) ：删除与指定键相匹配的元素。
• clear() ：移除 unordered_set 中的所有元素，但不改变其容量。
• find(key) ：查找一个给定键的元素。如果找到，返回一个指向该元素的迭代器；如果未找到，返回 end()。
• count(key) ：返回容器中等于给定键的元素数量。对于 unordered_set，这个值只能是 0 或 1。
• empty() ：检查 unordered_set 是否为空。
• size() ：返回 unordered_set 中的元素数量。
• max_size() ：返回 unordered_set 可以容纳的最大元素数量，这通常是一个非常大的数值。
• begin() , end() ：提供遍历 unordered_set 的能力。begin() 返回指向第一个元素的迭代器，而 end() 返回指向容器末尾的迭代器。

#include <iostream>
#include <unordered_set>

int main() 
{
    std::unordered_set<int> mySet = {1, 2, 3, 4, 5};

    // 插入新元素
    mySet.insert(6);

    // 检查元素是否存在
    if (mySet.find(3) != mySet.end()) {
        std::cout << "3 is found" << std::endl;
    }

    // 删除元素
    mySet.erase(4);

    // 遍历并打印元素
    for (auto& elem : mySet) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

我们一起思考一下这道题的思路，一个数组 nums = [100,4,200,1,3,2]，要找出最长数字连续序列，数组里有重复元素，去重可以简化过程，那么这里可以考虑用到哈希表，如果数组中元素是按顺序的就更好了，但是显然排序算法最快的时间复杂度也需要 O(nlogn)，所以不考虑使用排序算法，那么我们先考虑暴力的方式，遍历数组，逐个计算最长序列，最长序列需要考虑两个方向，比当前的元素大的方向，比当前元素小的方向，由于每个都元素都会遍历到，所以我们按照一个方向就可以了，比如只计算比当前元素大的方向，计算当前的最长序列长度curLongestLen，并且不断维护全局最长的序列的长度longestLen，但是这样做还有一个问题比如计算到1的时候，会计算1234，计算3的时候会计算34，计算2的时候会计算234，其实这里的3和2都没必要计算，以为计算1的时候必然会算到2，算到3，那么如何优化这一点呢，只需要加一个判断，就是哈希表中有比当前的元素小的元素，就先不计算，跳过当前元素，因为一会计算到比当前元素小的元素的时候还会计算一遍。

这种方法在时间复杂度上已经相对优化，为 O(n)，简单来说因为每个元素最多被访问两次：一次是加入集合，一次是在找连续序列时。严格一点计算主要针对下面两个部分：

(1) 构建 unordered_set：

• 对于输入数组 nums 中的每个元素，执行一次 insert 操作。
• unordered_set 的 insert 操作平均时间复杂度是 O(1)。
• 因此，对于 n 个元素，构建整个 unordered_set 的总时间复杂度是 O(n)。

(2) 遍历 unordered_set 查找连续序列：

• 遍历集合中的每个数字（n个），对于每个数字，检查它是否是连续序列的“起点”（即检查 num-1 是否存在于集合中）。
• 检查一个数字是否在 unordered_set 中的操作的平均时间复杂度是 O(1)。
• 对于每个“起点”（不存在比它小一个值的元素），通过进行连续检查，检查 num+1, num+2, ... 是否存在于集合中来计算连续序列的长度。
• 这个过程中共有下面三种元素，每种元素被访问的次数，如下所示

这意味着，尽管内层循环看起来像是嵌套在外层循环中，但这个过程中，每个元素最多被访问两次，时间复杂度也就是O(2n)= O(n)。

综上所述，构建 unordered_set 需要 O(n) 时间，遍历 unordered_set 并查找连续序列也需要O(n)时间，因为每个元素最多被访问两次。因此，整体算法的时间复杂度是 O(n) + O(n) = O(n)。

这个分析基于平均情况下的时间复杂度。值得注意的是，unordered_set 的操作时间复杂度在最坏情况下可能会退化到 O(n)，但这种情况在良好设计的哈希函数下极为罕见。因此，在实际应用中，可以认为这种方法的时间复杂度接近 O(n)。

那么下面一起看一下代码吧。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        //nums = [100,4,200,1,3,2]
        unordered_set<int> arr_set;
        for(const int& num : nums)//①
        {
            arr_set.insert(num);
        }

        int curNum = 0;
        int longestlen = 0;
        for(const int& num : arr_set)
        {
            int curLongestlen = 1;
            curNum = num;
            if(!arr_set.count(curNum-1))
            {
                while(arr_set.count(curNum+1))
                {
                    curNum++;
                    curLongestlen++;
                }
                longestlen = curLongestlen > longestlen ? curLongestlen : longestlen;
            }
        }
        return longestlen;
    }
};    

这里代码中的 ① 使用引用进行遍历有以下几个好处：

1. 性能优化：通过引用遍历元素可以避免拷贝容器中的元素，这意味着当元素类型较大时，可以显著减少拷贝构造函数或赋值操作的开销。即使对于基本数据类型（如 int），在大规模数据处理时，这种避免拷贝的做法也有助于提升效率。

2. 修改容器元素：如果遍历的目的是为了修改容器中的元素，使用引用是必要的。注意，如果想修改元素，就不能使用 const 修饰引用。例如，for(int& num : nums) { num = someValue; } 可以修改 nums 中的每个元素，这里是强调不修改原来的元素，避免误修改。

3. 常量引用的安全性：使用 const int& 表示这是一个对 int 类型的常量引用，这确保了遍历过程中不会意外修改容器中的元素，即保持了操作的const-safety。这是一种好的编程实践，特别是在只需要读取容器中元素而不需要修改它们的场景下。

题目三：leetcode 49. 字母异位词分组

一、题目

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

提示：

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

二、题解

C++ 知识卡片3——std::sort

简介

• std::sort 是标准模板库（STL）中的一个非常强大且灵活的排序函数，默认升序排序。
• template void sort (RandomAccessIterator first, RandomAccessIterator last);
  • 对[first, last) 范围内的数据进行排序
  • 默认升序排列
• template <class RandomAccessIterator, class Compare> void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
  • 对[first, last) 范围内的数据进行排序
  • 按照自定义的比较函数 comp 进行排序 （见代码示例 1）

可排序的内容

• 基本数据类型数组或容器（如 int、float、char、std::vector、std::deque 、std::string等）。
• 字符串（ std::string），将按每一个字符的 ASCII 或 Unicode 值排序。
• 自定义对象的数组或容器，需要提供自定义的比较函数（见代码示例 1）或重载 < 操作符（代码示例 2）。

头文件

• 需要包含头文件 #include <algorithm>

代码示例 1

#include <algorithm>
#include <vector>
#include <iostream>
#include <string>

class Person {
public:
    std::string name;
    int age;

    Person(std::string n, int a) : name(n), age(a) {}
};

// 自定义比较函数
bool comparePersons(const Person& a, const Person& b) {
    return a.age < b.age;
}

int main() {
    std::vector<Person> people = {
        {"Alice", 30},
        {"Bob", 25},
        {"Carol", 20}
    };

    std::sort(people.begin(), people.end(), comparePersons);

    for (const Person& p : people) {
        std::cout << p.name << " is " << p.age << " years old.\n";
    }

    return 0;
}

代码示例 2

#include <algorithm>
#include <vector>
#include <iostream>
#include <string>

class Person {
public:
    std::string name;
    int age;

    Person(std::string n, int a) : name(n), age(a) {}

    // 重载 '<' 操作符，根据年龄排序
    bool operator<(const Person& other) const {
        return age < other.age;
    }
};

int main() {
    std::vector<Person> people = {
        {"Alice", 30},
        {"Bob", 25},
        {"Carol", 20}
    };

    std::sort(people.begin(), people.end());

    for (const Person& p : people) {
        std::cout << p.name << " is " << p.age << " years old.\n";
    }

    return 0;
}

C++ 知识卡片4 ——std::vector

简介

std::vector 是 C++ 标准模板库（STL）的一部分，它是一个序列容器，可以存储可变大小的数组。vector 提供了动态数组的功能，这意味着它可以在运行时动态地改变大小，自动管理存储空间。与普通数组相比，vector 提供了更高的灵活性和更广泛的功能集，如自动管理内存、提供对元素的直接访问等。

头文件

要使用 std::vector，需要包含头文件 <vector>。

常用方法

• push_back(value) ：在 vector 的末尾添加一个元素。
• pop_back() ：删除 vector 末尾的元素。
• size() ：返回 vector 中元素的数量。
• empty() ：检查 vector 是否为空。
• clear() ：删除 vector 中的所有元素。
• insert(position, value) ：在指定位置之前插入一个元素。
• erase(position) 或 erase(start, end) ：删除指定位置的元素或删除一个范围内的元素。
• at(index) ：访问指定位置的元素（带边界检查）。
• operator[] ：访问指定位置的元素（无边界检查）。
• front() ：访问第一个元素。
• back() ：访问最后一个元素。
• begin() , end() ：返回指向容器开始和结束的迭代器。

代码示例

#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec; // 声明一个int类型的vector

    // 添加元素
    vec.push_back(10);
    vec.push_back(20);

    // 访问元素
    std::cout << "第一个元素: " << vec.front() << std::endl;
    std::cout << "最后一个元素: " << vec.back() << std::endl;

    // 使用迭代器遍历vector
    std::cout << "vector中的元素: ";
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 删除最后一个元素
    vec.pop_back();

    // 检查大小和是否为空
    std::cout << "vector大小: " << vec.size() << std::endl;
    std::cout << "vector是否为空: " << (vec.empty() ? "是" : "否") << std::endl;

    return 0;
}

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> strs_map;
        for(string s :strs)
        {
            string key = s;
            sort(key.begin(), key.end());
            strs_map[key].push_back(s);
        }
        vector<vector<string>> result_arr;
        for(auto kv: strs_map)
        {
            result_arr.push_back(kv.second);
        }
        return result_arr;
    }
};

题目四：leetcode 1. 两数之和

一、题目

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入： nums = [2,7,11,15], target = 9
输出： [0,1]
解释： 因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入： nums = [3,2,4], target = 6
输出： [1,2]

示例 3：

输入： nums = [3,3], target = 6
输出： [0,1]

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

进阶： 你可以想出一个时间复杂度小于 O(n2) 的算法吗？

二、题解

解决这类问题时可以考虑使用哈希表（在 C++ 中为 unordered_map），主要原因在于哈希表提供快速查询的能力，这使得寻找配对的另一个数字变得非常高效。

当遍历数组时，对于每个元素 x，我们可以在常数时间内查找 target - x 是否已经存在于哈希表中。如果存在，那么我们找到了一对有效的配对，并且可以直接返回它们的下标。如果不存在，我们将当前元素的值和它的索引加入到哈希表中，以便在遍历到后续元素时使用。下面看下具体的代码。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> nums_map;
        for(int i =0; i < nums.size(); i++)
        {
            if(nums_map.count(target-(nums[i])))
            {
                return {i, nums_map[target-(nums[i])]};
            }
            nums_map[nums[i]]=i;
        }
        return {};
    }
};

三、总结