Valid Parentheses ( Java + Python)

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

	/*
	Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
	The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
	*/
	public class Solution {
	public boolean isValid(String s) {
	if (s==null || s.length()==0){
	return true;
	}
	Stack<Character> checker=new Stack<Character>();
	int i=0;
	while (i<s.length()){
	if (s.charAt(i)=='(' || s.charAt(i)=='[' || s.charAt(i)=='{'){
	checker.push(s.charAt(i));
	i++;
	}
	else if (s.charAt(i)==')' || s.charAt(i)==']' || s.charAt(i)=='}'){
	if (checker.isEmpty()){
	return false;
	}
	else{
	char temp=checker.peek();
	if (isPair(temp, s.charAt(i))){
	checker.pop();
	i++;
	}
	else{
	return false;
	}
	}
	}
	else{
	return false;
	}
	}
	if (checker.isEmpty() ){
	return true;
	}
	return false;
	}
	// check is given two chars are pair
	private boolean isPair(char c1, char c2){
	String validChars="()[]{}";
	int indexC1=validChars.indexOf(c1);
	int indexC2=validChars.indexOf(c2);
	if (indexC1<0||indexC2<0){
	return false;
	}
	if (indexC1+1==indexC2){
	return true;
	}
	return false;
	}
	}

view raw ValidParentheses.java hosted with ❤ by GitHub

	"""
	Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
	The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
	"""
	# rewrite at 3/2/2014
	class Solution:
	# @return a boolean
	def isValid(self, s):
	if s==None or len(s)==0:
	return True
	stack=[]
	dict={'}':'{', ']':'[',')':'('}
	for c in s:
	if c=='(' or c=='[' or c=='{':
	stack.append(c)
	elif dict[c]:
	if len(stack)==0:
	return False
	else:
	last=stack[-1]
	if dict[c]!=last:
	return False
	else:
	stack.pop()
	else:
	return False
	return len(stack)==0

view raw ValidParentheses.py hosted with ❤ by GitHub

Longest Common Prefix (Java)

Leetcode

Write a function to find the longest common prefix string amongst an array of strings.

	/*
	Write a function to find the longest common prefix string amongst an array of strings.
	*/
	// rewrite at 2/28/2014
	public class Solution {
	public String longestCommonPrefix(String[] strs) {
	if (strs==null||strs.length==0){
	return "";
	}
	if (strs.length==1){
	return strs[0];
	}
	String str=strs[0];
	for (int i=0; i<str.length(); i++){
	char c=str.charAt(i);
	for (int j=1; j<strs.length; j++){
	if (strs[j].length()==i || strs[j].charAt(i)!=c){
	return str.substring(0, i);
	}
	}
	}
	return str;
	}
	}
	// old version
	public class Solution {
	public String longestCommonPrefix(String[] strs)
	{
	if (strs.length==0) return “”;
	int index=0;
	while (index<strs[0].length())
	{
	char c=strs[0].charAt(index);
	for (int i=1; i<strs.length;i++)
	{
	// Don’t forget to also check if index out of range of other str in strs beside strs[0]
	if (index==strs[0].length()||index==strs[i].length()||strs[i].charAt(index)!=c)
	{
	return strs[0].substring(0,index);
	}
	}
	index++;
	}
	return strs[0];
	}
	}

view raw Longest common prefix.java hosted with ❤ by GitHub

Anagrams (Java)

LeetCode

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

	/*
	Given an array of strings, return all groups of strings that are anagrams.
	Note: All inputs will be in lower-case.
	*/
	public class Solution {
	public ArrayList<String> anagrams(String[] strs) {
	ArrayList<String> result=new ArrayList<String>();
	if (strs==null||strs.length==0){
	return result;
	}
	HashMap<String,ArrayList<String>> hm=new HashMap<String, ArrayList<String>>();
	for (String s:strs){
	char[] temp=s.toCharArray();
	Arrays.sort(temp);
	String tempStr=new String(temp);
	if (hm.containsKey(tempStr)){
	hm.get(tempStr).add(s);
	}
	else{
	ArrayList<String> tempList=new ArrayList<String>();
	tempList.add(s);
	hm.put(tempStr, tempList);
	}
	}
	for (ArrayList<String> list: hm.values()){
	if (list.size()>1){
	for (String str:list){
	result.add(str);
	}
	}
	}
	return result;
	}
	}

view raw Anagrams.java hosted with ❤ by GitHub

Valid Sudoku (Java)

LeetCode

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

Solution: Helpe table

Declare 9 boolean array with length 9  separately for rows, columns and blocks and hold them in ArrayList. Because the number range of sudoku is 1-9, so each number in each row, col and block should be unique, then we can go through every position of given board, check if the number has been

Found in current row,current column  and current block. If so, return false;

*** Be careful about the index of block in blockChecker

	/*
	Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
	The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
	A partially filled sudoku which is valid.
	Note:
	A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
	*/
	public class ValidSudoku {
	public boolean isValidSudoku(char[][] board) {
	if (board==null|| board.length!=9 || board[0].length!=9){
	return false;
	}
	// initialize the Checkers
	ArrayList<boolean[]> rowChecker=new ArrayList<boolean[]>();
	ArrayList<boolean[]> colChecker=new ArrayList<boolean[]>();
	ArrayList<boolean[]> blockChecker=new ArrayList<boolean[]>();
	for (int i=0; i<9; i++){
	rowChecker.add(new boolean[9]);
	colChecker.add(new boolean[9]);
	blockChecker.add(new boolean[9]);
	}
	for (int i=0; i<9; i++){
	for (int j=0; j<9; j++){
	if (board[i][j]=='.'){
	continue;
	}
	// current value, there should be a positin represented of c at each checkers
	// pay attention to the indice of block checker
	int c= board[i][j]-'1' ;
	if (rowChecker.get(j)[c]==true || colChecker.get(i)[c]==true || blockChecker.get(i/3*3+j/3)[c]==true){
	return false;
	}
	else{
	rowChecker.get(j)[c]=true;
	colChecker.get(i)[c]=true;
	blockChecker.get(i/3*3+j/3)[c]=true;
	}
	}
	}
	return true;
	}
	}

