# 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 的做法

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

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

```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;
for (int i = 1; i < length; i++) {
maxProfitEndedAt[i] = Math.max(maxProfitEndedAt[i - 1], prices[i] - prices[buyDay]);
}
}
//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]);
}```

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 {
}
}
//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.

```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 tail;

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

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);
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) {
} else {
}
cache.put(newNode.key, newNode);
}

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