当前位置： 首页 > news >正文

8.25学习日志

news 2025/8/26 10:12:02

题目：

169. 多数元素 - 力扣（LeetCode）

知识点：

C++ 哈希容器全面总结

两大类容器对比

特性哈希容器 (unordered_)有序容器 (红黑树)
底层结构哈希表红黑树
时间复杂度平均 O(1)，最差 O(n)稳定 O(log n)
元素顺序无序有序（按键排序）
内存占用较低较高
适用场景快速查找、不关心顺序需要有序遍历、范围查询

四大核心容器详解

1. unordered_set - 唯一键集合

#include <unordered_set>unordered_set<int> uniqueNums = {1, 2, 3, 4, 5};// 基本操作
uniqueNums.insert(6);          // 插入元素
uniqueNums.erase(3);           // 删除元素
bool exists = uniqueNums.contains(2);  // C++20 检查存在
// 或者使用 find()
bool exists = (uniqueNums.find(2) != uniqueNums.end());// 遍历
for (int num : uniqueNums) {cout << num << " ";  // 顺序不确定
}

2. unordered_map - 键值对映射

#include <unordered_map>unordered_map<string, int> ageMap = {{"Alice", 25},{"Bob", 30}
};// 访问和修改
ageMap["Charlie"] = 35;        // 插入或修改
int age = ageMap.at("Alice");  // 安全访问（会检查）
ageMap.erase("Bob");           // 删除// 检查键是否存在
if (ageMap.count("Alice") > 0) {// 键存在
}// 遍历键值对
for (const auto& [name, age] : ageMap) {cout << name << ": " << age << endl;
}

3. unordered_multiset - 允许重复键的集合

unordered_multiset<int> multiNums = {1, 2, 2, 3, 3, 3};// 可以插入重复元素
multiNums.insert(2);  // 现在有三个2// 统计特定元素出现次数
int count = multiNums.count(2);  // 返回3

4. unordered_multimap - 允许重复键的映射

unordered_multimap<string, string> phonebook;// 可以插入相同键的不同值
phonebook.insert({"Alice", "123-4567"});
phonebook.insert({"Alice", "987-6543"});// 查找所有相同键的值
auto range = phonebook.equal_range("Alice");
for (auto it = range.first; it != range.second; ++it) {cout << it->second << endl;  // 输出所有Alice的电话
}

重要成员函数

共同拥有的函数

// 容量相关
container.empty();     // 是否为空
container.size();      // 元素数量
container.clear();     // 清空容器// 查找相关
container.find(key);   // 返回迭代器，找不到返回end()
container.count(key);  // 返回键出现的次数
container.contains(key); // C++20，返回bool// 桶相关（哈希表特性）
container.bucket_count();    // 桶的数量
container.load_factor();     // 负载因子
container.max_load_factor(); // 最大负载因子

自定义哈希函数和比较函数

自定义哈希函数

struct Person {string name;int age;
};// 自定义哈希函数
struct PersonHash {size_t operator()(const Person& p) const {return hash<string>()(p.name) ^ hash<int>()(p.age);}
};// 自定义相等比较
struct PersonEqual {bool operator()(const Person& a, const Person& b) const {return a.name == b.name && a.age == b.age;}
};unordered_set<Person, PersonHash, PersonEqual> personSet;

使用 Lambda 表达式（C++20）

auto hash = [](const Person& p) {return hash<string>{}(p.name) ^ hash<int>{}(p.age);
};
auto equal = [](const Person& a, const Person& b) {return a.name == b.name && a.age == b.age;
};unordered_set<Person, decltype(hash), decltype(equal)> personSet(10, hash, equal);

性能优化技巧

1. 预分配空间

unordered_map<int, int> map;
map.reserve(1000);  // 预分配空间，避免重新哈希

2. 设置合适的负载因子

unordered_set<int> set;
set.max_load_factor(0.7);  // 设置最大负载因子
set.rehash(1000);          // 重新哈希

3. 使用emplace避免拷贝

unordered_map<string, vector<int>> map;
// 使用emplace避免临时对象创建
map.emplace("key", vector<int>{1, 2, 3});

常见使用场景

1. 统计频率（最常用）

