第八节数据结构

1.栈和队列

　　队列：BFS　　栈：DFS

　　例题：　　

　　(1)min stack:

　　思路：使用两个栈实现。第二个栈对应相应层为栈顶的最小值。

　　　　　更节省空间的方法是：相邻层如果值相同可用计数的机制来节省空间。

　　(2)Largest Rectangle in Histogram 思路：这道题暴力解法的时间复杂度是O(n^2),因此不太可能用动态规划。本题O(n)的解法是使用单调栈。计算以每个柱形为高的最大矩形，称为基于该柱形的最大矩形，这个最大矩形的左右两边一直延伸到两边第一个比当前柱形低的地方。使用单调栈的思想是：在该柱形出栈时计算基于它的最大矩形，并且单调栈保证了它出栈后的下一个栈顶元素是它左边第一个低于它的柱形，当前push的使它出栈的柱形 是 它右边第一个低于它的柱形。计算这两个柱形下标的差值加1就是该最大矩形的宽度。如果它出栈后栈空，说明它的左边没有低于它的柱形，则最大矩形的宽就直接等于当前push的使它出栈的柱形的下标。

(3)histogram近似题

　　　Maximal Rectangle

　　　Max Tree

　 (4)两个栈实现队列

　 (5)两个队列实现栈

2.hash

(1)hash函数：a.字符串的hash函数是O(n)时间复杂度的，其中n为字符串长度。

　　　　　　　b.用模运算的法则来避免计算hash函数溢出。(lintcode128题)

(2)hash表如何解决冲突？

open hashing vs closed hashing

(3)rehash(lintcode129题)

(4)LRU缓存

这题相当于自己实现LinkedHashMap。linkedHashMap是双链表与hash表的结合。

LRU策略：• Newest node append to tail. • Eldest node remove from head

3 heap

　　(1)掌握堆的原理（国内常考）：Heapify(lintcode130)，

　　(2)堆的应用：

　　　Ugly Number

　　　Top k Largest Number I and II...(其中Top k Largest Number I还能用快速选择).

　 ...

附：Top k Largest Number I的快速选择算法（平均时间复杂度O(N)）：

class Solution {
    /*
     * @param nums an integer array
     * @param k an integer
     * @return the top k largest numbers in array
     */
    public int[] topk(int[] nums, int k) {
        // Write your code here
        int[] res = new int[k];
        helper(nums, 0, nums.length - 1, k);
        List<Integer> result = new ArrayList<Integer>();
        for (int i = 0; i < k && i < nums.length; ++i)
            result.add(nums[i]);

        Collections.sort(result, Collections.reverseOrder());
        int[] topk = new int[k];
        for (int i = 0; i < k; ++i)
            topk[i] = result.get(i);

        return topk;
    }
    
    public void helper(int[] nums, int start, int end, int k){
        int target_index = randomSelect(start, end);
        int index = partition(nums, start, end, target_index);

        if (index - start + 1 == k) {
            return;
        } else if (index - start + 1 < k) {
            helper(nums, index + 1, end, k - (index - start + 1));
        } else {
            helper(nums, start, index - 1, k);
        }
    }
    
    public int partition(int[] nums, int start, int end, int target_index) {
        int i = start;
        int j = end;
        swap(nums, j--, target_index);
        while (i <= j) {
            if (nums[i] < nums[end]) {
                swap(nums, i, j--);
            } else {
                i++;
            }
        }
        swap(nums, i, end);
        return i;
    }
    
    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    
    public int randomSelect(int start, int end) {
        return (start + end) / 2;
    }
};

4. TreeMap:

　　平衡树的性能综合来看最好，以下操作都是O(lgn):

　　查找

　　删除任意节点

　　插入

　　查找小于给定值的最大值

　　查找大于给定值的最小值

应用：

　　building-outline

　　top-k-frequent-wordsII

　　Contains Duplicate III

　　LFU

第八节 数据结构

第八节数据结构