Best Time to Buy and Sell Stock III

Best Time to Buy and Sell Stock III

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 at most two transactions.

Example

Given an example [4,4,6,1,1,4,2,5], return 6.

Note

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution: O(n) Time 先参考 Best Time to Buy and Sell Stock I 的做法

这次的不同点在与要做两次交易,所以我们要找一个分界点,分别算左右两边的一次交易利润和的最大值。所以我们可以做Best Time to Buy and Sell Stock I两次

第一次是从左到右扫[0-i]区间,也就是先确定buyDay,然后根据每个prices[i]来确定sellDay。

第二次是从右到左扫[i-end]区间,也就是先确定sellDay,然后根据每个prices[i]来确定buyDay。

所以这两个循环时间都是O(n)

最后我们要用一个循环来设分界点,然后取

max(maxProfitEndedAt[i]+maxProfitStartedFrom[i+1])

注意这个max不是最终答案,假设只有两天[1,2] 这种情况算下来是0,因为分界点两边都是1天不足以完成交易,而且有可能的情况是第一天买入,最后一天买进,这种情况按两次交易算也无法取到最大值,所以最后结果还要考虑到只做一次交易的情况,因为没有规定必须做两次交易

Math.max(maxWithTwoTransaction, maxProfitEndedAt[length - 1]);

这一部分的时间复杂度也是O(n)

所以整体的时间复杂度就是O(n)

public int maxProfit(int[] prices) {
    if (prices == null || prices.length <= 1) {
        return 0;
    }
    int length = prices.length;
    int[] maxProfitEndedAt = new int[length];
    int[] maxProfitStartedFrom = new int[length];

    //get the max profit from 0 to i with one transaction
    maxProfitEndedAt[0] = 0;
    int buyDay = 0;
    for (int i = 1; i < length; i++) {
        maxProfitEndedAt[i] = Math.max(maxProfitEndedAt[i - 1], prices[i] - prices[buyDay]);
        if (prices[i] < prices[buyDay]) {
            buyDay = i;
        }
    }
    //get the max profit form i to length-1 with one transaction
    maxProfitStartedFrom[length - 1] = 0;
    int sellDay = length - 1;
    for (int i = length - 2; i >= 0; i--) {
        maxProfitStartedFrom[i] = Math.max(maxProfitStartedFrom[i + 1], prices[sellDay] - prices[i]);
        if (prices[i] > prices[sellDay]) {
            sellDay = i;
        }
    }
    //to have two transactions
    //pick a pivot day i, to get the max(maxProfitEndedAt[i]+maxProfitStartedFrom[i+1])
    int maxWithTwoTransaction = 0;
    for (int i = 0; i < length - 2; i++) {
        maxWithTwoTransaction = Math.max(maxWithTwoTransaction,
                                         maxProfitEndedAt[i] + maxProfitStartedFrom[i + 1]);
    }
    return Math.max(maxWithTwoTransaction, maxProfitEndedAt[length - 1]);
}

 

FacebookTwitterGoogle+Share

Trailing Zeros

Trailing Zeros

Write an algorithm which computes the number of trailing zeros in n factorial.

Example

11! = 39916800, so the out should be 2

Challenge

O(log N) time

Solution: 只要找里面有多少个5, 乘出来就会有多少个0,因为2永远是够的

# of 5:n/5+n/25+n/(5^3)…..

public long trailingZeros(long n) {
    long base = 5;//important to use long type
    long count = 0;
    while (n >= base) {
        count += n / base;
        base *= 5;
    }
    return count;
}

Majority Number I & II & III

Majority Number I (找一个出现次数>1/2的数)

Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it.

Example

Given [1, 1, 1, 1, 2, 2, 2], return 1

Challenge

O(n) time and O(1) extra space

Solution: 用的抵消的思想,如果两个数不一样大,就相互抵消,一样大就保留, 用count计数

public int majorityNumber(ArrayList<Integer> nums) {
    int candidate = -1;
    int count = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (count == 0) {
            candidate = nums.get(i);
            count++;
        } else {
            if (candidate == nums.get(i)) {
                count++;
            } else {
                count--;
            }
        }
    }
    return candidate;
}

Majority Number II (找一个出现次数>1/3的数)

Given an array of integers, the majority number is the number that occurs more than 1/3 of the size of the array.

Find it.

Example

Given [1, 2, 1, 2, 1, 3, 3], return 1.

Note

There is only one majority number in the array.

Challenge

O(n) time and O(1) extra space.

Solution: 策略和I一样,只是现在有两个candidate,

public int majorityNumber(ArrayList<Integer> nums) {
    int candidate1 = -1;
    int candidate2 = -1;
    int count1 = 0;
    int count2 = 0;
    for (Integer num : nums) {
        if (candidate1 == num) {
            count1 ++;
        } else if (candidate2 == num) {
            count2 ++;
        } else if (count1 == 0) {
            candidate1 = num;
            count1 = 1;
        } else if (count2 == 0) {
            candidate2 = num;
            count2 = 1;
        } else {
            count1--;
            count2--;
        }
    }
    if (count1 == 0) {
        return candidate2;
    }
    if (count2 == 0) {
        return candidate1;
    }
    count1 = 0;
    count2 = 0;
    for (Integer num : nums) {
        if (num == candidate1) {
            count1++;
        }
        if (num == candidate2) {
            count2++;
        }
    }
    return count1 > count2 ? candidate1 : candidate2;
}

