Leetcode: Valid Parentheses

Posted on March 6, 2013 by Ying

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 boolean isValid(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(s==null||s.length()%2!=0){
            return false;
        }
        ArrayList<Character> leftBrackets = new ArrayList<Character>();
        for(int i=0;i<s.length();i++){
            char curr = s.charAt(i);
            if(curr=='(' || curr=='{' || curr=='[' ){
                leftBrackets.add(curr);
            }else{
                if(leftBrackets.size()==0){
                    return false;
                }
                char lastLeft = leftBrackets.get(leftBrackets.size()-1);
                if((lastLeft=='('&&curr==')') ||
                   (lastLeft=='{'&&curr=='}') ||
                   (lastLeft=='['&&curr==']')){
                       leftBrackets.remove(leftBrackets.size()-1);
                   }else{
                       return false;
                   }
            }
        }
        if(leftBrackets.size()!=0){
            return false;
        }
        return true;        
    }

Leetcode: String to Integer (atoi)

Posted on March 6, 2013 by Ying

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Requirements for atoi:The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

public class Solution {
    public int atoi(String str) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<Integer> validBits = new ArrayList<Integer>();
        int sign=0;
        if(str==null||str.length()==0){
            return 0;
        }
        int index = 0;
        while(str.charAt(index)==' '){
            index++;
        }
        if(!(isNum(str, index) || str.charAt(index)=='+' || str.charAt(index)=='-')){
            return 0;
        }
        if(str.charAt(index)=='-'){
            sign = -1;
            index++;
        }else{
            sign = 1;
            if(str.charAt(index)=='+'){
                index++;
            }
        }
        //now find the first non-zero bit
        while(str.charAt(index)=='0'){
            index++;
        }
        while(index<str.length() && isNum(str,index)){
            int asc = (int)str.charAt(index);
            int bit = asc-'0';
            validBits.add(bit);
            index++;
        }

        int length = validBits.size();
        if(length==0){
            return 0;
        }

        double sum =0;
        for(int i=0;i<length;i++){
            sum+=validBits.get(i)*Math.pow(10,length-i-1);
        }
        if(sign<0){
            if(sum*sign<(double)Integer.MIN_VALUE){
                return Integer.MIN_VALUE;
            }else{
                return (int)(sum*sign);
            }
        }else{
            if(sum>(double)Integer.MAX_VALUE){
                return Integer.MAX_VALUE;
            }else{
                return (int)sum;
            }
        }

    }

    public boolean isNum(String str, int index){
        int asc = (int)str.charAt(index);
        if(asc>='0' && asc<='9'){
            return true;
        }
        return false;
    }
}

Leetcode: Next Permutation

Posted on March 2, 2013 by Ying

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

public class Solution {
    public void nextPermutation(int[] num) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(num==null||num.length<=1){
            return;
        }

        int i=num.length-2;
        while(i>=0 && num[i]>=num[i+1]){
            i--;
        }
        if(i==-1){
            int m = 0;
            int n = num.length-1;
            while(m<n){
                swap(num,m,n);
                m++;
                n--;
            }

        }else{
            int minIndex = i+1;
            for(int j=minIndex+1;j<num.length;j++){
                if(num[j]>num[i] && num[j]<num[minIndex]){
                    minIndex=j;
                }
            }
            swap(num,i,minIndex);

            for(int k=i+1;k<num.length;k++){
                minIndex = k;
                for(int l=k+1;l<num.length;l++){
                    if(num[l]<num[minIndex]){
                        minIndex=l;
                    }
                }
                swap(num,k,minIndex);
            }
        }

    }

    public void swap(int[] num, int i, int j){
        int tmp = num[i];
        num[i] = num[j];
        num[j] = tmp;
    }

}

Leetcode: Merge Intervals

Posted on February 8, 2013 by Ying

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(intervals==null||intervals.size()<=1){
            return intervals;
        }
        //sort the intervals by the start time.
        //1. convert ArrayList to array
        Interval[] intervalArr = new Interval[intervals.size()];
        int index = 0;
        for(Interval interval:intervals){
            intervalArr[index++] = interval;
        }
        //2. use quick sort to sort intervals by the start time O(nlgn)
        sort(intervalArr,0,intervalArr.length-1);

        //3. only need to compare the new interval with the last interval in the sorted list
        ArrayList<Interval> merged = new ArrayList<Interval>();
        Interval last = intervalArr[0];
        for(int i=1;i<intervalArr.length;i++){
            if(last.end<intervalArr[i].start){
                merged.add(last);
                last = intervalArr[i];
            }else{
                Interval newInterval = new Interval(last.start, Math.max(last.end, intervalArr[i].end));
                last = newInterval;
            }
        }
        merged.add(last);

        return merged;
    }

    public void sort(Interval[] inters,int start, int end){
        int pivot = partition(inters, start, end);
        if(start<pivot-1){
            sort(inters, start, pivot-1);
        }
        if(pivot<end){
            sort(inters, pivot, end);
        }
    }

    public int partition(Interval[] inters, int start, int end){
        int middle = (start+end)/2;
        Interval pivot = inters[middle];

        int i=start;
        int j=end;
        while(i<=j){
            while(inters[i].start<pivot.start){
                i++;
            }

            while(inters[j].start>pivot.start){
                j--;
            }

            if(i<=j){
                swap(inters,i,j);
                i++;
                j--;
            }
        }

        return i;
    }

    public void swap(Interval[] inters, int i, int j){
        Interval tmp = inters[i];
        inters[i] = inters[j];
        inters[j] = tmp;
    }

}

