Practices

4missing-bitSet.java

//1,000,000 ints find 4 missing numbers
//naive way: bitset, using O(n) space

static List<Integer> findmissing(int[] array)
{
	
	BitSet bset = new BitSet(array.length);
	for(int i=0;i<array.length;++i)
	{
		bset.set(array[i]);
	}
	ArrayList<Integer> list = new ArrayList<Integer>();
	for(int i=0;i<array.length+4;++i)
	{
		if(!bset.get(i))
			list.add(i);
	}
	return list;
}
//blocks: using O(n/4) space
	int blksize = size/20;
	int l=0,r=blksize;
	List<Integer> list = new ArrayList<Integer>();
	while(r<=size)
	{	
		list.addAll(findmissingblks(array,l,r));
		l = r;
		r = r+blksize;
	}
static List<Integer> findmissingblks(int[] array, int l, int r)
{
	
	BitSet bset = new BitSet(r-l+1);
	for(int i=0;i<array.length;++i)
	{
		if(array[i]<=r && array[i]>=l)
			bset.set(array[i]);
	}
	ArrayList<Integer> list = new ArrayList<Integer>();
	for(int i=l;i<r;++i)
	{
		
		if(!bset.get(i))
			list.add(i);
	}

	return list;
}

//no additional hashset, sorted array ONLY
static List<Integer> findmissingsorted(int[] array)
{
	ArrayList<Integer> list = new ArrayList<Integer>();
	int expect = 0;
	for(int i=0;i<array.length;++i)
	{
		if(array[i]!=expect)
		{
			while(array[i]!=expect)
			{
				list.add(expect);
				expect++;	
			}
			
		}
		expect++;
	}
	int corner = 4-list.size();
	for(int i=1;i<=corner;++i)
	{
		list.add(array[array.length-1]+i);
	}
	
	return list;
}

anagram of one word.java

//O(N)
static List<String> anagrams(String[] dictionary, String word)
{	//sort each word in dictionary alphabetically
	//sort the given word
	//compare
	List<String> list = new ArrayList<String>();
	String s;
	String target = sortString(word);
	for(String str:dictionary)
	{
		
		s = sortString(str);
		if(target.equals(s))
		{
			list.add(str);
		}
	}
	return list;
}

static String sortString(String word)
{
	char[] array = word.toCharArray();
	Arrays.sort(array);
	StringBuilder sb = new StringBuilder();
	sb.append(array);
	return sb.toString();
}

binaryPalindrome.java

//O(N)
static boolean is_palindrome(int n)
{
	//we have one number n
	//if n's binary expression is palindrome, then if we reverse the expression, we will still get same value as n
	
	int count = 0;
	int m1,m2;
	m1 = n;
	m2 = 0;
	//calculate how many bits we have
	for (count = 0; m1 != 0; count++) m1 >>= 1;
		m1 = n;
	//reversely store bits into m1
	for (; count > 0; count--)
	{
		m2 <<= 1; m2 += (m1 & 1); m1 >>= 1; }
	//compare
	if (m2 == n) 
		return true; 
	else 
		return false;
}

bipartite.java

//BFS, O(Edges), space O(Vertices)
//each time we visit a node, we color it;
//for all neighbor nodes of node A, if the neighbor node we are currently visiting has already been colored, compare:
//    if the color is the same as A, not good
//    else keep checking

  public boolean isBipartite(List<GraphNode> graph) {
    HashMap<GraphNode, Integer> colorSet = new HashMap<GraphNode, Integer>();//store node and color
    Deque<GraphNode> q = new ArrayDeque<GraphNode>();//for BFS
    //initialization
    GraphNode curr = graph.get(0);
    q.offer(curr);
    colorSet.put(curr, 1);
    int color,currColor;
    //BFS
    while(!q.isEmpty())
    {
      curr = q.poll();
      currColor = colorSet.get(curr);
       
      for(GraphNode neighbor : curr.neighbors)
      {
        //not yet colored
        if(!colorSet.containsKey(neighbor))
        {
          q.offer(neighbor);
          colorSet.put(neighbor, 1-currColor);
        }
        //colored
        else
        {
          color = colorSet.get(neighbor);
          if(color == colorSet.get(curr))
          {
            return false;
          }
          
        }
        
      }
    }
    return true;
  }

BSTminLarge.java