view raw ValidSudoku.java hosted with ❤ by GitHub

Path Sum II (Java)

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

Solution:  DFS

Apply DFS check every possible combination, record result if meet requirement

	Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
	For example:
	Given the below binary tree and sum = 22,
	5
	/ \
	4 8
	/ / \
	11 13 4
	/ \ / \
	7 2 5 1
	return
	[
	[5,4,11,2],
	[5,8,4,5]
	]
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	// code rewrite 2/21
	public class Solution {
	public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
	ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
	if (root==null){
	return result;
	}
	ArrayList<Integer> current=new ArrayList<Integer>();
	buildResult(root, sum, current, result);
	return result;
	}
	private void buildResult(TreeNode root,int sum, ArrayList<Integer> current, ArrayList<ArrayList<Integer>> result){
	if (root==null){
	return;
	}
	int currentVal=root.val;
	current.add(currentVal);
	if (root.left==null && root.right==null){
	if (sum-currentVal==0){
	ArrayList<Integer> temp=new ArrayList<Integer> (current);
	result.add(temp);
	}
	}
	buildResult(root.left, sum-currentVal, current, result);
	buildResult(root.right, sum-currentVal, current, result);
	current.remove(current.size()-1);
	}
	}
	public class Solution {
	public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
	// Start typing your Java solution below
	// DO NOT write main() function
	ArrayList <Integer> current=new ArrayList<Integer>();
	ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
	pathSumHelper(root, sum, current, result);
	return result;
	}
	public void pathSumHelper
	(TreeNode root, int sum, ArrayList<Integer> current, ArrayList<ArrayList<Integer>> result)
	{
	if (root==null){
	return;
	}
	current.add(root.val);
	int current_sum=sum-root.val;
	if (current_sum==0&& root.left==null && root.right==null){
	ArrayList<Integer> temp=new ArrayList<Integer>();
	for(int i:current){
	temp.add(i);
	}
	result.add(temp);
	}
	pathSumHelper(root.left, current_sum, current, result);
	pathSumHelper(root.right, current_sum, current, result);
	current.remove(current.size()-1);
	}
	}

view raw Path Sum II.java hosted with ❤ by GitHub

Subsets (Java)

Leetcode

Given a set of distinct integers, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Solution: DFS

For  subset of a given set, it must contain a [],
So we can initialize a result with [[]] as start point.  For example, given set [1,2,3]
We can build the result from [[]]-> [[],[1]]->[[],[1],[2],[1,2]]->[[],[1],[2], [1,2], [3], [1,3], [2,3], [1, 2,3]]

	/*
	Given a set of distinct integers, S, return all possible subsets.
	Note:
	Elements in a subset must be in non-descending order.
	The solution set must not contain duplicate subsets.
	For example,
	If S = [1,2,3], a solution is:
	[
	[3],
	[1],
	[2],
	[1,2,3],
	[1,3],
	[2,3],
	[1,2],
	[]
	]
	*/
	public class Solution {
	public ArrayList<ArrayList<Integer>> subsets(int[] S) {
	ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
	if (S==null|| S.length==0){
	return result;
	}
	Arrays.sort(S);
	// start point to build all the subsets
	ArrayList<Integer> temp=new ArrayList<Integer>();
	result.add(temp);
	for (int i=0; i<S.length; i++){
	insert(S[i], result);
	}
	return result;
	}
	private void insert(int i, ArrayList<ArrayList<Integer>> result){
	ArrayList<ArrayList<Integer>> tempResult=new ArrayList<ArrayList<Integer>> ();
	for (ArrayList<Integer> current: result){
	ArrayList<Integer> temp=new ArrayList<Integer> (current);
	temp.add(i);
	tempResult.add(temp);
	}
	result.addAll(tempResult);
	}
	}

view raw Subsets.java hosted with ❤ by GitHub

Jump Game (Java)

Leetcode

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

	/*
	Given an array of non-negative integers, you are initially positioned at the first index of the array.
	Each element in the array represents your maximum jump length at that position.
	Determine if you are able to reach the last index.
	For example:
	A = [2,3,1,1,4], return true.
	A = [3,2,1,0,4], return false.
	*/
	// DP Solution: use int[] checker to record the max length current position can reach, if the length
	// passed the length of given array return true
	public class Solution {
	public boolean canJump(int[] A) {
	if (A==null||A.length==0){
	return false;
	}
	if (A.length==1){
	return true;
	}
	int[] checker=new int[A.length];
	checker[0]=A[0];
	for (int i=1; i<checker.length; i++){
	if (i<=checker[i-1]){
	checker[i]=Math.max(A[i]+i, checker[i-1]);
	if (checker[i]>=A.length-1){
	return true;
	}
	}
	else{
	// if current i can not be reach by previous jump then return false
	return false;
	}
	}
	return true;
	}
	}
	This greedy solution below failed at test case {2,4,2,1,0,4}, there should be more test cases make
	this solution fail but for some reason this solution can pass OJ.
	Thank you very much for Guangsen Wang point it out!
	// Greedy ALgorithm solution
	// depend on the question description, the num in the given array are non-negative number
	// so we can keep jump until to the end of the array if the num is not 0
	/*
	public class Solution {
	public boolean canJump(int[] A) {
	if (A==null ||A.length==0){
	return false;
	}
	int current=0;
	while (current<A.length){
	if (current==A.length-1){
	return true;
	}
	if (A[current]==0){
	return false;
	}
	current+=A[current];
	}
	return true;
	}
	}
	*/

view raw JumpGame.java hosted with ❤ by GitHub

