LeetCode 1236. 网络爬虫

Categories:

题目描述
思路分析
1. 解法一：BFS + 同域名过滤（推荐）
相似题目

题目描述

✅ 1236. 网络爬虫

思路分析

解法一：BFS + 同域名过滤（推荐）

核心思路：

提取起始 URL 的主机名，只爬取相同主机名的链接。

使用队列进行 BFS，哈希集合去重。

每次从 HtmlParser 获取相邻 URL，满足同域名且未访问则加入队列。

复杂度分析：

时间复杂度：O(n + e)，其中 n 为可访问页面数，e 为边数。

空间复杂度：O(n)，存储访问集合与队列。

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Queue;
import java.util.Set;

class Solution {
    public List<String> crawl(String startUrl, HtmlParser htmlParser) {
        String host = getHost(startUrl);
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new ArrayDeque<>();

        visited.add(startUrl);
        queue.offer(startUrl);

        while (!queue.isEmpty()) {
            String cur = queue.poll();
            for (String next : htmlParser.getUrls(cur)) {
                if (!host.equals(getHost(next))) {
                    continue;
                }
                if (visited.add(next)) {
                    queue.offer(next);
                }
            }
        }

        return new ArrayList<>(visited);
    }

    private String getHost(String url) {
        int idx = url.indexOf("://");
        int start = idx >= 0 ? idx + 3 : 0;
        int slash = url.indexOf('/', start);
        if (slash == -1) {
            return url.substring(start);
        }
        return url.substring(start, slash);
    }
}

func crawl(startUrl string, htmlParser HtmlParser) []string {
    host := getHost(startUrl)
    visited := make(map[string]struct{})
    queue := make([]string, 0)

    visited[startUrl] = struct{}{}
    queue = append(queue, startUrl)

    for head := 0; head < len(queue); head++ {
        cur := queue[head]
        for _, next := range htmlParser.GetUrls(cur) {
            if getHost(next) != host {
                continue
            }
            if _, ok := visited[next]; ok {
                continue
            }
            visited[next] = struct{}{}
            queue = append(queue, next)
        }
    }

    res := make([]string, 0, len(visited))
    for url := range visited {
        res = append(res, url)
    }
    return res
}

func getHost(url string) string {
    start := 0
    if idx := strings.Index(url, "://"); idx >= 0 {
        start = idx + 3
    }
    if slash := strings.Index(url[start:], "/"); slash >= 0 {
        return url[start : start+slash]
    }
    return url[start:]
}

相似题目

题目	难度	考察点
125. 验证回文串	简单	字符串处理
130. 被围绕的区域	中等	图遍历
200. 岛屿数量	中等	BFS/DFS
417. 太平洋大西洋水流问题	中等	图遍历
847. 访问所有节点的最短路径	困难	BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/11758818