网络公司做的网站被告图片侵权,网站建设重要新,小说排行榜,搜狗站长工具综合查询994. 腐烂的橘子
BFS #xff08;广度优先搜索#xff09;可以看成是层序遍历。从某个结点出发#xff0c;BFS 首先遍历到距离为 1 的结点#xff0c;然后是距离为 2、3、4…… 的结点。因此#xff0c;BFS 可以用来求最短路径问题。BFS 先搜索到的结点#xff0c;一定是…994. 腐烂的橘子
BFS 广度优先搜索可以看成是层序遍历。从某个结点出发BFS 首先遍历到距离为 1 的结点然后是距离为 2、3、4…… 的结点。因此BFS 可以用来求最短路径问题。BFS 先搜索到的结点一定是距离最近的结点。
题目要求返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。实际上就是求腐烂橘子到所有新鲜橘子的最短路径。那么这道题就可以使用 BFS。
class Solution {public int orangesRotting(int[][] grid) {int n grid.length;int m grid[0].length;Queueint[] queue new LinkedList();// 统计新鲜橘子的数量int count 0;for(int i0; in; i){for(int j0; jm; j){if(grid[i][j]1){count;}else if(grid[i][j]2){// 多源头以所有腐烂的橘子为初始起点并将它们加入队列queue.add(new int[]{i,j});}}}// 统计层数也就是最短路径即本题的最短分钟数int round0;while(count0 !queue.isEmpty()){round;// 多源头需要关注这些点的扩散状态 int k queue.size();for(int i0; ik; i){int[] orange queue.poll();int r orange[0];int c orange[1];// 保证取值在[0,m), [0,n)中if(r-10 grid[r-1][c]1){// 不要忽略将其置为腐烂橘子避免重复计算grid[r-1][c]2;count--;queue.add(new int[]{r-1,c});}if(r1n grid[r1][c]1){grid[r1][c]2;count--;queue.add(new int[]{r1,c});}if(c-10 grid[r][c-1]1){grid[r][c-1]2;count--;queue.add(new int[]{r,c-1});}if(c1m grid[r][c1]1){grid[r][c1]2;count--;queue.add(new int[]{r,c1});}}}if(count0){return -1;}else{return round;}}
}
207. 课程表
考查 拓扑排序
1.找到入度为0的点入队
2.从图中删掉入度为0的点直至全部被删掉。
3.依次删掉的顺序即为拓扑排序的结果。
若课程 a 存在前置课程 b 的话我们添加一条从 b 到 a 的有向边同时统计所有点的入度。
当处理完所有的 g[i] 后将所有的入度为 0 的课程含义为没有前置课程要求的科目进行入队操作跑一遍「拓扑排序」若所有课程都能顺利出队说明所有课程都能使完成。
class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {ListListInteger adjacency new ArrayList();for(int i0; inumCourses; i){adjacency.add(new ArrayList());}int[] flags new int[numCourses];for(int[] cp : prerequisites){adjacency.get(cp[1]).add(cp[0]);}for(int i0; inumCourses; i){if(!dfs(adjacency,flags,i)) return false;}return true;}public boolean dfs(ListListInteger adjacency, int[] flags, int i){// 说明在本轮 DFS 搜索中节点 i 被第 2 次访问即 课程安排图有环 直接返回 Falseif(flags[i]1) return false;// 说明当前访问节点已被其他节点启动的 DFS 访问无需再重复搜索直接返回 True。if(flags[i]-1) return true;// 标记其被本轮 DFS 访问过flags[i]1;// 递归访问当前节点 i 的所有邻接节点 j当发现环直接返回 Falsefor(Integer j : adjacency.get(i)){if(!dfs(adjacency,flags, j)) return false;}// 当前节点所有邻接节点已被遍历并没有发现环则将当前节点 flag 置为 −1并返回 Trueflags[i]-1;return true;}
}
208. 实现 Trie (前缀树)
假定每个节点都有26个孩子节点因为都是小写字母将字符串中的字符插入到对应的位置。
还有一个点要明确节点的值仅仅表示从根节点到本节点的路径构成的字符串是否有效而已。
分两步
首先看表示字符串的路径是否存在其次看该路径的终点处的节点是否有效
class Trie {// 前缀树的数据结构class TreeNode{boolean val;TreeNode[] children new TreeNode[26];}private TreeNode root;public Trie() {root new TreeNode();}public void insert(String word) {TreeNode p root;for(char c : word.toCharArray()){int i c - a;// 初始化孩子节点if(p.children[i]null) p.children[i]new TreeNode();// 将p节点下移pp.children[i];}// 将字符串最后一个字符置为有效p.val true;}public boolean search(String word) {TreeNode p root;for(char c : word.toCharArray()){int i c - a;if(p.children[i]null) return false;pp.children[i];}// 路径存在直接返回该路径的终点处的节点的有效性return p.val;}public boolean startsWith(String prefix) {TreeNode p root;for(char c : prefix.toCharArray()){int i c - a;if(p.children[i]null) return false;pp.children[i];}return true;}
}/*** Your Trie object will be instantiated and called as such:* Trie obj new Trie();* obj.insert(word);* boolean param_2 obj.search(word);* boolean param_3 obj.startsWith(prefix);*/