3Sum Closest (Java)

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

	Given an array S of n integers, find three integers in S such that the sum is closest to a given number,
	target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
	For example, given array S = {-1 2 1 -4}, and target = 1.
	The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
	// 2/18/2014 code rewrite
	public class Solution {
	public int threeSumClosest(int[] num, int target) {
	if (num==null||num.length==0){
	return -1;
	}
	int result=0;
	int minDif=Integer.MAX_VALUE;
	Arrays.sort(num);
	for (int i=0; i<num.length-2; i++ ){
	int first=num[i];
	int left=i+1;
	int right=num.length-1;
	while (left<right){
	int value=first+num[left]+num[right];
	if (value==target){
	return value;
	}
	int diff=Math.abs(value-target);
	if (diff<minDif){
	result=value;
	minDif=diff;
	}
	if (value>target){
	do {right--;} while(left<right && num[right]==num[right+1]);
	}
	else if (value<target){
	do {left++;} while (left<right && num[left]==num[left-1]);
	}
	}
	}
	return result;
	}
	}
	public class Solution {
	public int threeSumClosest(int[] num, int target) {
	// Start typing your Java solution below
	// DO NOT write main() function
	Arrays.sort(num);
	int min=Integer.MAX_VALUE;
	int result=0;
	for (int i=0; i<num.length; i++){
	if (i>0&&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>target){
	int diff=sum-target;
	if (diff<min){
	min=diff;
	result=sum;
	}
	do {end--;} while(start<end && num[end]==num[end+1]);
	}
	else if (sum<target){
	int diff=target-sum;
	if (diff<min){
	min=diff;
	result=sum;
	}
	do {start++;} while(start<end&& num[start]==num[start-1]);
	}
	else{
	min=0;
	result=sum;
	break;
	}
	}
	}
	return result;
	}
	}

view raw 3 Sum Closest .java hosted with ❤ by GitHub

Convert Sorted List to Binary Search Tree (Java)

Given a singly linked list where elements are sorted in ascending order, convert it to a height 

balanced BST.

Solution:

Provide two solutions below.  One is relatively simple to come out which just convert the LinkedList to
 array then Convert the array to BST. But this solution may not be the one Interviewer wants.

The second one  performs the conversion in place, apply the feature of linked list  we can build the tree
from  bottom to up. Meanwhile use start and end two value to indicate the bounds

	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) { val = x; next = null; }
	* }
	*/
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	"build tree from bottom to up, use start and end indicate the bound"
	public class Solution {
	public TreeNode sortedListToBST(ListNode head) {
	if (head==null) {
	return null;
	}
	ListNode temp=head;
	int start=0;
	int end=0;
	while (temp.next!=null){
	temp=temp.next;
	end++;
	}
	// java is pass by value, so inorder to memory the move of the head
	// you have to put the head into a array or other warpper class
	ListNode[] headHolder={head};
	return buildTree(headHolder,start, end );
	}
	private TreeNode buildTree(ListNode[] headHolder, int start, int end){
	if (start>end){
	return null;
	}
	int mid=(start+end)/2;
	TreeNode left=buildTree(headHolder, start, mid-1);
	TreeNode root=new TreeNode (headHolder[0].val);
	// current node in ListNode has been used, move it one step to the right
	headHolder[0]=headHolder[0].next;
	root.left=left;
	TreeNode right=buildTree (headHolder, mid+1, end);
	root.right=right;
	return root;
	}
	}
	// "convert list to array first, then just convert the array to BST recursively"
	public class Solution {
	public TreeNode sortedListToBST(ListNode head) {
	// Start typing your Java solution below
	// DO NOT write main() function
	int size=0;
	ListNode temp=head;
	while(temp!=null){
	size++;
	temp=temp.next;
	}
	int [] num=new int[size];
	temp=head;
	int i=0;
	while(temp!=null){
	num[i++]=temp.val;
	temp=temp.next;
	}
	return arrayToBST(num, 0, num.length-1);
	}
	public TreeNode arrayToBST(int[] num, int start, int end){
	if (start>end) return null;
	int mid=(start+end)/2;
	TreeNode parent=new TreeNode(num[mid]);
	parent.left=arrayToBST(num, start, mid-1);
	parent.right=arrayToBST(num, mid+1, end);
	return parent;
	}
	}

view raw convert sorted list to BST.java hosted with ❤ by GitHub

Search for a Range (Java)

Leetcode

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

Solution: because of O(logn), so we should consider about binary search, so how to apply binary search to find the low bound and high bound? We can make target -0.5 for searching low bound and target+0. 5 for the high bound. Be careful the corner case

	Given a sorted array of integers, find the starting and ending position of a given target value.
	Your algorithm's runtime complexity must be in the order of O(log n).
	If the target is not found in the array, return [-1, -1].
	For example,
	Given [5, 7, 7, 8, 8, 10] and target value 8,
	return [3, 4].
	Time complexity: O(logn)
	public class Solution {
	public int[] searchRange(int[] A, int target) {
	if (A==null) return null;
	int[] result={-1,-1};
	int low=binarySearch(A,target-0.5);
	// Be care for there , low>=A.length must be check first or
	// there may be a out of boundary exception cause
	// the binarySearch function in this question return low instead of null
	// if the target are not in the array
	if (low>=A.length||A[low]!=target){
	return result;
	}
	result[0]=low;
	result[1]=binarySearch(A,target+0.5)-1;
	return result;
	}
	public int binarySearch(int[] A, double t){
	int low = 0, high = A.length - 1;
	while(low <= high){
	int m = (low + high) / 2;
	if(A[m] == t) return m;
	if(A[m] > t) high = m - 1;
	else low = m + 1;
	}
	return low;
	}
	}

view raw Search for a Range.java hosted with ❤ by GitHub

Flatten Binary Tree to Linked List (Java)

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Solution:

Divide and Conquer, convert left and right tree to list separately, then connect root. right to list converted by left tree, make root. left to null, then search for the lastNode of right tree and connect it to list converted by original right tree.

	Flatten Binary Tree to Linked List
	Given a binary tree, flatten it to a linked list in-place.
	For example,
	Given
	1
	/ \
	2 5
	/ \ \
	3 4 6
	The flattened tree should look like:
	1
	\
	2
	\
	3
	\
	4
	\
	5
	\
	6
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	// rewrite at 2/8
	public class FlattenBinaryTreeToLinked {
	public void flatten(TreeNode root) {
	if (root==null){
	return;
	}
	covertToList(root);
	}
	private TreeNode covertToList(TreeNode root){
	if (root==null){
	return root;
	}
	// convert right tree to list
	TreeNode tempRight=covertToList(root.right);
	// convert left tree to list and connect it to right of root
	root.right=covertToList(root.left);
	// make left side to null;
	root.left=null;
	TreeNode tempRoot=root;
	// find the right most node which used to connect list coverted by original right tree
	while (tempRoot.right!=null){
	tempRoot=tempRoot.right;
	}
	tempRoot.right=tempRight;
	return root;
	}
	}
	// old version
	public class Solution {
	public void flatten(TreeNode root) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (root==null||(root.left==null&&root.right==null)){
	return ;
	}
	else{
	if (root.left!=null){
	TreeNode temp=root.right;
	root.right=root.left;
	TreeNode rightMost=findRightMost(root.right);
	rightMost.right=temp;
	root.left=null;
	flatten(root.right);
	}
	else{
	flatten(root.right);
	}
	}
	}
	public TreeNode findRightMost(TreeNode root){
	if (root.right!=null){
	return findRightMost(root.right);
	}
	else{
	return root;
	}
	}
	}

view raw FlattenBinaryTreeToLinked List.java hosted with ❤ by GitHub

Count and Say (Java)

Leetcode

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

	The count-and-say sequence is the sequence of integers beginning as follows:
	1, 11, 21, 1211, 111221, ...
	1 is read off as "one 1" or 11.
	11 is read off as "two 1s" or 21.
	21 is read off as "one 2, then one 1" or 1211.
	Given an integer n, generate the nth sequence.
	Note: The sequence of integers will be represented as a string.
	// 2/8/2014 rewrite, interative version
	public class CountAndSay {
	public String countAndSay(int n) {
	if (n<1){
	return null;
	}
	int i=2;
	String current="1";
	while (i<=n){
	current=say(current);
	i++;
	}
	return current;
	}
	// count each char in given input string
	private String say(String input){
	char last=input.charAt(0);
	String result="";
	int i=1;// index
	int count=1;// count for each char
	while (i<input.length()){
	if (input.charAt(i)==last){
	count++;
	}
	else{
	result+=count;
	result+=last;
	last=input.charAt(i);
	count=1;
	}
	i++;
	}
	result+=count;
	result+=last;
	return result;
	}
	}
	// below is recursive version
	Time Complexity O(n^2)
	public class Solution {
	public String countAndSay(int n) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (n<=1){
	return String.valueOf(1);
	}
	else{
	return say(countAndSay(n-1));
	}
	}
	private String say(String s){
	int i=0;
	int count=1;
	StringBuffer sb=new StringBuffer();
	while(i<s.length()){
	int j=i+1;
	while(j<s.length()&&s.charAt(j)==s.charAt(i)){
	count++;
	j++;
	}
	sb.append(count);
	sb.append(s.charAt(i));
	i=j;
	count=1;
	}
	return sb.toString();
	}
	}

view raw CountAndSay.java hosted with ❤ by GitHub

Binary Tree Zigzag Level Order Traversal (Java)

LeetCode

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

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

	"Time Complexity is O(n)"
	"Take advantage of two stack"
	"one is used hold current level's node another is used to hold next level's hold,"
	"moreover there is flag used to mark the sequece (left to rigth or right to left)"
	"put the root first into curretn stack then pop it out, put left and right into next_level stack (pay attention to sequence)"
	"once current stack is empty swap current and next level, level ++, reverse sequence"
	// rewrite at 2/7/2014
	public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
	ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>> ();
	if (root==null ){
	return result;
	}
	boolean leftToRight=true;
	Stack<TreeNode> current=new Stack<TreeNode>();
	Stack<TreeNode> next=new Stack<TreeNode>();
	current.push(root);
	int level=0;
	while (!current.isEmpty()){
	if (result.size()==level){
	ArrayList<Integer> temp=new ArrayList<Integer>();
	result.add(temp);
	}
	TreeNode currentNode=current.pop();
	result.get(level).add(currentNode.val);
	if (leftToRight){
	if (currentNode.left!=null) next.push(currentNode.left);
	if (currentNode.right!=null) next.push(currentNode.right);
	}
	else{
	if (currentNode.right!=null) next.push(currentNode.right);
	if (currentNode.left!=null) next.push(currentNode.left);
	}
	// current level is empty, swap current level and next level
	// reverse boolean leftToRight
	// level++;
	if (current.isEmpty()){
	level++;
	leftToRight=!leftToRight;
	Stack<TreeNode> temp=current;
	current=next;
	next=temp;
	}
	}
	return result;
	}
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	import java.util.*;
	public class Solution {
	public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
	// Start typing your Java solution below
	// DO NOT write main() function
	ArrayList<ArrayList<Integer>> result= new ArrayList<ArrayList<Integer>>();
	Stack<TreeNode> current_level =new Stack<TreeNode> ();
	Stack<TreeNode> next_level=new Stack<TreeNode>();
	boolean leftToright=false;
	int level=0;
	if (root!=null){
	current_level.push(root);
	while(!current_level.isEmpty()){
	TreeNode current=current_level.pop();
	addToarraylist(result, current.val,level);
	if (leftToright){
	if (current.right!=null){
	next_level.push(current.right);
	}
	if (current.left!=null){
	next_level.push(current.left);
	}
	}
	else{
	if (current.left!=null){
	next_level.push(current.left);
	}
	if (current.right!=null){
	next_level.push(current.right);
	}
	}
	if (current_level.isEmpty()){
	Stack<TreeNode> temp=current_level;
	current_level=next_level;
	next_level=temp;
	level++;
	leftToright=!leftToright;
	}
	}
	}
	return result;
	}
	public void addToarraylist(ArrayList<ArrayList<Integer>> result,int value, int level){
	if (level==result.size()){
	ArrayList<Integer> temp=new ArrayList<Integer>();
	temp.add(value);
	result.add(temp);
	}
	else{
	ArrayList<Integer> temp=result.get(level);
	temp.add(value);
	}
	}
	}