vector<int> nums = {1, 2, 2, 3, 3, 3};
unordered_map<int, int> freq;for (int num : nums) {freq[num]++;
}

2. 去重

vector<int> nums = {1, 2, 2, 3, 3, 3};
unordered_set<int> uniqueNums(nums.begin(), nums.end());

3. 缓存（Memoization）

unordered_map<int, int> cache;int fibonacci(int n) {if (cache.count(n)) return cache[n];if (n <= 1) return n;int result = fibonacci(n-1) + fibonacci(n-2);cache[n] = result;return result;
}

4. 快速查找

unordered_set<string> dictionary = {"apple", "banana", "cherry"};bool isWordValid(const string& word) {return dictionary.contains(word);
}

注意事项

  1. 迭代器失效：插入操作可能使所有迭代器失效（重新哈希时）

  2. 自定义类型：必须提供哈希函数和相等比较函数

  3. 内存占用：哈希表有额外的内存开销用于维护桶结构

  4. 最坏情况：所有元素哈希到同一个桶时，性能退化为 O(n)

选择指南

  • 使用 unordered_set/map 当：需要快速查找，不关心顺序

  • 使用 set/map 当：需要有序遍历或范围查询

  • 使用 multi 版本当：允许重复键

  • 使用哈希容器当：数据量较大，查找性能关键

  • C++ Lambda 表达式全面总结

    1. 基本语法结构

    [捕获列表] (参数列表) -> 返回类型 {// 函数体
}

    2. 最简单的 Lambda 表达式

    // 无参数，无返回值
auto hello = [] {cout << "Hello Lambda!" << endl;
};
hello();  // 输出: Hello Lambda!// 带参数
auto add = [](int a, int b) {return a + b;
};
cout << add(3, 5);  // 输出: 8

    3. 捕获列表详解

    值捕获 [=]

    int x = 10, y = 20;
auto captureByValue = [=] {cout << x + y;  // 可以访问外部变量，但不能修改// x = 5;  // 错误：不能修改值捕获的变量
};

    引用捕获 [&]

    int x = 10;
auto captureByRef = [&] {x = 20;  // 可以修改外部变量cout << x;  // 输出: 20
};

    混合捕获

    int a = 1, b = 2, c = 3, d = 4;
auto mixed = [=, &b, &c] {  // a,d 值捕获，b,c 引用捕获// a = 10;  // 错误：值捕获不能修改b = 20;     // 可以修改c = 30;     // 可以修改
};

    显式指定捕获

    int x = 1, y = 2, z = 3;
auto explicitCapture = [x, &y] {  // 只捕获x(值)和y(引用)cout << x + y;  // z 不可访问
};

    4. mutable 关键字

    int counter = 0;
auto increment = [counter]() mutable {counter++;  // 可以修改值捕获的变量（副本）return counter;
};
cout << increment();  // 输出: 1
cout << increment();  // 输出: 2
cout << counter;      // 输出: 0（原始值未改变）

    5. 返回类型推导和显式声明

    // 自动推导返回类型
auto autoReturn = [](int a, int b) { return a + b; };// 显式声明返回类型
auto explicitReturn = [](int a, int b) -> double {return (a + b) / 2.0;
};// 复杂返回类型需要显式声明
auto complexReturn = []() -> std::vector<int> {return {1, 2, 3};
};

    6. Lambda 作为函数参数

    使用 std::function

    #include <functional>
#include <vector>void processNumbers(const vector<int>& nums, function<void(int)> processor) {for (int num : nums) {processor(num);}
}// 使用
processNumbers({1, 2, 3}, [](int n) {cout << n * 2 << " ";
});

    使用模板

    template<typename Func>
void templateProcess(const vector<int>& nums, Func func) {for (int num : nums) {func(num);}
}// 使用
templateProcess({1, 2, 3}, [](int n) {return n * n;
});

    7. 在 STL 算法中的应用

    #include <algorithm>
