Daily Archives: September 26, 2014

Leetcode: Best Time to Buy and Sell Stock

Posted on by
Reply

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Solution: One Pass O(n) time.

For each day i,

1. think of if sell it at day i, compare the profit with maxProfit.

2. check if day i is a better day than any previous day to buy a stock, meaning the price is cheaper than any previous day, then we buy the stock at day i.

public int maxProfit(int[] prices) {
    if (prices == null || prices.length <= 1) {
        return 0;
    }
    int maxProfit = 0;
    int sum = 0;
    int buyDate = 0;
    for (int i = 1; i < prices.length; i++) {
        maxProfit = Math.max(maxProfit, prices[i] - prices[buyDate]);
        if (prices[i] < prices[buyDate]) {
            buyDate = i;
        }
    }
    return maxProfit;
}

 

FacebookTwitterGoogle+Share

Leetcode: Search a 2D Matrix

Posted on by
Reply

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int start = 0;
        int end = m * n - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            int midVal = matrix[mid / n][mid % n];
            if (midVal == target) {
                return true;
            } else if (midVal > target) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return false;
    }
}

Note: O(log(m*n))

Leetcode: Binary Tree Level Order Traversal II

Posted on by
Reply

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new LinkedList<List<Integer>>();
        if (root == null) {
            return result;
        }
        List<TreeNode> currLevel = new LinkedList<TreeNode>();
        currLevel.add(root);
        while (currLevel.size() > 0) {
            result.add(0, new LinkedList<Integer>());
            List<TreeNode> nextLevel = new LinkedList<TreeNode>();
            while (currLevel.size() > 0) {
                TreeNode runner = currLevel.remove(0);
                result.get(0).add(runner.val);
                if (runner.left != null) {
                    nextLevel.add(runner.left);
                }
                if (runner.right != null) {
                    nextLevel.add(runner.right);
                }
            }
            currLevel = nextLevel;
        }
        return result;
    }
}