view raw BinaryTreeZigzagLevelOrderTraversal.java hosted with ❤ by GitHub

Combination Sum

LeetCode

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7, 
A solution set is: 
[7] 
[2, 2, 3] 

Solution: DFS

calculate each possible combination

	/*
	Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
	The same repeated number may be chosen from C unlimited number of times.
	Note:
	All numbers (including target) will be positive integers.
	Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
	The solution set must not contain duplicate combinations.
	For example, given candidate set 2,3,6,7 and target 7,
	A solution set is:
	[7]
	[2, 2, 3]
	*/
	public class CombinationSum {
	public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
	ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
	if (candidates==null || candidates.length==0|| target<0){
	return result;
	}
	Arrays.sort(candidates);
	int start=0;
	ArrayList<Integer> current=new ArrayList<Integer>();
	buildResult(candidates, start, current, target, result);
	return result;
	}
	private void buildResult(int[] candidates, int start, ArrayList<Integer> current, int target, ArrayList<ArrayList<Integer>> result){
	if (target==0){
	ArrayList<Integer> temp=new ArrayList<Integer>(current);
	result.add(temp);
	return;
	}
	for (int i=start; i<candidates.length; i++){
	if (target-candidates[i]<0){
	return;
	}
	current.add(candidates[i]);
	buildResult(candidates, i,current, target-candidates[i], result );
	current.remove(current.size()-1);
	}
	}
	}

view raw CombinationSum.java hosted with ❤ by GitHub

Partition List (Java)

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

	/*
	Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
	You should preserve the original relative order of the nodes in each of the two partitions.
	For example,
	Given 1->4->3->2->5->2 and x = 3,
	return 1->2->2->4->3->5.
	*/
	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) {
	* val = x;
	* next = null;
	* }
	* }
	*/
	public class PartitionList {
	public ListNode partition(ListNode head, int x) {
	if (head==null || head.next==null){
	return head;
	}
	// leftSide
	ListNode preLeftHead=new ListNode (-1);
	ListNode leftEnd=preLeftHead;
	// rightSide
	ListNode preRightHead=new ListNode(-1);
	ListNode rightEnd=preRightHead;
	ListNode run=head;
	while (run!=null){
	ListNode temp=run.next;
	if (run.val<x){
	leftEnd.next=run;
	leftEnd=leftEnd.next;
	}
	else{
	rightEnd.next=run;
	rightEnd=rightEnd.next;
	}
	run.next=null;
	run=temp;
	}
	// connect left and right
	leftEnd.next=preRightHead.next;
	return preLeftHead.next;
	}
	}

view raw PartitionList.java hosted with ❤ by GitHub

Triangle (Java)

LeetCode

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Solution: DP (met during Amazon interview)

Declare pathSum array with length of triangle size(). For triangle, the bottom row length is equal to the height of triangle, so use pathSum to hold the bottom row's value, then from bottom to up, find minimum path

	/*
	Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
	For example, given the following triangle
	[
	[2],
	[3,4],
	[6,5,7],
	[4,1,8,3]
	]
	The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
	Note:
	Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
	*/
	public class Solution {
	public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
	if (triangle==null|| triangle.size()==0){
	return 0;
	}
	// declare an int[] pathSum with length of triangle.size(), witch used to record the current path sum from bottom to up
	int[] pathSum=new int[triangle.size()];
	// calculate minimum path sum from bottom to up
	int rowNum=triangle.size();
	for (int row=rowNum-1; row>=0; row--){
	int colNum=triangle.get(row).size();
	for (int col=0; col<colNum; col++){
	if (row==rowNum-1){
	// from bottom to up, current is bottom level
	pathSum[col]=triangle.get(row).get(col);
	}
	else{
	// if not bottom level, so from previous level wich are store in pathSum find smaller value can access current point,
	//then update it
	pathSum[col]=Math.min(pathSum[col], pathSum[col+1])+triangle.get(row).get(col);
	}
	}
	}
	// right no, the pathSum[0] contains the minimum path sum
	return pathSum[0];
	}
	}

view raw Triangle.java hosted with ❤ by GitHub

Pow(x, n) (Java)

LeetCode:

Implement pow(x, n).

Solution: Binary Search

	This is a simple question, however the format is very important
	x^n={
	x^n= 1.0 if n==0,
	x^(n/2)* x^(n/2) if n!=0 and n is even,
	x^|n/2| * x^|n/2| * x if n>0 and n is odd,
	x^|n/2| * x^|n/2| * x^-1 if n<0 and n is odd,
	}
	Once it got this formula, then, the code become relatively easy.
	the time complexity is O(lgn) hint: (half=pow(x,n/2))
	public class Solution {
	public double pow(double x, int n) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	// n is even , then x^n=x^n/2*x^n/2
	// n>0 and n is odd, x^n=x^n/2 * x^n/2 *x
	// n<0 and n is odd, x^n=x^n/2 *x^n/2 *x^-1
	if (n==0) {
	return 1.0;
	}
	double half=pow(x, n/2);
	if (n%2==0){
	return half*half;
	}
	else if (n>0){
	return half*half*x;
	}
	else {
	return half*half* (1/x);
	}
	}
	}

view raw power(x, n).java hosted with ❤ by GitHub

N-Queens (Java)

