leetcode 399
问题
问题例子
解题思路
图作为数据结构, 使用广度遍历搜索。
算法实现
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <string>
#include <queue>
using namespace std;
#define LOG(msg) std::cout << __func__ << " (line " << __LINE__ << "): " << msg << std::endl
class Solution {
public:
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
// unordered_map 相当于动态数组,搜索是O(1)
unordered_map<string, int> var;
int id = 0;
int size = equations.size();
for(int i=0; i<size; i++){
string va = equations[i][0];
string vb = equations[i][1];
if(var.find(va) == var.end()){
var[va] = id++;
}
if(var.find(vb) == var.end()){
var[vb] = id++;
}
}
int n_var = id;
//使用vector<vector<double>> 实现图,不使用哈希, 使用index 访问效率更好~
vector<vector<pair<int, double> > > edge(n_var);
for(int i=0; i< equations.size(); i++){
string va = equations[i][0];
string vb = equations[i][1];
int va_id = var[va];
int vb_id = var[vb];
edge[va_id].push_back(make_pair(vb_id, values[i]));
edge[vb_id].push_back(make_pair(va_id, 1.0/values[i]));
}
vector<double> ret;
for(int i=0; i<queries.size(); i++){
double res = -1.0;
string va = queries[i][0];
string vb = queries[i][1];
if(va == vb){
//queries 的第一个和第二个字符串相同,直接返回 1;
if(var.find(va) == var.end()){
ret.push_back(res);
}else{
ret.push_back(1.0);
}
LOG("queries va:"<<va<<", vb:"<<vb);
}else{
if(var.find(va) != var.end() && var.find(vb) != var.end()){
int va_id = var[va];
int vb_id = var[vb];
queue<int> buf;
buf.push(va_id);
/*
(a,a) ratios[va_id] = 1
(a,b) ratios[vb_id] = ratios[va_id] * val
ratios 默认除了 ratios[va_id] 之外都是负数,不会对非负ratios值进行更新,
ratios[vx_id] 表示(a,x) 的值,不需要再进行更新。
*/
vector<double> ratios(n_var, -1);
ratios[va_id] = 1.0;
//buf不为空,并且还没有获得(a,b)的值
while(!buf.empty() && ratios[vb_id] <0){
//获取buf的第一个元素
int cur_id = buf.front();
for(const auto [y, cur_val]: edge[cur_id]){
if(ratios[y] <0){
LOG("y:"<<y<<",cur_val:"<<cur_val);
//ratios 记录(a, cur_id)的值, 同时将cur_id放入buffer
ratios[y] = ratios[cur_id] * cur_val;
LOG("y:"<<y<<",ratios[y]:"<<ratios[y]);
//例如(a,b) a已经放入queue, 现在将b放入queue
buf.push(y);
}
}
buf.pop();
}
res = ratios[vb_id];
LOG("queries va:"<<va<<", vb:"<<vb);
LOG("res:"<<res<<", vb_id"<<vb_id<<", ratios"<<ratios[vb_id]);
ret.push_back(res);
}else{
//var不存在queries 的string, 返回-1
ret.push_back(res);
LOG("queries va:"<<va<<", vb:"<<vb);
}
}
}
return ret;
}
};
int main(){
Solution s;
setlocale(LC_ALL, "en_US.UTF-8");
vector<vector<string>> equations = {{"a","b"}, {"b","c"}};
vector<double> values = {2.0,3.0};
// vector<vector<string>> queries = {{"a","c"}, {"b","a"}, {"a","e"}, {"a","a"}, {"x","x"}};
vector<vector<string>> queries = {{"a","c"}};
vector<double> res = s.calcEquation(equations, values, queries);
return 0;
}
数据结构
unordered map
unordered_map
是 C++ STL 中的一个关联容器,它提供了一种键-值对的映射关系,类似于字典或哈希表。与 map
不同的是,unordered_map
使用哈希表来实现,因此插入、查找和删除操作的平均时间复杂度为 O(1)。
下面是关于 unordered_map
的一些介绍:
特点:
unordered_map
是基于哈希表实现的关联容器,可以快速插入、查找和删除元素。- 元素不按照插入顺序排序,而是根据键的哈希值进行存储和访问。
- 支持快速的查找操作,平均时间复杂度为 O(1)。
- 支持键和值的任意类型,可以自定义哈希函数。
- 不支持重复的键,每个键只能对应一个值。
使用方式:
- 首先包含
<unordered_map>
头文件。 - 创建
unordered_map
对象并指定键和值的类型,如unordered_map<int, string> myMap;
。 - 使用
insert()
方法插入键值对,使用find()
方法查找键对应的值,使用erase()
方法删除键值对。 - 可以使用迭代器遍历
unordered_map
中的所有元素。
- 首先包含
示例代码:
#include <iostream> #include <unordered_map> int main() { std::unordered_map<int, std::string> myMap; myMap.insert({1, "apple"}); myMap.insert({2, "banana"}); auto it = myMap.find(1); if (it != myMap.end()) { std::cout << "Value for key 1: " << it->second << std::endl; } myMap.erase(2); for (auto& pair : myMap) { std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl; } return 0; }
注意事项:
- 在使用自定义类型作为键时,需要提供哈希函数和相等比较函数。
- 插入、查找和删除操作的性能高效,适合需要快速查找和检索的场景。
unordered_map
不保证元素的顺序,如果需要有序的键值对,可以考虑使用map
。
总的来说,unordered_map
提供了一种高效的键值对映射容器,适用于需要快速查找和插入操作的场景。
std::unordered_map
是 C++ 标准库中的关联容器,提供了一种键-值对的映射关系。下面是一个简单的例子,展示了 std::unordered_map
的基本用法:
#include <iostream>
#include <unordered_map>
#include <string>
int main() {
// 创建一个 unordered_map,键为字符串类型,值为整数类型
std::unordered_map<std::string, int> myMap;
// 插入键值对
myMap["apple"] = 5;
myMap["banana"] = 3;
myMap["orange"] = 7;
// 访问元素
std::cout << "Number of apples: " << myMap["apple"] << std::endl;
// 检查元素是否存在
if (myMap.find("banana") != myMap.end()) {
std::cout << "Number of bananas: " << myMap["banana"] << std::endl;
}
// 遍历整个 unordered_map
for (const auto& pair : myMap) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
return 0;
}
在上面的例子中,我们首先创建了一个 std::unordered_map
对象 myMap
,键为字符串类型,值为整数类型。然后我们向 myMap
中插入了一些键值对,并展示了如何访问元素、检查元素是否存在以及遍历整个 std::unordered_map
。
需要注意的是,std::unordered_map
是无序的,键值对的顺序不固定。如果需要按特定顺序访问 std::unordered_map
中的元素,可以考虑使用 std::map
,它是有序的关联容器。
vector
vector
是 C++ STL 中的一个动态数组容器,它能够存储一组连续的元素,并且支持动态扩展和缩小容量。vector
提供了许多便捷的方法来操作元素,是 C++ 中常用的容器之一。
下面是关于 vector
的一些介绍:
特点:
vector
是一个动态数组,可以根据需要动态增加或减少容量。- 元素在内存中是连续存储的,支持快速的随机访问。
- 提供了丰富的方法来操作元素,如插入、删除、查找等。
- 可以自定义存储的元素类型,支持任意类型的元素。
使用方式:
- 首先包含
<vector>
头文件。 - 创建
vector
对象并指定存储的元素类型,如std::vector<int> myVector;
。 - 使用
push_back()
方法在末尾插入元素,使用pop_back()
方法删除末尾元素。 - 可以通过下标访问元素,使用
at()
方法进行安全的访问。 - 可以使用迭代器遍历
vector
中的所有元素。
- 首先包含
示例代码:
#include <iostream> #include <vector> int main() { std::vector<int> myVector; myVector.push_back(10); myVector.push_back(20); std::cout << "Size of vector: " << myVector.size() << std::endl; for (int i = 0; i < myVector.size(); ++i) { std::cout << "Element at index " << i << ": " << myVector[i] << std::endl; } myVector.pop_back(); for (auto it = myVector.begin(); it != myVector.end(); ++it) { std::cout << "Element: " << *it << std::endl; } return 0; }
注意事项:
- 当
vector
需要动态增加容量时,可能会导致重新分配内存和复制元素,影响性能。 - 使用
reserve()
方法可以提前分配一定的容量,避免不必要的内存分配。 - 在需要频繁插入和删除元素的情况下,考虑使用
list
或deque
容器,它们在插入和删除操作上更高效。
- 当
总的来说,vector
是一个灵活、高效的动态数组容器,适用于需要随机访问和动态调整大小的情况。通过合理地使用 vector
,可以方便地管理一组元素,并进行各种操作。
queue
在 C++ STL(标准模板库)中,std::queue
是一个队列容器适配器,它提供了一个先进先出(FIFO)的数据结构。std::queue
是基于 std::deque
(双端队列)实现的,也可以基于 std::list
实现。
以下是 std::queue
的一些重要特点和常用操作:
- 特点:
- 元素按照先进先出的顺序排列,即最先进入队列的元素最先被取出。
- 不支持随机访问,只能在队列的前端(front)和后端(back)进行操作。
- 提供了入队(push)、出队(pop)、访问队首元素(front)、访问队尾元素(back)等操作。
- 常用操作:
push(val)
: 将元素val
入队,即将元素添加到队列的末尾。pop()
: 将队首元素出队,即删除队列中的第一个元素。front()
: 返回队首元素的引用,但不删除该元素。back()
: 返回队尾元素的引用,但不删除该元素。empty()
: 判断队列是否为空,返回true
表示队列为空,返回false
表示队列非空。size()
: 返回队列中元素的个数。
下面是一个简单的示例展示如何使用 std::queue
:
#include <iostream>
#include <queue>
int main() {
std::queue<int> myQueue;
myQueue.push(1);
myQueue.push(2);
myQueue.push(3);
std::cout << "Queue size: " << myQueue.size() << std::endl; // 输出队列大小
while (!myQueue.empty()) {
std::cout << myQueue.front() << " "; // 输出队首元素
myQueue.pop(); // 出队
}
std::cout << std::endl;
return 0;
}
总的来说,std::queue
提供了一个简单易用的队列数据结构,适用于需要先进先出操作的场景。在实际应用中,可以根据具体需求选择合适的容器适配器。