//find the minimum value that larger than the node
//O(logN) since it is a BST 
int find(TreeNode root, int target, TreeNode closest)
{	
	//reach the leaf
	if(root.left == null && root.right == null)
	{
		if(root.value>=target) return root.value;
		return closest.value;
	}
	//find the target
	if(root.value == target) return target;
	//binary search 
	//if current value < target
	//check if current.right's value is larger than target, if so, the closest node is updated to be right
	if(root.value<target)
	{
		if(root.right == null) return closest;
		if(root.right.value>target)
			closest = root.right;
		//continue searching
		return find(root.right, target, closest);
	}
	//if current value > target
	//check if current.left's value is larger than target, if so, update closest
	else
	{
		if(root.left == null) return closest;
		if(root.left.value>target)
			closest = root.left;
		return find(root.left, target, closest);
		
	}

checkConnectionBFS.java

//Using BFS, O(Edges), space O(Vertices)
//0: able to go
public static boolean checkConnection(int[][] grid, int ah, int aw, int bh, int bw)
	{	//bfs
		class Node{
			int h;
			int w;
			public Node(int h, int w)
			{
				this.h=h;
				this.w=w;
			}
		}
		boolean[][] visited = new boolean[grid.length][grid[0].length];
		Deque<Node> q = new ArrayDeque<Node>();
		Node startNode = new Node(ah, aw);
		q.offer(startNode);
		while(!q.isEmpty())
		{
			Node curr = q.poll();
			int w = curr.w;
			int h = curr.h;
			//up:h-1, down:h+1, right:w+1, left:w-1
			if(w==bw && h==bh) return true;//done
			if(h-1>=0 && grid[h-1][w]==0 && !visited[h-1][w])
			{
				visited[h-1][w] = true;
				q.offer(new Node(h-1,w));
			}
			if(h+1<grid.length && grid[h+1][w]==0 && !visited[h+1][w])
			{
				visited[h+1][w] = true;
				q.offer(new Node(h+1,w));
			}
			if(w-1>=0 && grid[h][w-1]==0 && !visited[h][w-1])
			{
				visited[h][w-1] = true;
				q.offer(new Node(h,w-1));
			}
			if(w+1<grid[0].length && grid[h][w+1]==0 &&!visited[h][w+1])
			{
				visited[h][w+1] = true;
				q.offer(new Node(h, w+1));
			}
		}
		return false;
	}

closestBST.java

//O(logN) 
//find the closest value in BST
  public int closest(TreeNode root, int target) {

    return close(root, target, Integer.MAX_VALUE);
  }
  int close(TreeNode root, int target, int min)
  {
    if(root==null) return min;
    if(Math.abs(min-target)>Math.abs(root.key-target))
      min = root.key;
    if(root.key>target) return close(root.left, target, min);
    else
      return close(root.right, target, min);
  }

fibonacci.java

public static BigInteger fib(int K)
{
	if(K==0) return BigInteger.valueOf(0);
	BigInteger sum = BigInteger.valueOf(0);
    BigInteger k1 = BigInteger.valueOf(0);
    BigInteger k2 = BigInteger.valueOf(1);
    BigInteger fib = k1.add(k2);//K==2
    if(K>1) 
    	sum = fib.add(k2);//sum of k==1 and k==2
    else
    	sum = fib; //k==1, no loop 
    for(int i=2; i<K;++i)
    {
        k1 = k2;
        k2 = fib;
        fib = k1.add(k2);
        sum = sum.add(fib);
    }
    System.out.println(sum);
    return fib;
}

findAllNonrepeatOrdered.java

/*Byte: -2^7 to 2^7-1
Short: -2^15 to 2^15-1
int: -2^31 to 2^31-1
long: -2^63 to 2^63-1
float: 32bits, 0.0f
double: 64bits
Boolean: 8bits
Char: 16bits, unicode
*/
static List<Character> findnonrepeat(String s)
{
	HashSet<Character> repeat = new HashSet<>();
	TreeSet<Character> nonrepeat = new TreeSet<>();
	char[] arr = s.toCharArray();
	for(int i=0;i<arr.length;++i)
	{
		if(!repeat.contains(arr[i]))
			if(nonrepeat.contains(arr[i]))
			{
				repeat.add(arr[i]);
				nonrepeat.remove(arr[i]);
			}
			else
				nonrepeat.add(arr[i]);
		
	}
	List<Character> list = new ArrayList<Character>();
	for(char c:nonrepeat)
		list.add(c);
	return list;

}

findClosestNode.java

//O(N)
//3d center -> nearest node
public static Node findclose(Node[] nodeList)
{
	int sumx=0;
	int sumy=0;
	int sumz=0;
	int avgx, avgy, avgz;
	int n = nodeList.length;
	for(int i=0;i<n;++i)
	{
		sumx+=nodeList[i].x;
		sumy+=nodeList[i].y;
		sumz+=nodeList[i].z;
		
	}
	avgx = sumx/n;
	avgy = sumy/n;
	avgz = sumz/n;
	
	Node center = new Node(avgx, avgy, avgz);
	double min=Double.MAX_VALUE;
	Node minNode=null;
	for(int i=0;i<n;++i)
	{
		int x = nodeList[i].x;
		int y = nodeList[i].y;
		int z = nodeList[i].z;
		
		double distance = Math.sqrt( (x-center.x)*(x-center.x) + (y-center.y)*(y-center.y) + (z-center.z)*(z-center.z));
		if(min>distance)
		{
			min = distance;
			minNode = nodeList[i];
		}
		
	}
	return minNode;
}

//graph floyd-warshall -> find the total distance for all nodes -> get minimum

findDupStrInt.java

//O(N)
public static List<Integer> findDuplicates(String s)
	{
		//list: duplicated value
		//set: store value for checking duplicate
		List<Integer> list = new ArrayList<Integer>();
		HashSet<Integer> set = new HashSet<Integer>();
		char[] arr = s.toCharArray();
		
		for(int i=0;i<arr.length;++i)
		{
			if(set.contains(arr[i]-'0'))
				list.add(arr[i]-'0');
			else
				set.add(arr[i]-'0');
		}
		return list;
	}

findfirstnonrepeating.java

static char findchar(String s)
{
	HashMap<Character, Integer> map = new HashMap<>();
	char[] arr = s.toCharArray();
	for(int i=0;i<arr.length;++i)
	{
		if(map.containsKey(arr[i]))
			map.put(arr[i], map.get(arr[i])+1);
		else
			map.put(arr[i],1);
	}
	for(int i=0;i<arr.length;++i)
	{
		if(map.get(arr[i])==1)
			return arr[i];
	}
	return 'a';
}
//O(N)
static char findcharonce(String s)
{
	HashSet<Character> repeat = new HashSet<>();
	//use linkedhashset to keep the order of input
	HashSet<Character> nonrepeat = new LinkedHashSet<>();
	char[] arr = s.toCharArray();
	for(int i=0;i<arr.length;++i)
	{
		if(!repeat.contains(arr[i]))
			if(nonrepeat.contains(arr[i]))
			{
				repeat.add(arr[i]);
				nonrepeat.remove(arr[i]);
			}
			else
				nonrepeat.add(arr[i]);
		
	}
	return (char)nonrepeat.toArray()[0];

}

//in a stream
static void firstNRCharStream()
{
	HashSet<Character> repeat = new HashSet<>();
	HashSet<Character> nonrepeat = new LinkedHashSet<>();
	Scanner cin = new Scanner(System.in);
	while(cin.hasNext())
	{
		String s = cin.nextLine();
		char[] arr = s.toCharArray();
		for(int i=0;i<arr.length;++i)
		{
			if(!repeat.contains(arr[i]))
				if(nonrepeat.contains(arr[i]))
				{
					repeat.add(arr[i]);
					nonrepeat.remove(arr[i]);
				}
				else
					nonrepeat.add(arr[i]);
		}
		if(nonrepeat.isEmpty()) System.out.println("no unique char");
		else
			System.out.println(nonrepeat.toArray()[0]);
	}
	
}

findMedianThreshold.java

package leetcode;
//O(logN)
//@Test(expected= NullPointerException.class)
public class Threshold {

	public static void main(String[] args) throws Exception
	{
		int[] a = {1,1,3,3,3,8,10};
		System.out.println(findMedian(a,7));
	}
	static int findMedian(int[] array, int threshold) throws Exception
	{
		if(array == null) return -1;
		if(threshold>array[array.length-1]) throw new NullPointerException();
		int firstidx = firstOccur(array, threshold);
		int size = array.length-firstidx;
		if(size%2==0)
			return array[firstidx+size/2-1]+(array[firstidx+size/2] - array[firstidx+size/2-1])/2;
		else
			return array[firstidx+size/2];
	}
	//duplicate value
	static int firstOccur(int[] array, int target)
	{
		if(array==null) return -1;
		if(array.length==0) return -1;
		int l=0, r=array.length-1;
		int mid;
		while(l<r-1)
		{
			mid = l+(r-l)/2;
			if(array[mid]>=target)
				r=mid;
			else
				l=mid+1;
		}
		if(array[l]>=target) return l;
		else return r;
	}
}

findpartitionSum.java

static int findpartition(int[] array)
{
	//lsum | rsum
	//0 | 1 2 3 4 5
	//two pointers moving facing each other
	int l = 0;
	int r =array.length-1;
	//two sums to keep tracking of current status
	int lsum = 0;
	int rsum = 0;
	//set up right sum
	for(int i=0;i<array.length;++i)
	{
		rsum+=array[i];
	}

	while(l<=r)
	{
		if(lsum==rsum)
			return (l==0)?0:l-1;
		else
		{	
			if(l==0)
				lsum=0;
			else 
				lsum+=array[l-1];
			rsum-=array[l++];
		}
	}
	return 0;
}

inputMedian.java

package build;
import java.util.*;
/*
maxheap contains smaller part
minheap contains larger part
keep that the size difference<2
if size equal, return mean
if size diff, return peek of the larger size heap

*/
public class InputStreamMedian {
public static void main(String[] args)
{
	Comparator<Integer> maxcomparator = new Comparator<Integer>()
	{
		@Override
		public int compare(Integer a, Integer b)
		{
			if(a<b) return 1;
			return -1;
		}
	
	};
	PriorityQueue<Integer> maxheap = new PriorityQueue<Integer>(maxcomparator);//store the smaller part
	PriorityQueue<Integer> minheap = new PriorityQueue<Integer>();//store the larger part

	Scanner cin = new Scanner(System.in);
	int number;
	ArrayList<Integer> list = new ArrayList<Integer>();
	while(cin.hasNext())
	{
		number = cin.nextInt();
		list.add(number);
		if(minheap.size()==0)
		{
			minheap.add(number);
		}
		else
			if(maxheap.size()==0)
			{
				int mintop = minheap.poll();
				minheap.add(Math.max(mintop, number));
				maxheap.add(Math.min(mintop, number));
				
			}
			else
			{
				int mintop = minheap.peek();
				int maxtop = maxheap.peek();
				//in smaller part
				if(number<maxtop)
				{
					if(maxheap.size()<=minheap.size())
					{
						maxheap.offer(number);
					}
					else
					{
						minheap.offer(maxheap.poll());
						maxheap.offer(number);
					}
				}
				else//in middle
					if(number>=maxtop && number<=mintop)
					{
						if(maxheap.size()<=minheap.size())
							maxheap.offer(number);
						else
							minheap.offer(number);	
					}
					else//in larger part
					{
						
						if(minheap.size()<=maxheap.size())
						{
							minheap.offer(number);
						}
						else
						{
							maxheap.offer(minheap.poll());
							minheap.offer(number);
						}
					}
			}
		System.out.println("list:"+list);
		if(maxheap.size()==minheap.size())
			System.out.println("median = "+(maxheap.peek()+minheap.peek())/2);
		else
			if(maxheap.size()>minheap.size())
				System.out.println("median = "+maxheap.peek());
			else
				System.out.println("median = "+minheap.peek());
	}
			
}


}

KclosestOnePoint.java

	/*
	 * getClosestK
	 * return an array of k closest points to origin
	 * 
	 * @author Xiang Li <[email protected]>
	 * @param points	the array of all points in the plane
	 * @param origin	the origin point
	 * @param k			the number of closest points we need to find
	 * @return	the array of k closest points
	 *
	 * Runs in O(NlogN) when k is large
	 * 
	 * 
	 * 
	 */
public static class Point{
	int x;
	int y;
	int z;
	public Point(int x, int y, int z)
	{
		this.x = x;
		this.y = y;
		this.z = z;
	}
}

	public static Point[] getClosestK(Point[] points, Point origin, int k)
	{
		//new local class that contains distance from one point to origin
		//obj - the point that this PointInfo represents
		//d - the distance between obj and origin
		class PointInfo
		{
			Point obj;
			double d;
			public PointInfo(Point obj, double d)
			{
				this.obj = obj;
				this.d = d;
			}

		}
		//new comparator to:
		//1. help construct a maxheap (java's PriorityQueue is a minheap by default)
		//2. help construct the maxheap with type T being PointInfo
		Comparator<PointInfo> comparator = new Comparator<PointInfo>()
		{
			@Override
			public int compare(PointInfo a, PointInfo b)
			{
				//compare the distances from origin
				if(a.d-b.d<0) return 1;
				else if(a.d-b.d==0) return 0;
				else return -1;
			}
		};
		
		/*
		 * maxheap's usage
		 * In this problem, we will use a maxheap to do: 
		 * 1. put first k points into the maxheap
		 * 2. from k+1 to points.length, if the top element in maxheap is 
		 *    further from origin than the current visiting point,
		 *    then we poll the top element and add the current point into maxheap
		 * 3. after the above steps are done, we will have k points with smallest distances from origin
		 * 
		 * 
		 * 
		 */
		PriorityQueue<PointInfo> maxheap = new PriorityQueue<PointInfo>(comparator);
		PointInfo[] pointInfos = new PointInfo[points.length];
		
		//put all points into our new array of PointInfo to make next step easier
		for(int i=0; i<points.length;++i)
		{
			Point point = points[i];
			double d = Math.sqrt((double)((origin.x - point.x)*(origin.x - point.x)) + 
					(double)((origin.y-point.y)*(origin.y-point.y))+(double)((origin.z-point.z)*(origin.z-point.z)));
			//Math.abs((double)(origin.x-point.x)/(double)(origin.y-point.y));
			pointInfos[i] = new PointInfo(point, d);
		}
		//SETP 1: put first k elements into maxheap
		for(int i=0;i<k;++i)
		{
			maxheap.offer(pointInfos[i]);
		}
		//STEP 2: from k+1 to N, if the current point is closer to origin than the top element of maxheap, 
		//poll and add curren point
		for(int i=k;i<pointInfos.length;++i)
		{
			
			PointInfo pointInfo = pointInfos[i];
				if(maxheap.peek().d > pointInfo.d)
				{
					maxheap.poll();
					maxheap.offer(pointInfo);
				}
		}
		
		Point[] sol = new Point[k];
		int i=0;
		//STEP 3: the top k elements are our desired points
		while(!maxheap.isEmpty())
		{
			sol[i++] = maxheap.poll().obj;
		}
		return sol;

	}

LCA with parent nodes.java

int getDepth(TreeNode node)
{
  int depth = 0;
  while(node!=null)
  {
    depth++;
    node = node.parent;
  }
}


public TreeNode findLCA(TreeNode node1, TreeNode node2)
{
  int d1 = getDepth(node1);
  int d2 = getDepth(node2);
  if(d1<d2)
  {
    TreeNode tnode = node1;
    node1 = node2;
    node2 = tnode;
    int t = d1;
    d1 = d2;
    d2 = t;
  }
  while(d1>d2)
  {
    node1 = node1.parent;
  }
  
  while(node1!=node2)
  {
    node1 = node1.parent;
    node2 = node2.parent;
  }
  return node1;
}

LRU.java

//Least Recently Used (LRU) cache
//we expect O(1) searching time
//use a hashmap for storing value
//use a linkedlist to keep track of the new and old frequency

public class LRUCache {
	//node class
	//the linkedlist will help keep new and old frequency
	//head - lr - a - b -c - mr - tail
	//head.next: least recently used
	//tail.prev: most recently used
	private class Node {
		Node prev;
		Node next;
		int key;
		int value;
		//ensure O(1) searching: doubly linked list, best for removing one node
		public Node(int key, int value) {
			this.key = key;
			this.value = value;
			this.prev = null;
			this.next = null;
		}
	}
	
	private int capacity;
	private HashMap<Integer, Node> map = new HashMap<Integer, Node>();
	private Node head = new Node(-1, -1);
	private Node tail = new Node(-1, -1);
	//initialization
	public LRUCache(int capacity) {
		this.capacity = capacity;
		tail.prev = head;
		head.next = tail;
	}
	//get method
	public int get(int key) {
		//not found
		if (!map.containsKey(key)) {
			return -1;
		}

		// STEP 1: remove current from list 
		Node current = map.get(key);//O(1)
		current.prev.next = current.next;
		current.next.prev = current.prev;
		//STEP 2: move current to tails: the current is most recently used now
		addToTail(current);
		return current.value;
	}
	//set method
	public void set(int key, int value) {
		if (get(key) != -1) {
			map.get(key).value = value;
			return;
		}
		//STEP 1: remove least recently used node
		if (map.size() == capacity) {
			// remove head.next node
			map.remove(head.next.key);
			head.next = head.next.next;
			head.next.prev = head;
		}
		//STEP 2: add new node to tail
		Node insert = new Node(key, value);
		map.put(key, insert);
		addToTail(insert);
	}
	//helper function
	private void addToTail(Node current) {
		current.prev = tail.prev;
		tail.prev = current;
		current.prev.next = current;
		current.next = tail;
	}
}

mergeLinkedList.java

  public ListNode merge(ListNode one, ListNode two) {
    if(one==null) return two;
    if(two==null) return one;
    ListNode newHead;
    if(one.value < two.value)
    {
      newHead = one;
      one = one.next;
    }
    else
    {
      newHead = two;
      two = two.next;
    }
    ListNode saveHead = newHead;
    while(one!=null || two!=null)
    {
      if(two==null)
      {
       while(one!=null)
       {
        newHead.next = one;
        one = one.next;
        newHead = newHead.next;
       }
      }
      if(one==null)
      {
        while(two!=null)
        {
          newHead.next = two;
          two = two.next;
          newHead = newHead.next;
        }
      }
      else
      {
        if(one.value>two.value)
        {
          newHead.next = two;
          two = two.next;
        }
        else
        {
          newHead.next = one;
          one = one.next;
        }
        newHead = newHead.next;
      
      }
    }
    return saveHead;
  }

plusOne.java

public class Solution {
    public int[] plusOne(int[] digits) {
        List<Integer> result = new ArrayList<Integer>();
        int addi = 1;
        int sum = 0;
        for(int i=digits.length-1;i>=0;--i)
        {
            sum = addi+digits[i];
            addi = sum/10;
            result.add(sum%10);
        }
        if(addi==1)
        {
            result.add(1);
        }
        int[] answer = new int[result.size()];
        int i=result.size()-1;
        //put the result reversely into answer
        for(int number:result)
        {
            answer[i--] = number;
        }
        return answer;
    }
}

preToPost.java

public static String preTopost(String pre){
    if(pre.length() <= 1){
        return pre;
    }
    Deque<Character> opstack = new ArrayDeque<Character>();
    StringBuilder post = new StringBuilder();
    char[] prefix = pre.toCharArray();
    for(int i=0;i<prefix.length;++i)
    {
    	if(prefix[i] == '+' || prefix[i] =='-' || prefix[i] =='*' || prefix[i] =='/')
    	{
    		opstack.push(prefix[i]);
    	}
    	else
    	{
    		post.append(prefix[i]);
    		/*
    		The stack is popped and placed into output string while the top of stack is an
            operator marked LEFT_DONE. LEFT_DONE is a marker that actually indicates the
            left operand for this operator is already converted to postfix. After popping out
            these LEFT_DONE operators the next operator is marked LEFT_DONE.
    		*/
    		while(!opstack.isEmpty() && opstack.peek() == '#')
    		{
    			opstack.pop();
    			post.append(opstack.pop());
    		}
    		opstack.push('#');
    	}
    	
    }
    return post.toString();
    
}

reverseInt.java

//with overflow detection
static int reverse(int number)
{  public int reverse(int x) {
        int max = 1<<31; 
        int ret = 0;

        while(x!=0) 
        {   //overflow detection
            if (ret != 0 && max/ret < 10 && max/ret > -10) 
            return 0;
        
            ret = ret*10 + x%10; 
            x = x/10;
            
        }

        return ret;
    }
}


//using BigInteger
static BigInteger reverse2(int number)
{
	return reverseLarge(BigInteger.valueOf(number));
}
static BigInteger reverseLarge(BigInteger number)
{
	BigInteger newnum = BigInteger.valueOf(0);
	while(!number.equals(BigInteger.valueOf(0)))
	{
		
		newnum = newnum.multiply(BigInteger.valueOf(10));
		newnum = newnum.add(number.mod(BigInteger.valueOf(10)));
		number = number.divide(BigInteger.valueOf(10));
	}
	return newnum;
}

reverseLinkedListCycle.java

static ListNode reverse(ListNode head)
{
	if(head==null) return head;
	if(head.next==null || head.next==head) return head;
	ListNode next;
	ListNode tail = head;
	//find tail
	while(tail.next!=head)
	{
		tail = tail.next;
	}
	//reverse begin
	ListNode prev = tail;
	ListNode curr = head;
	
	while(curr.next!=head)
	{
		next = curr.next;
		curr.next = prev;
		prev = curr;
		curr = next;
		
	}
	tail.next = prev;
	head.next=tail;
	return tail;
}

reverseSentence.java

//reverse the string
//reverse every word
static void rev(String s)
{
	char[] arr = s.toCharArray();
	//reverse entire string
	reverse(arr, 0, arr.length-1);
	String str = new String(arr);
	String[] sarr = str.split(" ");
	str = "";
	//reverse every word
	for(int i =0;i<sarr.length;++i)
	{
		char[] a = sarr[i].toCharArray();
		reverse(a,0,a.length-1);
		str+=new String(a);
		if(i<sarr.length-1)
		{
			str+=" ";
		}
	}
	System.out.println(str);
	
}
static void reverse(char[] arr,int l, int r)
{
	
	if(l>=r) return;
	swap(arr, l, r);
	reverse(arr, l+1, r-1);
}
static void swap(char[] arr, int a, int b)
{
	if(a==b) return;
	arr[a]^=arr[b];
	arr[b]^=arr[a];
	arr[a]^=arr[b];
}
}

