在大二快過完兩個(gè)月的時(shí)候我終于開始想刻苦學(xué)習(xí)了胞得。。稼跳。（尷尬啊~）
所以希望在這剩下的兩個(gè)月的時(shí)候能夠刷完《算法》第四版盟庞，然后把題海刷完作為新年禮物送給自己。求圍觀岂贩，好讓我堅(jiān)持下去Ｃ＞！萎津！哈哈哈~
這些答案有我自己寫的卸伞，也有官網(wǎng)上的，也有參照網(wǎng)上別人的答案锉屈，所以
如果有錯(cuò)誤或者是更好的解法或者是代碼風(fēng)格荤傲，歡迎指出，歡迎一起學(xué)習(xí)颈渊。
先貼出官網(wǎng)地址：http://algs4.cs.princeton.edu
（學(xué)習(xí)的時(shí)候多上官網(wǎng)多查官網(wǎng)文檔是一個(gè)很好的習(xí)慣哦~
附：官網(wǎng)上也有習(xí)題答案）
在CSDN上發(fā)現(xiàn)一個(gè)良心博主遂黍，習(xí)題答案很不錯(cuò)终佛，
貼出網(wǎng)址，歡迎大家去學(xué)習(xí)~
http://blog.csdn.net/furzoom/article/details/52692580
環(huán)境包下載
官網(wǎng)教程：http://algs4.cs.princeton.edu/windows/
由于《算法》中StdIn/StdOut 是作者自己寫的庫(kù)雾家，Java中是沒有這些庫(kù)的铃彰，所以要運(yùn)行書中的代碼的話就要在網(wǎng)上下載這些庫(kù)的實(shí)現(xiàn)。
實(shí)現(xiàn)方法：在官網(wǎng)下載algs4.jar和stdlib.jar兩個(gè)包芯咧，將其導(dǎo)入eclipse中即可牙捉。下載地址如下：
http://algs4.cs.princeton.edu/code/algs4.jar
http://introcs.cs.princeton.edu/java/stdlib/stdlib.jar
導(dǎo)入步驟的圖片如下：
image.png
第一章 1.3 背包，隊(duì)列和棧
-
1.3.1
答案
public boolean isFull()
{ return N == a.length; }
整個(gè)程序
import java.util.Iterator;
import java.util.NoSuchElementException;
public class FixedCapacityStackOfStrings implements Iterable<String> {
private String[] a; // holds the items
private int N; // number of items in stack
// create an empty stack with given capacity
public FixedCapacityStackOfStrings(int capacity) {
a = new String[capacity];
N = 0;
}
public boolean isEmpty() { return N == 0; }
public boolean isFull() { return N == a.length; }
public void push(String item) { a[N++] = item; }
public String pop() { return a[--N]; }
public String peek() { return a[N-1]; }
public Iterator<String> iterator() { return new ReverseArrayIterator(); }
public class ReverseArrayIterator implements Iterator<String> {
private int i = N-1;
public boolean hasNext() {
return i >= 0;
}
public String next() {
if (!hasNext()) throw new NoSuchElementException();
return a[i--];
}
public void remove() {
throw new UnsupportedOperationException();
}
}
public static void main(String[] args) {
int max = Integer.parseInt(args[0]);
FixedCapacityStackOfStrings stack = new FixedCapacityStackOfStrings(max);
while (!StdIn.isEmpty()) {
String item = StdIn.readString();
if (!item.equals("-")) stack.push(item);
else if (stack.isEmpty()) StdOut.println("BAD INPUT");
else StdOut.print(stack.pop() + " ");
}
StdOut.println();
// print what's left on the stack
StdOut.print("Left on stack: ");
for (String s : stack) {
StdOut.print(s + " ");
}
StdOut.println();
}
}
-
1.3.2
答案
was best times of the was the it (1 left on stack)
-
1.3.3
答案
b f g
-
1.3.4
官網(wǎng)答案
/******************************************************************************
* Compilation: javac Parentheses.java
* Execution: java Parentheses
* Dependencies: In.java Stack.java
*
* Reads in a text file and checks to see if the parentheses are balanced.
*
* % java Parentheses
* [()]{}{[()()]()}
* true
*
* % java Parentheses
* [(])
* false
*
******************************************************************************/
public class Parentheses {
private static final char LEFT_PAREN = '(';
private static final char RIGHT_PAREN = ')';
private static final char LEFT_BRACE = '{';
private static final char RIGHT_BRACE = '}';
private static final char LEFT_BRACKET = '[';
private static final char RIGHT_BRACKET = ']';
public static boolean isBalanced(String s) {
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == LEFT_PAREN) stack.push(LEFT_PAREN);
if (s.charAt(i) == LEFT_BRACE) stack.push(LEFT_BRACE);
if (s.charAt(i) == LEFT_BRACKET) stack.push(LEFT_BRACKET);
if (s.charAt(i) == RIGHT_PAREN) {
if (stack.isEmpty()) return false;
if (stack.pop() != LEFT_PAREN) return false;
}
else if (s.charAt(i) == RIGHT_BRACE) {
if (stack.isEmpty()) return false;
if (stack.pop() != LEFT_BRACE) return false;
}
else if (s.charAt(i) == RIGHT_BRACKET) {
if (stack.isEmpty()) return false;
if (stack.pop() != LEFT_BRACKET) return false;
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
In in = new In();
String s = in.readAll().trim();
StdOut.println(isBalanced(s));
}
}
-
1.3.5
答案
打印 N 的二進(jìn)制表示 （當(dāng)n為50時(shí)為110010）敬飒。
-
1.3.6
答案
反轉(zhuǎn)隊(duì)列上的項(xiàng)目
-
1.3.7
官網(wǎng)答案
/******************************************************************************
* Compilation: javac Stack.java
* Execution: java Stack < input.txt
* Dependencies: StdIn.java StdOut.java
* Data files: http://algs4.cs.princeton.edu/13stacks/tobe.txt
*
* A generic stack, implemented using a singly linked list.
* Each stack element is of type Item.
*
* This version uses a static nested class Node (to save 8 bytes per
* Node), whereas the version in the textbook uses a non-static nested
* class (for simplicity).
*
* % more tobe.txt
* to be or not to - be - - that - - - is
*
* % java Stack < tobe.txt
* to be not that or be (2 left on stack)
*
******************************************************************************/
import java.util.Iterator;
import java.util.NoSuchElementException;
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;
}
/**
* Initializes an empty stack.
*/
public Stack() {
first = null;
n = 0;
}
/**
* Returns true if this stack is empty.
*
* @return true if this stack is empty; false otherwise
*/
public boolean isEmpty() {
return first == null;
}
/**
* Returns the number of items in this stack.
*
* @return the number of items in this stack
*/
public int size() {
return n;
}
/**
* Adds the item to this stack.
*
* @param item the item to add
*/
public void push(Item item) {
Node<Item> oldfirst = first;
first = new Node<Item>();
first.item = item;
first.next = oldfirst;
n++;
}
/**
* Removes and returns the item most recently added to this stack.
*
* @return the item most recently added
* @throws NoSuchElementException if this stack is empty
*/
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
}
/**
* Returns (but does not remove) the item most recently added to this stack.
*
* @return the item most recently added to this stack
* @throws NoSuchElementException if this stack is empty
*/
public Item peek() {
if (isEmpty()) throw new NoSuchElementException("Stack underflow");
return first.item;
}
/**
* Returns a string representation of this stack.
*
* @return the sequence of items in this stack in LIFO order, separated by spaces
*/
public String toString() {
StringBuilder s = new StringBuilder();
for (Item item : this) {
s.append(item);
s.append(' ');
}
return s.toString();
}
/**
* Returns an iterator to this stack that iterates through the items in LIFO order.
*
* @return an iterator to this stack that iterates through the items in LIFO order
*/
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;
}
}
/**
* Unit tests the {@code Stack} data type.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
Stack<String> stack = new Stack<String>();
while (!StdIn.isEmpty()) {
String item = StdIn.readString();
if (!item.equals("-"))
stack.push(item);
else if (!stack.isEmpty())
StdOut.print(stack.pop() + " ");
}
StdOut.println("(" + stack.size() + " left on stack)");
}
}
- 1.3.8
沒有在書中找到DoublingStackOfStrings的代碼
歡迎大家指出
-
1.3.9
答案
public static String getCompleteExpression(String exp)
{
String[] params = exp.split(" ");
Stack<String> oprStack = new Stack<String>();
Stack<String> dataStack = new Stack<String>();
for (int i = 0; i < params.length; i++) {
if (isOperator(params[i])) {
oprStack.push(params[i]);
} else if (params[i].equals(")")) {
String d1 = dataStack.pop();
String d2 = dataStack.pop();
String op = oprStack.pop();
dataStack.push("( " + d2 + " " + op + " "+ d1 + " )");
} else {
dataStack.push(params[i]);
}
}
return dataStack.pop();
}
public static void main(String[] args)
{
String expression = "1 + 2 ) * 3 - 4 ) * 5 - 6 ) ) )";
String result = getCompleteExpression(expression);
System.out.println(result);
}
private static boolean isOperator(String s)
{
return (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/"));
}
-
1.3.10
答案
/******************************************************************************
* Compilation: javac InfixToPostfix.java
* Execution: java InfixToPostFix
* Dependencies: Stack.java StdIn.java StdOut.java
*
* Reads in an infix expression and outputs an equivalent postfix
* expression.
*
* Windows users: replace [Ctrl-d] with [Ctrl-z] to signify end of file.
*
* % java InfixToPostfix
* ( 2 + ( ( 3 + 4 ) * ( 5 * 6 ) ) )
* [Ctrl-d]
* 2 3 4 + 5 6 * * +
*
* % java InfixToPostfix | java EvaluatePostfix
* ( 2 + ( ( 3 + 4 ) * ( 5 * 6 ) ) )
* [Ctrl-d]
* 212
*
******************************************************************************/
public class InfixToPostfix {
public static void main(String[] args) {
Stack<String> stack = new Stack<String>();
while (!StdIn.isEmpty()) {
String s = StdIn.readString();
if (s.equals("+")) stack.push(s);
else if (s.equals("*")) stack.push(s);
else if (s.equals(")")) StdOut.print(stack.pop() + " ");
else if (s.equals("(")) StdOut.print("");
else StdOut.print(s + " ");
}
StdOut.println();
}
}
今天時(shí)間比較倉(cāng)促邪铲，先pull下來，等明天的時(shí)候先擴(kuò)充答案然后繼續(xù)發(fā)（搬運(yùn)）下面題的答案无拗。
