class MyQueue {
/* M1
private Stack stack, stack2;
// Push element x to the back of queue.
public void push(int x) {
while ( !stack.isEmpty() )
{
stack2.push( stack1.pop() );
}
stack2.push(x);
while( !stack2.isEmpty() )
{
stack.push( stack2.pop() );
}
}
// Removes the element from in front of queue.
public void pop() {
stack.pop();
}
// Get the front element.
public int peek() {
stack.peek();
}
// Return whether the queue is empty.
public boolean empty() {
return stack.isEmpty();
}
*/
// Last Exceed input : empty if delcare this way: private Stack stack, stack2;
private Stack stack = new Stack<>();
private Stack stack2 = new Stack<>();
public void push ( int x)
{
while( !stack2.isEmpty() )
{
stack.push( stack2.pop() );
}
stack.push(x);
}
public void pop()
{
while ( !stack.isEmpty() )
{
stack2.push(stack.pop());
}
stack2.pop();
}
public int peek()
{
while ( !stack.isEmpty() )
{
stack2.push(stack.pop());
}
return stack2.peek();
}
public boolean empty()
{
while( !stack2.isEmpty() )
{
stack.push( stack2.pop() );
}
return stack.isEmpty();
}
}
Saturday, July 11, 2015
[Leetcode]07/09 [Data Structure]Implement Queue using Stacks
/*
M1:
two stacks
push O(n)
pop O(1)
peek O(1)
M2:
one stack
push O(n)
pop O(n)
peek O(n)
*/
[Leetcode]07/09 [Data Structure] Implement Stack using Queues
/*
Method1: two queues
Push:O(1)
Pop:O(n)
Top:O(n)
Logic:
1. push: append new element to q1
2. pop: mov all elements in q1 other than the last one to q2
and then remove the one left in q1
Method2:
push:O(n)
pop:O(1)
top:O(1)
Logic:
1. new element always locates at the first element in q1: when push, add new element in q2 and append all elements in q1 onto q2 one by one
2. swap q1 and q2
3. first is pop and top
Method3:
Push:O(1)
Pop:O(n)
Top:O(n)
1. push: append
2. pop and top: append all elements before that last element to last element in q1
*/
class MyStack {
/*
Method2:
push:O(n)
pop:O(1)
top:O(1)
Logic:
1. new element always locates at the first element in q1:
How?
- add new element in empty q2
- append evry single element in q1 to q2
- swap q1 and q2
3. first is pop and top since it is the newest element
private Queue q1 = new LinkedList();
private Queue q2 = new LinkedList();
// Push element x onto stack.
public void push(int x) {
q2.offer(x);
while ( !q1.isEmpty() )
{
q2.offer(q1.poll() );
}
// swap
Queue tmp = q1;
q1 = q2;
q2 = tmp;
}
// Removes the element on top of the stack.
public void pop() {
q1.poll();// the first element of q1
}
// Get the top element.
public int top() {
return q1.peek();
}
// Return whether the stack is empty.
public boolean empty() {
return q1.isEmpty();
}
*/
/*
Method3:
Push:O(1)
Pop:O(n)
Top:O(n)
1. push: append new element to q
2. pop and top: append all elements before that last element to last element in q1
*/
private Queue q = new LinkedList();
public void push( int x)
{
q.offer(x);
}
public void pop()
{
// try to move the last index to the first index and use poll()
// to remvoe it
int size = q.size();
// 123458 => 812345
// 6 letter 5 times = 1 to size()-1
for ( int i =1; i < size; i++ )
{
q.offer( q.poll() );
}
q.poll();
}
public int top()
{
int size = q.size();
for ( int i =1; i < size; i++)
{
q.offer(q.poll());
}
int top = q.peek();
q.offer(q.poll());
return top;
}
public boolean empty()
{
return q.isEmpty();
}
}
[Leetcode]07/09 [Data Structure]Min Stack
/*
Time:O(1), Space:O(n)
push O(1)
pop O(1)
top O(1)
getMin O(1)
*/
class MinStack {
ArrayList stack = new ArrayList();
ArrayList minStack = new ArrayList();
public void push(int x) {
// check min
stack.add(x);
if ( minStack.isEmpty() || minStack.get( minStack.size()-1 ) >= x )
{
minStack.add(x);
}
}
public void pop() {
// top
if ( stack.isEmpty() )
{
return;
}
int elem = stack.remove( stack.size() -1 );
if ( !minStack.isEmpty() && elem == minStack.get(minStack.size() -1 ) )
{
minStack.remove( minStack.size() -1 );
}
}
public int top() {
// top
if (! stack.isEmpty() )
{
return stack.get( stack.size() - 1 );
}
return 0;
}
public int getMin() {
// top
if ( !minStack.isEmpty() )
{
return minStack.get( minStack.size() -1 );
}
return 0;
}
}
[Leetcode]07/09 [Hash]Fraction to Recurring Decimal
/*
Method1:
Time:O(); Space:O(n), map
Logic: Use remainder to judge recurring or not
1. sign
2. long
3. check remainder
0.16
_______
6 ) 1.00
0
1 0 <-- data-blogger-escaped--="" data-blogger-escaped-16="" data-blogger-escaped-1="" data-blogger-escaped-36="" data-blogger-escaped-40="" data-blogger-escaped-4="" data-blogger-escaped-6="" data-blogger-escaped-as="" data-blogger-escaped-at="" data-blogger-escaped-before="" data-blogger-escaped-fractional="" data-blogger-escaped-is="" data-blogger-escaped-mark="" data-blogger-escaped-part="" data-blogger-escaped-position="1" data-blogger-escaped-remainder="4" data-blogger-escaped-repeating="" data-blogger-escaped-seen="" data-blogger-escaped-so="" data-blogger-escaped-starts="" data-blogger-escaped-the="" data-blogger-escaped-was="" data-blogger-escaped-which=""> 1(6).
NOTE:
map.put(rem, ans.length()-1);
1. 0.6
ans.length = 1
ans.length -1 = 0, put "(" at 0
0.(6)
2. 0.65
ans.length =2
ans.length -1 = 1, put "(" at 1
0.6(5)
Method2:
Time:O(); Space:O()
Given numerator = 2, denominator = 3, return "0.(6)".
Reference:
1.http://yuanhsh.iteye.com/blog/2176178
2.http://www.programcreek.com/2014/03/leetcode-fraction-to-recurring-decimal-java/
*/
public class Solution {
public String fractionToDecimal(int numerator, int denominator) {
/*Method1: */
// special case
if ( denominator == 0 )
{
return "NaN";
}
if ( numerator == 0 )
{
return "0";
}
String sign = (denominator>>>31 ^ numerator>>>31) == 1 ? "-": "";
Long num = (long)numerator, den = (long)denominator; // -2147483648 => 2147483648 okay, int.MAX_VALUE = 2147483647, Long.MAX_VALUE is 9,223,372,036,854,775,807.
num = Math.abs(num);
den = Math.abs(den);
long major = num / den;
long rem = num % den;
// Case1: remainder == 0
if ( rem == 0 )
{
return sign+major;
}
// Case2: remainder != 0
String pre = sign + major + ".";
StringBuilder ans = new StringBuilder();
HashMap map = new HashMap();
while ( rem != 0 )
{
// get the remainder+'0' / dennominator
int res = (int) (rem*10 / den );
if ( map.containsKey(rem) )
{
int insert_index = map.get(rem);
ans.insert(insert_index, "(");
ans.append(")"); // append at last index
break;
}
else
{
// append res first
ans.append(res);
map.put( rem, ans.length( )-1 );
}
rem = (rem*10)%den;
}
// insert pre at the most front
return ans.insert(0, pre). toString();
/*Method2:
if ( denominator == 0 )
{
return "NaN";
}
if ( numerator == 0 )
{
return "0";
}
String sign = ( numerator>>>31 ^ denominator>>>31 ) ==1 ?"-" :"" ;
long num = (long) numerator, den = (long) denominator;
num = Math.abs( num );
den = Math.abs( den );
long major = num / den;
long rem = num % den;
long rem_temp = rem;
// Case 1: rem == 0
if ( rem == 0 )
{
return sign+major;
}
// Case 2: rem != 0
String pre = sign + major + ".";
Set set = new LinkedHashSet();
while ( !set.contains(rem) && rem != 0 )
{
set.add(rem);
rem = (rem*10) % den;
}
// recurring
String part2 = "";
Boolean repeated = false;
for ( long i:set )
{
if ( i == rem )
{
part2+="(";
repeated = true;
}
part2 += (rem_temp*10)/ den;
rem_temp = (rem_temp*10) %den;
}
if ( repeated )
{
part2+=")";
}
return pre+part2;
*/
}
}
[Leetcode]07/09 [Hash]Repeated DNA Sequences
/*
HashMap to store decimal value of sequence to check if any two sequence has the same decimal value
Method1:
Time:O(n); Space:O(n)
Logic: Binary
1. A=00,
C=01,
G=10 ,
T=11
2. AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT =>
00000000000001010101010100000000101001..
3. AAACCC = 00 00 00 01 01 01 = 21
4. check value 21 repeated or not in the map
NOTE:
0xFFFFF = 2*10 =20 digits
(sum<<2 class="brush:java;" data-blogger-escaped-0001="" data-blogger-escaped-0011="" data-blogger-escaped-0100="" data-blogger-escaped-0101="" data-blogger-escaped-0111="" data-blogger-escaped-0x3fffffff="" data-blogger-escaped-0xfffff="" data-blogger-escaped-1.="" data-blogger-escaped-1="" data-blogger-escaped-2.="" data-blogger-escaped-7="" data-blogger-escaped-:="" data-blogger-escaped-a:="" data-blogger-escaped-ascii="" data-blogger-escaped-blog="" data-blogger-escaped-c:="" data-blogger-escaped-character="" data-blogger-escaped-cnt="" data-blogger-escaped-digit="" data-blogger-escaped-digits="" data-blogger-escaped-every="" data-blogger-escaped-g:="" data-blogger-escaped-given="" data-blogger-escaped-http:="" data-blogger-escaped-https:="" data-blogger-escaped-i-9="" data-blogger-escaped-i="" data-blogger-escaped-last="" data-blogger-escaped-logic:="" data-blogger-escaped-map.get="" data-blogger-escaped-map="" data-blogger-escaped-method2:="" data-blogger-escaped-n="" data-blogger-escaped-need="" data-blogger-escaped-note:="" data-blogger-escaped-null="" data-blogger-escaped-only="" data-blogger-escaped-pre="" data-blogger-escaped-refereence:="" data-blogger-escaped-represent="" data-blogger-escaped-res.add="" data-blogger-escaped-return:="" data-blogger-escaped-s.charat="" data-blogger-escaped-s.substring="" data-blogger-escaped-s="AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" data-blogger-escaped-space:o="" data-blogger-escaped-sum="" data-blogger-escaped-summap.put="" data-blogger-escaped-t:="" data-blogger-escaped-the="" data-blogger-escaped-three="" data-blogger-escaped-time:o="" data-blogger-escaped-to="" data-blogger-escaped-wiki="" data-blogger-escaped-yuanhsh.iteye.com="" data-blogger-escaped-zh.wikipedia.org="">
public class Solution {
public List findRepeatedDnaSequences(String s) {
/* Method1:
List res = new ArrayList();
Map map = new HashMap();
map.put('A', 0);
map.put('C', 1);
map.put('G', 2);
map.put('T', 3);
Map sumMap = new HashMap();
int sum = 0;
for ( int i = 0; i < s.length(); i++ )
{
// 00 00 00 01 01 01
// MSB LSB
// i = 0, 3 & 0XFFFFF = 11
// i = 1, 11 00(11<<2 data-blogger-escaped-00="" data-blogger-escaped-01="" data-blogger-escaped-0xfffff="" data-blogger-escaped-10-letter-long="" data-blogger-escaped-10="" data-blogger-escaped-11="" data-blogger-escaped-1="" data-blogger-escaped-2="" data-blogger-escaped-9="" data-blogger-escaped-cnt="" data-blogger-escaped-continue="" data-blogger-escaped-i-9="" data-blogger-escaped-i="" data-blogger-escaped-if="" data-blogger-escaped-integer="" data-blogger-escaped-list="" data-blogger-escaped-map.get="" data-blogger-escaped-method2:="" data-blogger-escaped-null="" data-blogger-escaped-record="" data-blogger-escaped-res.add="" data-blogger-escaped-res="" data-blogger-escaped-return="" data-blogger-escaped-s.charat="" data-blogger-escaped-s.substring="" data-blogger-escaped-sequence="" data-blogger-escaped-sum="" data-blogger-escaped-summap.put="" data-blogger-escaped-tring=""> res = new ArrayList();
HashMap sumMap = new HashMap();
int sum = 0;
for ( int i = 0; i < s.length(); i++ )
{
sum = ( (sum<<3 data-blogger-escaped-0x3fffffff="" data-blogger-escaped-10-letter-long="" data-blogger-escaped-7="" data-blogger-escaped-9="" data-blogger-escaped-cnt="" data-blogger-escaped-continue="" data-blogger-escaped-i-9="" data-blogger-escaped-i="" data-blogger-escaped-if="" data-blogger-escaped-integer="" data-blogger-escaped-null="" data-blogger-escaped-pre="" data-blogger-escaped-record="" data-blogger-escaped-res.add="" data-blogger-escaped-res="" data-blogger-escaped-return="" data-blogger-escaped-s.charat="" data-blogger-escaped-s.substring="" data-blogger-escaped-sequence="" data-blogger-escaped-sum="" data-blogger-escaped-summap.put="">
[Leetcode]07/09 [Hash]Count Primes
/*
No hashMap here @@
Time:O(n^2), Space:O(1)
Logic:
isPrime:O(n)
1-n check isPrime:O(n)*O(n)=O(n^2)
Time:O(nlog(logn)); Space:O(n)
Logic:
，Sieve of Eratosthenes
step 1. assume all number are prime number
step 2. starting from 2, take out all 2*2, 2*3, 2*4...2*X
and then take out all 3*2, 3*3, 3*4...3*X
step 3. count all isPrime number
NOTE:
i < Math.sqrt(n)
boolean isPrime[] = new boolean[n+1];
*/
public class Solution {
public int countPrimes(int n) {
// speical case
if ( n <= 2 )
{
return 0;
}
boolean isPrime[] = new boolean[n+1];
// step 1.
for ( int i =2; i < n ; i++ )
{
isPrime[i] = true;
}
// step 2.
for ( int i =2; i < Math.sqrt(n); i++ )
{
if (isPrime[i])
{
for ( int j = i+i; j < n; j=j+i)
{
isPrime[j] = false;
}
}
}
// step3
int count = 0;
for ( int i =2; i < n ; i++ )
{
if (isPrime[i])
{
count++;
}
}
return count;
}
}
Wednesday, July 8, 2015
07/08 [hash]Happy Number
/*
Time:O(); Space:O()
Logic:
1. perform calculation of a^2 ++ b^2
2. record the value of a^2 ++ b^2 in the HashSet
*/
public class Solution {
public boolean isHappy(int n) {
HashSet set = new HashSet();
while (!set.contains(n))
{
set.add(n);
n = sum(getDigits(n));
if ( n ==1 )
{
return true;
}
}
return false;
}
private int sum (int[] arr)
{
int sum = 0;
for ( int i: arr)
{
sum+= i*i;
}
return sum;
}
private int[] getDigits(int n)
{
String s = String.valueOf(n);
int[] result = new int[s.length()];
int i = 0;
while ( n > 0 )
{
int m = n%10;
result[i++] = m;
n = n/10;
}
return result;
}
}
[Leetcode]07/08 [hash] Isomorphic Strings
/*
Method1:
Time:O(n^2); Space:O(n)
Logic:
check each correpsonding character set if in the map
and backward check if
the corresponding key of c2 is the same as current c1
getKey()
Method2:
Time:O(n):Space:O(2n)
Logic:
Two hashmap
sourceMap[ t[x] ] = s[x]
targetMap[ s[x] ] = t[x]
False if two map relationship valid;Otherwise, it is ture.
Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.
*/
public class Solution {
public boolean isIsomorphic(String s, String t) {
/* Metho1:
// special case
if ( s== null || t == null )
{
return false;
}
if ( s.length() != t.length() )
{
return false;
}
if ( s.length() ==0 && t.length() == 0 )
{
return true;
}
HashMap map = new HashMap();
for ( int i = 0; i < s.length();i++ )
{
char c1 = s.charAt(i);
char c2 = t.charAt(i);
//Input:
// "ab", "aa"
//Output:
//true
//Expected:
//false
// **** Need to backward check
//if ( map.containsKey(c1) )
//{
// if ( c2 != map.get(c1) )
// {
// return false;
// }
//}
//else
//{
// map.put(c1,c2);
//}
Character c = getKey(map,c2);
if ( c != null && c != c1)
{
return false;
}
else if ( map.containsKey(c1) )
{
if ( c2 != map.get(c1) )
{
return false;
}
}
else
{
map.put(c1,c2);
}
}
return true;
*/
/*Method2:*/
if ( s.length() != t.length() )
{
return false;
}
if ( s.length() == 0 && t.length() == 0)
{
return true;
}
if ( s == null || t == null )
{
return false;
}
HashMap map1 = new HashMap();
HashMap map2 = new HashMap();
for ( int i = 0 ;i < s.length() ;i ++)
{
char c1 = s.charAt(i);
char c2 = t.charAt(i);
if ( map1.containsKey(c1) )
{
if ( map1.get(c1) != c2 )
{
return false;
}
}
if ( map2.containsKey(c2) )
{
if ( map2.get(c2) != c1 )
{
return false;
}
}
map1.put( c1,c2 );
map2.put( c2,c1);
}
return true;
}
// a method for getting key given a target value
// a method for getting key of a target value
private Character getKey(HashMap map, Character value )
{
for ( Map.Entry entry : map.entrySet() )
{
if ( entry.getValue().equals(value) )
{
return entry.getKey();
}
}
return null;
}
}
[Leetcode]07/06 [String] Reverse Words in a String
/*
Recursive
NOTE null vs ""
"" is an actual string, you can still invoke methods or functions on it like
a.length()
a.substring(0, 1)
null, like b, Java would throw a NullPointerException if you tried invoking, say b.length()
http://stackoverflow.com/questions/4802015/difference-between-null-and-java-string
Mrthod1:
Time:O(n), Sapce:O(n)
Logic:
Split and keep appending inside
1. split by space to get each word
- iterate thru string when ' ' is met, record the word and skip ' '
2. append getting word in the end
Ex.
the sky is blue
=> "sky is blue" + "the"
=> "is blue" + "sky " + "the"
=> "blue" + "is " + "sky "+"the"
=> "" + "blue" + "is " + "sky "+"the"
NOTE:
return helper(s,index).append(cur);
return helper(s,index).append(cur).append(' ');
Method2: (Iterative) Two poitners
Time:O(n), SpacE:O(n)
Logic:
先反转整体，再反转局部
1. "the sky is blue" => "eulb si yks eht" O(n)
2. "eulb si yks eht" => "blue is sky the" O(n)
NOTE:
s = s.trim();
It returns a copy of this string with leading and trailing white space removed
// skip one of double spaces
if ( i != s.length() -1 && s.charAt(i)== ' ' && s.charAt(i)==s.charAt(i+1) )
{
continue;
}
*/
public class Solution {
public String reverseWords(String s) {
/* Method1:
s = s.trim();
return helper(s,0).toString();
*/
/* Method2:*/
if ( s == null )
{
return null;
}
if ( s.length() == 0 )
{
return "";
}
s = s.trim();
// 1. reverse entire string from the last character
StringBuilder res = new StringBuilder();
for ( int i = s.length()-1; i >=0 ; i-- )
{
// skip one of double spaces
if ( i != s.length() -1 && s.charAt(i)== ' ' && s.charAt(i)==s.charAt(i+1) )
{
continue;
}
res.append(s.charAt(i));
}
// 2. reverse each word, scan twice:
// one for length and one for reverse
int left = 0;
int right = 0;
while ( right < res.length() )
{
// 1. get the end index of each word
while( right < res.length() && res.charAt(right) != ' ' )
{
right++;
}
int next = right + 1; // right after ' '
right--;
// 2. two poitners for each word,
// one point to start and the other point the end
while( left < right )
{
// 3. swap
char temp = res.charAt(left);
res.setCharAt( left++, res.charAt(right) );
res.setCharAt( right--, temp );
}
// 4. reset the start for two poitners
left = next;
right = next;
}
return res.toString();
}
// Method1:
private StringBuilder helper( String s, int index )
{
// Base case
if ( index >= s.length() )
{
return new StringBuilder();
}
// 1. append not ' '
StringBuilder cur = new StringBuilder();
int lastIndex = index;
while ( index < s.length() && s.charAt(index) != ' ' )
{
cur.append( s.charAt(index++) );
}
// 2. remove ' '
while ( index < s.length() && s.charAt(index) == ' ' )
{
index++;
}
// 3. first word append to the end
if (lastIndex == 0 )
{
return helper(s,index).append(cur);
}
// 4. not the first word
return helper(s,index).append(cur).append(' ');
}
}
[Leetcode] 07/06 [String] Generate Parentheses
Recursive
Time:O(); Space:O()
Logic:
==> (( => (( ) => (( ))
( L2 R0 L2 R1 L2 R2
L1 R0
==> ( ) => ( ) ( => ( ) ( )
L1 R1 L2 R1 L2 R2
NOTE:
C_0 =1, C_1 = 1, C_2 =2 ,C_3 = 5, C_4 = 14
C_0 =1, C_n+1 = [i=0~n]signma(C_i*C_n-i), for n >= 0
C3 = C_0*C2 + C_1*C_1 + C_2*C_0 = 2 + 1 + 2 = 5
C_n+1 = ( 2(2*n+1) / n+2 )* C_n
the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively-defined objects.
Re-interpreting the symbol X as an open parenthesis and Y as a close parenthesis, Cn counts the number of expressions containing n pairs of parentheses which are correctly matched:
C_0 = 1 \quad \mbox{and} \quad C_{n+1}=\sum_{i=0}^{n}C_i\,C_{n-i}\quad\text{for }n\ge 0;
public class Solution {
public List generateParenthesis(int n) {
ArrayList res = new ArrayList();
if ( n < 0 )
{
return res;
}
helper( n,n, new String(), res );
return res;
}
private void helper( int l, int r, String item, ArrayList res )
{
// Base case
// remaining r should be greater or equal to l
if ( r < l )
{
return;
}
// when consuming all l and r, return current combination
if ( l == 0 && r == 0 )
{
res.add(item);
}
if ( l > 0 )
{
helper( l-1, r, item+"(", res);
}
if ( r > 0 )
{
helper(l, r-1, item+")", res);
}
}
}
Tuesday, July 7, 2015
Monday, July 6, 2015
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid.
Some examples:
Add Your Encoded Code Here
/* Method2:*/
Stack stack = new Stack();
stack.push(1);
int res = 0;
int sign = 1;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '+' || c == '-') {
sign = c == '+' ? 1: -1;
} else if (c == '(') {
stack.push(sign * stack.peek());
sign = 1;
} else if (c == ')') {
sign = stack.pop();
} else if (Character.isDigit(c)) {
int num = 0;
while (i < s.length() && Character.isDigit(s.charAt(i))) {
num = num * 10 + (s.charAt(i) - '0');
i++;
}
i--;
res += sign * num * stack.peek();
}
}
return res;
Subscribe to:
Posts (Atom)