数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++ 中的最小公共区域
假设我们有一些区域列表，每个列表的第一个区域包含该列表中的所有其他区域。基本上，如果区域 X 包含另一个区域 Y，则 X 大于 Y。根据定义，区域 X 包含自身。因此，如果我们有两个区域 r1 和 r2，我们必须找到包含这两个区域的最小区域。因此，如果我们有 r1、r2 和 r3，使得 r1 包含 r3，则保证不存在 r2 使得 r2 包含 r3。因此，如果输入类似于 [["Earth","North America","South America"], ["North America","United States","Canada"], ["United States","New York","Boston"],["Canada","Ontario","Quebec"],["South America","Brazil"]]，并且 r1 = ‘Quebec’ 且 r2 = ‘New York’，则输出将为 ‘North America’
为了解决这个问题，我们将遵循以下步骤：
- 创建一个名为 parent 的映射
- 对于 i 从 0 到 r 的大小
- 对于 j 从 1 到 r[i] 的大小
- parent[r[i, j]] := r[i, 0]
- 对于 j 从 1 到 r[i] 的大小
- 创建一个名为 chain 的集合，并将 x 插入到 chain 中
- 当 x 在 parent 中时，
- x := parent[x]
- 将 x 插入到 chain 中
- 当 y 存在于 chain 中时
- y := parent[y]
- 返回 y
让我们看看下面的实现来更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string findSmallestRegion(vector<vector<string>>& r, string x, string y) {
map < string, string> parent;
for(int i = 0; i < r.size(); i++){
for(int j = 1; j < r[i].size(); j++){
parent[r[i][j]] = r[i][0];
}
}
set <string> chain;
chain.insert(x);
while(parent.find(x)!=parent.end()){
x = parent[x];
chain.insert(x);
}
while(chain.find(y)==chain.end()){
y = parent[y];
}
return y;
}
};
main(){
vector<vector<string>> v = {
{"Earth","North America","South America"},
{"North America","United States","Canada"},
{"United States","New York","Boston"},
{"Canada","Ontario","Quebec"},{"South America","Brazil"}
};
Solution ob;
cout << (ob.findSmallestRegion(v, "Quebec", "New York"));
}输入
[["Earth","North America","South America"],["North America","United States","Canada"], ["United States","New York","Boston"],["Canada","Ontario","Quebec"],["South America","Brazil"]] "Quebec" "New York"
输出
North America
更新于：2020年5月2日
浏览量：130
广告