Mündəricat
Problem bəyanat
Web Crawler LeetCode Həlli – URL verilmişdir startUrl və interfeys HtmlParser, altında olan bütün bağlantıları taramaq üçün veb tarayıcı tətbiq edin eyni host adı as startUrl.
Veb tarayıcınız tərəfindən əldə edilən bütün URL-ləri geri qaytarın hər üçün.
Tarayıcınız:
- Səhifədən başlayın:
startUrl - çağırış
HtmlParser.getUrls(url)verilmiş URL-in veb səhifəsindən bütün URL-ləri əldə etmək. - Eyni keçidi iki dəfə taramayın.
- Yalnız altındakı bağlantıları araşdırın eyni host adı as
startUrl
Yuxarıdakı nümunə URL-də göstərildiyi kimi, host adı belədir example.org. Sadəlik naminə, bütün URL-lərin istifadə edildiyini güman edə bilərsiniz HTTP protokolu heç port müəyyən edilmişdir. Məsələn, URL-lər http://leetcode.com/problems və http://leetcode.com/contest URL-lər eyni host adı altındadır http://example.org/test və http://example.com/abc eyni host adı altında deyil.
The HtmlParser interfeysi belə müəyyən edilir:
interface HtmlParser {
// Return a
verilmiş veb səhifəsindən bütün URL-lərin siyahısı
url.
public List<String> getUrls(String url);
}
Aşağıda problemin funksionallığını izah edən iki nümunə verilmişdir, fərdi test məqsədləri üçün üç dəyişənə sahib olacaqsınız. urls, edges və startUrl. Diqqət yetirin ki, yalnız girişiniz olacaq startUrl kodunuzda isə urls və edges kodda sizin üçün birbaşa əlçatan deyil.
Input: 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/" Output: [ "http://news.yahoo.com", "http://news.yahoo.com/news", "http://news.yahoo.com/news/topics/", "http://news.yahoo.com/us" ]
Izahat
Hər bir URL istiqamətləndirilmiş qrafikin qovşağı kimi qəbul edilə bilər və biz htmlParser-in getUrls funksiyasına zəng etdikdə cari qovşaq (yəni URL) ilə əlaqəli kənarları alırıq. Beləliklə, müəyyən bir kənarın etibarlı olub olmadığını (hər ikisi üçün host adı eynidir) yoxlayan sadə BFS/DFS keçidi işləyəcək və əgər bu etibarlı kənardırsa, biz onu nəticəyə əlavə edə bilərik.
Kodu
Web Crawler LeetCode Həlli üçün Java Kodu
class Solution {
public List<String> crawl(String startUrl, HtmlParser htmlParser) {
Set<String> set = new HashSet<>();
Queue<String> queue = new LinkedList<>();
String hostname = getHostname(startUrl);
queue.offer(startUrl);
set.add(startUrl);
while (!queue.isEmpty()) {
String currentUrl = queue.poll();
for (String url : htmlParser.getUrls(currentUrl)) {
if (url.contains(hostname) && !set.contains(url)) {
queue.offer(url);
set.add(url);
}
}
}
return new ArrayList<String>(set);
}
private String getHostname(String Url) {
String[] ss = Url.split("/");
return ss[2];
}
}
Web Crawler LeetCode Həlli üçün C++ Kodu
class Solution {
public:
vector<string> crawl(string startUrl, HtmlParser htmlParser) {
const string hostname = startUrl.substr(0, startUrl.find('/', 7));
vector<string> q {startUrl};
unordered_set<string> seen(q.cbegin(), q.cend());
for (int i = 0; i < q.size(); ++i) {
string url = q[i];
for (auto& child : htmlParser.getUrls(url)) {
if (child.find(hostname) == string::npos || seen.count(child)) continue;
q.push_back(child);
seen.insert(child);
}
}
return q;
}
};
Veb Tarayıcı LeetCode Həlli üçün Python Kodu
class Solution:
def crawl(self, startUrl: str, htmlParser: 'HtmlParser') -> List[str]:
visited = {startUrl}
domain = startUrl.split("http://")[1].split("/")[0]
ans = [startUrl]
queue = collections.deque([startUrl])
while queue:
for _ in range(len(queue)):
url = queue.popleft()
check = htmlParser.getUrls(url)
for new_url in check:
if new_url in visited:
continue
if new_url.split("http://")[1].split("/")[0] != domain:
continue
ans.append(new_url)
visited.add(new_url)
queue.append(new_url)
return ans
Mürəkkəblik təhlili
Zamanın mürəkkəbliyi
O(N) çünki biz hər bir node bir dəfə baş çəkirdik.
Kosmik Mürəkkəblik
O(N) çünki qonşu qovşaqları izləmək üçün növbəmiz olacaq.