sqrt.java

//Newton Method
	/*
	 *  t^m = x
	 *  1. each time, guess a value that between 0 and x
	 *  2. find the mean value of x and x/value
	 *  3. repeat step 2 until reach the tolerance
	 * 
	 */
	static float sqrt(int x, float tolerance)
	{
		if(x==0) return 0;
		
		double preValue;
		double currValue = x/2.0f;
		preValue = currValue;
		currValue = (x/preValue + preValue)/2.0;
		while(Math.abs(currValue-preValue) > tolerance)
		{
			preValue = currValue;
			currValue = (x/preValue + preValue)/2.0;
			
		}
		return (float)currValue;
	}

stringTruncate.java

static String truncate(String s, int len)
{
	char[] arr = s.toCharArray();
	List<Character> set = new ArrayList<Character>();
	for(int i=0;i<arr.length;++i)
	{
		if(arr[i]<='9' && arr[i]>='0')
			set.add(arr[i]);
	}
	
	int lenother = len-set.size();
	System.out.println(lenother);
	StringBuilder sb = new StringBuilder();
	int i=0;
	int j=0;
	while(i<len && lenother>0)
	{
		if(arr[i]>'9' || arr[i]<'0')
			lenother--;
		else
			j++;
		sb.append(arr[i]);
		i++;
	}
	System.out.println(i+" "+j);
	while(j<set.size())
	{
		sb.append(set.get(j++));
	}
	
	return sb.toString();
}

