Best Time to Buy and Sell Stock 系列问题

Best Time to Buy and Sell Stock

阅读全文

动态规划的一些常规性问题

###最长递增子序列问题(Longest Increasing Subsequence)

Given a sequence of integers, find the longest increasing subsequence (LIS).

阅读全文

Manacher's Algorithm 线性时间求字符串的最长回文字串

转自:http://www.felix021.com/blog/read.php?2040

首先用一个非常巧妙的方式,将所有可能的奇数/偶数长度的回文子串都转换成了奇数长度:在每个字符的两边都插入一个特殊的符号。比如 abba 变成 #a#b#b#a#, aba变成 #a#b#a#。 为了进一步减少编码的复杂度,可以在字符串的开始加入另一个特殊字符,这样就不用特殊处理越界问题,比如$#a#b#a#(注意,下面的代码是用C语言写就,由于C语言规范还要求字符串末尾有一个’\0’所以正好OK,但其他语言可能会导致越界)。

阅读全文

Sliding Window Maximum

使用双端队列保存进入窗口数字的下标,如果双端队列为空,那么插入;
如果队列的最后的下标所对应的数要大于当前的数,那么从后面插入当前的数,应为这个数可能是以后的最大值;
如果队列的最后的下标所对应的数要小于当前的数,那么将所有要小于当前数的元素都弹出去;
最后保证所有不在窗口内的数出队列;
队列最前面的数即为当时窗口的最大值。

阅读全文

Hash Heap

在Java的PriorityQueue中,有remove这一个函数,可以删除指定的元素。此时的时间复杂度为O(n),因为在删除之前得先遍历一遍数组,找到该元素。

但是如果对这个操作的调用比较频繁,那么我们就可以对这个函数进行改进,即用一个Hash Table存储每个元素的数组的下标,这样,删除元素时,我们不用遍历数组来找到该元素的位置,直接删除即可,时间复杂度为O(logn)。

阅读全文

LeetCode: Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

阅读全文

LeetCode: Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

阅读全文

LeetCode: Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.

Example

Given: 1 –> 2 –> 6 –> 3 –> 4 –> 5 –> 6, val = 6

阅读全文

LeetCode: Rectangle Area

Find the total area covered by two rectilinear rectangles in a 2D plane.

Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

阅读全文

LeetCode: Word Pattern

Given a pattern and a string str, find if str follows the same pattern.

Examples:

  • pattern = “abba”, str = “dog cat cat dog” should return true.

阅读全文