LeetCode 1236. 网络爬虫

约 10 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 微软
标签
字符串 深度优先搜索 广度优先搜索 交互
目录

题目描述

✅ 1236. 网络爬虫

题意分析

给一个起始 URL 和一个只能通过 getUrls(url) 拿到某页面全部外链的接口，要求返回所有「从起始页出发能到达、且与起始页同主机名」的 URL，顺序任意。

这是一个交互式题目：整张图不是一次性给出的，只能按需展开。这决定了不能预处理邻接表，只能边走边问。

「同主机名」是一个过滤条件而不是终止条件——遇到外域链接要跳过它，但不能因此停止对其他链接的探索。主机名的定义是 http:// 之后到下一个 / 之前的那一段，题目保证所有 URL 都以 http:// 开头且不含端口号，这让主机名提取变成一个纯粹的下标切分。

要注意页面之间的链接可能构成环，同一个页面也可能被多个页面链接到，所以必须去重，否则会无限展开。

另外 getUrls 是外部调用，代价远高于集合操作，应该保证每个页面只调用一次。

边界：起始页没有任何外链、所有外链都是外域、链接构成自环或互相引用的环、某个页面重复出现在多个页面的外链里。

解法：BFS + 同域名过滤

核心思路

把每个 URL 看成图上的一个节点，getUrls(u) 返回的就是 u 的出边。要求「所有可达且同域」的节点，本质是从起点做一次可达性遍历，并在扩展时用主机名做过滤。

朴素地递归展开会有两个问题：一是不去重就会在环上无限递归；二是页面链很长时递归深度不可控。所以选择用显式队列做逐层展开——不是因为需要层数信息（本题不问距离），而是因为队列写法天然避免了栈深度问题，且更容易看清「入队即标记」这一关键点。

维持的不变量是：visited 集合恰好等于「已经确认可达、同域，且已经入队（可能尚未展开）」的 URL 集合。队列里的每个元素都在 visited 中，且每个元素只会入队一次。这条不变量保证了两件事——getUrls 对每个页面至多调用一次，以及循环必然终止（可达页面是有限的，每个至多入队一次）。

去重必须在入队时而不是出队时完成。如果等到出队才检查，同一个页面可能被多个不同的父页面同时塞进队列，虽然靠出队检查也能保证只展开一次，但队列会膨胀，而且更容易写错。用 Set.add 的返回值同时完成「查是否已存在」和「插入」，一步到位。

过滤放在入队之前：先比对主机名，不同域直接跳过，连 visited 都不记。这样 visited 最后就直接是答案集合，不需要再做一次筛选。

主机名提取：所有 URL 都以 http:// 开头，这 7 个字符是定长的，所以主机名从下标 7 开始，到第一个 / 之前结束；若从下标 7 往后再没有 /，整个后缀就是主机名。用定长偏移比查找 :// 更直接，也避免了在字符串字面量里写斜杠。

解题步骤

  • 先用 getHost(startUrl) 算出目标主机名并存下来。整个过程中它是常量，只需算一次；每次和邻居比较时再算邻居的主机名即可。
  • 把 startUrl 同时放进 visited 和队列。起点必须先标记再入队，否则如果某个页面链回起点，起点会被重复展开。注意起点无需做同域检查——它定义了主机名，与自己必然同域。
  • 队列非空时弹出一个 URL，对它调用一次 getUrls。每个 URL 只在出队时调用一次接口，这是把外部调用次数压到最低的关键。
  • 对每个邻居先判 host.equals(getHost(next))，不同域就 continue。为什么先判域再判去重：外域页面根本不该进入 visited，否则最终结果里会混入不该返回的 URL。
  • 同域邻居用 visited.add(next) 判断是否是新页面。Set.add 返回 true 表示之前没有，此时才入队；返回 false 表示已经在集合里（无论是否已展开），直接忽略。这一行同时完成了去重和标记。
  • 队列耗尽后，visited 就是答案，转成列表返回。不需要排序，题目允许任意顺序。
  • getHost 从下标 7 开始找第一个 /：找到就截取 [7, slash)，没找到就返回从 7 到末尾的整个后缀（对应 http://a.com 这种没有路径部分的 URL）。

以下面这个小图走一遍：startUrl = "http://a.com/x"，getUrls("http://a.com/x") 返回 ["http://a.com/y", "http://b.com/z", "http://a.com/x"]，getUrls("http://a.com/y") 返回 ["http://a.com/x", "http://a.com/w"]，getUrls("http://a.com/w") 返回空列表。

首先 getHost("http://a.com/x")：从下标 7 开始（字符 'a'），往后找到第一个 / 在下标 12，截取 [7, 12) 得到 "a.com"。visited = {http://a.com/x}，队列 [http://a.com/x]。

第一轮弹出 http://a.com/x，调用 getUrls 得到三个链接。http://a.com/y 的主机名是 a.com，同域，visited.add 返回 true，入队。http://b.com/z 的主机名是 b.com，不同域，跳过——注意它不会进 visited，所以不会出现在最终答案里。http://a.com/x 同域但 visited.add 返回 false（起点已在集合里），忽略，这一步挡住了回边。

第二轮弹出 http://a.com/y，得到两个链接。http://a.com/x 已在 visited，忽略。http://a.com/w 是新的同域页面，入队。

第三轮弹出 http://a.com/w，外链为空，无事发生。队列耗尽，返回 visited 的三个元素：http://a.com/x、http://a.com/y、http://a.com/w。getUrls 恰好被调用三次，每个可达同域页面一次。

代码实现

// 入队即标记，同域过滤放在标记之前，visited 最终就是答案。
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 start = 7;
        int slash = url.indexOf('/', start);
        if (slash == -1) {
            return url.substring(start);
        }
        return url.substring(start, slash);
    }
}