Trie.java

package build;
import java.util.*;
public class Trie {
	private int SIZE = 26;
	private TrieNode root;
	Trie()
	{
		root = new TrieNode();
	}
	private class TrieNode{
		private int count;
		private TrieNode[] children;
		private boolean isLeaf;
		private char ch;
		TrieNode()
		{
			count=1;
			children = new TrieNode[SIZE];
			isLeaf = false;
		}
	}
	
	public void insert(String s)
	{
		if(s==null || s.length()<=0) 
			return;
		TrieNode node = root;
		char[] letters = s.toCharArray();
		for(int i=0;i<s.length();++i)
		{
			int pos = letters[i]-'a';
			if(node.children[pos]==null)
			{
				node.children[pos] = new TrieNode();
				node.children[pos].ch = letters[i];
			}
			else
			{
				node.children[pos].count++;
			}
			node = node.children[pos];
				
		}
		node.isLeaf=true;
	}
	
	public int countPrefix(String prefix)
	{
		if(prefix==null || prefix.length()<=0)
			return -1;
		TrieNode node = root;
		char[] letters = prefix.toCharArray();
		for(int i=0;i<prefix.length();++i)
		{
			int pos = letters[i]-'a';
			if(node.children[pos]==null)
				return 0;
			else
				node = node.children[pos];
		}
		return node.count;
	}
	
