这周的作业可谓是一波三折,但是收获了不少,熟悉了广度优先搜索还有符号图的建立。此外还知道了 Integer.MAX_VALUE。
SAP:
求 v 和 w 的大概思路是对 v 和 w 分别广度优先搜索,然后遍历图中每一个顶点,如果 v 和 w 都可以到达一个顶点,就计算 v 和 w 到这一顶点的距离和,最后求出最短的距离以及对应的顶点便是所求 length 和 ancestor。
至于 Iterable<Integer> v 和 Iterable<Integer> w,开始我是求 v 中每一个顶点和 w 中的每一个顶点的距离,然后求出最短距离,但提交后时间测试通不过。参考了其他人的一些博客后发现可以遍历一次完成对 v 或 w 的广度优先搜索,于是自己写了一个 BFS 类。然而这次提交出现了 OperationCountLimitExceededException,最后检查了半天才发现 bfs 时丢了一句 'if(!marked[w]) '。。。后来发现官方提供的 BreadthFirstDirectedPaths 类可以完成 Iterable<Integer> v 的广度优先搜索,于是干脆直接调用这个。
但是提交后还是有问题。。。对于没有共同祖先的情况判断不正确,不能返回 - 1,检查了半天发现每次求 length 或 ancestor 都应该在前面加上 anc = -1; 否则这次求返回的是上次的 anc。
- import edu.princeton.cs.algs4. * ;
- import edu.princeton.cs.algs4.In;
- public class SAP {
- private Digraph G;
- private int anc = -1;
- // constructor takes a digraph (not necessarily a DAG)
- public SAP(Digraph G) {
- if (G == null) throw new IllegalArgumentException();
- this.G = new Digraph(G);
- }
- // length of shortest ancestral path between v and w; -1 if no such path
- public int length(int v, int w) {
- if (v < 0 || v > G.V() - 1 || w < 0 || w > G.V() - 1) throw new IllegalArgumentException();
- anc = -1;
- BreadthFirstDirectedPaths bv = new BreadthFirstDirectedPaths(G, v);
- BreadthFirstDirectedPaths bw = new BreadthFirstDirectedPaths(G, w);
- int minLength = Integer.MAX_VALUE;
- for (int i = 0; i < G.V(); i++) {
- if (bv.hasPathTo(i) && bw.hasPathTo(i)) {
- int l = bv.distTo(i) + bw.distTo(i);
- if (l < minLength) {
- minLength = l;
- anc = i;
- }
- }
- }
- if (minLength == Integer.MAX_VALUE) return - 1;
- else return minLength;
- }
- // a common ancestor of v and w that participates in a shortest ancestral path; -1 if no such path
- public int ancestor(int v, int w) {
- length(v, w);
- return anc;
- }
- // length of shortest ancestral path between any vertex in v and any vertex in w; -1 if no such path
- public int length(Iterable < Integer > v, Iterable < Integer > w) {
- if (v == null || w == null) throw new IllegalArgumentException();
- anc = -1;
- for (int i: v) {
- if (i < 0 || i > G.V() - 1) throw new IllegalArgumentException();
- }
- for (int i: w) {
- if (i < 0 || i > G.V() - 1) throw new IllegalArgumentException();
- }
- BreadthFirstDirectedPaths bv = new BreadthFirstDirectedPaths(G, v);
- BreadthFirstDirectedPaths bw = new BreadthFirstDirectedPaths(G, w);
- int minLength = Integer.MAX_VALUE;
- for (int i = 0; i < G.V(); i++) {
- if (bv.hasPathTo(i) && bw.hasPathTo(i)) {
- int l = bv.distTo(i) + bw.distTo(i);
- if (l < minLength) {
- minLength = l;
- anc = i;
- }
- }
- }
- if (minLength == Integer.MAX_VALUE) return - 1;
- else return minLength;
- }
- // a common ancestor that participates in shortest ancestral path; -1 if no such path
- public int ancestor(Iterable < Integer > v, Iterable < Integer > w) {
- length(v, w);
- return anc;
- }
- // do unit testing of this class
- public static void main(String[] args) {
- }
- }
WordNet:
wordnet 涉及到符号图的问题,开始用 ST<String, Integer> 来完成 noun 到 id 的索引,后来发现一个 noun 可能对应多个 id, 于是改为 ST<String, Bag<Integer>>。
需要检查有向图是否合格:1. 不能有环。通过类 DirectedCycle 完成。 2. 只能有一个 root。经参考别人的博客发现一个很巧妙的方法,如果一个顶点是根,那么它不指向其它顶点,所以它不会出现在 hypernyms 每行的第一个 id。
方法 sap 需要通过 id 得到 noun,用数组的话不能提前知道数组大小,于是参考网上用 ArrayList<String> 完成 id 到 noun 的索引。
- import edu.princeton.cs.algs4. * ;
- import java.util.ArrayList;
- public class WordNet {
- private ST < String,
- Bag < Integer >> st;
- private ArrayList < String > idList;
- private Digraph G;
- // constructor takes the name of the two input files
- public WordNet(String synsets, String hypernyms) {
- if (synsets == null || hypernyms == null) throw new IllegalArgumentException();
- st = new ST < String,
- Bag < Integer >> ();
- idList = new ArrayList < String > ();
- int count = 0;
- In in1 = new In(synsets);
- while (in1.hasNextLine()) {
- String[] a = in1.readLine().split(",");
- String[] a2 = a[1].split(" ");
- for (int i = 0; i < a2.length; i++) {
- if (st.contains(a2[i])) st.get(a2[i]).add(Integer.parseInt(a[0]));
- else {
- Bag < Integer > b = new Bag < Integer > ();
- b.add(Integer.parseInt(a[0]));
- st.put(a2[i], b);
- }
- }
- count++;
- idList.add(a[1]);
- }
- G = new Digraph(count);
- In in2 = new In(hypernyms);
- boolean[] isNotRoot = new boolean[count];
- int rootNumber = 0;
- while (in2.hasNextLine()) {
- String[] a = in2.readLine().split(",");
- isNotRoot[Integer.parseInt(a[0])] = true;
- for (int i = 1; i < a.length; i++) G.addEdge(Integer.parseInt(a[0]), Integer.parseInt(a[i]));
- }
- for (int i = 0; i < count; i++) {
- if (!isNotRoot[i]) rootNumber++;
- }
- DirectedCycle d = new DirectedCycle(G);
- if (rootNumber > 1 || d.hasCycle()) throw new IllegalArgumentException();
- }
- // returns all WordNet nouns
- public Iterable < String > nouns() {
- return st.keys();
- }
- // is the word a WordNet noun?
- public boolean isNoun(String word) {
- if (word == null) throw new IllegalArgumentException();
- return st.contains(word);
- }
- // distance between nounA and nounB (defined below)
- public int distance(String nounA, String nounB) {
- if (nounA == null || nounB == null || !isNoun(nounA) || !isNoun(nounB)) throw new IllegalArgumentException();
- SAP s = new SAP(G);
- Bag < Integer > ida = st.get(nounA);
- Bag < Integer > idb = st.get(nounB);
- return s.length(ida, idb);
- }
- // a synset (second field of synsets.txt) that is the common ancestor of nounA and nounB
- // in a shortest ancestral path (defined below)
- public String sap(String nounA, String nounB) {
- if (nounA == null || nounB == null || !isNoun(nounA) || !isNoun(nounB)) throw new IllegalArgumentException();
- SAP s = new SAP(G);
- Bag < Integer > ida = st.get(nounA);
- Bag < Integer > idb = st.get(nounB);
- int root = s.ancestor(ida, idb);
- return idList.get(root);
- }
- // do unit testing of this class
- public static void main(String[] args) {
- }
- }
Outcast:
- public class Outcast {
- private WordNet wordnet;
- // constructor takes a WordNet object
- public Outcast(WordNet wordnet) {
- this.wordnet = wordnet;
- }
- // given an array of WordNet nouns, return an outcast
- public String outcast(String[] nouns) {
- int length = nouns.length;
- int[][] distance = new int[length][length];
- for (int i = 0; i < length; i++) {
- for (int j = i; j < length; j++) {
- distance[i][j] = wordnet.distance(nouns[i], nouns[j]);
- }
- }
- int maxDistance = 0;
- int sum = 0;
- int num = 0;
- for (int i = 0; i < nouns.length; i++) {
- sum = 0;
- for (int j = 0; j < nouns.length; j++) {
- if (i < j) sum += distance[i][j];
- else sum += distance[j][i];
- }
- if (sum > maxDistance) {
- maxDistance = sum;
- num = i;
- }
- }
- return nouns[num];
- }
- // see test client below
- public static void main(String[] args) {}
- }
来源: http://www.bubuko.com/infodetail-2431706.html