Leetcode

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Slution: DFS

	/*
	The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
	Given an integer n, return all distinct solutions to the n-queens puzzle.
	Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
	For example,
	There exist two distinct solutions to the 4-queens puzzle:
	[
	[".Q..", // Solution 1
	"...Q",
	"Q...",
	"..Q."],
	["..Q.", // Solution 2
	"Q...",
	"...Q",
	".Q.."]
	]
	*/
	public class Solution {
	public ArrayList<String[]> solveNQueens(int n) {
	ArrayList<String[]> result=new ArrayList<String[]> ();
	if (n<1){
	return result;
	}
	String[] rows=new String[n];
	int row=0;
	solutions(row, n, rows, result);
	return result;
	}
	// DFS soluve question
	private void solutions(int stRow, int n,String[] rows, ArrayList<String[]> result ){
	if (stRow>=n){
	result.add(rows.clone());
	return;
	}
	for(int col=0; col<n; col++){
	if (!isValid(col, stRow, rows)){
	continue;
	}
	char[] chars=new char[n];
	Arrays.fill(chars, '.');
	chars[col]='Q';
	rows[stRow]=String.copyValueOf(chars);
	solutions(stRow+1, n, rows, result);
	}
	}
	// check if current col has conflit with previous Q
	private boolean isValid(int col,int stRow, String[] rows){
	// checkColumn
	for (int i=0; i<stRow; i++){
	int qCol=rows[i].indexOf("Q");
	if (qCol==col){
	return false;
	}
	int rowDistance=Math.abs(stRow-i);
	int colDistance=Math.abs(col-qCol);
	if (rowDistance==colDistance){
	return false;
	}
	}
	return true;
	}
	}

view raw N-Queens.java hosted with ❤ by GitHub

Insertion Sort List (Java)

LeetCode

Sort a linked list using insertion sort.

	/*
	Sort a linked list using insertion sort.
	*/
	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) {
	* val = x;
	* next = null;
	* }
	* }
	*/
	public class InsertionSortList {
	public ListNode insertionSortList(ListNode head) {
	if (head==null ||head.next==null){
	return head;
	}
	ListNode preHead=new ListNode (-1);
	preHead.next=head;
	ListNode run=head;
	while (run!=null && run.next!=null){
	if (run.val>run.next.val){
	// find node which is not in order
	ListNode smallNode=run.next;
	ListNode pre=preHead;
	// find position for smallNode
	while (pre.next.val<smallNode.val){
	pre=pre.next;
	}
	ListNode temp=pre.next;
	pre.next=smallNode;
	run.next=smallNode.next;
	smallNode.next=temp;
	}
	else{
	// node is in order
	run=run.next;
	}
	}
	return preHead.next;
	}
	}

view raw InsertionSortList.java hosted with ❤ by GitHub

Add Binary (Java)

LeetCode

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

	/*
	Given two binary strings, return their sum (also a binary string).
	For example,
	a = "11"
	b = "1"
	Return "100".
	*/
	public class AddBinary {
	public String addBinary(String a, String b) {
	if (a==null ||a.length()==0){
	return b;
	}
	if (b==null || b.length()==0){
	return a;
	}
	StringBuilder sb=new StringBuilder();
	int lastA=a.length()-1;
	int lastB=b.length()-1;
	int carry=0;
	while (lastA>=0 ||lastB>=0 ||carry>0){
	int num1=lastA>=0?a.charAt(lastA--)-'0':0;
	int num2=lastB>=0?b.charAt(lastB--)-'0':0;
	int current=(num1+num2+carry)%2;
	carry=(num1+num2+carry)/2;
	sb.insert(0, current);
	}
	return sb.toString();
	}
	}

view raw AddBinary.java hosted with ❤ by GitHub

Letter Combinations of a Phone Number (Java)

Leetcode

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"].

Solution: DFS, Helper table

	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

Construct Binary Tree from Inorder and Postorder Traversal (Java)

LeetCode

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

	//2/4/2014 rewrite code
	public class Solution {
	public TreeNode buildTree(int[] inorder, int[] postorder) {
	if (inorder==null||inorder.length==0||postorder==null ||postorder.length==0){
	return null;
	}
	int iSt=0;
	int iEd=inorder.length-1;
	int pSt=0;
	int pEd=postorder.length-1;
	return buildTree(inorder, iSt, iEd, postorder, pSt, pEd);
	}
	private TreeNode buildTree(int[] inorder, int iSt, int iEd, int[] postorder, int pSt, int pEd){
	if (iSt>iEd || pSt>pEd){
	return null;
	}
	TreeNode root=new TreeNode (postorder[pEd]);
	int index=0;
	for (int i=iSt; i<=iEd; i++){
	if (inorder[i]==root.val){
	index=i;
	break;
	}
	}
	int len=index-iSt;
	root.left=buildTree(inorder, iSt, index-1, postorder, pSt, pSt+len-1);
	root.right=buildTree(inorder, index+1, iEd, postorder, pSt+len-1+1, pEd-1);
	return root;
	}
	}
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	public class Solution {
	public TreeNode buildTree(int[] inorder, int[] postorder) {
	// Start typing your Java solution below
	// DO NOT write main() function
	int inorder_start=0;
	int inorder_end=inorder.length-1;
	int postorder_start=0;
	int postorder_end=postorder.length-1;
	return buildTree(inorder, inorder_start, inorder_end,
	postorder, postorder_start, postorder_end
	);
	}
	public TreeNode buildTree(int[] inorder, int inorder_start, int inorder_end,int[] postorder, int postorder_start, int postorder_end)
	{
	if (inorder_start>inorder_end||postorder_start>postorder_end){
	return null;
	}
	int rootVal=postorder[postorder_end];
	TreeNode root= new TreeNode(rootVal);
	for (int i=inorder_start; i<=inorder_end; i++){
	if (inorder[i]==rootVal){
	TreeNode left=buildTree(inorder, inorder_start, i-1,
	postorder, postorder_start,
	postorder_start+i-inorder_start-1);"Memoried the boundary case"
	TreeNode right=buildTree(inorder, i+1, inorder_end,
	postorder, postorder_end-inorder_end+i,postorder_end-1);"memoried the boundary case"
	root.left=left;
	root.right=right;
	}
	}
	return root;
	}
	}

