Sunday, February 1, 2015

Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
Solution1: brute force
public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] res = new int[2];
        
        for(int i = 0; i < numbers.length; i++) {
            for(int j = i + 1; j < numbers.length; j++) {
                if(numbers[i] + numbers[j] == target) {
                    res[0] = i + 1;
                    res[1] = j + 1;
                }
            }
        }
        return res;
    }
}
Solution2:  HashMap
Time complexity depends on the put and get operations of HashMap which is normally O(1).
O(n) runtime, O(n) space.
public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] res = new int[2];
        HashMap map = new HashMap();
        
        for(int i = 0; i < numbers.length; i++) {
            if(map.containsKey(target-numbers[i])) {
                res[0] = map.get(target - numbers[i]) + 1;
                res[1] = i + 1;
            }else {
                map.put(numbers[i], i);
            }
        }
        return res;
    }
}
Solution3:  
先对数组进行排序,然后使用夹逼的方法找出满足条件的pair. 
算法的时间复杂度是O(nlogn+n)=O(nlogn),空间复杂度取决于排序算法。
注意:输出结果改成了满足相加等于target的两个数,而不是他们的index。因为要排序,如果要输出index,需要对原来的数的index进行记录,方法是构造一个数据结构,包含数字的值和index,然后排序。
public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] res = new int[2];
        
        Arrays.sort(numbers);
        int l = 0, r = numbers.length - 1;
        while(l < r) {
            if(numbers[l] + numbers[r] == target) {
                res[0] = numbers[l];
                res[1] = numbers[r];
                return res;
            }else if(numbers[l] + numbers[r] > target) {
                r--;
            }else {
                l++;
            }
        }
        return null;
    }
}

Saturday, January 31, 2015

Best Time to Buy and Sell Stock II

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 as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Solution: 从头到尾扫描prices,如果i比i-1大,那么price[i] – price[i-1]就可以计入最后的收益中。这样扫描一次O(n)就可以获得最大收益了。constant space.
public class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length <= 1)
            return 0;
        
        int profit = 0;
        for(int i = 1; i < prices.length; i++) {
            profit += Math.max(0, prices[i] - prices[i - 1]);
        }
        return profit;
    }
}

Saturday, July 26, 2014

Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
    1
   / \
  2   2
 / \ / \
3  4 4  3
But the following is not:
    1
   / \
  2   2
   \   \
   3    3
Note: Bonus points if you could solve it both recursively and iteratively.
confused what "{1,#,2,3}" means?
Solution1: recursion
Run time complexity is O(n), space complexity is stack space O(logn).

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) 
            return true;
        
        return helper(root.left, root.right);
    }
    
    public boolean helper(TreeNode left, TreeNode right) {
        if(left == null && right == null)
            return true;
        if(left == null || right == null)
            return false;
        if(left.val != right.val)
            return false;
        return helper(left.right, right.left) && helper(left.left, right.right);
    }
}
Solution2: iterative
用两个queue来保存左右节点,一层一层遍历。
Run time complexity is O(n), space complexity is O(n).
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) 
            return true;
        if(root.left == null && root.right == null)
            return true;
        if(root.left == null || root.right == null)
            return false;
        
        LinkedList queue1 = new LinkedList();
        LinkedList queue2 = new LinkedList();
        queue1.add(root.left);
        queue2.add(root.right);
        while(!queue1.isEmpty() && !queue2.isEmpty()) {
            TreeNode curL = queue1.poll();
            TreeNode curR = queue2.poll();
            if(curL.left == null && curR.right != null || curL.left != null && curR.right == null)
                return false;
            if(curL.right == null && curR.left != null || curL.right != null && curR.left == null)
                return false;
            if(curL.val != curR.val)
                return false;
            
            if(curL.left != null && curR.right != null) {
                queue1.add(curL.left);
                queue2.add(curR.right);
            }
            if(curL.right != null && curR.left != null) {
                queue1.add(curL.right);
                queue2.add(curR.left);
            }
        }
        return true;
    }
}

