hot100 208.实现前缀树 207.课程表

时间：2024-11-20 06:59:46

208.实现前缀树

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word 。
  • boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

GPT

以下是 Java 中 Trie 类的实现，包括所要求的三个方法：insert、search 和 startsWith。

实现代码

class Trie {
    // 定义 Trie 树的节点
    private class TrieNode {
        private TrieNode[] children;
        private boolean isEnd;

        public TrieNode() {
            children = new TrieNode[26]; // 假设只包含小写字母 a-z
            isEnd = false; // 标记是否是一个完整单词的结尾
        }
    }

    private TrieNode root;

    public Trie() {
        root = new TrieNode(); // 初始化根节点
    }

    // 插入单词
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a'; // 计算字母在数组中的索引
            if (node.children[index] == null) {
                node.children[index] = new TrieNode(); // 创建新节点
            }
            node = node.children[index];
        }
        node.isEnd = true; // 标记单词结尾
    }

    // 检索单词
    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEnd; // 确保节点存在且是单词结尾
    }

    // 检查前缀
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null; // 确保节点存在
    }

    // 辅助函数：搜索前缀或单词
    private TrieNode searchPrefix(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return null; // 不存在该前缀
            }
            node = node.children[index];
        }
        return node;
    }
}

使用示例

以下代码展示了如何使用 Trie 类：

public class Main {
    public static void main(String[] args) {
        Trie trie = new Trie();

        // 插入单词
        trie.insert("apple");
        System.out.println(trie.search("apple"));   // 返回 true
        System.out.println(trie.search("app"));     // 返回 false
        System.out.println(trie.startsWith("app")); // 返回 true

        trie.insert("app");
        System.out.println(trie.search("app"));     // 返回 true
    }
}

功能解释

  1. insert(String word)
    • 将单词逐字符插入到 Trie 中。
    • 遇到不存在的节点时，创建新的节点。
  1. search(String word)
    • 检查 Trie 中是否存在完整的单词。
    • 如果找到以 word 结尾的节点，且 isEnd 标记为 true，返回 true。
  1. startsWith(String prefix)
    • 检查 Trie 中是否存在以 prefix 开头的任何单词。
    • 不需要检查 isEnd，只要节点存在即可。
  1. 辅助函数 searchPrefix(String prefix)
    • 用于查找前缀或单词对应的最后一个节点。
    • 提供通用的前缀查找功能。

时间复杂度

  1. 插入（insert）：(O(m))，其中 (m) 是单词的长度。
  2. 查找单词（search）：(O(m))。
  3. 查找前缀（startsWith）：(O(m))。

这里的效率非常高，因为每次操作只需沿着树路径移动，操作次数与单词长度成正比。

207.课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

  • 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

解决这个问题的核心在于判断给定的课程和先修关系是否构成有向无环图（DAG），如果图中有环则不能完成所有课程。以下提供两种经典方法来解决问题：拓扑排序和深度优先搜索（DFS）检测环。

方法 1：拓扑排序（Kahn 算法）

思路：
  1. 通过入度表记录每个课程的先修要求。
  2. 使用队列存储所有入度为 0 的课程（没有先修要求）。
  3. 从队列中逐个取出课程，并将它们对其他课程的影响（即减小它们的入度）更新。
  4. 如果最终处理的课程数等于 numCourses，说明可以完成所有课程；否则不能。
实现：
import java.util.*;

public class CourseSchedule {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 构建图和入度表
        int[] inDegree = new int[numCourses];
        Map<Integer, List<Integer>> graph = new HashMap<>();
        
        for (int i = 0; i < numCourses; i++) {
            graph.put(i, new ArrayList<>());
        }
        
        for (int[] pair : prerequisites) {
            int course = pair[0];
            int pre = pair[1];
            graph.get(pre).add(course);
            inDegree[course]++;
        }

        // 将所有入度为 0 的节点加入队列
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }

        int count = 0; // 记录已经完成的课程数
        while (!queue.isEmpty()) {
            int current = queue.poll();
            count++;
            for (int next : graph.get(current)) {
                inDegree[next]--;
                if (inDegree[next] == 0) {
                    queue.add(next);
                }
            }
        }
        
        return count == numCourses;
    }

    public static void main(String[] args) {
        CourseSchedule cs = new CourseSchedule();
        int numCourses = 2;
        int[][] prerequisites = {{1, 0}};
        System.out.println(cs.canFinish(numCourses, prerequisites)); // true
    }
}

方法 2：深度优先搜索（DFS）检测环

思路：
  1. 使用一个访问状态数组 visit 来跟踪每个课程的状态：
    • 0：未访问。
    • 1：当前路径中（正在访问）。
    • 2：访问完成。
  1. 对图进行深度优先搜索（DFS），如果在某个路径中访问到一个状态为 1 的节点，说明存在环。
  2. 如果所有课程都能被访问完且没有检测到环，则可以完成所有课程。
实现：
import java.util.*;

public class CourseScheduleDFS {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 构建图
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < numCourses; i++) {
            graph.put(i, new ArrayList<>());
        }
        for (int[] pair : prerequisites) {
            int course = pair[0];
            int pre = pair[1];
            graph.get(pre).add(course);
        }

        // 访问状态数组
        int[] visit = new int[numCourses];
        
        // 检测环的 DFS 方法
        for (int i = 0; i < numCourses; i++) {
            if (hasCycle(i, graph, visit)) {
                return false;
            }
        }
        return true;
    }

    private boolean hasCycle(int course, Map<Integer, List<Integer>> graph, int[] visit) {
        if (visit[course] == 1) return true; // 检测到环
        if (visit[course] == 2) return false; // 已经访问完成，无需重复检查
        
        visit[course] = 1; // 标记为正在访问
        for (int next : graph.get(course)) {
            if (hasCycle(next, graph, visit)) {
                return true;
            }
        }
        visit[course] = 2; // 标记为访问完成
        return false;
    }

    public static void main(String[] args) {
        CourseScheduleDFS cs = new CourseScheduleDFS();
        int numCourses = 2;
        int[][] prerequisites = {{1, 0}};
        System.out.println(cs.canFinish(numCourses, prerequisites)); // true
    }
}

测试用例

public class Test {
    public static void main(String[] args) {
        int[][] prerequisites1 = {{1, 0}, {0, 1}};
        int[][] prerequisites2 = {{1, 0}, {2, 1}, {3, 2}};

        CourseSchedule cs = new CourseSchedule();
        CourseScheduleDFS csDFS = new CourseScheduleDFS();

        // 方法1 - 拓扑排序
        System.out.println(cs.canFinish(2, prerequisites1)); // false
        System.out.println(cs.canFinish(4, prerequisites2)); // true

        // 方法2 - DFS 检测环
        System.out.println(csDFS.canFinish(2, prerequisites1)); // false
        System.out.println(csDFS.canFinish(4, prerequisites2)); // true
    }
}

总结

  • 拓扑排序方法适合处理大规模数据，算法复杂度为 (O(V + E))。
  • DFS 检测环更加直观，适合理解和学习，复杂度同样为 (O(V + E))。

相关文章