view raw ConstructBinaryTreeFromInorderArrayAndPostorderArray.java hosted with ❤ by GitHub

Validate Binary Search Tree (Java)

LeetCode

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

	/*
	Given a binary tree, determine if it is a valid binary search tree (BST).
	Assume a BST is defined as follows:
	The left subtree of a node contains only nodes with keys less than the node's key.
	The right subtree of a node contains only nodes with keys greater than the node's key.
	Both the left and right subtrees must also be binary search trees.
	*/
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	public class ValidateBinarySearchTree {
	public boolean isValidBST(TreeNode root) {
	if (root==null){
	return true;
	}
	return check(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
	}
	private boolean check(TreeNode root, int left, int right){
	if (root==null){
	return true;
	}
	if (root.val<=left ||root.val>=right){
	return false;
	}
	return check(root.left, left, root.val) && check(root.right, root.val, right);
	}
	}
	public class ValidateBinarySearchTree {
	public boolean isValidBST(TreeNode root) {
	if (root==null){
	return true;
	}
	int[] pre={Integer.MIN_VALUE};
	return check(root, pre);
	}
	private boolean check(TreeNode root, int[] pre){
	if (root==null){
	return true;
	}
	if (!check(root.left, pre)){
	return false;
	}
	if (pre[0]>=root.val){
	return false;
	}
	else{
	pre[0]=root.val;
	}
	if (!check(root.right, pre)){
	return false;
	}
	return true;
	}
	}

view raw ValidateBinarySearchTree .java hosted with ❤ by GitHub

Construct Binary Tree from Preorder and Inorder Traversal (Java)

LeetCode

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Solution: Divide and Conquer

According to the rule of preorder traversal,  the first item in the preorder array must be the root. and the question also told us "You may assume that duplicates do not exist in the tree." so we can go through inorder array find the root's position, then  we got left tree and right tree. finally we can apply recursion to got the tree we want base on above logic.

	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	public class Solution {
	public TreeNode buildTree(int[] preorder, int[] inorder) {
	if (preorder==null||preorder.length==0|| inorder==null ||inorder.length==0){
	return null;
	}
	int pSt=0;
	int pEd=preorder.length-1;
	int iSt=0;
	int iEd=inorder.length-1;
	return buildTree(preorder, pSt, pEd, inorder, iSt, iEd);
	}
	private TreeNode buildTree(int[] preorder, int pSt, int pEd, int[] inorder, int iSt, int iEd){
	if (pSt>pEd || iSt>iEd){
	return null;
	}
	TreeNode root=new TreeNode (preorder[pSt]);
	int index=0;
	for (int i=iSt; i<=iEd; i++){
	if (inorder[i]==root.val){
	index=i;
	break;
	}
	}
	// length of left tree
	int len=index-iSt;
	// pay attention to bounds of preorder and inorder
	root.left=buildTree(preorder, pSt+1, pSt+1+len-1, inorder, iSt, index-1);
	root.right=buildTree(preorder, pSt+1+len-1+1, pEd, inorder, index+1, iEd);
	return root;
	}
	}

view raw ConstructBinaryTreeFromInorderArrayAndPreorderArray.java hosted with ❤ by GitHub

Reverse Linked List II (Java)

LeetCode

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

	/*
	Reverse a linked list from position m to n. Do it in-place and in one-pass.
	For example:
	Given 1->2->3->4->5->NULL, m = 2 and n = 4,
	return 1->4->3->2->5->NULL.
	Note:
	Given m, n satisfy the following condition:
	1 ≤ m ≤ n ≤ length of list.
	*/
	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) {
	* val = x;
	* next = null;
	* }
	* }
	*/
	public class Solution {
	public ListNode reverseBetween(ListNode head, int m, int n) {
	if (head==null || head.next==null){
	return head;
	}
	ListNode preHead=new ListNode(0);
	preHead.next=head;
	ListNode pre=preHead;
	ListNode current=head;
	ListNode end=head;
	int countM=1;
	int countN=1;
	// find M point and N point
	while (countM<m || countN<n ){
	if (countM<m){
	pre=pre.next;
	current=current.next;
	countM++;
	}
	if (countN<n){
	end=end.next;
	countN++;
	}
	}
	// reverse from M point to N Point
	reverse(pre, end.next);
	return preHead.next;
	}
	private void reverse(ListNode pre, ListNode endNext){
	ListNode cur=pre.next;
	while (cur.next!=endNext){
	ListNode next=cur.next;
	ListNode temp=pre.next;
	pre.next=next;
	cur.next=next.next;
	next.next=temp;
	}
	}
	}

view raw ReverseLinkedListII.java hosted with ❤ by GitHub

Next Permutation (Java)

LeetCode

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1




	Implement next permutation, which rearranges numbers into the lexicographically
	next greater permutation of numbers.If such arrangement is not possible, it must
	rearrange it as the lowest possible order (ie, sorted in ascending order).
	The replacement must be in-place, do not allocate extra memory.
	Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
	1,2,3 → 1,3,2
	3,2,1 → 1,2,3
	1,1,5 → 1,5,1
	Time complexity n+n+logn-> O(n);
	public class Solution {
	public void nextPermutation(int[] num) {
	for (int i=num.length-1; i>0; i--){
	if (num[i]>num[i-1]){
	reverse(num, i, num.length-1);
	// can use normal back to front scan replace bsearch, not slow so much, but bsearch is better
	int j=bSearch(num, num[i-1]+0.5, i,num.length-1);
	int temp=num[j];
	num[j]=num[i-1];
	num[i-1]=temp;
	return;
	}
	}
	Arrays.sort(num);
	}
	private int bSearch(int[] num, double target,int start, int end ){
	while (start<=end){
	int mid=(start+end)/2;
	if (num[mid]==target)
	{
	return mid;
	}
	else if (num[mid]>target){
	end=mid-1;
	}
	else{
	start=mid+1;
	}
	}
	return start;
	}
	private void reverse(int[] num, int start, int end){
	while (start<end){
	int temp=num[start];
	num[start]=num[end];
	num[end]=temp;
	start++;
	end--;
	}
	}
	}

