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

LeetCode Hot100 (1/100)

web 2025/5/15 7:22:20

目录

一、有关数组和动态数组的排序（sort函数）

 1.普通数组的排序

基本用法

降序排序

2.vector的排序

基本用法

降序排序

二、数组长度和一些vector的基本语法

1. 静态数组长度计算​

 2. 安全获取数组长度（C++17 起）​

 3.vector 基本语法​

3.1 声明与初始化​​

​​3.2 常用操作​

3.3数组转换成vector

三、列表初始化

 1. ​​基础概念​​

2. ​​常见场景​​

3. ​​底层原理​​

4.return 时的列表初始化

        4.1. ​​直接返回列表​​

        4.2 ​​对比传统写法​​

5.特殊场景处理

        5.1 ​​返回空容器​

        5.2 ​​返回嵌套结构

6.注意事项

        6.1类型匹配​        

        6.2 函数返回类型必须明确​

题目1----两数之和

1.空模板解析

2.实际后台运行版本

3.哈希表

3.1 unordered_map

1. ​​核心特性​​

2. ​​常用函数（表格）​​

 3. ​​代码用法示例​

3.2 unordered_set

1. ​​核心特性​​

2. ​​常用函数（表格）​​

3. ​​代码用法示例​

4.题解

一、有关数组和动态数组的排序（sort函数）

 1.普通数组的排序
基本用法
#include <algorithm> // 必须包含的头文件int main() {int arr[] = {5, 3, 9, 1, 7};int n = sizeof(arr) / sizeof(arr[0]); // 计算数组长度// 默认升序排序（从小到大）std::sort(arr, arr + n); // 参数为指针范围：[arr, arr + n)// 输出结果：1 3 5 7 9return 0;
}
降序排序
#include <algorithm>
#include <functional> // 需要包含此头文件以使用 greater<>int main() {int arr[] = {5, 3, 9, 1, 7};int n = sizeof(arr) / sizeof(arr[0]);// 使用 greater<int>() 降序排序std::sort(arr, arr + n, std::greater<int>());// 输出结果：9 7 5 3 1return 0;
}
2.vector的排序
基本用法
#include <algorithm>
#include <vector>int main() {std::vector<int> vec = {5, 3, 9, 1, 7};// 默认升序排序std::sort(vec.begin(), vec.end()); // 参数为迭代器范围// 输出结果：1 3 5 7 9return 0;
}
降序排序
#include <algorithm>
#include <vector>
#include <functional>int main() {std::vector<int> vec = {5, 3, 9, 1, 7};// 降序排序std::sort(vec.begin(), vec.end(), std::greater<int>());// 输出结果：9 7 5 3 1return 0;
}

二、数组长度和一些vector的基本语法

1. 静态数组长度计算​
int arr[] = {3, 1, 4, 1, 5, 9};
int length = sizeof(arr) / sizeof(arr[0]); // 计算元素个数

 数组作为函数参数传递时会退化为指针，此时 sizeof(arr) 返回指针大小而非数组大小

错误示例：

void func(int arr[]) {int len = sizeof(arr)/sizeof(arr[0]); // 错误！返回指针大小/元素大小的比值
}
 2. 安全获取数组长度（C++17 起）​
#include <iterator>
int arr[] = {1, 2, 3};
int length = std::size(arr); // 直接获取数组长度（需C++17及以上）
 3.vector 基本语法​
3.1 声明与初始化​​
语法说明示例
​​默认初始化​​创建空 vectorvector<int> v1;
​​列表初始化​​直接初始化元素vector<int> v2 = {1, 2, 3};
​​指定大小和值​​创建含 n 个 val 的 vectorvector<int> v3(5, 10); // 5个10
​​拷贝初始化​​复制另一个 vectorvector<int> v4(v3);
​​3.2 常用操作​
操作语法说明
​​添加元素​​push_back(val)在末尾插入元素
​​访问元素​​v[i] 或 v.at(i)下标访问（at() 会检查边界）
​​获取大小​​v.size()返回元素个数
​​判断空​​v.empty()返回是否为空
​​清空元素​​v.clear()移除所有元素
​​调整大小​​v.resize(n, val)调整大小为 n，新增元素初始化为 val
3.3数组转换成vector
int arr[] = {5, 2, 8};
vector<int> v(arr, arr + sizeof(arr)/sizeof(arr[0]));

三、列表初始化

 1. ​​基础概念​​

列表初始化使用 ​​花括号 {}​​ 初始化对象，是 C++11 引入的​​统一初始化语法​​，适用于所有类型。