	public boolean has(String s)
	{
		if(s==null || s.length()<=0) 
			return false;
		TrieNode node = root;  
        char[] letters=s.toCharArray();  
        for (int i = 0, len = s.length(); i < len; i++) {  
            int pos = letters[i] - 'a';  
            if (node.children[pos] != null) {  
                node = node.children[pos];  
            } else {  
                return false;  
            }  
        }  
        return node.isLeaf;  
	}
	
	public void preTraverse(TrieNode node)
	{
		if(node!=null)
		{
			System.out.println(node.ch+' ');
			for(TrieNode child:node.children)
			{
				preTraverse(child);
			}
		}
	}
}

Two Sum Design.java

	public class TwoSum {
		private Map<Integer, Integer> table = new HashMap<>();

		public void add(int input) {
			int count = table.containsKey(input) ? table.get(input) : 0;
			table.put(input, count + 1);
		}

		public boolean find(int val) {
			for (Map.Entry<Integer, Integer> entry : table.entrySet()) {
				int num = entry.getKey();
				int y = val - num;
				if (y == num) {
					// For duplicates, ensure there are at least two individual
					// numbers.
					if (entry.getValue() >= 2)
						return true;
				} else if (table.containsKey(y)) {
					return true;
				}
			}
			return false;
		}
	}

