Substring with Concatenation of All Words

	You are given a string, S, and a list of words, L, that are all of the same length.
	Find all starting indices of substring(s) in S that is a concatenation of each word in L
	exactly once and without any intervening characters.
	For example, given:
	S: "barfoothefoobarman"
	L: ["foo", "bar"]
	You should return the indices: [0,9].
	(order does not matter).
	Time complexity: O((M - N) * N)
	public class Solution {
	public ArrayList<Integer> findSubstring(String S, String[] L) {
	ArrayList<Integer> result=new ArrayList<Integer> ();
	if (S==null||L==null||S.length()==0 ||L.length==0){
	return result;
	}
	int wordLen=L[0].length();
	int totalLen=wordLen*L.length;
	if (S.length()<totalLen){
	return result;
	}
	HashMap<String, Integer> checker=new HashMap<String, Integer>();
	for (String temp: L){
	if (checker.containsKey(temp)){
	checker.put(temp, checker.get(temp)+1);
	}
	else{
	checker.put(temp,1);
	}
	}
	for(int i=0; i<=S.length()-totalLen; i++){
	if (isValid(checker, S, i,wordLen, totalLen)){
	result.add(i);
	}
	}
	return result;
	}
	private boolean isValid(HashMap<String, Integer> checker,String S, int i, int wordLen, int totalLen){
	HashMap<String, Integer> tmpChecker=new HashMap<String, Integer>(checker);
	int start=i;
	int end=i+wordLen;
	while(end-i<=totalLen){
	String tmpString=S.substring(start, end);
	if (tmpChecker.containsKey(tmpString)){
	if (tmpChecker.get(tmpString)==0){
	return false;
	}
	tmpChecker.put(tmpString, tmpChecker.get(tmpString)-1);
	start=end;
	end=start+wordLen;
	}
	else{
	return false;
	}
	}
	return true;
	}
	}

view raw Substring with Concatenation of All Words.java hosted with ❤ by GitHub

Recover Binary Search Tree

LeetCode

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Solution: 

Use an extra class called Pre_first_second, which is used to record the previous node of current root node, first wrong node and second wrong node, preoder-traverse the entire tree find the invalid two nodes and store hem into pre-first_sercond structure. 

	Two elements of a binary search tree (BST) are swapped by mistake.
	Recover the tree without changing its structure.
	Note:
	A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	// 1/31/2014 rewrite version
	class Pre_First_Second{
	TreeNode pre=null;
	TreeNode first=null;
	TreeNode second=null;
	}
	public class Solution {
	public void recoverTree(TreeNode root) {
	if (root==null){
	return;
	}
	Pre_First_Second pfs=new Pre_First_Second();
	findBadPoints(root, pfs);
	int temp=pfs.second.val;
	pfs.second.val=pfs.first.val;
	pfs.first.val=temp;
	}
	private void findBadPoints(TreeNode root, Pre_First_Second pfs){
	if (root==null){
	return;
	}
	findBadPoints(root.left, pfs);
	if (pfs.pre!=null&& pfs.pre.val>root.val){
	if (pfs.first==null){
	pfs.first=pfs.pre;
	}
	pfs.second=root;
	}
	pfs.pre=root;
	findBadPoints(root.right, pfs);
	}
	}
	// below is old version
	class Pre_first_second{
	TreeNode first=null;
	TreeNode second=null;
	TreeNode pre=null;
	}
	public class Solution {
	public void recoverTree(TreeNode root) {
	// Start typing your Java solution below
	// DO NOT write main() function
	// ArrayList<TreeNode>pre_first_second=new ArrayList<TreeNode>(3);
	Pre_first_second pre_first_second=new Pre_first_second();
	inorder(root,pre_first_second);
	TreeNode mistakeNode1=pre_first_second.first;
	TreeNode mistakeNode2=pre_first_second.second;
	int temp=mistakeNode1.val;
	mistakeNode1.val=mistakeNode2.val;
	mistakeNode2.val=temp;
	}
	public void inorder(TreeNode root, Pre_first_second pre_first_second){
	if (root==null){
	return;
	}
	inorder(root.left, pre_first_second);
	if (pre_first_second.pre==null){
	pre_first_second.pre=root;
	}
	else{
	if (pre_first_second.pre.val>root.val){
	if(pre_first_second.first==null){
	pre_first_second.first=pre_first_second.pre;
	}
	pre_first_second.second=root;
	}
	pre_first_second.pre=root;
	}
	inorder(root.right,pre_first_second);
	}
	}

