一、アルゴリズム第四版(二分検索、リュック、キュー、スタック)
23679 ワード
整理自アルゴリズム第4版アルゴリズム第4版code及びDataダウンロード自ライブラリダウンロード
きそぶ
にぶんたんさく
/* * int * ， * In StdIn StdOut */
package edu.princeton.cs.algs4;
import java.util.Arrays;
public class BinarySearch {
private BinarySearch() { }
public static int indexOf(int[] a, int key) {
int lo = 0;
int hi = a.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (key < a[mid]) hi = mid - 1;
else if (key > a[mid]) lo = mid + 1;
else return mid;
}
return -1;
}
public static int rank(int key, int[] a) {
return indexOf(a, key);
}
public static void main(String[] args) {
In in = new In(args[0]);
int[] whitelist = in.readAllInts();
Arrays.sort(whitelist);
while (!StdIn.isEmpty()) {
int key = StdIn.readInt();
if (BinarySearch.indexOf(whitelist, key) == -1)
StdOut.println(key);
}
}
}自分で書いたバージョン:
public class BinarySearch {
private BinarySearch() {}
public static int indexof(ArrayList<Integer> a, int key){
int max = a.size()-1;
int min = 0;
int mid = (max-min)/2 + min;
while(min<=max){
mid = (max-min)/2 + min;
if (key> a.get(mid)) min = mid + 1;
else if (key<a.get(mid)) max = mid - 1;
else return mid;
}
return -1;
}
public static ArrayList<Integer> read(){
ArrayList<Integer> list = new ArrayList<Integer>();
Scanner in =null;
try {
in = new Scanner(new File("D:\\Algorithm\\tinyW.txt"));
while(in.hasNext()){
list.add(in.nextInt());
}
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
System.out.println(" ");
e.printStackTrace();
}
in.close();
return list;
}
public static void main(String[] args) {
ArrayList<Integer> list = read();
list.sort(null);
int index = indexof(list,33);
System.out.println("index:" + index);
}リュックサック
リュックサックは、要素を削除することをサポートしない集合データ型であり、インスタンスで要素を収集し、収集されたすべての要素を反復的に巡回することを支援することを目的としています.反復の順序は不確定であり、使用例とは無関係である.内部にノードノードノードを定義します.nextはfirstを最初に返し、反復するためcurrentの値を変更することに注意してください.ソース:
package bag;
import java.util.Iterator;
import java.util.NoSuchElementException;
import edu.princeton.cs.introcs.StdIn;
import edu.princeton.cs.introcs.StdOut;
public class Bag<Item> implements Iterable<Item> {
private Node<Item> first; // beginning of bag
private int N; // number of elements in bag
// helper linked list class
private static class Node<Item> {
private Item item;
private Node<Item> next;
}
public Bag() {
first = null;
N = 0;
}
public boolean isEmpty() {
return first == null;
}
public int size() {
return N;
}
public void add(Item item) {
Node<Item> oldfirst = first;
first = new Node<Item>();
first.item = item;
first.next = oldfirst;
N++;
}
public Iterator<Item> iterator() {
return new ListIterator<Item>(first);
}
// an iterator, doesn't implement remove() since it's optional
private class ListIterator<Item> implements Iterator<Item> {
private Node<Item> current;
public ListIterator(Node<Item> first) {
current = first;
}
public boolean hasNext() { return current != null; }
public void remove() { throw new UnsupportedOperationException(); }
public Item next() {
if (!hasNext()) throw new NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}
}
public static void main(String[] args) {
Bag<String> bag = new Bag<String>();
while (!StdIn.isEmpty()) {
String item = StdIn.readString();
bag.add(item);
}
StdOut.println("size of bag = " + bag.size());
for (String s : bag) {
StdOut.println(s);
}
}
}キュー
FIFOソース:
package queue;
import java.util.Iterator;
import java.util.NoSuchElementException;
import edu.princeton.cs.introcs.StdIn;
import edu.princeton.cs.introcs.StdOut;
public class Queue<Item> implements Iterable<Item> {
private Node<Item> first; // beginning of queue
private Node<Item> last; // end of queue
private int N; // number of elements on queue
// helper linked list class
private static class Node<Item> {
private Item item;
private Node<Item> next;
}
public Queue() {
first = null;
last = null;
N = 0;
}
public boolean isEmpty() {
return first == null;
}
public int size() {
return N;
}
public Item peek() {
if (isEmpty()) throw new NoSuchElementException("Queue underflow");
return first.item;
}
public void enqueue(Item item) {
Node<Item> oldlast = last;
last = new Node<Item>();
last.item = item;
last.next = null;
if (isEmpty()) first = last;
else oldlast.next = last;
N++;
}
public Item dequeue() {
if (isEmpty()) throw new NoSuchElementException("Queue underflow");
Item item = first.item;
first = first.next;
N--;
if (isEmpty()) last = null; // to avoid loitering
return item;
}
public String toString() {
StringBuilder s = new StringBuilder();
for (Item item : this)
s.append(item + " ");
return s.toString();
}
public Iterator<Item> iterator() {
return new ListIterator<Item>(first);
}
// an iterator, doesn't implement remove() since it's optional
private class ListIterator<Item> implements Iterator<Item> {
private Node<Item> current;
public ListIterator(Node<Item> first) {
current = first;
}
public boolean hasNext() { return current != null; }
public void remove() { throw new UnsupportedOperationException(); }
public Item next() {
if (!hasNext()) throw new NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}
}
}スタック
LIFOソース:
package stack;
import java.util.Iterator;
import java.util.NoSuchElementException;
import edu.princeton.cs.introcs.StdIn;
import edu.princeton.cs.introcs.StdOut;
public class Stack<Item> implements Iterable<Item> {
private Node<Item> first; // top of stack
private int N; // size of the stack
// helper linked list class
private static class Node<Item> {
private Item item;
private Node<Item> next;
}
public Stack() {
first = null;
N = 0;
}
public boolean isEmpty() {
return first == null;
}
public int size() {
return N;
}
public void push(Item item) {
Node<Item> oldfirst = first;
first = new Node<Item>();
first.item = item;
first.next = oldfirst;
N++;
}
public Item pop() {
if (isEmpty()) throw new NoSuchElementException("Stack underflow");
Item item = first.item; // save item to return
first = first.next; // delete first node
N--;
return item; // return the saved item
}
public Item peek() {
if (isEmpty()) throw new NoSuchElementException("Stack underflow");
return first.item;
}
public String toString() {
StringBuilder s = new StringBuilder();
for (Item item : this)
s.append(item + " ");
return s.toString();
}
public Iterator<Item> iterator() {
return new ListIterator<Item>(first);
}
// an iterator, doesn't implement remove() since it's optional
@SuppressWarnings("hiding")
private class ListIterator<Item> implements Iterator<Item> {
private Node<Item> current;
public ListIterator(Node<Item> first) {
current = first;
}
public boolean hasNext() {
return current != null;
}
public void remove() {
throw new UnsupportedOperationException();
}
public Item next() {
if (!hasNext()) throw new NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}
}
}スタックの例:演算式の評価
public class Evaluate {
public static void main(String[] args)
{
Stack<String> ops = new Stack<String>();
Stack<Double> vals = new Stack<Double>();
while (!StdIn.isEmpty())
{ // Read token, push if operator.
String s = StdIn.readString();
if (s.equals("(")) ;
else if (s.equals("+")) ops.push(s);
else if (s.equals("-")) ops.push(s);
else if (s.equals("*")) ops.push(s);
else if (s.equals("/")) ops.push(s);
else if (s.equals("sqrt")) ops.push(s);
else if (s.equals(")"))
{ // Pop, evaluate, and push result if token is ")".
String op = ops.pop();
double v = vals.pop();
if (op.equals("+")) v = vals.pop() + v;
else if (op.equals("-")) v = vals.pop() - v;
else if (op.equals("*")) v = vals.pop() * v;
else if (op.equals("/")) v = vals.pop() / v;
else if (op.equals("sqrt")) v = Math.sqrt(v);
vals.push(v);
} // Token not operator or paren: push double value.
else vals.push(Double.parseDouble(s));
}
StdOut.println(vals.pop());
}
}