Two Sum Sorted.java

public int[] twoSum(int[] numbers, int target)
{
  int i=0, j=numbers.length-1;
  while(i<j)
  {
    int sum = numbers[i]+numbers[j];
    if(sum<target)
    {
      i++;
    }
    else if(sum>target)
    {
      j--;
    }
    else
    {
      return new int[]{i+1,j+1};
    }
  }
  return null;
}
//O(N) time O(1) space

Two Sum.java

//naive way O(n^2)
static int[] twosum(int[] nums, int target)
{
	int[] ret = new int[2];
	for(int i=0;i<nums.length;++i)
	{
		int x = nums[i];
		for(int j=i+1;j<nums.length;++j)
		{
			if(x+nums[j]==target)
			{
				ret[0] = i;
				ret[1] = j;
				return ret;
						
			}
		}
	}
	return null;
}

//O(N) time and space
public int[] twoSum(int[] numbers, int target)
{
  HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
  for(int i=0;i<numbers.length;++i)
  {
    int x = numbers[i];
    if(map.containsKey(target-x))
    {
      return new int[]{map.get(target-x)+1, i+1};
    }
    map.put(x,i);
  }
  return null;
}

twoSumPairZero.java

static void minSumPair(int arr[])
{
	int sum  = Integer.MAX_VALUE;
	int minsum = Integer.MAX_VALUE;
	if(arr.length<2) return; 
	//sort array
	Arrays.sort(arr);
	int l=0, r=arr.length-1;
	int minl=l, minr = r;
	//two pointers moving facing each other
	while(l<r)
	{
		sum = arr[l]+arr[r];
		if(Math.abs(sum) < Math.abs(minsum))
		{
			minsum = sum;
			minl = l;
			minr = r;
		}
		//reach where sum == 0 or closest to 0
		if(sum<0)
			l++;
		else
			r--;
	}
	System.out.println(arr[minl]+" "+arr[minr]);
}

