网站首页怎么设计,php网站开发txt,大型网站建设套餐,十大免费erp管理软件BFS 解决拓扑排序 1.课程表1.1. 题⽬链接#xff1a;1.2 题⽬描述#xff1a;1.3. 解法#xff1a;1.4 代码 2. 课程表2.1题⽬链接#xff1a;2.2 题⽬描述#xff1a;2.3解法#xff1a;2.4代码 3. ⽕星词典#xff08;hard#xff09;3.1题⽬链接#xff1a;3.2 题⽬… BFS 解决拓扑排序 1.课程表1.1. 题⽬链接1.2 题⽬描述1.3. 解法1.4 代码 2. 课程表2.1题⽬链接2.2 题⽬描述2.3解法2.4代码 3. ⽕星词典hard3.1题⽬链接3.2 题⽬描述3.3 解法3.4代码 1.课程表
1.1. 题⽬链接
https://leetcode.cn/problems/course-schedule
1.2 题⽬描述 1.3. 解法 算法思路 原问题可以转换成⼀个拓扑排序问题。 ⽤ BFS 解决拓扑排序即可。 拓扑排序流程 a. 将所有⼊度为 0 的点加⼊到队列中 b. 当队列不空的时候⼀直循环 i. 取出队头元素 ii. 将于队头元素相连的顶点的⼊度 - 1 iii. 然后判断是否减成 0,。如果减成 0就加⼊到队列中。 1.4 代码
class Solution
{public boolean canFinish(int n, int[][] p) {// 1. 准备⼯作 int[] in new int[n]; // 统计每⼀个顶点的⼊度 MapInteger, ListInteger edges new HashMap(); // 邻接表存图 // 2. 建图 for(int i 0; i p.length; i){int a p[i][0], b p[i][1]; // b - aif(!edges.containsKey(b)){edges.put(b, new ArrayList());}edges.get(b).add(a);in[a];}// 3. 拓扑排序 QueueInteger q new LinkedList();// (1) 先把⼊度为 0 的点加⼊到队列中 for(int i 0; i n; i){if(in[i] 0) q.add(i);}// (2) bfswhile(!q.isEmpty()){int t q.poll();for(int a : edges.getOrDefault(t, new ArrayList())){in[a]--;if(in[a] 0) q.add(a);}}// 4. 判断是否有环 for(int x : in)if(x ! 0) return false;return true;}
}2. 课程表
2.1题⽬链接
https://leetcode.cn/problems/course-schedule-ii
2.2 题⽬描述 2.3解法 算法思路 原问题可以转换成⼀个拓扑排序问题。 ⽤ BFS 解决拓扑排序即可。 拓扑排序流程 a. 将所有⼊度为 0 的点加⼊到队列中 b. 当队列不空的时候⼀直循环 i. 取出队头元素 ii. 将于队头元素相连的顶点的⼊度 - 1 iii. 然后判断是否减成 0,。如果减成 0就加⼊到队列中。 2.4代码
class Solution
{public int[] findOrder(int n, int[][] prerequisites) {// 1. 准备⼯作 int[] in new int[n]; // 统计每个顶点的⼊度 ListListInteger edges new ArrayList();for(int i 0; i n; i){edges.add(new ArrayList());}// 2. 建图 for(int i 0; i prerequisites.length; i){int a prerequisites[i][0], b prerequisites[i][1]; // b - aedges.get(b).add(a);in[a];}// 3. 拓扑排序 QueueInteger q new LinkedList();int[] ret new int[n];int index 0;for(int i 0; i n; i){if(in[i] 0) q.add(i);}while(!q.isEmpty()){int t q.poll();ret[index] t;for(int a : edges.get(t)){in[a]--;if(in[a] 0) q.add(a);}}if(index n) return ret;return new int[0];}
}3. ⽕星词典hard
3.1题⽬链接
https://leetcode.cn/problems/Jf1JuT
3.2 题⽬描述 3.3 解法 算法思路 将题意搞清楚之后这道题就变成了判断有向图时候有环可以⽤拓扑排序解决。 如何搜集信息如何建图 a. 两层 for 循环枚举出所有的两个字符串的组合 b. 然后利⽤指针根据字典序规则找出信息。 3.4代码
class Solution
{MapCharacter, SetCharacter edges new HashMap(); // 邻接表 MapCharacter, Integer in new HashMap(); // 统计每个节点的⼊度 boolean check;public String alienOrder(String[] words) {// 1. 初始化⼊度哈希表 建图 for(String s : words){for(int i 0; i s.length(); i){char ch s.charAt(i);in.put(ch, 0);}}int n words.length;for(int i 0; i n; i){for(int j i 1; j n; j){add(words[i], words[j]);if(check true) return ;}}// 2. 拓扑排序 QueueCharacter q new LinkedList();for(char ch : in.keySet()){if(in.get(ch) 0) q.add(ch);}StringBuffer ret new StringBuffer();while(!q.isEmpty()){char t q.poll();ret.append(t);if(!edges.containsKey(t)) continue;for(char ch : edges.get(t)){in.put(ch, in.get(ch) - 1);if(in.get(ch) 0) q.add(ch);}}// 3. 判断 for(char ch : in.keySet()){if(in.get(ch) ! 0) return ;}return ret.toString();}public void add(String s1, String s2){int n Math.min(s1.length(), s2.length());int i 0;for( ; i n; i){char c1 s1.charAt(i), c2 s2.charAt(i);if(c1 ! c2){// c1 - c2if(!edges.containsKey(c1)){edges.put(c1, new HashSet());}if(!edges.get(c1).contains(c2)){edges.get(c1).add(c2);in.put(c2, in.get(c2) 1);}break;}}if(i s2.length() i s1.length()) check true;}
}
