# [Leetcode] Best Time to Buy and Sell Stock II

## Problem

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).

## Analysis

• Sum up all possible increase
• Time; O(n)
• Space; O(1)

Reference

# [Leetcode] Best Time to Buy and Sell Stock III

## Problem

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.

## Analysis

• 用一个数组pre记录在第i天或之前完成一个transaction的左右收益
• 用一个数组back记录从第i天或之后开始完成一个transaction的最大收益
• 则完成两个transactions的最大收益为 max(pre[i], back[i])

Reference

# [Leetcode] Best Time to Buy and Sell Stock

## Problem

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.

## Analysis

• 遍历数组，记录当前最小值，记录当前最大profit
• 当前profit = 当前值 – 当前最小值
• 时间复杂度: O(n)
• 空间复杂度: O(1)

# [Leetcode] Longest Increasing Subsequence

## Problem

Given an unsorted array of integers, find the length of longest increasing subsequence.
For example,
Given `[10, 9, 2, 5, 3, 7, 101, 18]`,
The longest increasing subsequence is `[2, 3, 7, 101]`, therefore the length is `4`. Note that there may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?

## Analysis

• 遍历所有的数字，同时维护一个valid数组，来保存当前扫描到的有用的数
• tail 表示当前valid数组的最后一个数，
• 对于当前读到的数x
• 如果x>tail，则把x append到数组中
• 如果x<valid数组的第一个数，则将其替换为x
• 否则，则二分查找到valid数组中第一个大于或等于x的数，替换为x
• 返回valid数组中有效的数个数

# [Leetcode] Two Sum

## Problem

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

## Analysis

• 用一个hash表来围护每个数和其对应的index
• 如果有重复的数字，则overwrite， 即保留最后出现的index
• 然后遍历所有的数，如果 （target – 当前数）在哈希表中，且俩数的index不一样，则找到解了
• 复杂度
• Time: O(n)
• Space: O(n)

## Code

Reference
[1] https://leetcode.com/problems/two-sum/

# [Leetcode] Reverse Words in a String

## Problem

Given an input string, reverse the string word by word.
For example,
Given s = “`the sky is blue`“,
return “`blue is sky the`“.

## Analysis

• 首先split string by space
• 然后 append word in reverse order
• 注意 如果当前非空，在append下一个word之前，需要append空格

Reference

# [Leetcode] Rotate image

## Problem

You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Could you do this in-place?

# [Leetcode] Peek Iterator

## Problem:

Given an Iterator class interface with methods: `next()` and `hasNext()`, design and implement a PeekingIterator that support the `peek()` operation — it essentially peek() at the element that will be returned by the next call to next().

Example:
Assume that the iterator is initialized to the beginning of the list: `[1, 2, 3]`.
Call `next()` gets you 1, the first element in the list.
Now you call `peek()` and it returns 2, the next element. Calling `next()` after that still return 2.
You call `next()` the final time and it returns 3, the last element. Calling `hasNext()` after that should return false.

## Analysis:

Iterator接口只提供了next() 和 hasNext() 函数

• next(), 取下一个元素，同时指针移到下下个元素
• hasNext(), 返回是否还有下一个元素

• peek()
• 如果cache有效，直接返回cache中的值。
• 否则，调用next函数取下一个元素放在cache中，并将cache设为有效
• next()
• 如果cache有效，则返回cache中的值，并将cache置为失效
• 否则，直接调用next函数
• hasNext()
• 如果cache有效，则直接返回true
• 否则，直接调用hasNext函数