Valid Palindrome.java

//O(N)
	public boolean isPalindrome(String s) {
		//starting from both ends
		 int i = 0, j = s.length() - 1;
		 //move facing each other, compare characters
		 while (i < j) {
			 while (i < j && !Character.isLetterOrDigit(s.charAt(i))) i++;
			 while (i < j && !Character.isLetterOrDigit(s.charAt(j))) j--;
			 	if (Character.toLowerCase(s.charAt(i))!= Character.toLowerCase(s.charAt(j))) {
			 		return false;
			 	}
			 	i++; j--;
		 	}
		 return true;
		}

validBST.java

  public boolean isBST(TreeNode root) {
    if(root==null) return true;
    return isbst(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
  }
  boolean isbst(TreeNode root, int min, int max)
  {
      if(root == null) return true;
      return (root.key<max) && (root.key>min) && isbst(root.left, min, root.key) 
        && isbst(root.right, root.key, max);
  }

wordBreak.java

/*
dp[i] = true if s.substring(0,i+1) is in dict
        true if dp[j]==true adn s.substring(j+1, i+1) is in dict
        false otherwise
*/
public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
        if(s==null || s.length()==0) return false;
	boolean[] dp = new boolean[s2.length()];
	for(int i=0;i<dp.length;++i)
	{
		String substr = s.substring(0,i+1);
		if(wordDict.contains(substr))
			dp[i] = true;
		else
		{
			for(int j=0;j<i;++j)
			{
				String subsubstr = s.substring(j+1,i+1);
				if(dp[j] && wordDict.contains(subsubstr))
					dp[i] = true;
			}
		}
	}
	return dp[dp.length-1];
    }
}

