Daily Archives: March 8, 2013

Leetcode: Valid Palindrome

Posted on by
Reply

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

 

public boolean isPalindrome(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(s==null || s.length()<=1){
            return true;
        }
        String lowercase = s.toLowerCase();
        ArrayList<Character> validChars = new ArrayList<Character>();
        for(int i=0;i<lowercase.length();i++){
            int asc=(int)lowercase.charAt(i);
            
            if((asc<='9' && asc>='0') ||
               (asc<='z' && asc>='a')){
                   validChars.add(lowercase.charAt(i));
               }
        }
        
        int left = 0;
        int right = validChars.size()-1;
        while(left<right){
            if(validChars.get(left)!=validChars.get(right)){
                return false;
            }else{
                left++;
                right--;
            }
        }
        return true;
    }
FacebookTwitterGoogle+Share

Leetcode: Validate Binary Search Tree

Posted on by
Reply

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. 
    public boolean isValidBST(TreeNode root) {
    // write your code here
    return isValidBSTHelper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);

}
//return if the root val is within the [min,max] range
public boolean isValidBSTHelper(TreeNode root, int min, int max) {
    if (root == null) {
        return true;
    }
    if (min > root.val || root.val > max) {
        return false;
    }
    return isValidBSTHelper(root.left, min, root.val - 1) &&
           isValidBSTHelper(root.right, root.val + 1, max);
}

九章详解

Leetcode: Merge Sorted Array

Posted on by
Reply

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

public void merge(int A[], int m, int B[], int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int runnerA = m-1;
        int runnerB = n-1;
        int runner = m+n-1;
        while(runnerA>=0 && runnerB>=0){
            A[runner] = Math.max(A[runnerA],B[runnerB]);
            runner--;
            if(A[runnerA]>=B[runnerB]){
                runnerA--;
            }else{
                runnerB--;
            }
        }   
        
        if(runnerB>=0){
            for(int i=0;i<=runnerB;i++){
                A[i]=B[i];
            }
        }
    }

Leetcode: Climbing Stairs

Posted on by
Reply

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

public int climbStairs(int n) {
    if (n <= 1) {
        return n;
    }
    int[] result = new int[n + 1];
    result[0] = 1;
    result[1] = 1;
    for (int i = 2; i <= n; i++) {
        result[i] = result[i - 1] + result[i - 2];
    }
    return result[n];
}

O(N)

Leetcode: Insert Interval

Posted on by
Reply

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<Interval> output = new ArrayList<Interval>();
        if(intervals==null||intervals.size()==0){
            output.add(newInterval);
            return output;
        }
        int index =0;
        for(int i=0;i<intervals.size();i++){
            Interval curr = intervals.get(i);
            if(curr.end<newInterval.start){
                output.add(curr);
                index++;
            }else if(newInterval.end<curr.start){
                output.add(curr);
            }else{
                newInterval = new Interval(Math.min(newInterval.start, curr.start),
                                               Math.max(newInterval.end, curr.end));
            }
        }

        output.add(index,newInterval);
        return output;
    }

Leetcode: Pow(x, n)

Posted on by
Reply

Implement pow(x, n).

public double pow(double x, int n) {
    // Start typing your Java solution below
    // DO NOT write main() function
    boolean positive = n >= 0 ? true : false;

    int nabs = n == Integer.MIN_VALUE ? Integer.MAX_VALUE : Math.abs(n);

    double product = n == Integer.MIN_VALUE ? powHelp(x, nabs) * x : powHelp(x, nabs);

    return positive ? product : 1 / product;

}

public double powHelp(double base, int n) {
    if (n == 0) {
        return 1;
    }
    if (n == 1) {
        return base;
    }

    double tmp = powHelp(base, n / 2);
    return tmp * tmp * powHelp(base, n % 2);
}

O(logN)

Version with no helper function

public double myPow(double x, int n) {
        if(n==0){
            return 1;
        }
        int n_abs = Math.abs(n);
        if(n_abs==1){
            return n>0?x:1/x;
        }
        double tmp =  myPow(x, n/2);
        return tmp*tmp*myPow(x, n%2);
    }