#include <vector>vector<int> numbers = {1, 2, 3, 4, 5};// 使用 Lambda 进行排序
sort(numbers.begin(), numbers.end(), [](int a, int b) {return a > b;  // 降序排序
});// 使用 Lambda 进行过滤
vector<int> evenNumbers;
copy_if(numbers.begin(), numbers.end(), back_inserter(evenNumbers),[](int n) { return n % 2 == 0; });// 使用 Lambda 进行转换
vector<int> squared;
transform(numbers.begin(), numbers.end(),back_inserter(squared),[](int n) { return n * n; });

    8. 捕获 this 指针（在类中使用）

    class MyClass {
private:int value = 42;public:void printValue() {auto lambda = [this] {  // 捕获this指针cout << "Value: " << this->value << endl;};lambda();}// C++17 推荐使用 [*this] 值捕获当前对象void printValueCopy() {auto lambda = [*this] {  // 值捕获当前对象cout << "Value: " << value << endl;};lambda();}
};

    9. 泛型 Lambda（C++14+）

    // 使用 auto 参数
auto genericAdd = [](auto a, auto b) {return a + b;
};cout << genericAdd(1, 2);      // 输出: 3
cout << genericAdd(1.5, 2.3);  // 输出: 3.8
cout << genericAdd(string("a"), string("b"));  // 输出: "ab"// 模板 Lambda（C++20）
auto templateLambda = []<typename T>(T a, T b) {return a + b;
};

    10. 立即调用的 Lambda 表达式 (IILE)

    // 立即执行
int result = [](int a, int b) {return a * b;
}(5, 6);  // result = 30// 用于复杂初始化
const auto config = [] {map<string, int> configMap;configMap["timeout"] = 1000;configMap["retries"] = 3;return configMap;
}();  // 立即调用

    11. Lambda 与 std::function 的关系

    #include <functional>// std::function 可以存储任何可调用对象
function<int(int, int)> func;// 存储 Lambda
func = [](int a, int b) { return a + b; };
cout << func(2, 3);  // 输出: 5// 存储函数指针
func = plus<int>();
cout << func(2, 3);  // 输出: 5

    12. 实际应用案例

    回调函数

    class Button {
public:function<void()> onClick;void click() {if (onClick) onClick();}
};Button btn;
btn.onClick = [] {cout << "Button clicked!" << endl;
};
btn.click();

    线程池任务

    #include <thread>
#include <vector>vector<thread> threads;
for (int i = 0; i < 5; i++) {threads.emplace_back([i] {cout << "Thread " << i << " running" << endl;});
}for (auto& t : threads) {t.join();
}

    资源管理（RAII）

    auto resourceGuard = [](auto* resource) {// 模拟RAII：在Lambda结束时自动清理return std::unique_ptr<decltype(resource)>(resource, [](auto* res) { delete res; });
};auto guard = resourceGuard(new int(42));

    13. 注意事项和最佳实践

  • 避免过度捕获：只捕获需要的变量

  • 小心引用捕获：确保被引用的对象生命周期足够长

  • 性能考虑：小Lambda通常被编译器内联，性能很好

  • 可读性：复杂Lambda考虑写成命名函数

  • 14. Lambda 的类型

    // 每个Lambda都有唯一的类型
auto lambda1 = [] { return 1; };
auto lambda2 = [] { return 1; };// lambda1 和 lambda2 类型不同
// decltype(lambda1) != decltype(lambda2)// 但可以转换为相同的 std::function
function<int()> func1 = lambda1;
function<int()> func2 = lambda2;

  • C++20 新特性：

    // 可默认构造和赋值的无状态Lambda
auto lambda = []() constexpr { return 42; };// 模板参数列表
auto templateLambda = []<typename T>(T value) { return value; };

题解：

169. 多数元素 - 力扣（LeetCode）

使用哈希表：

class Solution {
public:int majorityElement(vector<int>& nums) {unordered_map<int, int> countMap;int n = nums.size();for (int num : nums) {countMap[num]++;if (countMap[num] > n / 2) {return num;}}return -1;}
};

return -1; 是一个安全回退的选择，虽然在这个特定问题中永远不会被执行，但它：

  • 满足编译器要求

  • 使代码更完整

  • 遵循防御性编程原则

  • 可以作为错误标识（如果意外发生）

Boyer-Moore 投票算法：

class Solution {
public:int majorityElement(vector<int>& nums) {int candidate = nums[0];int count =1;for(int i=1;i<nums.size();++i){if(count ==0){candidate = nums[i];count =1;}else if(nums[i]==candidate){count++;}else{count--;}}return candidate;}
};

  1. 初始化候选元素 candidate 为第一个元素，计数器 count 为 1

  2. 遍历数组：

    • 如果计数器为 0，选择当前元素作为新的候选元素

    • 如果当前元素等于候选元素，计数器加 1

    • 如果当前元素不等于候选元素，计数器减 1

  3. 遍历结束后，候选元素就是多数元素

时间复杂度： O(n)
空间复杂度： O(1)

这个算法之所以有效，是因为多数元素出现的次数超过数组长度的一半，所以最终候选元素一定会是多数元素。

Lambda 相关的力扣典型题目

1. 排序相关题目

179. 最大数 (Largest Number)

class Solution {
public:string largestNumber(vector<int>& nums) {// 使用Lambda自定义排序规则sort(nums.begin(), nums.end(), [](int a, int b) {string s1 = to_string(a) + to_string(b);string s2 = to_string(b) + to_string(a);return s1 > s2;  // 降序排列});if (nums[0] == 0) return "0";string result;for (int num : nums) {result += to_string(num);}return result;}
};

56. 合并区间 (Merge Intervals)

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {if (intervals.empty()) return {};// 使用Lambda按区间起始点排序sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {return a[0] < b[0];});vector<vector<int>> merged;for (const auto& interval : intervals) {if (merged.empty() || merged.back()[1] < interval[0]) {merged.push_back(interval);} else {merged.back()[1] = max(merged.back()[1], interval[1]);}}return merged;}
};

2. 优先队列自定义比较

347. 前 K 个高频元素 (Top K Frequent Elements)

class Solution {
public:vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int, int> freq;for (int num : nums) freq[num]++;// 使用Lambda定义最小堆的比较函数auto comp = [&freq](int a, int b) {return freq[a] > freq[b];  // 最小堆};priority_queue<int, vector<int>, decltype(comp)> pq(comp);for (auto& [num, count] : freq) {pq.push(num);if (pq.size() > k) {pq.pop();}}vector<int> result;while (!pq.empty()) {result.push_back(pq.top());pq.pop();}reverse(result.begin(), result.end());return result;}
};

3. STL算法应用

452. 用最少数量的箭引爆气球 (Minimum Number of Arrows to Burst Balloons)

class Solution {
public:int findMinArrowShots(vector<vector<int>>& points) {if (points.empty()) return 0;// 使用Lambda按结束点排序sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) {return a[1] < b[1];});int arrows = 1;int end = points[0][1];for (int i = 1; i < points.size(); i++) {if (points[i][0] > end) {arrows++;end = points[i][1];}}return arrows;}
};

4. 自定义数据结构比较

973. 最接近原点的 K 个点 (K Closest Points to Origin)

class Solution {
public:vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {// 使用Lambda定义距离比较函数auto distance = [](const vector<int>& point) {return point[0] * point[0] + point[1] * point[1];};// 使用nth_element进行部分排序nth_element(points.begin(), points.begin() + k, points.end(),[&](const vector<int>& a, const vector<int>& b) {return distance(a) < distance(b);});return vector<vector<int>>(points.begin(), points.begin() + k);}
};

5. 复杂排序和分组

49. 字母异位词分组 (Group Anagrams)

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> groups;for (const string& s : strs) {string key = s;sort(key.begin(), key.end());groups[key].push_back(s);}vector<vector<string>> result;// 使用Lambda转换map到vectortransform(groups.begin(), groups.end(), back_inserter(result),[](const auto& pair) {return pair.second;});return result;}
};

6. 线程池和异步编程（模拟）

1116. 打印零与奇偶数 (Print Zero Even Odd)

class ZeroEvenOdd {
private:int n;mutex mtx;condition_variable cv;int current;bool printZero;public:ZeroEvenOdd(int n) : n(n), current(1), printZero(true) {}void zero(function<void(int)> printNumber) {for (int i = 0; i < n; i++) {unique_lock<mutex> lock(mtx);cv.wait(lock, [this] { return printZero; });printNumber(0);printZero = false;cv.notify_all();}}void even(function<void(int)> printNumber) {for (int i = 2; i <= n; i += 2) {unique_lock<mutex> lock(mtx);cv.wait(lock, [this] { return !printZero && current % 2 == 0; });printNumber(current++);printZero = true;cv.notify_all();}}void odd(function<void(int)> printNumber) {for (int i = 1; i <= n; i += 2) {unique_lock<mutex> lock(mtx);cv.wait(lock, [this] { return !printZero && current % 2 == 1; });printNumber(current++);printZero = true;cv.notify_all();}}
};

7. 函数式编程风格

1337. 矩阵中战斗力最弱的 K 行 (The K Weakest Rows in a Matrix)

class Solution {
public:vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {int m = mat.size();vector<pair<int, int>> strength; // (soldier_count, index)// 使用Lambda计算每行的士兵数量auto countSoldiers = [](const vector<int>& row) {return accumulate(row.begin(), row.end(), 0);};for (int i = 0; i < m; i++) {strength.emplace_back(countSoldiers(mat[i]), i);}// 使用Lambda进行排序sort(strength.begin(), strength.end(), [](const pair<int, int>& a, const pair<int, int>& b) {if (a.first == b.first) return a.second < b.second;return a.first < b.first;});vector<int> result;transform(strength.begin(), strength.begin() + k, back_inserter(result),[](const pair<int, int>& p) { return p.second; });return result;}
};

8. 递归中的Lambda

394. 字符串解码 (Decode String)

class Solution {
public:string decodeString(string s) {int index = 0;// 使用Lambda递归解析function<string()> decode = [&]() -> string {string result;int num = 0;while (index < s.size()) {char c = s[index++];if (isdigit(c)) {num = num * 10 + (c - '0');} else if (c == '[') {string inner = decode();for (int i = 0; i < num; i++) {result += inner;}num = 0;} else if (c == ']') {break;} else {result += c;}}return result;};return decode();}
};

Lambda 在算法题中的优势

  1. 简洁性：避免定义额外的比较函数或函数对象

  2. 可读性：将比较逻辑直接放在使用的地方

  3. 灵活性：可以捕获外部变量，实现复杂的比较逻辑

  4. 性能：通常会被编译器内联优化

http://www.xdnf.cn/news/1363825.html

相关文章：

  • Portswigger靶场之Blind SQL injection with conditional errorsPRACTITIONERLAB
  • 36 NoSQL 注入
  • 大模型微调 Prompt Tuning与P-Tuning 的区别?
  • Java多态大冒险：当动物们开始“造反”
  • leetcode-hot-100 (二分查找）
  • 实用电脑小工具分享，守护电脑隐私与提升效率21/64
  • LengthFieldBasedFrameDecoder 详细用法
  • excel 破解工作表密码
  • 无锁队列的设计与实现
  • 记一次 element-plus el-table-v2 表格滚动卡顿问题优化
  • 【学习记录】CSS: clamp、@scope
  • 一键编译安装zabbix(centos)
  • Go编写的轻量文件监控器. 可以监控终端上指定文件夹内的变化, 阻止删除,修改,新增操作. 可以用于AWD比赛或者终端应急响应
  • go-redis库使用总结
  • 跨语言统一语义真理及其对NLP深层分析影响
  • 人体工学优化：握力环直径 / 重量设计与便携性、握持舒适度的协同分析
  • Spring Security（第五篇）：从单体到前后端分离 —— JSON 响应与处理器实战
  • 0826xd
  • QtExcel/QXlsx
  • 力扣82:删除排序链表中的重复元素Ⅱ
  • 《Password Guessing Using Large Language Models》——论文阅读
  • 离线可用的网络急救方案
  • JavaScript Intl.RelativeTimeFormat：自动生成 “3 分钟前” 的国际化工具
  • [React]Antd Select组件输入搜索时调用接口
  • 基于RFM模型的客户群体大数据分析及用户聚类系统的设计与实现
  • 【Flink】运行模式
  • 文献阅读笔记：KalmanNet-融合神经网络和卡尔曼滤波的部分已知动力学状态估计
  • Zabbix Vs. Grafana
  • win11中系统的WSL安装Centos以及必要组件
  • nmcli命令详解