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

Code

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

Code

Reference
[1] https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

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

Code

Reference
[1] https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

[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数组中有效的数个数

时间复杂度: O(nlogn)

Code

Reference
[1] http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/
[2] https://leetcode.com/problems/longest-increasing-subsequence/

[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空格

Code


Reference

[Leetcode] Rotate image

Problem

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

Analysis

对于一个n*n的矩阵,可以像剥洋葱一样对每一层进行rotate,一共有n/2层

对于每一层,采用 matrix[i][j] = matrix[n-1-j][i] 进行 in-place的rotation

时间复杂度: O(n^2)
空间复杂度: O(n^2)

Code

[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() 函数只取下一个元素,而并不真正移动指针。即,peek如果多次连续被调用,返回的值应该不变 (一直是当前元素)。因此可以用next函数来取下一个元素,并将其cache,所以如果peek多次被调用,只需要返回cache中的值即可。

具体实现如下

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

Code: