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

7.28学习日志

news 2025/7/31 18:16:29

 题目：

1. 两数之和 - 力扣（LeetCode）

1768. 交替合并字符串 - 力扣（LeetCode）

1769. 移动所有球到每个盒子所需的最小操作数 - 力扣（LeetCode）

49. 字母异位词分组 - 力扣（LeetCode）

for (int pos : ballPositions) ：

这句代码 for (int pos : ballPositions) 使用的是 C++11 引入的范围 for 循环（range-based for loop），专门用于遍历容器（如 vector、数组等）中的所有元素，语法简洁直观。

它的作用等价于传统的 for 循环：

for (int j = 0; j < ballPositions.size(); j++) {int pos = ballPositions[j];// 循环体内容
}

 

各部分含义：

  • int pos：声明一个变量 pos，用于接收容器中每个元素的值（这里是小球的位置索引，类型为 int）。
  • ballPositions：要遍历的容器（这里是存储小球位置的 vector）。
  • 循环过程：自动从容器的第一个元素开始，依次将每个元素的值赋给 pos，直到遍历完所有元素。

优势：

  • 代码更简洁，不需要手动控制索引（如 j 的初始值、终止条件、自增），减少了出错的可能。
  • 可读性更强，一眼就能看出是要遍历 ballPositions 中的所有元素。

在这段代码中，这个循环的目的是：依次取出每个小球的位置 pos，计算它到当前目标位置 i 的距离（abs(i - pos)），并累加到总操作数中。

vector<int> answer(n, 0)：

vector<int> answer(n, 0); 这行代码的作用是创建一个初始化为特定值的向量容器，具体含义如下：

  • vector<int>：声明这是一个存储 int 类型元素的向量（动态数组）。
  • answer：向量的名称，后续用于存储计算结果。
  • (n, 0)：这是向量的初始化参数：
    • 第一个参数 n 表示向量的初始大小（即包含 n 个元素），这里的 n 是之前通过 boxes.size() 获取的字符串长度。
    • 第二个参数 0 表示向量中所有元素的初始值，即每个位置都会被默认赋值为 0。

举例说明：

如果 n = 3，那么这行代码会创建一个包含 3 个元素的向量 answer，初始状态为 [0, 0, 0]。

作用：

提前为结果分配好空间并初始化，避免后续动态扩容的性能开销，同时确保每个位置都有一个初始值（0），后续只需根据计算结果更新对应位置的值即可。

在这段代码中，answer 向量最终会存储每个盒子位置对应的最小操作数，因此初始大小与字符串 boxes 的长度相同（每个位置对应一个结果）。

Vector 的用法

Vector 是 C++ 标准模板库(STL)中的一个动态数组容器，它提供了动态大小调整、快速随机访问和高效的尾部插入/删除操作。以下是 vector 的主要用法：

基本操作

1. 包含头文件和声明

#include <vector>
using namespace std;vector<int> v1;              // 空vector
vector<int> v2(10);          // 包含10个元素，默认值为0
vector<int> v3(10, 5);       // 包含10个元素，每个初始化为5
vector<int> v4 = {1, 2, 3};  // 初始化列表
vector<int> v5(v4);          // 拷贝构造

2. 添加元素

v1.push_back(10);       // 在末尾添加元素10
v1.emplace_back(20);    // C++11, 更高效的添加方式
v1.insert(v1.begin(), 5); // 在开头插入5

3. 访问元素

int a = v1[0];          // 通过下标访问，不检查边界
int b = v1.at(1);       // 通过at访问，会检查边界
int c = v1.front();     // 第一个元素
int d = v1.back();      // 最后一个元素

4. 删除元素

v1.pop_back();          // 删除最后一个元素
v1.erase(v1.begin());   // 删除第一个元素
v1.erase(v1.begin(), v1.begin()+2); // 删除前两个元素
v1.clear();             // 清空vector

5. 容量和大小

int size = v1.size();       // 当前元素数量
bool empty = v1.empty();    // 是否为空
int cap = v1.capacity();    // 当前分配的存储容量
v1.reserve(100);            // 预分配空间
v1.shrink_to_fit();         // 减少容量以匹配大小(C++11)

常用算法

#include <algorithm>sort(v1.begin(), v1.end());             // 排序
reverse(v1.begin(), v1.end());          // 反转
auto it = find(v1.begin(), v1.end(), 5); // 查找元素5
int cnt = count(v1.begin(), v1.end(), 5); // 计数

遍历vector

// 1. 使用下标
for(size_t i = 0; i < v1.size(); ++i) {cout << v1[i] << " ";
}// 2. 使用迭代器
for(auto it = v1.begin(); it != v1.end(); ++it) {cout << *it << " ";
}// 3. 范围for循环(C++11)
for(int num : v1) {cout << num << " ";
}

多维vector

vector<vector<int>> matrix(3, vector<int>(4)); // 3行4列矩阵
matrix[0][1] = 5; // 访问元素

性能特点

  • 随机访问：O(1)

  • 尾部插入/删除：O(1) 平摊

  • 中间/头部插入/删除：O(n)

  • 当容量不足时，重新分配内存通常是原大小的2倍(实现相关)

Vector 是 C++ 中最常用的容器之一，适用于需要频繁随机访问但主要在尾部添加/删除元素的场景。

Vector 的拷贝构造详解

vector<int> v5(v4); 这行代码使用了 vector 的拷贝构造函数，它创建了一个新的 vector v5，其内容是 v4 的完整副本。

拷贝构造的详细说明

  1. 基本概念：

    • 拷贝构造函数会创建一个新 vector，其元素是原 vector 的精确拷贝

    • 新 vector 的大小和容量与原 vector 相同

    • 元素会逐个拷贝（对于基本类型如 int 是值拷贝，对于对象会调用拷贝构造函数）

  2. 内存分配：

    • 新 vector 会分配自己的内存空间

    • 不会与原 vector 共享内存

    • 修改其中一个不会影响另一个

  3. 示例代码：

#include <iostream>
#include <vector>
using namespace std;int main() {vector<int> v4 = {1, 2, 3, 4, 5};// 使用拷贝构造创建v5vector<int> v5(v4);// 输出两个vector的内容cout << "v4: ";for(int num : v4) cout << num << " ";cout << "\nv5: ";for(int num : v5) cout << num << " ";// 修改v5不会影响v4v5[0] = 100;cout << "\nAfter modification:\n";cout << "v4: ";for(int num : v4) cout << num << " ";cout << "\nv5: ";for(int num : v5) cout << num << " ";return 0;
}

输出结果：

v4: 1 2 3 4 5 
v5: 1 2 3 4 5 
After modification:
v4: 1 2 3 4 5 
v5: 100 2 3 4 5

其他拷贝方式

  1. 赋值运算符：

    vector<int> v6;
v6 = v4;  // 使用赋值运算符拷贝

  2. 范围构造：

    vector<int> v7(v4.begin(), v4.end());  // 使用迭代器范围拷贝

  3. C++11 移动构造（非拷贝，转移所有权）：

    vector<int> v8(std::move(v4));  // v4的内容被"移动"到v8，v4变为空

性能考虑

  • 拷贝构造的时间复杂度是 O(n)，因为需要拷贝所有元素

  • 对于大型 vector，拷贝可能很昂贵

  • 如果不需要保留原 vector，考虑使用移动语义（C++11）

拷贝构造是创建 vector 副本的最直接方式，适用于需要独立修改副本而不影响原 vector 的场景。

Vector 元素访问方式比较：operator[] 和 at()

在 C++ 的 vector 中，有两种主要方式访问元素：使用 operator[] 和使用 at() 成员函数。它们有相似的功能但有重要区别。

1. 使用 operator[] 访问

int a = v1[0];  // 通过下标访问，不检查边界

特点：

  • 不进行边界检查：如果索引越界，行为是未定义的(UB)

  • 性能更高：因为没有额外的边界检查开销

  • 适用于：已知索引安全的情况，或对性能要求极高的代码

示例：

vector<int> v = {10, 20, 30};
cout << v[1];  // 输出20 - 安全访问
cout << v[5];  // 未定义行为 - 可能崩溃或输出垃圾值

2. 使用 at() 访问

int b = v1.at(1);  // 通过at访问，会检查边界

特点：

  • 进行边界检查：如果索引越界，抛出 std::out_of_range 异常

  • 安全性更高：适合不确定索引是否有效的情况

  • 性能稍低：因为有额外的边界检查开销

  • 适用于：用户输入或不确定索引是否有效的情况

示例：

vector<int> v = {10, 20, 30};
try {cout << v.at(1);  // 输出20 - 安全访问cout << v.at(5);  // 抛出std::out_of_range异常
} catch (const out_of_range& e) {cerr << "错误: " << e.what() << endl;
}

对比表格

特性operator[]at()
边界检查不检查检查
越界行为未定义行为抛出异常
性能更高稍低
安全性较低较高
适用场景已知索引安全的情况不确定索引是否有效

最佳实践建议

  1. 确定索引安全时使用 operator[]（如循环中的迭代变量）

    for(size_t i = 0; i < v.size(); ++i) {cout << v[i] << " ";  // 安全使用operator[]
}

  2. 不确定索引安全时使用 at()（如处理用户输入）

    size_t index;
cin >> index;
try {cout << "值: " << v.at(index);
} catch (const out_of_range&) {cout << "索引超出范围!";
}

  3. C++17 后可考虑使用 std::optional 或 if 检查结合 operator[]

    if(index < v.size()) {cout << v[index];
} else {cout << "索引无效";
}

记住：在调试阶段，使用 at() 可以帮助快速发现越界访问的问题，而在发布版本中，对已知安全的访问可以使用 operator[] 来提高性能。

C++ 中 map 实现：

  1. std::map（基于红黑树，有序）

  2. std::unordered_map（基于哈希表，无序）

1. std::map（有序映射）

  • 底层结构：红黑树（自平衡二叉搜索树）

  • 特点：

    • 键（key）按升序自动排序（默认 < 比较，可自定义排序规则）

    • 查找、插入、删除的时间复杂度：O(log n)

    • 适用于需要有序遍历的情况

基本用法

#include <iostream>
#include <map>int main() {std::map<std::string, int> ageMap;// 插入数据ageMap["Alice"] = 25;ageMap["Bob"] = 30;ageMap.insert({"Charlie", 35});// 访问数据std::cout << "Bob's age: " << ageMap["Bob"] << std::endl;// 遍历（按 key 升序）for (const auto& pair : ageMap) {std::cout << pair.first << ": " << pair.second << std::endl;}// 查找if (ageMap.find("Alice") != ageMap.end()) {std::cout << "Alice found!" << std::endl;}// 删除ageMap.erase("Bob");return 0;
}

输出：

Bob's age: 30
Alice: 25
Bob: 30
Charlie: 35
Alice found!

2. std::unordered_map（无序映射）

  • 底层结构：哈希表（Hash Table）

  • 特点：

    • 键无序（但访问更快）

    • 平均时间复杂度：O(1)（最坏情况 O(n)）

    • 适用于需要快速查找但不需要排序的情况

基本用法

#include <iostream>
#include <unordered_map>int main() {std::unordered_map<std::string, int> ageMap;// 插入数据ageMap["Alice"] = 25;ageMap["Bob"] = 30;ageMap.insert({"Charlie", 35});// 访问数据std::cout << "Bob's age: " << ageMap["Bob"] << std::endl;// 遍历（顺序不确定）for (const auto& pair : ageMap) {std::cout << pair.first << ": " << pair.second << std::endl;}// 查找if (ageMap.find("Alice") != ageMap.end()) {std::cout << "Alice found!" << std::endl;}// 删除ageMap.erase("Bob");return 0;
}

输出（顺序可能不同）：

Bob's age: 30
Charlie: 35
Alice: 25
Bob: 30
Alice found!

map vs unordered_map

特性std::mapstd::unordered_map
底层结构红黑树（有序）哈希表（无序）
查找时间O(log n)平均 O(1)，最坏 O(n)
插入/删除O(log n)平均 O(1)，最坏 O(n)
内存占用较低（树结构）较高（哈希表可能有冲突）
是否有序是（按 key 排序）否（顺序不确定）
适用场景需要有序遍历需要快速查找，不关心顺序

常见操作

1. 插入数据

std::map<std::string, int> m;
m["key1"] = 10;          // 方式1
m.insert({"key2", 20});   // 方式2
m.emplace("key3", 30);    // 方式3（更高效）

2. 访问数据

int val1 = m["key1"];  // 如果 key 不存在，会插入默认值（如 0）
int val2 = m.at("key2");  // 如果 key 不存在，抛出异常

3. 查找数据

auto it = m.find("key1");//m.find("key1")指在map/unordered_map 中查找键 "key1"
if (it != m.end()) {//说明键存在std::cout << "Found: " << it->second << std::endl;
}
//it->first 是键（key）
//it->second 是值（value）

4. 删除数据

m.erase("key1");  // 删除指定 key
m.erase(m.begin());  // 删除迭代器指向的元素
m.clear();  // 清空整个 map

5. 遍历

for (const auto& pair : m) {std::cout << pair.first << ": " << pair.second << std::endl;
}

6.降序

// 在 std::map 的模板参数中指定了比较函数 std::greater<std::string>，按 key 降序排序
std::map<std::string, int, std::greater<std::string>> ageMap = {{"Bob", 30},{"Alice", 25},{"Charlie", 35}
};
for (const auto& pair : ageMap) {std::cout << pair.first << ": " << pair.second << std::endl;
}//std::less<Key> 会让树保持 左小右大（升序）。
//std::greater<Key> 会让树保持 左大右小（降序）。

