Monthly Archives: March 2013

Leetcode: Merge k Sorted Lists

Posted on by
Reply

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

public ListNode mergeKLists(ArrayList<ListNode> lists) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ListNode fakeHead = new ListNode(-1);
        ListNode runner = fakeHead;
        int nonTraversed = 0;
        //count the number of not-null ListNode
        for(ListNode curr:lists){
            if(curr!=null){
                nonTraversed++;
            }
        }
        while(nonTraversed>0){
            int min = Integer.MAX_VALUE;
            int minIndex = -1;
            for(int i=0;i<lists.size();i++){
                ListNode curr = lists.get(i);
                if(curr!=null){
                    if(curr.val<min){
                        minIndex = i;
                        min = curr.val;
                    }
                }
            }
            runner.next = lists.get(minIndex);
            runner = runner.next;
            lists.set(minIndex, lists.get(minIndex).next);
            if(lists.get(minIndex)==null){
                nonTraversed--;
            }
        }
        return fakeHead.next;
    }

O(N*k) k is the size of lists and N is the total number of elements in all the inputs lists

We can improve our solution by using Heap which can have O(Nlogk) runtime complexity.

 

 

FacebookTwitterGoogle+Share

Leetcode: Roman to Integer

Posted on by
Reply

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

public int romanToInt(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<Character> oneLetters = new ArrayList<Character>();
        oneLetters.add('I');
        oneLetters.add('X');
        oneLetters.add('C');
        oneLetters.add('M');
        ArrayList<Character> fiveLetters = new ArrayList<Character>();
        fiveLetters.add('V');
        fiveLetters.add('L');
        fiveLetters.add('D');

        int num=0;
        for(int i=0;i<s.length();i++){
            int bit = fiveLetters.indexOf(s.charAt(i));
            //if the current letter is in fiveLetters
            if(bit!=-1){
                num+=5*(int)Math.pow(10,bit);
            }else{
                bit = oneLetters.indexOf(s.charAt(i));
                //if the current letter is in oneLetters && there is a bigger number afterwards
                if( i+1<s.length() && 
                  (fiveLetters.indexOf(s.charAt(i+1))>=bit ||
                   oneLetters.indexOf(s.charAt(i+1))>bit)){
                    num-=(int)Math.pow(10,bit);
                }
                //else, just add this num
                else{
                    num+=(int)Math.pow(10,bit);
                }
            }

        }
        return num;
    }

Leetcode: Integer to Roman

Posted on by
Reply

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

public String intToRoman(int num) {
        // Start typing your Java solution below
        // DO NOT write main() function
        String[] oneLetters = {"I","X","C","M"};
        String[] fiveLetters = {"V","L","D",""};
        String numStr = num+"";
        String output = "";
        for(int i=numStr.length()-1;i>=0;i--){
            String tmp = "";
            int bit = (int)num%(int)Math.pow(10,i+1)/(int)Math.pow(10,i);
            switch (bit){
                case 1: tmp = oneLetters[i];
                        break;
                case 2: tmp = oneLetters[i]+oneLetters[i];
                        break;
                case 3: tmp = oneLetters[i]+oneLetters[i]+oneLetters[i];
                        break;
                case 4: tmp = oneLetters[i]+fiveLetters[i];
                        break;
                case 5: tmp = fiveLetters[i];
                        break;
                case 6: tmp = fiveLetters[i]+oneLetters[i];
                        break;
                case 7: tmp = fiveLetters[i]+oneLetters[i]+oneLetters[i];
                        break;
                case 8: tmp = fiveLetters[i]+oneLetters[i]+oneLetters[i]+oneLetters[i];
                        break;
                case 9: tmp = oneLetters[i]+oneLetters[i+1];
                        break;
                default: tmp = "";
                        break;
            }
            output+=tmp;
        }
        return output;
    }

Leetcode: Add Two Numbers

Posted on by
Reply

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ListNode runner1=l1;
        ListNode runner2=l2;
        ListNode head = new ListNode(-1);
        ListNode runner = head;
        int carry=0;
        while(runner1!=null || runner2!=null ||carry!=0){
            int val1 = runner1==null?0:runner1.val;
            int val2 = runner2==null?0:runner2.val;
            int sum =val1+val2+carry;
            if(sum>9){
                carry=1;
            }else{
                carry=0;
            }
            runner.next = new ListNode(sum%10);
            runner = runner.next;
            runner1 = runner1==null?null:runner1.next;
            runner2 = runner2==null?null:runner2.next;
        }

        return head.next;
    }

 

 

Leetcode: Word Ladder

Posted on by
Reply

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

 

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;
    }

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;
    }