leetcode 399

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

数据结构

unordered map

unordered_map 是 C++ STL 中的一个关联容器，它提供了一种键-值对的映射关系，类似于字典或哈希表。与 map 不同的是，unordered_map 使用哈希表来实现，因此插入、查找和删除操作的平均时间复杂度为 O(1)。

下面是关于 unordered_map 的一些介绍：

1. 特点：

   • unordered_map 是基于哈希表实现的关联容器，可以快速插入、查找和删除元素。
   • 元素不按照插入顺序排序，而是根据键的哈希值进行存储和访问。
   • 支持快速的查找操作，平均时间复杂度为 O(1)。
   • 支持键和值的任意类型，可以自定义哈希函数。
   • 不支持重复的键，每个键只能对应一个值。

2. 使用方式：

   • 首先包含 <unordered_map> 头文件。
   • 创建 unordered_map 对象并指定键和值的类型，如 unordered_map<int, string> myMap;。
   • 使用 insert() 方法插入键值对，使用 find() 方法查找键对应的值，使用 erase() 方法删除键值对。
   • 可以使用迭代器遍历 unordered_map 中的所有元素。

3. 示例代码：

   #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;
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21

4. 注意事项：

   • 在使用自定义类型作为键时，需要提供哈希函数和相等比较函数。
   • 插入、查找和删除操作的性能高效，适合需要快速查找和检索的场景。
   • 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

在上面的例子中，我们首先创建了一个 std::unordered_map 对象 myMap，键为字符串类型，值为整数类型。然后我们向 myMap 中插入了一些键值对，并展示了如何访问元素、检查元素是否存在以及遍历整个 std::unordered_map。

需要注意的是，std::unordered_map 是无序的，键值对的顺序不固定。如果需要按特定顺序访问 std::unordered_map 中的元素，可以考虑使用 std::map，它是有序的关联容器。

vector

vector 是 C++ STL 中的一个动态数组容器，它能够存储一组连续的元素，并且支持动态扩展和缩小容量。vector 提供了许多便捷的方法来操作元素，是 C++ 中常用的容器之一。

下面是关于 vector 的一些介绍：

1. 特点：

   • vector 是一个动态数组，可以根据需要动态增加或减少容量。
   • 元素在内存中是连续存储的，支持快速的随机访问。
   • 提供了丰富的方法来操作元素，如插入、删除、查找等。
   • 可以自定义存储的元素类型，支持任意类型的元素。

2. 使用方式：

   • 首先包含 <vector> 头文件。
   • 创建 vector 对象并指定存储的元素类型，如 std::vector<int> myVector;。
   • 使用 push_back() 方法在末尾插入元素，使用 pop_back() 方法删除末尾元素。
   • 可以通过下标访问元素，使用 at() 方法进行安全的访问。
   • 可以使用迭代器遍历 vector 中的所有元素。

3. 示例代码：

   #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;
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22

4. 注意事项：

   • 当 vector 需要动态增加容量时，可能会导致重新分配内存和复制元素，影响性能。
   • 使用 reserve() 方法可以提前分配一定的容量，避免不必要的内存分配。
   • 在需要频繁插入和删除元素的情况下，考虑使用 list 或 deque 容器，它们在插入和删除操作上更高效。

总的来说，vector 是一个灵活、高效的动态数组容器，适用于需要随机访问和动态调整大小的情况。通过合理地使用 vector，可以方便地管理一组元素，并进行各种操作。

queue

在 C++ STL（标准模板库）中，std::queue 是一个队列容器适配器，它提供了一个先进先出（FIFO）的数据结构。std::queue 是基于 std::deque（双端队列）实现的，也可以基于 std::list 实现。

以下是 std::queue 的一些重要特点和常用操作：

1. 特点：

• 元素按照先进先出的顺序排列，即最先进入队列的元素最先被取出。
• 不支持随机访问，只能在队列的前端（front）和后端（back）进行操作。
• 提供了入队（push）、出队（pop）、访问队首元素（front）、访问队尾元素（back）等操作。

2. 常用操作：

• 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

总的来说，std::queue 提供了一个简单易用的队列数据结构，适用于需要先进先出操作的场景。在实际应用中，可以根据具体需求选择合适的容器适配器。