資料結構
網路
關係資料庫管理系統 (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
廣告