2. ​​常见场景​​
场景示例等效传统写法
​​初始化变量​​vector<int> v = {1, 2, 3};vector<int> v; v.push_back(1); ...
​​函数返回值​​return {i, j};return vector<int>{i, j};
​​构造函数参数​​pair<int, string> p{5, "test"};pair<int, string> p(5, "test");
3. ​​底层原理​​
  • 编译器会尝试将 {} 中的内容转换为目标类型的 initializer_list。
  • 对 vector 来说，内部定义了接受 initializer_list 的构造函数：
4.return 时的列表初始化
        4.1. ​​直接返回列表​​
vector<int> twoSum(...) {return {i, j}; // 隐式构造 vector<int> 对象
}

等效代码：

vector<int> temp;
temp.push_back(i);
temp.push_back(j);
return temp;
        4.2 ​​对比传统写法​​
写法性能可读性
return {i, j};✅ 更优（直接构造）✅ 简洁
return vector<int>{i, j};✅ 相同❌ 冗余
vector<int> res; ... return res;❌ 可能拷贝❌ 冗长
5.特殊场景处理
        5.1 ​​返回空容器​
return {}; // 返回空 vector，等效 return vector<int>();
        5.2 ​​返回嵌套结构
vector<pair<int, int>> func() {return {{1, 2}, {3, 4}}; // 列表初始化嵌套结构
}
6.注意事项
        6.1类型匹配​        
// 错误示例：列表元素类型不匹配
vector<string> v = {1, 2}; // int 无法隐式转为 string
        6.2 函数返回类型必须明确​
auto func() { // 错误：无法推导返回类型return {1, 2}; 
}
vector<int> func() { // 正确return {1, 2};
}

题目1----两数之和

