LeetCode 1236. 网络爬虫

2024-10-15 HGNULB 约 6 分钟

文章信息 7 个分类 4 个标签

分类

LeetCode CodeTop 中等未解决会员题 1-2 微软

题目描述

✅ 1236. 网络爬虫

题意分析

给定起始 URL 和页面链接解析接口，从起点出发爬取所有可达、且与起点具有相同主机名的页面，返回这些完整 URL，顺序不限。不同路径的 URL 可以属于同一主机，页面之间也可能存在重复链接、自环或其他环。

只能沿允许访问的同主机页面继续展开，发现外部主机链接后直接忽略，不能先访问外站再经它寻找其他页面。需要去重的是完整 URL，而判断访问范围时比较的是主机名，这两个键的用途不同。

解法：BFS + 同域名过滤

核心思路

[!blue]

把页面看作图节点，getUrls 返回的链接看作它的出边。用队列保存已经发现但尚未展开的页面，用 visited 保存已经安排访问的完整 URL。从起点开始反复取出页面、获取链接，就能遍历允许范围内的可达图。

起点在入队前就加入 visited。对每条新链接，先检查主机名是否与起点一致；不一致就跳过，一致且完整 URL 尚未出现时，立即标记再入队。这样多个父页面同时指向同一个目标时，只有第一次发现会安排它，环和重复链接也不会造成无限访问。

标记必须发生在入队时，而不是等真正出队展开时。后者会让一个尚在队列里的页面被其他入口重复加入，导致多次调用解析接口。当前做法保证每个允许访问的 URL 最多入队并解析一次。

主机名必须完整相等，不能以整条 URL 是否包含主机文字来判断。当前实现按题目给定的 http://主机/路径、无端口地址形式提取主机：从协议后的下标七开始，到之后第一个斜杠之前；如果没有路径分隔斜杠，则取到字符串末尾。

每次加入的页面都由一个已经可达的同主机页面链接得到，因此结果没有越界页面；任意合法可达路径上的页面又会依次被展开，因此不会漏掉允许访问的目标。队列耗尽后，visited 就是全部结果，转换为列表返回即可，不需要排序或维护最短距离。

解题步骤

提取起始 URL 的主机名，将完整起始 URL 同时加入访问集合和队列。

取出一个页面，调用接口获取它指向的全部 URL。

逐条过滤不同主机的链接，对同主机且尚未出现的完整 URL 先标记，再入队。

继续处理队列中的其他页面，直到全部已发现页面都已展开。

将访问集合转换为结果列表返回。

代码实现

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) {
        // 题目保证使用 http 协议，从协议前缀之后提取主机。
        int start = 7;
        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 {
    // 题目保证使用 http 协议，从协议前缀之后提取主机。
    for i := 7; i < len(url); i++ {
        if url[i] == '/' {
            return url[7:i]
        }
    }
    return url[7:]
}

复杂度分析

时间复杂度：设允许访问的可达页面数为 V，这些页面返回的链接总数为 E，URL 最大长度为 L。本地字符串提取、比较和哈希处理期望为 $O((V+E)L)$，另调用 V 次解析接口，接口自身耗时单独考虑。

空间复杂度：队列与访问集合按保存的 URL 长度计为 $O(VL)$；解析接口一次返回的链接数据不计入这部分本地持久状态。

关键点总结

[!green]

主机名决定是否允许访问，完整 URL 决定是不是同一个已发现页面。

入队即标记，visited 包括正在等待展开的页面，不只包括已处理页面。

每个允许页面只展开一次，图中的环和重复边由去重自然处理。

主机提取按题目限定的地址形式实现，不需要改变页面路径或拼接新链接。

易错点总结

[!yellow]

出队时才标记，可能让同一页面在等待期间被多个父页面重复入队。

用包含关系或简单文字前缀代替完整主机相等，会把主机或路径中包含相同文字的外部 URL 误收进来。

按主机名去重，会把同一主机下的不同页面都合并掉；访问集合必须保存完整 URL。

遇到一条外站链接就结束整个邻居循环，会漏掉之后的合法同主机链接，应只跳过当前链接。

没有处理不带路径的 URL，找不到后续斜杠时会错误截取主机；应取到字符串末尾。

相似题目

题目	难度	关联与区别
1242. 多线程网络爬虫	中等	爬取范围与去重规则相同，原题增加多线程执行，需要原子去重及正确判断全部任务结束。
841. 钥匙和房间	中等	同样从起点遍历可达对象，本题边由解析URL得到且需按主机名过滤。

转载与许可

作者 HGNULB

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

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！