So the overall time complexity is O(nlgn)

Leetcode: Length of Last Word

Posted on February 8, 2013 by Ying

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example,
Given s = "Hello World",
return 5.

public int lengthOfLastWord(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(s==null||s.length()==0){
            return 0;
        }

        String[] words = s.split(" ");
        String lastword = "";
        if(words.length>0){
            lastword = words[words.length-1];
        }
        return lastword.length();
    }

Remind:
The string “boo:and:foo”, for example, yields the following results with these expressions:
Regex Result
: { “boo”, “and”, “foo” }
o { “b”, “”, “:and:f” }

So in this problem, if the input is ” “, the length of words is 0.

Leetcode: Construct Binary Tree from Inorder and Postorder Traversal

Posted on February 8, 2013 by Ying

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

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

/**
 * 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
        if(inorder.length==0){
            return null;
        }
        
        //last element of postorder is the root
        TreeNode root = new TreeNode(postorder[postorder.length-1]);
        //find the root element in the inorder array
        //elements occur before it are in its left sub-tree
        //elements occur after it are in its right sub-tree
        int index = 0;
        for(int i=0;i<inorder.length;i++){
            if(inorder[i]==root.val){
                index = i;
                break;
            }
        }
        int[] leftInOrder = new int[index];
        int[] leftPostOrder = new int[index];
        int[] rightInOrder = new int[inorder.length-index-1];
        int[] rightPostOrder = new int[inorder.length-index-1];
        
        for(int i=0;i<inorder.length;i++){
            if(i<index){
                leftInOrder[i] = inorder[i]; 
            }
            if(i>index){
                rightInOrder[i-index-1] = inorder[i];
            }
        }
        
        for(int i=0;i<postorder.length-1;i++){
            if(i<index){
                leftPostOrder[i] = postorder[i];
            }else{
                rightPostOrder[i-index]=postorder[i]; 
            }
        }
        
        root.left = buildTree(leftInOrder,leftPostOrder);
        root.right = buildTree(rightInOrder,rightPostOrder);
        return root;
    }
}

Leetcode: Binary Tree Inorder Traversal

Posted on January 9, 2013 by Ying

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

return [1,3,2].

1. Recursive Version

public ArrayList<Integer> inorderTraversal(TreeNode root) {
    //recursive version
    ArrayList<Integer> result = new ArrayList<>();
    traversalHelper(root, result);
    return result;
}

public void traversalHelper(TreeNode root, ArrayList<Integer> result) {
    if (root == null) {
        return;
    }
    traversalHelper(root.left, result);
    result.add(root.val);
    traversalHelper(root.right, result);
}

2. Non-recursive Version

public ArrayList<Integer> inorderTraversal(TreeNode root) {
    //non-recursive version
    ArrayList<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    while (curr != null || !stack.empty()) {
        TreeNode left = curr;
        while (left != null) {
            stack.push(left);
            left = left.left;
        }
        curr = stack.pop();
        result.add(curr.val);
        curr = curr.right;
    }
    return result;
}

Leetcode: Anagrams

Posted on January 8, 2013 by Ying

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

Note: All inputs will be in lower-case.

public ArrayList<String> anagrams(String[] strs) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<String> output = new ArrayList<String>();
        HashMap<String,ArrayList<String>> patterns = new HashMap<String,ArrayList<String>>();

        for(int i=0;i<strs.length;i++){
            char[] charArr = strs[i].toCharArray();
            Arrays.sort(charArr);
            String sorted = new String(charArr);

            if(patterns.containsKey(sorted)){
                patterns.get(sorted).add(strs[i]);
            }else{
                ArrayList<String> newPattern = new ArrayList<String>();
                newPattern.add(strs[i]);
                patterns.put(sorted,newPattern);
            }
        }

        for(String str :patterns.keySet()){
            if(patterns.get(str).size()>1){
                output.addAll(patterns.get(str));
            }
        }
        return output;
    }

Analysis: Time complexity: O(n*mlgm) (n is # of strings, m is the average length of each string) Space Complexity: O(n*m)

M	T	W	T	F	S	S
« Feb
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

Now Now Now

내일은 없어

Category Archives: Leetcode

Leetcode: Valid Parentheses

Leetcode: String to Integer (atoi)

Leetcode: Next Permutation

Leetcode: Merge Intervals

Leetcode: Length of Last Word

Leetcode: Construct Binary Tree from Inorder and Postorder Traversal

Leetcode: Binary Tree Inorder Traversal

Leetcode: Anagrams