algorithm

編程作業: WordNet 100分 檢查沒有環且同根 如果自製BFS可以更快(搜尋到共同祖先即停止) WordNet.java import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; import java.util.Map; import java.util.Set; import edu.princeton.cs.algs4.Digraph; import edu.princeton.cs.algs4.DirectedCycle; import edu.princeton.cs.algs4.In; public class WordNet { private final Map<Integer, String> synsetsById; private final Map<String, Set<Integer>> synsets; private final Digraph digraph; private final SAP sap; private final Iterable<String> iterable = () -> new NounsIterator(); // constructor takes the name of the two input files public WordNet(String synsets, String hypernyms) { this(new In(requireNonNull(synsets)), new In(requireNonNull(hypernyms))); } private WordNet(In synsets, In hypernyms) { requireNonNull(synsets); requireNonNull(hypernyms); this.

用途 判斷2個目標是否在同一組、判斷2個目標是否相連 實現 用1維陣列表示N個目標 array[n]表示第n個目標的父節點 每個群組可視為一棵樹，任意2點有相同根節點表示同組 array[i]==i表示到達根節點 將2點設為同組只需 public void unite(int p, int q) { int i = root(p); int j = root(q); id[i] = j; } 瓶頸 樹太深時尋找根節點費時 優化 另外開個陣列紀錄群組大小，合併時將小樹放到大樹下，減少深度 在訪問根的過程中，將所有節點的父節點都順手改為父父節點，減少深度 參考資料 https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

編程作業: Percolation 100分關鍵在使用2個WeightedQuickUnionUF，一個繪圖用，一個判斷滲透用 Percolation.java import edu.princeton.cs.algs4.WeightedQuickUnionUF; public class Percolation { private static final int FULL_ROOT = 0; private final int n; private final boolean[] open; private final WeightedQuickUnionUF uf; private final WeightedQuickUnionUF ufForCheckPercolates; private final int END_ROOT; private int openSize; private boolean percolates; public Percolation(int n) { if (n <= 0) throw new java.lang.IllegalArgumentException(); this.n = n; final int size = n * n + 2; this.open = new boolean[size]; this.

用途 判斷是否包含子字串及位置 實現 透過hash讓比對快速失敗 參考資料

編程作業: Deques and Randomized Queues Deque使用節點，RandomizedQueue使用陣列，100分沒有太困難 Deque.java import java.util.Iterator; public class Deque<Item> implements Iterable<Item> { private final Node head; private final Node tail; private int size; public Deque() { this.head = new Node(); this.tail = new Node(); this.head.next = this.tail; this.tail.pre = this.head; } public boolean isEmpty() { return this.size == 0; } public int size() { return this.size; } public void addFirst(Item item) { checkNullItem(item); Node newNode = new Node(item); insertAfter(this.

編程作業: Collinear Points 100分關鍵是FastCollinearPoints在判斷線段重複時不使用Set或Sort，而是只有當前點是當前線段的左下端點時才加入 Point.java /****************************************************************************** * Compilation: javac Point.java * Execution: java Point * Dependencies: none * * An immutable data type for points in the plane. * For use on Coursera, Algorithms Part I programming assignment. * ******************************************************************************/ import java.util.Comparator; import edu.princeton.cs.algs4.StdDraw; public class Point implements Comparable<Point> { private final int x; // x-coordinate of this point private final int y; // y-coordinate of this point /** * Initializes a new point.

編程作業: 8 Puzzle 只有99分 Board.java import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Board { private final short[] blocks; private final int n; private int i0; private int hamming; private int manhattan; private long hash; public Board(int[][] blocks) { this(blocks.length, copy(blocks)); } private Board(int n, short[] blocks) { this.blocks = Arrays.copyOf(blocks, blocks.length); this.n = n; this.hash = 0; for (int i = 0; i < blocks.length; i++) { if (this.

編程作業: Kd-Trees 100分關鍵在如果當前最短距離>區域到點最短距離時才找，區域到點的最短距離可先用點到線的距離比過 PointSET.java import java.util.LinkedList; import java.util.List; import java.util.TreeSet; import edu.princeton.cs.algs4.Point2D; import edu.princeton.cs.algs4.RectHV; public class PointSET { private TreeSet<Point2D> set; public PointSET() { this.set = new TreeSet<>(); } public boolean isEmpty() { return this.set.isEmpty(); } public int size() { return this.set.size(); } public void insert(Point2D p) { requireNonNull(p); this.set.add(p); } public boolean contains(Point2D p) { requireNonNull(p); return this.set.contains(p); } public void draw() { for (Point2D p : this.set) p.