Majority Number III (找一个出现次数>1/k的数)

Given an array of integers and a number k, the majority number is the number that occurs more than 1/k of the size of the array.

Find it.

Example

Given [3,1,2,3,2,3,3,4,4,4] and k=3, return 3.

Note

There is only one majority number in the array.

Challenge

O(n) time and O(k) extra space

Solution: Similar approach as I & II

public int majorityNumber(ArrayList<Integer> nums, int k) {
    Map<Integer, Integer> majorityCounts = new HashMap<>();
    for (Integer num : nums) {
        if (majorityCounts.containsKey(num)) {
            majorityCounts.put(num, majorityCounts.get(num) + 1);
        } else {
            if (majorityCounts.size() < k - 1) {
                majorityCounts.put(num, 1);
            } else {
                List<Integer> toBeRemoved = new ArrayList<>();
                for (Integer key : majorityCounts.keySet()) {
                    if (majorityCounts.get(key) > 1) {
                        majorityCounts.put(key, majorityCounts.get(key) - 1);
                    } else {
                        toBeRemoved.add(key);
                    }
                }
                //important here: can not remove the element while iterating the set
                //which will cause ConcurrentModificationException
                for (Integer key : toBeRemoved) {
                    majorityCounts.remove(key);
                }
            }
        }
    }
    Set<Integer> results = majorityCounts.keySet();
    int maxCount = 0;
    int candidate = 0;
    for (Integer key : majorityCounts.keySet()) {
        majorityCounts.put(key, 0);
    }
    for (Integer num : nums) {
        if (majorityCounts.containsKey(num)) {
            int count = majorityCounts.get(num) + 1;
            majorityCounts.put(num, count);
            if (count > maxCount) {
                maxCount = count;
                candidate = num;
            }
        }
    }
    return candidate;
}

Max Tree

Max Tree

Given an integer array with no duplicates. A max tree building on this array is defined as follow:

  • The root is the maximum number in the array
  • The left subtree and right subtree are the max trees of the subarray divided by the root number.

Construct the max tree by the given array.

Example

Given [2, 5, 6, 0, 3, 1], the max tree constructed by this array is:

<code>    6
   / \
  5   3
 /   / \
2   0   1
</code>
Challenge

O(n) time and memory.

Solution: 用stack来维护在每个数出现前比它大得数。

策略:

When new node comes in, if it is larger than the peek, stack.pop() and at the same time append it as the new node’s left child. until the stack peek is larger than the new node or the stack is empty, at this time, the peek.right = new node. then we push new node into the stack. if the stack is empty when the new node is pushed, the new node is the temporary root.

用7,3,8,2,4,5走一遍就理解了

public TreeNode maxTree(int[] A) {
    if (A == null || A.length == 0) {
        return null;
    }
    Stack<TreeNode> stack = new Stack<>();
    TreeNode root = null;
    for (int i = 0; i < A.length; i++) {
        TreeNode curr = new TreeNode(A[i]);
        while (!stack.isEmpty() && A[i] >= stack.peek().val) {
            TreeNode tmp = stack.pop();
            tmp.right = curr.left;
            curr.left = tmp;
        }
        if (!stack.isEmpty()) {
            stack.peek().right = curr;
        } else {
            root = curr;
        }
        stack.push(curr);
    }
    return root;
}

LRU Cache

LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Solution: Use a doubly linked list, with a head and tail node pointers, as well as a hashMap with all the key and node pairs.

1. When get(), it first checks if the key is in the map, if it is, remove that node from its original position and move to the tail (right before the tail node). if it doesn’t exists, return -1.

2. When set(key, value), it first call get function, to see if it exists, them update the value, otherwise, check if the queue is full, then remove the first element (the one right after head node) and add the new node to the tail.

Set(), Get() O(1) Time.

public class Solution {
    public class Node {
        int key;
        int value;
        Node prev;
        Node next;
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
            this.prev = null;
            this.next = null;
        }
    }

    Map<Integer, Node> cache;
    int capacity;
    Node head;
    Node tail;

    public Solution(int capacity) {
        cache = new HashMap<>();
        this.capacity = capacity;
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (cache.containsKey(key)) {
            //remove it from its original place
            //put to the tail the queue
            Node node = cache.get(key);
            removeNode(node);
            addToTail(node);
            return node.value;
        }
        return -1;
    }

    public void set(int key, int value) {
        if (get(key) != -1) {
            cache.get(key).value = value;
            return;
        }
        Node newNode = new Node(key, value);
        if (cache.size() < capacity) {
            addToTail(newNode);
        } else {
            cache.remove(head.next.key);
            removeNode(head.next);
            addToTail(newNode);
        }
        cache.put(newNode.key, newNode);
    }

    public void addToTail(Node node) {
        node.prev = tail.prev;
        node.prev.next = node;
        node.next = tail;
        tail.prev = node;
    }

    public void removeNode(Node node) {
        if (node.prev != null) {
            node.prev.next = node.next;
        }
        if (node.next != null) {
            node.next.prev = node.prev;
        }
        node.next = null;
        node.prev = null;
    }
}