1.空模板解析
// 头文件（通常在LeetCode平台已隐式包含，但本地编译需手动添加）
// #include <vector>
// using namespace std;// 定义解决方案类（LeetCode答题标准模板）
class Solution {
public: // 访问权限修饰符，表示以下成员对外公开（LeetCode需要调用该函数）// 定义名为twoSum的成员函数// 参数说明：// vector<int>& nums → 整型向量的引用（避免拷贝整个数组）// int target → 整型目标值// 返回值：vector<int> → 包含两个索引的向量vector<int> twoSum(vector<int>& nums, int target) {// 函数实现区（需补全）return {}; // 无解时返回空向量（题目保证有解时可省略）*/}/* 关键语法说明：1. vector<int>& → 引用传递参数，直接操作原数组（避免拷贝）2. nums.size() → 获取向量元素数量（等效于数组长度）3. {i, j} → C++11统一初始化，等价于 vector<int>{i, j}};
2.实际后台运行版本
#include <iostream>
#include <vector>
using namespace std;class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {for (int i = 0; i < nums.size(); ++i) {for (int j = i + 1; j < nums.size(); ++j) {if (nums[i] + nums[j] == target) {return {i, j};}}}return {}; // 实际题目保证有解，此句仅为编译通过}
};// 测试用例
int main() {vector<int> nums = {2, 7, 11, 15};int target = 9;Solution sol;vector<int> res = sol.twoSum(nums, target);cout << "[" << res[0] << ", " << res[1] << "]" << endl; // 输出 [0, 1]return 0;
}
3.哈希表

在 C++ 中，哈希表主要通过 unordered_map（键值对）和 unordered_set（唯一键集合）实现

特性unordered_mapunordered_set
​​存储内容​​键值对（key-value）唯一值（value）
​​查找依据​​键（key）值本身（value）
​​典型应用场景​​需要快速通过键访问值的场景需要快速判断元素是否存在的场景

哈希表原理： 

哈希表实现：哈希表C++哈希表详解（知识点+相关LeetCode题目）-CSDN博客

3.1 unordered_map
1. ​​核心特性​​
  • 存储键值对（key-value），键唯一
  • 基于哈希表实现，查找时间复杂度平均为 ​​O(1)​​
  • 无序存储（元素顺序与插入顺序无关）
2. ​​常用函数（表格）​​
函数/操作说明时间复杂度
unordered_map<K, V> map;初始化空哈希表O(1)
map[key] = value;插入或修改键值对（若 key 存在则覆盖）平均 O(1)
map.insert({key, value});插入键值对（若 key 存在则不插入）平均 O(1)
map.find(key)返回指向键的迭代器（若不存在返回 end()）平均 O(1)
map.count(key)返回键存在的次数（0 或 1）平均 O(1)
map.erase(key)删除指定键的键值对平均 O(1)
map.size()返回元素个数O(1)
map.empty()判断哈希表是否为空O(1)
 3. ​​代码用法示例​
#include <unordered_map>
#include <iostream>
using namespace std;int main() {// 初始化unordered_map<string, int> scores = {{"Alice", 90}, {"Bob", 85}};// 插入元素scores["Charlie"] = 88;          // 方式1：operator[]scores.insert({"David", 95});    // 方式2：insert// 访问元素cout << "Alice的分数: " << scores["Alice"] << endl; // 直接访问if (scores.find("Eve") != scores.end()) {          // 安全访问cout << "Eve存在" << endl;}// 删除元素scores.erase("Bob");// 遍历for (const auto& pair : scores) {cout << pair.first << ": " << pair.second << endl;}return 0;
}
3.2 unordered_set
1. ​​核心特性​​
  • 存储唯一元素（无重复值）
  • 基于哈希表实现，查找时间复杂度平均为 ​​O(1)​​
  • 无序存储
2. ​​常用函数（表格）​​
函数/操作说明时间复杂度
unordered_set<T> set;初始化空集合O(1)
set.insert(value);插入元素（若存在则不插入）平均 O(1)
set.find(value)返回指向元素的迭代器（若不存在返回 end()）平均 O(1)
set.count(value)返回元素存在的次数（0 或 1）平均 O(1)
set.erase(value)删除元素平均 O(1)
set.size()返回元素个数O(1)
set.empty()判断集合是否为空O(1)
3. ​​代码用法示例​
#include <unordered_set>
#include <iostream>
using namespace std;int main() {// 初始化unordered_set<int> primes = {2, 3, 5, 7};// 插入元素primes.insert(11);primes.insert({13, 17}); // 插入多个元素// 查询元素if (primes.count(5) > 0) {cout << "5是质数" << endl;}// 删除元素primes.erase(7);// 遍历for (const auto& num : primes) {cout << num << " ";}return 0;
}
4.题解

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {//两个for循环复杂度也就 n方// for(int i=0;i<nums.size();i++)
// for(int j=i+1;j<nums.size();j++)
// {
//     if(nums[i]+nums[j]==target) return {i,j};  
// }//哈希表,注意题目里的可以按任意顺序返回答案，其实有暗示的意思unordered_map<int,int> m;
//由于不知道这两个数是那两个数，一种方法是把数组全部先放到哈希表里，然后遍历哈希表（麻烦）
// 可以每次往哈希表里插入的时候，就检查一下，前面插入的数有没有匹配的（检查的复杂度为1）for(int i=0;i<nums.size();i++)
{if (m.find((target-nums[i]))!=m.end()) return {m[target-nums[i]],i};else{m[nums[i]]=i;}
}return {};}
};

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

相关文章：

  • 家庭宽带的内网穿透实践
  • 数学实验（Matlab符号运算）
  • 面试篇： Redis（持续更新）
  • vue3基础学习 [简单标签] (vscode)
  • More Effective C++：改善编程与设计（上）
  • Redis内存淘汰策略和过期键删除策略有哪些？
  • Flutter在键盘的上方加一个完成按钮
  • JAVA异常体系
  • Linux proc文件系统 内存影射
  • YOLO11解决方案之热力图探索
  • 二分查找的边界问题
  • KUKA机器人中断编程3—暂停功能的编程
  • Selenium-Java版（环境安装）
  • fio 命令在 Linux 系统中的应用示例
  • Android锁
  • android studio导入项目
  • json-server的用法-基于 RESTful API 的本地 mock 服务
  • jQuery知识框架
  • Spring Cloud Gateway 聚合 Swagger 文档：一站式API管理解决方案
  • 鸿蒙OSUniApp 实现精美的用户登录和注册页面#三方框架 #Uniapp
  • Vue ElementUI原生upload修改字体大小和区域宽度
  • WeakAuras Lua Script ICC （BarneyICC）
  • 【周输入】510周阅读推荐-2
  • TTS-Web-Vue系列：Vue3实现侧边栏与顶部导航的双向联动
  • 23-单调队列-滑动窗口
  • LeetCode 每日一题 3341. 到达最后一个房间的最少时间 I + II
  • NAT网关（网络地址转换网关）的用途与场景
  • Mac的web服务器
  • [滑动窗口]越短越合法（可转化成越长越合法）
  • 【每天一个知识点】模型轻量化（Model Compression and Acceleration）技术