// 入队即标记，同域过滤放在标记之前，visited 最终就是答案。
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 {
	for i := 7; i < len(url); i++ {
		if url[i] == '/' {
			return url[7:i]
		}
	}
	return url[7:]
}

复杂度分析

  • 时间复杂度：$O(V + E)$，其中 V 为可达的同域页面数、E 为这些页面上的外链总数（含指向外域的链接）。每个页面出队一次并调用一次 getUrls，每条外链被检查一次，检查内容是一次主机名提取（$O(L)$，L 为 URL 长度）加一次哈希操作，所以更精确地说是 $O((V + E) \cdot L)$。
  • 空间复杂度：$O(V \cdot L)$。visited 存下全部可达同域 URL 的字符串，队列长度不超过 visited 的大小，两者同阶；结果列表是 visited 的一份拷贝。

关键点总结

  • 交互式图遍历题的核心是「把接口调用当成取邻居」，其余部分和普通 BFS 完全一致。识别出这一点后，重点就落在两件事上：去重和减少接口调用次数。
  • 去重标记必须在入队时打，不能等到出队。「入队即标记」保证每个节点最多入队一次，队列规模有界，且外部接口调用次数恰好等于节点数——这是本题最值得强调的实现细节。
  • 过滤条件（同域）要放在标记之前。先过滤再标记，visited 最终就直接是答案；先标记再过滤则要在末尾再筛一遍，多一步且容易漏。
  • 用 Set.add 的布尔返回值同时完成「判重 + 标记」，比 contains 后再 add 少一次哈希查找，也少一处写漏的可能。
  • 字符串定长前缀（http:// 恰好 7 个字符）可以直接用下标偏移切分，比查找分隔符更快也更少出错；前提是题目明确保证了协议前缀，面试时要主动确认这个前提。
  • 面试延伸：本题用 DFS 递归写同样正确且更短，但页面链很长时可能爆栈；面试官若追问「怎么并行加速」，答案就是 1242 题——把 visited 换成并发安全集合、用线程池并行展开，并额外解决「何时判定全部任务完成」的问题。

易错点总结

  • 错误写法：出队时才检查 visited 并标记 → 图里存在 A→C、B→C 时 C 会被入队两次，虽然靠出队检查仍能只展开一次，但若忘了出队检查就会对 C 调用两次 getUrls，环状结构下直接死循环。
  • 错误写法：先 visited.add(next) 再判断主机名 → http://b.com/z 这个外域链接被写进 visited，最终返回的列表里混入了不该出现的外域 URL。
  • 错误写法：起点不加进 visited 就入队 → 走查里 http://a.com/x 链回自己，起点会被反复入队展开，形成死循环。
  • 错误写法：getHost 从下标 0 开始找第一个 / → http://a.com/x 的第一个 / 出现在协议部分（下标 5），截取出空串，所有页面的主机名都变成空串，外域链接不再被过滤，会把整个网络爬完。
  • 错误写法：getHost 没处理「后面没有 /」的情况，直接 url.substring(7, url.indexOf('/', 7)) → http://a.com 这种无路径 URL 上 indexOf 返回 -1，substring(7, -1) 抛异常。
  • 错误写法：用 startsWith(host) 代替主机名相等判断 → host = "a.com" 时 http://a.com.evil.net/x 会被误判为同域并爬取，返回结果多出外域页面。
  • 错误写法：用 contains(host) 判断同域 → http://x.com/redirect?to=a.com 这类 URL 会被误判成同域。
  • 错误写法：把过滤条件写成「主机名不同就 break」而不是 continue → 走查里 http://b.com/z 排在 http://a.com/x 的第二个链接位置，break 会导致第三个链接不再被检查；若外域链接排在最前面，整层邻居全被跳过，答案严重缺失。
  • 错误写法：每次判断邻居时都重新调用 getHost(startUrl) → 结果正确但每条边多一次字符串扫描，在外链极多时是无谓开销；更糟的是有人会顺手把它写成 getHost(cur)，此时过滤基准变成当前页面而非起点，逻辑虽在本题等价（同域页面主机名相同），一旦允许跨域跳转就会出错。
  • 错误写法：返回队列而不是 visited → 队列在循环结束时必然为空，返回空列表。

相似题目

题目 难度 考察点
1242. 多线程网络爬虫 中等 同一遍历加并发，难点转为线程安全去重与终止判定
133. 克隆图 中等 遍历同时构造副本，访问表要存「原节点到新节点」的映射
841. 钥匙和房间 中等 邻接表直接给出，问的是可达集合是否覆盖全部节点
200. 岛屿数量 中等 隐式网格图，需要对每个未访问格子发起一次独立遍历