wordBreak2.java

public class Solution {
    public static List<String> wordBreak(String s, Set<String> dict) {
        List<String> dp[] = new ArrayList[s.length()+1];
        dp[0] = new ArrayList<String>();
        for(int i=0; i<s.length(); i++){
            //i是开始位置
            if( dp[i] == null ) continue; //前面的部分必须是可以匹配的
            for(String word:dict){
                int len = word.length();
                int end = i+len;
                if(end > s.length()) continue;
                if(s.substring(i,end).equals(word)){
                    if(dp[end] == null){
                        dp[end] = new ArrayList<String>();
                    }
                    dp[end].add(word);//记录上一个位置
                }
            }
        }

        List<String> ans = new LinkedList<String>();
        if(dp[s.length()] == null) return ans; 
        ArrayList<String> tmp = new ArrayList<String>();
        dfsStringList(dp,s.length(),ans, tmp);
        return ans;
    }

    public static void dfsStringList(List<String> dp[],int end,List<String> res, ArrayList<String> tmp){
        if(end <= 0){
            String ans = tmp.get(tmp.size()-1);
            for(int i=tmp.size()-2; i>=0; i--)
                ans += (" " + tmp.get(i) );
            res.add(ans);
            return;
        }
        for(String str:dp[end]){
            tmp.add(str);
            dfsStringList(dp,end-str.length(), res, tmp);
            tmp.remove(tmp.size()-1);
        }
    }
}

zigzagLevelOrder.java

public class BinaryTreeZigzagLevelOrderTraversal {
	//level order: BFS
	//two conditions: odd level or even level
	//odd level:offer last (the original order): left , right
	//even level: offer first (the reversed order): right, left
	public static void printTree(TreeNode root)
	{
		if(root == null) return;
		Deque<TreeNode> deque = new ArrayDeque<>();
		boolean oddLevel = true;
		deque.offerLast(root);
		while(!deque.isEmpty())
		{
			int size = deque.size();
			for(int i=0;i<size;++i)
			{
				if(oddLevel)
				{
					TreeNode cur = deque.pollFirst();
					System.out.print(cur.val);
					if(cur.left!=null)
						deque.offerLast(cur.left);
					if(cur.right!=null)
						deque.offerLast(cur.right);
					
				}
				else
				{
					TreeNode cur = deque.pollLast();
					System.out.print(cur.val);
					if(cur.right!=null)
						deque.offerFirst(cur.right);
					if(cur.left!=null)
						deque.offerFirst(cur.left);
					
				}
				
			}
			oddLevel = !oddLevel;
			System.out.println();
		}
	}
}


//level order
	public static void printTreeLV(TreeNode root)
	{
		if(root == null) return;
		Queue<TreeNode> q = new LinkedList<TreeNode>();
		q.offer(root);
		while(!q.isEmpty())
		{
			int size = q.size();
			for(int i=0;i<size;++i)
			{
				TreeNode cur = q.poll();
				System.out.print(cur.val);
				if(cur.left!=null)
				{
					q.offer(cur.left);
				}
				if(cur.right!=null)
				{
					q.offer(cur.right);
				}
			}
			System.out.println();
		}
	}