Thursday, July 24, 2014

Same Tree

Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
Solution1: recursion
如果两个结点都是null,返回true。
如果其中一个是null,说明在一棵树上结点到头,另一棵树结点还没结束,即树不相同,或者两个结点都非空,并且结点值不相同,返回false。
递归处理两个结点的左右子树,返回左右子树递归的与结果即可。
先序遍历,时间复杂度是O(n),空间复杂度是O(logn)。
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null)
            return true;
        
        if(p == null || q == null)
            return false;
        
        if(p.val != q.val)
            return false;
            
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}
Reference: http://blog.csdn.net/linhuanmars/article/details/22839819
Solution2: iterative
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null)
            return true;
        
        LinkedList q1 = new LinkedList();
        LinkedList q2 = new LinkedList();
        
        q1.offer(p);
        q2.offer(q);
        
        while(!q1.isEmpty() && !q2.isEmpty()) {
            TreeNode pNode = q1.poll();
            TreeNode qNode = q2.poll();
            
            if(pNode == null) {
                if(qNode != null)
                    return false;
                else 
                    continue;
            }
            
            if(qNode == null || qNode.val != pNode.val) {
                return false;
            }
            
            q1.offer(pNode.left);
            q1.offer(pNode.right);
            q2.offer(qNode.left);
            q2.offer(qNode.right);
        }
        return true;
    }
}

Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
Solution:
Run time complexity is O(n), constant space.
/**
 * 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)
            return null;
        if(head.next == null)
            return head;
        
        ListNode pre = head;
        ListNode cur = head.next;
        while(cur != null) {
            if(cur.val == pre.val) {
                pre.next = cur.next;
            }else {
                pre = cur;
            }
            cur = cur.next;
        }
        return head;
    }
}

Plus One

Given a non-negative number represented as an array of digits, plus one to the number.
The digits are stored such that the most significant digit is at the head of the list.
Solution:
从最后一位开始,对每一位进行加一,然后判断进位,如果有进位就继续到下一位,否则就可以返回了。
如果到了最高位进位仍然存在,重新new一个数组,把第一个为赋成1(因为只是加一操作,其余位一定是0,否则不会进最高位)。
一次扫描,所以算法复杂度是O(n),n是数组的长度。而空间上,一般情况是O(1),但是如果数是全9,那么是最坏情况,需要O(n)的额外空间。
public class Solution {
    public int[] plusOne(int[] digits) {
        if(digits == null || digits.length == 0)
            return null;
        
        for(int i = digits.length - 1; i >= 0; i--) {
            if(digits[i] + 1 == 10) {
                digits[i] = 0;
            }else {
                digits[i] = digits[i] + 1;
                return digits;
            }
        }
        
        //deal with the carry of the first number
        int[] res = new int[digits.length + 1];
        res[0] = 1;  
        //no need to copy the rest elements in digits, 
        //because when we have carry at the first number, 
        //this means that rest numbers in digits are already 0 now.
        return res;
    }
}

Reference: http://blog.csdn.net/linhuanmars/article/details/22365957

Follow up: Plus one,输入输出都是int,不能用+和-
Bit operator
&: 都是1, =1
|: 有1, = 1
^: 相同=0, 不同=1
~: 0->1, 1->0

Sunday, July 20, 2014

Length of Last Word

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.
Solution:
One pointer points to the end of string, then loop from right to left.
Run time complexity is O(n), constant space.
public class Solution {
    public int lengthOfLastWord(String s) {
        if(s == null || s.length() == 0)
            return 0;
        
        s = s.trim();  //get rid of space at beginning and end
        int count = 0;
        for(int i = s.length() - 1; i >= 0; i--) {
            if(s.charAt(i) != ' ') {
                count++;
            }else {
                return count;
            }
        }
        return count;
    }
}