view raw Next Permutation.java hosted with ❤ by GitHub

Permutations II (Java)

LeetCode

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

	Given a collection of numbers that might contain duplicates, return all possible unique permutations.
	For example,
	[1,1,2] have the following unique permutations:
	[1,1,2], [1,2,1], and [2,1,1].
	Time complexity O(n!);
	import java.util.*;
	public class PermutationII {
	public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (num==null){
	return null;
	}
	ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
	if (num.length==0){
	return result;
	}
	// Hashtable<ArrayList<Integer>, Boolean> ht=new Hashtable<ArrayList<Integer>, Boolean>();
	ArrayList<Integer> temp=new ArrayList<Integer>();
	temp.add(num[0]);
	result.add(temp);
	for (int i=1; i<num.length; i++){
	result=insert(num[i], result);
	}
	return result;
	}
	private ArrayList<ArrayList<Integer>> insert(int i, ArrayList<ArrayList<Integer>> result){
	ArrayList<ArrayList<Integer>> newResult=new ArrayList<ArrayList<Integer>>();
	Hashtable<ArrayList<Integer>, Boolean> ht=new Hashtable<ArrayList<Integer>, Boolean>();
	for (ArrayList<Integer> current: result){
	for (int j=0; j<=current.size(); j++){
	ArrayList<Integer> temp=new ArrayList<Integer>();
	temp.addAll(current);
	temp.add(j, i);
	if (!ht.containsKey(temp)){
	newResult.add(temp);
	ht.put(temp, true);
	}
	}
	}
	return newResult;
	}
	}

view raw PermutationII.java hosted with ❤ by GitHub

Best Time to Buy and Sell Stock III (Java)

LeetCode

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution: Divide and Conquer, DP

O(n^2) solution is easy came out, we can use O(n) time to get max profit depend on the solution of Best Time to Buy and Sell Stock I. so we can just dived the whole prices array at every point , try to calculate current max profit from left and right and then add them together is what we want. However, there are many repeat calculation when calculate left max profit and right max profit. So we can apply DP to record max profits for each left side and right side. then add them together at each point use one for loop

	/*
	Say you have an array for which the ith element is the price of a given stock on day i.
	Design an algorithm to find the maximum profit. You may complete at most two transactions.
	Note:
	You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
	*/
	public class BestTimetoBuyandSellStockIII {
	public int maxProfit(int[] prices) {
	if (prices==null || prices.length==0){
	return 0;
	}
	// record first max profit at first buy and sell
	int[] leftProfits=new int[prices.length];
	// record second max profit at second buy and sell
	int[] rightProfits=new int[prices.length];
	int max=0;
	buildProfitsArray(prices, leftProfits, rightProfits);
	// max profit made by left side + max profit made by rigth side is the max profit made by two buy and sell
	for (int i=0; i<prices.length; i++){
	max=Math.max(max, leftProfits[i]+rightProfits[i]);
	}
	return max;
	}
	private void buildProfitsArray(int [] prices, int[] leftProfits,int[] rightProfits){
	int min=Integer.MAX_VALUE;
	// max profits could make by buy stock at i from 0<=i<n and sell at i
	for (int i=0; i<leftProfits.length; i++){
	if (prices[i]<min){
	min=prices[i];
	}
	leftProfits[i]=i==0?0:Math.max(leftProfits[i-1], prices[i]-min);
	}
	int max=Integer.MIN_VALUE;
	// max profits could make by buy stock at i and sell at j, i<=j<n
	for (int i=rightProfits.length-1; i>=0; i--){
	if (prices[i]>max){
	max=prices[i];
	}
	rightProfits[i]=i==rightProfits.length-1?0: Math.max(rightProfits[i+1], max-prices[i]);
	}
	}
	}

view raw BestTimetoBuyandSellStockIII.java hosted with ❤ by GitHub

Remove Duplicates from Sorted List II (Java)

LeetCode

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

Solution: 

The logic is pretty straight, however, the corner cases need pay more attention.
check the comments in the code.

	/*
	Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
	For example,
	Given 1->2->3->3->4->4->5, return 1->2->5.
	Given 1->1->1->2->3, return 2->3.
	*/
	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) {
	* val = x;
	* next = null;
	* }
	* }
	*/
	public class Solution {
	public ListNode deleteDuplicates(ListNode head) {
	if (head==null || head.next==null){
	return head;
	}
	ListNode preHead=new ListNode (-1);
	preHead.next=head;
	ListNode pre=preHead;
	ListNode current=head;
	ListNode run=current.next;
	while (current!=null && run!=null){
	// check duplicats for current node;
	while (run!=null && run.val==current.val){
	run=run.next;
	}
	if (run==null){
	// current next is run, so no duplicate need to be removed
	// and no more nodes need to be check
	if (current.next==null){
	return preHead;
	}
	else{
	// current node until to null are all repeated
	// should remove them all.
	pre.next=null;
	return preHead.next;
	}
	}
	else{
	if (current.next==run){
	// no duplicate
	pre=current;
	current=run;
	run=run.next;
	}
	else{
	// removed duplicate
	pre.next=run;
	current=run;
	run=current.next;
	}
	}
	}
	return preHead.next;
	}
	}

view raw Remove DuplicatesFromSortedListII .java hosted with ❤ by GitHub