难度: Medium
Submission
运行时间: 172 ms
内存: 0.0 MB
# """
# This is HtmlParser's API interface.
# You should not implement it, or speculate about its implementation
# """
#class HtmlParser(object):
# def getUrls(self, url):
# """
# :type url: str
# :rtype List[str]
# """
import queue
Queue = queue.Queue
def get_domain_name(url):
# url = url[len('http://'):]
# hostname = url.split('/')[0]
# return f'http://{hostname}'
return url.split('/')[2]
class Solution:
def crawl(self, startUrl: str, htmlParser: 'HtmlParser') -> List[str]:
q = Queue()
q.put(startUrl)
seen = set()
seen.add(startUrl)
#res = [startUrl]
target_domain_name = get_domain_name(startUrl)
while(not q.empty()):
url = q.get()
candidate_urls = htmlParser.getUrls(url)
for c in candidate_urls:
if c not in seen and target_domain_name == get_domain_name(c):
q.put(c)
seen.add(c)
#res.append(c)
return list(seen)
Explain
本题解采用广度优先搜索（BFS）策略来遍历所有与起始URL具有相同域名的网页。首先，定义一个队列来存储待访问的URL，并将起始URL加入队列和已访问集合。然后，从队列中逐个取出URL，利用HtmlParser的getUrls方法获取该URL页面上的所有链接。对于每个链接，如果它未被访问过且域名与起始URL相同，就将其加入队列和已访问集合。最终，返回已访问集合中的所有URL，即为所有可达的同域名URL。
时间复杂度: O(N*M)
空间复杂度: O(N)
# 解析HtmlParser API的接口定义
# class HtmlParser(object):
# def getUrls(self, url):
# \"\"\"
# :type url: str
# :rtype List[str]
# \"\"\"
import queue
Queue = queue.Queue
def get_domain_name(url):
# 提取URL的域名部分
return url.split('/')[2]
class Solution:
def crawl(self, startUrl: str, htmlParser: 'HtmlParser') -> List[str]:
q = Queue()
q.put(startUrl)
seen = set()
seen.add(startUrl)
target_domain_name = get_domain_name(startUrl)
while(not q.empty()):
url = q.get()
candidate_urls = htmlParser.getUrls(url)
for c in candidate_urls:
if c not in seen and target_domain_name == get_domain_name(c):
q.put(c)
seen.add(c)
return list(seen)
Explore
在广度优先搜索（BFS）的实现中，我们通过对每个新发现的URL进行域名检查来确保只访问与起始URL域名相同的网页。具体方法是，定义一个辅助函数 `get_domain_name` 用于从URL中提取域名，然后在将URL添加到队列之前，比较其域名与起始URL的域名是否相同。只有当域名相同时，该URL才会被加入队列和已访问集合。这样可以有效防止访问到不同域名的网页。
HtmlParser的getUrls方法的行为依赖于其具体实现。一般而言，我们假设它返回页面上的所有链接（包括相对链接和绝对链接），但不必然保证这些链接都是有效或可访问的。在实际应用中，返回的URL列表可能包含已经失效或无法访问的链接，因此在实际使用中可能需要额外的错误处理或验证机制来确保链接的有效性。
如果URL格式不标准，如缺少协议头（例如，'http://'或'https://'），`get_domain_name`函数可能无法正确解析域名。在当前的实现中，函数通过分割URL字符串来获取域名，如果URL不符合预期的格式，这种简单的分割方法可能会导致错误或异常。因此，对于不标准或异常的URL格式，可能需要更健壮的解析策略，如使用正则表达式或专门的URL解析库来处理这种情况。
在处理大量的URL时，队列操作（如put和get）确实可能成为性能瓶颈。队列的大小可能迅速增长，尤其是在网页链接密集的情况下，这可能导致内存消耗大量增加。此外，频繁的队列操作可能影响总体性能。为了优化，可以考虑使用更高效的队列实现，例如使用并发队列（在多线程环境中），或者对URL进行批处理以减少队列操作次数。另外，使用更高效的数据结构（如双端队列）可能也有助于提升性能。