view raw Recover Binary Search Tree.java hosted with ❤ by GitHub

Unique Binary Search

	Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
	For example,
	Given n = 3, there are a total of 5 unique BST's.
	1 3 3 2 1
	\ / / / \ \
	3 2 1 1 3 2
	/ / \ \
	2 1 2 3
	/*
	"After carefully obsearve, you can find this quesiton should be solved by dp,"
	"then we create a array int[] count represent 1->n"
	"if n==0, then count[0] represent a null tree so count[0] is 1, if n=1, then only one root is possible is, so count[1]=1"
	"if n=2, then from 1->2, there should be two node, then two node could be 1root, 1 right or 1 left 1 root, so count[2]=2 "
	"Depend on this rule we can got count[3]= 0 left node*2 rigth node+2 left node * 0 right node"
	"so is n==3, so to represent 1->n, we should have three node, one root, one left, one right or two left zero right or two right"
	"zero left, the count[3]=count[0]*count[2]+count[2]*count[0]+count[1]*count[1]"
	"depndont count[3]=count[0]*count[2]+count[2]*count[0]+count[1]*count[1], we can know the rule in below code"
	*/
	public class UniqueBinarySearchTree {
	public int numTrees(int n) {
	// Start typing your Java solution below
	// DO NOT write main() function
	int[] count=new int[n+1];
	count[0]=1;
	count[1]=1;
	for(int i=2; i<=n; i++){
	for(int j=0; j<i; j++){
	count[i]+=count[j]*count[i-j-1];
	}
	}
	return count[n];
	}
	}
	// Another two Solution
	public int numTrees(int n){
	if (n<0){
	return 0;
	}
	int[] nums=new int[n+1];
	return numTrees(n, nums);
	}
	// recursive + catch
	private int numTrees(int n, int[] nums){
	if (nums[n]!=0){
	return nums[n];
	}
	if (n<=1){
	nums[0]=1;
	nums[1]=1;
	return 1;
	}
	if (n==2){
	nums[2]=2;
	return 2;
	}
	int sum=0;
	for (int i=1; i<=n; i++){
	sum+=numTrees(i-1, nums) * numTrees(n-i, nums);
	}
	nums[n]=sum;
	return nums[n];
	}
	// pure recursive
	public int numTrees(int n) {
	if (n<1){
	return 1;
	}
	if (n==1){
	return 1;
	}
	if (n==2){
	return 2;
	}
	int sum=0;
	for (int i=1; i<=n;i++){
	sum+=numTrees(i-1) * numTrees(n-i);
	}
	return sum;
	}

view raw UniqueBinarySearchTree.java hosted with ❤ by GitHub

Unique Binary Search Trees II

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Solution : Divide and Conquer

from 1-> n, for each point calculate left side trees and right side trees and then construct them together. 

	Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.
	For example,
	Given n = 3, your program should return all 5 unique BST's shown below.
	1 3 3 2 1
	\ / / / \ \
	3 2 1 1 3 2
	/ / \ \
	2 1 2 3
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; left = null; right = null; }
	* }
	*/
	public class Solution {
	public ArrayList<TreeNode> generateTrees(int n) {
	// Start typing your Java solution below
	// DO NOT write main() function
	ArrayList<TreeNode> result=generateBST(1,n);
	return result;
	}
	public ArrayList<TreeNode> generateBST(int start, int end){
	ArrayList<TreeNode> subTree=new ArrayList<TreeNode>();
	if (start>end){
	subTree.add(null);
	}
	else if (start==end){
	subTree.add(new TreeNode(start));
	}
	else{
	for (int i=start; i<=end; i++){
	// divied and conquer.
	// get collection of all left trees and right trees
	// then construct them together
	ArrayList<TreeNode> leftTree=generateBST(start, i-1);
	ArrayList<TreeNode> rightTree=generateBST(i+1, end);
	for (TreeNode leftNode:leftTree){
	for(TreeNode rightNode:rightTree){
	TreeNode root=new TreeNode(i);
	root.left=leftNode;
	root.right=rightNode;
	subTree.add(root);
	}
	}
	}
	}
	return subTree;
	}
	}

