网站建设培训班学费,设计网站实现PDF在线阅读需要怎么做,设置网站文件夹的安全项,国际域名和国内域名区别文章目录1. 题目2. 解题2.1 BFS2.2 DFS1. 题目
给定一个链接 startUrl 和一个接口 HtmlParser #xff0c;请你实现一个网络爬虫#xff0c;以实现爬取同 startUrl 拥有相同 域名标签 的全部链接。该爬虫得到的全部链接可以 任何顺序 返回结果。
你的网络爬虫应当按照如下模…
文章目录1. 题目2. 解题2.1 BFS2.2 DFS1. 题目
给定一个链接 startUrl 和一个接口 HtmlParser 请你实现一个网络爬虫以实现爬取同 startUrl 拥有相同 域名标签 的全部链接。该爬虫得到的全部链接可以 任何顺序 返回结果。
你的网络爬虫应当按照如下模式工作
自链接 startUrl 开始爬取调用 HtmlParser.getUrls(url) 来获得链接url页面中的全部链接同一个链接最多只爬取一次只输出 域名 与 startUrl 相同 的链接集合 如上所示的一个链接其域名为 example.org。 简单起见你可以假设所有的链接都采用 http协议 并没有指定 端口。 例如链接 http://leetcode.com/problems 和 http://leetcode.com/contest 是同一个域名下的 而链接http://example.org/test 和 http://example.com/abc 是不在同一域名下的。
HtmlParser 接口定义如下 interface HtmlParser {// 返回给定 url 对应的页面中的全部 url 。public ListString getUrls(String url);
}下面是两个实例用以解释该问题的设计功能对于自定义测试你可以使用三个变量 urls, edges 和 startUrl。 注意在代码实现中你只可以访问 startUrl 而 urls 和 edges 不可以在你的代码中被直接访问。
示例 1
输入
urls [http://news.yahoo.com,http://news.yahoo.com/news,http://news.yahoo.com/news/topics/,http://news.google.com,http://news.yahoo.com/us
]
edges [[2,0],[2,1],[3,2],[3,1],[0,4]]
startUrl http://news.yahoo.com/news/topics/
输出[http://news.yahoo.com,http://news.yahoo.com/news,http://news.yahoo.com/news/topics/,http://news.yahoo.com/us
]示例 2
输入
urls [http://news.yahoo.com,http://news.yahoo.com/news,http://news.yahoo.com/news/topics/,http://news.google.com
]
edges [[0,2],[2,1],[3,2],[3,1],[3,0]]
startUrl http://news.google.com
输入[http://news.google.com]
解释startUrl 链接到所有其他不共享相同主机名的页面。提示
1 urls.length 1000
1 urls[i].length 300
startUrl 为 urls 中的一个。
域名标签的长为1到63个字符包括点只能包含从‘a’到‘z’的ASCII字母、‘0’到‘9’的数字以及连字符即减号‘-’。
域名标签不会以连字符即减号‘-’开头或结尾。
关于域名有效性的约束可参考: https://en.wikipedia.org/wiki/Hostname#Restrictions_on_valid_hostnames
你可以假定url库中不包含重复项。来源力扣LeetCode 链接https://leetcode-cn.com/problems/web-crawler 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
简单的BFS或者DFS模板题
2.1 BFS
/*** // This is the HtmlParsers API interface.* // You should not implement it, or speculate about its implementation* class HtmlParser {* public:* vectorstring getUrls(string url);* };*/class Solution {
public:vectorstring crawl(string startUrl, HtmlParser htmlParser) {unordered_setstring visited;visited.insert(startUrl);queuestring q;q.push(startUrl);vectorstring ans;string cur, domain;while(!q.empty()){cur q.front();ans.push_back(cur);q.pop();domain getdomain(cur);vectorstring sub htmlParser.getUrls(cur);for(string link : sub){if(getdomain(link) domain !visited.count(link)){q.push(link);visited.insert(link);}}}return ans;}string getdomain(string url) {auto it find(url.begin()7, url.end(), /);return string(url.begin(), it);}
};184 ms 32.9 MB
2.2 DFS
class Solution {unordered_setstring visited;vectorstring ans;
public:vectorstring crawl(string startUrl, HtmlParser htmlParser) {visited.insert(startUrl);dfs(startUrl, htmlParser);return ans;}void dfs(string cur, HtmlParser htmlParser){ans.push_back(cur);string domain getdomain(cur);vectorstring sub htmlParser.getUrls(cur);for(string link : sub){if(getdomain(link) domain !visited.count(link)){visited.insert(link);dfs(link, htmlParser);}}}string getdomain(string url) {auto it find(url.begin()7, url.end(), /);return string(url.begin(), it);}
};我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
