Java | LeetCode
Задача: 1242. Web Crawler Multithreaded
Сложность: medium
Учитывая URL startUrl и интерфейс HtmlParser, реализуйте многопоточный веб-краулер, который будет просматривать все ссылки, находящиеся под тем же именем хоста, что и startUrl. Верните все URL, полученные вашим веб-краулером, в любом порядке.
Ваш краулер должен: Начинать со страницы: startUrl Вызывать HtmlParser.getUrls(url), чтобы получить все URL с веб-страницы данного URL. Не просматривать одну и ту же ссылку дважды. Исследовать только те ссылки, которые находятся под тем же именем хоста, что и startUrl.
Пример:
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"
]
👨💻 Алгоритм:
1⃣Извлечь имя хоста из startUrl.
Использовать многопоточность для обработки URL-адресов.
2⃣Хранить посещенные URL-адреса, чтобы избежать повторного посещения.
3⃣Использовать HtmlParser для получения URL-адресов с веб-страниц.
😎 Решение:
import java.net.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicBoolean;
class HtmlParser {
public List<String> getUrls(String url) {
return new ArrayList<>();
}
}
public class Solution {
public List<String> crawl(String startUrl, HtmlParser htmlParser) {
String hostname = extractHostname(startUrl);
Set<String> visited = ConcurrentHashMap.newKeySet();
ExecutorService executor = Executors.newFixedThreadPool(10);
Queue<Future<?>> futures = new ConcurrentLinkedQueue<>();
visited.add(startUrl);
futures.add(executor.submit(() -> visit(startUrl, htmlParser, hostname, visited, futures, executor)));
while (!futures.isEmpty()) {
try {
futures.poll().get();
} catch (InterruptedException | ExecutionException e) {
e.printStackTrace();
}
}
executor.shutdown();
return new ArrayList<>(visited);
}
private void visit(String url, HtmlParser htmlParser, String hostname, Set<String> visited, Queue<Future<?>> futures, ExecutorService executor) {
for (String nextUrl : htmlParser.getUrls(url)) {
if (extractHostname(nextUrl).equals(hostname) && visited.add(nextUrl)) {
futures.add(executor.submit(() -> visit(nextUrl, htmlParser, hostname, visited, futures, executor)));
}
}
}
private String extractHostname(String url) {
try {
URL u = new URL(url);
return u.getHost();
} catch (MalformedURLException e) {
e.printStackTrace();
return "";
}
}
}
Ставь 👍 и забирай 📚 Базу знаний
2 · 402 ·