view raw Unique Binary Search Trees II.java hosted with ❤ by GitHub

Merge K Sorted List

	Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) {
	* val = x;
	* next = null;
	* }
	* }
	*/
	public class Solution {
	public ListNode mergeKLists(ArrayList<ListNode> lists) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (lists==null||lists.isEmpty()){
	return null;
	}
	Comparator<ListNode> comparator =new Comparator<ListNode>(){
	public int compare (ListNode node1, ListNode node2){
	if (node1.val>node2.val) return 1;
	else if (node1.val<node2.val) return -1;
	else return 0;
	}
	};
	PriorityQueue<ListNode> heap=new PriorityQueue<ListNode>(lists.size(),comparator);
	for (ListNode i:lists){
	if (i!=null){
	heap.add(i);
	}
	}
	ListNode head=null;
	ListNode cur=null;
	while(!heap.isEmpty()){
	ListNode newNode=heap.poll();
	if (head==null){
	head=newNode;
	cur=newNode;
	if (cur.next!=null){
	heap.add(cur.next);
	}
	}
	else{
	cur.next=newNode;
	cur=newNode;
	if(cur.next!=null){
	heap.add(cur.next);
	}
	}
	}
	return head;
	}
	}

view raw Merge k Sorted Lists.java hosted with ❤ by GitHub

Integer to Roman

	Given an integer, convert it to a roman numeral.
	Input is guaranteed to be within the range from 1 to 3999.
	I = 1;
	V = 5;
	X = 10;
	L = 50;
	C = 100;
	D = 500;
	M = 1000;
	class Solution{
	public String intToRoman(int num) {
	// Start typing your Java solution below
	// DO NOT write main() function
	int [] nums={1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4,1};
	String [] digits={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I" };
	StringBuffer sb=new StringBuffer();
	int i=0;
	while(num>0){
	int times=num/nums[i];
	num=num-nums[i]*times;
	for (; times>0; times--){
	sb.append(digits[i]);
	}
	i++;
	}
	return sb.toString();
	}
	}

view raw Integer to Roman.java hosted with ❤ by GitHub

3 Sum

	Time: O(n^2)
	Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0?
	Find all unique triplets in the array which gives the sum of zero.
	Note:
	Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ? b ? c)
	The solution set must not contain duplicate triplets.
	public class Solution {
	public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
	// Start typing your Java solution below
	// DO NOT write main() function
	ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
	if (num.length<3) return result;
	Arrays.sort(num);
	for (int i=0; i<num.length; i++){
	if (i>0){
	if (num[i]==num[i-1]){
	continue;
	}
	}
	int start=i+1;
	int end=num.length-1;
	while(start<end){
	int sum=num[i]+num[start]+num[end];
	if (sum>0){
	end--;
	}
	else if (sum<0){
	start++;
	}
	else{
	ArrayList<Integer> current=new ArrayList<Integer>();
	current.add(num[i]);
	current.add(num[start]);
	current.add(num[end]);
	result.add(current);
	do {start++;} while(start<end&&num[start]==num[start-1]);
	do {end--;} while(start<end&&num[end]==num[end+1]);
	}
	}
	}
	return result;
	}
	}

view raw 3Sum.java hosted with ❤ by GitHub

Letter Combinations of a Phone Number

	Given a digit string, return all possible letter combinations that the number could represent.
	A mapping of digit to letters (just like on the telephone buttons) is given below.
	Input:Digit string "23"
	Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
	// 2/4/2014 version
	public class LetterCombinationsOfAPhoneNumber {
	public ArrayList<String> letterCombinations(String digits) {
	ArrayList<String> result=new ArrayList<String>();
	if (digits==null){
	return result;
	}
	String[] keyboard={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
	StringBuilder current=new StringBuilder();
	int index=0;
	buildResult(digits, index, current, keyboard, result);
	return result;
	}
	private void buildResult(String digits, int index, StringBuilder current, String[] keyboard, ArrayList<String> result){
	if (index==digits.length()){
	result.add(current.toString());
	return;
	}
	int num=digits.charAt(index)-'0';
	for (int i=0; i<keyboard[num].length(); i++){
	current.append(keyboard[num].charAt(i));
	buildResult(digits, index+1, current, keyboard, result);
	current.deleteCharAt(current.length()-1);
	}
	}
	}
	public class Solution {
	private char[][] map={
	{},{},{'a','b','c'},
	{'d','e','f'},{'g','h','i'},{'j','k','l'},
	{'m','n','o'}, {'p','q','s','r'}, {'t','u','v'},
	{'w','x','y','z'}
	};
	public ArrayList<String> letterCombinations(String digits) {
	// Start typing your Java solution below
	// DO NOT write main() function
	ArrayList<String> result=new ArrayList<String>();
	StringBuffer sb=new StringBuffer();
	combine(digits,0,sb,result);
	return result;
	}
	private void combine(String digits, int i, StringBuffer sb, ArrayList<String> result){
	if (i==digits.length()){
	result.add(sb.toString());
	}
	else{
	int index=digits.charAt(i)-'0';
	int len=map[index].length;
	for (int j=0; j<len; j++){
	sb.append(map[index][j]);
	combine(digits, i+1, sb, result);
	sb.deleteCharAt(sb.length()-1);
	}
	}
	}
	}

view raw LetterCombinationsOfAPhoneNumber.java hosted with ❤ by GitHub

Swap Nodes in Pairs

	Given a linked list, swap every two adjacent nodes and return its head.
	For example,
	Given 1->2->3->4, you should return the list as 2->1->4->3.
	Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) {
	* val = x;
	* next = null;
	* }
	* }
	*/
	public class Solution {
	public ListNode swapPairs(ListNode head) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (head==null) return head;
	ListNode helper=new ListNode(0);
	helper.next=head;
	ListNode n1=helper;
	ListNode n2=head;
	while(n2!=null&& n2.next!=null){
	n1.next=n2.next;
	n2.next=n2.next.next;
	n1.next.next=n2;
	n1=n2;
	n2=n2.next;
	}
	return helper.next;
	}
	}

view raw Swap Nodes in Pairs.java hosted with ❤ by GitHub

Reverse Nodes in k-Group

	Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
	If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
	You may not alter the values in the nodes, only nodes itself may be changed.
	Only constant memory is allowed.
	For example,
	Given this linked list: 1->2->3->4->5
	For k = 2, you should return: 2->1->4->3->5
	For k = 3, you should return: 3->2->1->4->5
	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) {
	* val = x;
	* next = null;
	* }
	* }
	*/
	public class Solution {
	public ListNode reverseKGroup(ListNode head, int k) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (head ==null || k==1){
	return head;
	}
	ListNode dummy =new ListNode (0);
	dummy.next=head;
	ListNode pre=dummy;
	int i=0;
	while (head!=null){
	i++;
	if (i%k==0){
	pre=reverse(pre,head.next);
	head=pre.next;
	}
	else {
	head=head.next;
	}
	}
	return dummy.next;
	}
	/**
	* Reverse a link list between pre and next exclusively
	* an example:
	* a linked list:
	* 0->1->2->3->4->5->6
	* | |
	* pre next
	* after call pre = reverse(pre, next)
	*
	* 0->3->2->1->4->5->6
	* | |
	* pre next
	* @param pre
	* @param next
	* @return the reversed list's last node, which is the precedence of parameter next
	*/
	public ListNode reverse(ListNode pre, ListNode next){
	ListNode last=pre.next;
	ListNode cur=last.next;
	while (cur!=next){
	last.next=cur.next;
	cur.next=pre.next;
	pre.next=cur;
	cur=last.next;
	}
	return last;
	}
	}

view raw Reverse Nodes in k-Group.java hosted with ❤ by GitHub

Remove Element

	Given an array and a value, remove all instances of that value in place and return the new length.
	The order of elements can be changed. It doesn't matter what you leave beyond the new length.
	Solution1: fit for less tartget elements in array
	public class Solution {
	public int removeElement(int[] A, int elem) {
	// Start typing your Java solution below
	// DO NOT write main() function
	int len=A.length;
	for (int i=0; i<len;){
	if (A[i]==elem){
	A[i]=A[--len];
	}
	else{
	i++;
	}
	}
	return len;
	}
	}
	Solution 2: fit more elemetns in array
	class Solution {
	public int removeElement(int [] A, int elem){
	int newLen=0;
	for (int i=0; i<A.length; i++){
	if (A[i]!=elem){
	A[newLen++]=A[i];
	}
	}
	return newLen;
	}
	}

view raw Remove Element.java hosted with ❤ by GitHub

Implement strStr()

	/*
	Implement strStr().
	Returns a pointer to the first occurrence of needle in haystack,
	or null if needle is not part of haystack.
	*/
	public class StrStr {
	public String strStr(String haystack, String needle) {
	if (haystack==null||needle==null){
	return null;
	}
	if (haystack.length()==0){
	if (needle.length()==0){
	return haystack;
	}
	else{
	return null;
	}
	}
	if (needle.length()==0){
	return haystack;
	}
	if (haystack.length()<needle.length()){
	return null;
	}
	// below code is a modified version of code in /**/ below, idea from a google+ friend.
	if (i>=0){
	return haystack.substring(i);
	}
	else{
	return null;
	}
	/*
	int i=0;
	int len=haystack.length()-needle.length();
	while(i<=len){
	if (haystack.charAt(i)==needle.charAt(0)){
	if (haystack.substring(i, i+needle.length()).equals(needle)){
	return haystack.substring(i);
	}
	}
	i++;
	}
	return null;
	*/
	}
	}
	// without use substring()
	public class Solution {
	public String strStr(String haystack, String needle) {
	// Start typing your Java solution below
	// DO NOT write main() function
	assert(haystack!=null && needle!=null);
	if (needle.length()==0){
	return haystack;
	}
	int i=0;
	while (i<haystack.length()){
	if (haystack.length()-i<needle.length()){
	break;
	}
	if (haystack.charAt(i)==needle.charAt(0)){
	int j=i;
	while (j-i<needle.length()&&needle.charAt(j-i)==haystack.charAt(j)){
	j++;
	if (j-i==needle.length()){
	return haystack.substring(i);
	}
	}
	}
	i++;
	}
	return null;
	}
	}

view raw StrStr.java hosted with ❤ by GitHub

Roman To Integer

	Given a roman numeral, convert it to an integer.
	Input is guaranteed to be within the range from 1 to 3999.
	import java.util.*;
	public class Solution {
	public int romanToInt(String s) {
	// Start typing your Java solution below
	// DO NOT write main() function
	Hashtable<Character, Integer> ht=new Hashtable<Character, Integer>();
	ht.put('I',1);
	ht.put('V',5);
	ht.put('X',10);
	ht.put('L',50);
	ht.put('C',100);
	ht.put('D', 500);
	ht.put('M',1000);
	int n=s.length();
	int sum=ht.get(s.charAt(n-1));
	for(int i=n-2; i>=0; i--){
	if (ht.get(s.charAt(i+1))>ht.get(s.charAt(i))){
	sum=sum-ht.get(s.charAt(i));
	}
	else if (ht.get(s.charAt(i+1))<=ht.get(s.charAt(i))){
	sum=sum+ht.get(s.charAt(i));
	}
	}
	return sum;
	}
	}

view raw Roman to Integer.java hosted with ❤ by GitHub