chouclee’s gists

chouclee / Hanoi.java

Created June 28, 2014 08:49

[CC150][3.4] In the classic problem of the Towers of Hanoi, you have 3 rods and N disks of different sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending order of size from top to bottom (e.g., each disk sits on top of an even larger one). You have the following constraints: (1) Only one disk can be moved at a t…

	// reference :　http://hawstein.com/posts/3.4.html
	import java.util.Stack;
	public class Hanoi {
	private Stack<Operation> stack;

	private class Operation {
	private int start;
	private int end;
	private String src;
	private String bridge;

chouclee / SetOfStacks.java

Created June 23, 2014 09:35

[CC150][3.3] Imagine a (literal) stack of plates If the stack gets too high, it might topple Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold Implement a data structure SetOfStacks that mimics this SetOfStacks should be composed of several stacks, and should create a new stack once the pre…

	import java.util.Stack;
	import java.util.ArrayList;

	public class SetOfStacks<T> {
	private ArrayList<myStack> stacks;
	private int threshold;
	private int currIdx;

	private class myStack {
	Stack<T> stack;

chouclee / solution.java

Created June 23, 2014 09:05

[CC150][2.7] Implement a function to check if a linked list is a palindrome.

	import java.util.LinkedList; //LinkedList in Java is double-linked list
	import java.util.ListIterator;
	import java.util.Stack;

	public class solution {
	public static<T> boolean isPalindrome(LinkedList<T> list) {
	if (list == null) throw new IllegalArgumentException();
	Stack<T> reverse = new Stack<T>();
	int N = 0;
	for (T element : list) {

chouclee / partition.java

Created June 23, 2014 06:44

[CC150][2.4] Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.

	import java.util.LinkedList;

	public class partition {
	public static<T extends Comparable<? super T>> LinkedList<T> parti(LinkedList<T> list, T pivot) {
	LinkedList<T> lessThan = new LinkedList<T>();
	LinkedList<T> equal = new LinkedList<T>();
	LinkedList<T> largerThan = new LinkedList<T>();
	int cmp;
	for (T element : list) {
	cmp = element.compareTo(pivot);

chouclee / minStack.java

Created June 20, 2014 05:50

[CC150][3.2] How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.

	import java.util.Stack;
	import java.util.Random;

	public class minStack<T extends Comparable<? super T>> {
	Stack<T> data;
	Stack<T> min;
	T minimum;
	int N;

	public minStack() {

chouclee / TripleStack.java

Created June 20, 2014 04:32

[CC150][3.1] Describe how you could use a single array to implement three stacks

	//* http://algs4.cs.princeton.edu/13stacks/
	//* [statck1 element, statck2 element, statck3 element, statck1 element,statck2 element,...,statck3 element]
	//* double the array size when one stack is full
	//* shrink the array size to half when all three stacks are one-quarter size full
	//* time complexity: average O(1) for push() and pop()
	import java.lang.reflect.Array;
	import java.util.Iterator;
	import java.util.NoSuchElementException;

	public class TripleStack<Item> {

chouclee / CircularList.java

Created June 19, 2014 14:08

[CC150][2.6] Given a circular linked list, implement an algorithm which returns node at the beginning of the loop DEFINITION Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.EXAMPLE input: A -> B -> C -> D -> E -> C [the same C as earlier] output: C

	import java.util.Random;
	import java.util.HashSet;

	public class CircularList<Item> {
	private Node first;
	private Node last;

	private class Node {
	private Item item;
	private Node next;

chouclee / add.java

Last active August 29, 2015 14:02

[CC150][2.5] You have two numbers represented by a linked list, where each node contains a single digit The digits are stored in reverse order, such that the 1’s digit is at the head of the list Write a function that adds the two numbers and returns the sum as a linked list. EXAMPLE Input: (3 -> 1 -> 5) + (5 -> 9 -> 2) Output: 8 -> 0 -> 8

	import java.util.LinkedList;
	import java.util.ListIterator;
	import java.util.Random;

	public class add {
	public static LinkedList<Integer> addList(LinkedList<Integer> a,
	LinkedList<Integer> b) {
	LinkedList<Integer> result = new LinkedList<Integer>();
	ListIterator<Integer> iterA = a.listIterator();
	ListIterator<Integer> iterB = b.listIterator();

chouclee / LinkedList.java

Last active August 29, 2015 14:02

[CC150][2.3] Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node. EXAMPLE Input: the node ‘c’ from the linked list a->b->c->d->e Result: nothing is returned, but the new linked list looks like a->b->d->e

	public class LinkedList<Item> {
	private Node<Item> first;
	private Node<Item> last;
	private int N;

	public LinkedList() {
	this.N = 0;
	}

	public void add(Node<Item> node) {

chouclee / nthToLast.java

Created June 19, 2014 06:15

[CC150][2.2] Implement an algorithm to find the nth to last element of a singly linked list

	import java.util.LinkedList;

	public class nthToLast {
	public static<Item> Item find(LinkedList<Item> list, int n) {
	int N = list.size();
	if ( n < 1 \|\| n > N) return null;
	int idx = N - n;
	return list.get(idx);
	}

Zhoucheng Li chouclee