总结

  • std::map：有序，适用于需要排序的场景（如按 key 遍历）。

  • std::unordered_map：更快，适用于高频查找但不需要排序的场景。

  • 选择依据：

    • 需要排序？→ std::map

    • 需要最快查找？→ std::unordered_map

题解

两数之和

class Solution {
public:string mergeAlternately(string word1, string word2) {string result;int i = 0;while(i<word1.size()&&i<word2.size()){result += word1[i];result += word2[i];i++;}while(i<word1.size()){result += word1[i];i++;}while(i<word2.size()){result += word2[i];i++;}return result;}
};

 移动所有球到每个盒子所需的最小操作数

class Solution {
public:vector<int> minOperations(string boxes) {int n=boxes.size();vector<int> ballPositions;//记录所有小球1的位置for(int i = 0;i<n;++i){if(boxes[i]=='1'){//如果字符为1 将索引i存入ballPositionsballPositions.push_back(i);}}   vector<int> answer(n,0);//对于每个盒子位置i,计算所有小修移动到i的操作数之和for(int i = 0;i<n;++i){int operations = 0;//操作数for(int pos : ballPositions){//范围for循环，遍历ballPositions中的每个位置operations += abs(i-pos);//累加当前小球到位置i的距离（操作数）}answer[i] = operations;}  return answer;}
};

 字母异位词分组

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string,vector<string>> map;//创建了一个无序哈希表map，键是字符串类型，值是字符串向量类型。这个哈希表用于存储 "排序后的字符串" 与 "原始字符串列表" 的映射关系。键（key）是排序后的字符串（用于标识字母异位词组），值（value）是 vector<string> 类型，存储了该组所有的原始字母异位词for(string& s: strs){//遍历输入的字符串向量strs中的每个字符串sstring key = s;//对每个字符串s，先创建一个副本keysort(key.begin(),key.end());//对key进行排序（按字符顺序），这样所有字母异位词排序后会得到相同的keymap[key].push_back(s);//将原始字符串s添加到哈希表中对应key的向量里}  vector<vector<string>> result;//建结果向量result，用于存储最终的分组结果（返回的是二维的）for(auto& pair: map){ //循环遍历哈希表中的每一对键值对（pair）：result.push_back(pair.second);//我们将每个分组的字符串向量添加到结果向量中}return result;}
};

 交替合并字符串

class Solution {
public:string mergeAlternately(string word1, string word2) {string result;int i = 0;while(i<word1.size()&&i<word2.size()){result += word1[i];result += word2[i];i++;}while(i<word1.size()){result += word1[i];i++;}while(i<word2.size()){result += word2[i];i++;}return result;}
};

 

 

http://www.lryc.cn/news/604098.html

相关文章：

  • ICT模拟零件测试方法--晶体管测试
  • 智能Agent场景实战指南 Day 23 : Agent安全与隐私保护
  • k8s搭建nfs共享存储
  • Ubuntu20.04安装和配置Samba实现Win11下共享文件夹
  • 工作中使用git可能遇到的场景
  • Leetcode 08 java
  • Linux笔记6——常用命令-5
  • 【核心技术一】Python异步编程深度解析
  • 基于springboot的零食商城的设计与实现/零食销售系统的设计与实现
  • 第2章 AB实验的关键问题
  • 全自动植树机solidwoeks图纸cad【7张】三维图＋设计说明说
  • sqli-labs通关笔记-第25关GET字符注入(过滤or和and 脚本法)
  • QWebEngineProfile setCachePath无效
  • 对College数据进行多模型预测(R语言)
  • 青少年软件编程图形化Scratch等级考试试卷（三级）2025年6月
  • 日语学习-日语知识点小记-构建基础-JLPT-N3阶段（11）：文法+单词
  • 层次分析法（Analytic Hierarchy Process，AHP）简介与简单示例
  • Qt 多线程数据库操作优化
  • MOGA（多目标遗传算法）求解 ZDT1 双目标优化问题
  • 选用Java开发商城的优势
  • Python的魔术方法
  • 答题抽奖活动小程序技术复盘
  • ETF期权的交割日对股市有什么影响？
  • 津发科技带你了解皮肤电信号中的SCL与SCR
  • 智慧园区系统引领未来：一场科技与生活的完美融合
  • LaTeX 下载安装保姆级教程
  • MC0244多重堡垒
  • SAP-ABAP：Excel 文件内容解析到 ABAP 内表函数ALSM_EXCEL_TO_INTERNAL_TABLE运用详解
  • Elasticsearch重点
  • 【高等数学】第七章 微分方程——第三节 齐次方程