【leetcode】1257. Smallest Common Region
2024-10-07 02:01:38
题目如下:
You are given some lists of
regions
where the first region of each list includes all other regions in that list.Naturally, if a region
X
contains another regionY
thenX
is bigger thanY
.Given two regions
region1
,region2
, find out the smallest region that contains both of them.If you are given regions
r1
,r2
andr3
such thatr1
includesr3
, it is guaranteed there is nor2
such thatr2
includesr3
.It's guaranteed the smallest region exists.
Example 1:
Input:
regions = [["Earth","North America","South America"],
["North America","United States","Canada"],
["United States","New York","Boston"],
["Canada","Ontario","Quebec"],
["South America","Brazil"]],
region1 = "Quebec",
region2 = "New York"
Output: "North America"Constraints:
2 <= regions.length <= 10^4
region1 != region2
- All strings consist of English letters and spaces with at most 20 letters.
解题思路:首先递归找出region1所属的regions链,并保持结果;然后再递归查找region2所属的regions链,找到第一个region在region1所属的regions链即可。
代码如下:
class Solution(object):
def findSmallestRegion(self, regions, region1, region2):
"""
:type regions: List[List[str]]
:type region1: str
:type region2: str
:rtype: str
"""
dic = {}
for region in regions:
parent = region[0]
for i in range(1,len(region)):
dic[region[i]] = parent dic_region1 = {}
while region1 in dic:
dic_region1[region1] = 1
region1 = dic[region1] while region2 in dic:
if region2 in dic_region1:
return region2
region2 = dic[region2]
return regions[0][0]
最新文章
- 基于netty http协议栈的轻量级流程控制组件的实现
- [转]Python 字符串操作实现代码(截取/替换/查找/分割)
- 打开hibernate文件报警告
- iOS UIButton setTitle与setAttributedTitle
- 移动端打印调试插件 - debug.js 介绍
- 从官方ROM中提取原生APK
- cxf(3.1.1) 异常Caused by: java.io.FileNotFoundException: class path resource [META-INF/cxf/cxf-extension-soap.xml]
- Jump Game II
- 在VSTO界面中,调用xll中的函数
- (转)myrepo
- 决策树简单介绍(二) Accord.Net中决策树的实现和使用
- android WebView, WebChromeClient和WebViewClient加载网页基本用法
- 机器学习 1、R语言
- 转 git操作小结
- R语言RJava安装步骤
- [LeetCode116]Path Sum
- MR-join连接1......
- 《生命》第三集:Mammals (哺乳动物)
- HTTP协议07-通用首部字段
- jquery-json 插件使用方法