总结

stack

最小栈

  • 保存当前元素前的最小元素

单调栈

  • 原理
    • 如果栈顶元素大于等于当前元素, 弹出栈顶, 这样能保持栈中元素单调递增, 这样栈顶便是比当前元素小的第一个元素
  • 什么时候用?
    • 为任意一个元素找它的左边和右边第一个比自己大/小的位置

Hash table

  1. 存在冲突
    1. Closed Hashing
      1. Linear Probing: f(i) = i
      2. Quadratic Probing: f(i) = i * i
      3. Double Hashing: f(i) = i * hash2(elem)
    2. Open Hashing
      • linkedlist
  2. 字符相同的不同字符串的Hashcode是不一样的比如 "abc" 和 "cba"
    1. 所以当需要判断他们为同一个的时候, 换成同一个顺序,再进行hash
    2. 如创建一个数组

Heap

  • 什么时候用?
    • 当出现top k, 前k个, 第k个 字眼的时候
    • 当输入数据是data stream, 即数据一个一个进来的情况, 并且需要排序
    • 当处理的数据是多个数组的时候, 数组需要可能需要排序. 
                        TreeMap     Heap    PriorityQueue

  1. Insert() logn logn logn

  2. Delete() logn logn O(n)

  3. Pop() logn logn logn

  4. Find() logn logn X

  5. Modify() logn logn X

  6. Min / Max() logn O(1) O(1)

  7. Upper / Lower logn X X

lower -> 大于Y的最小值

upper -> 小于Y的最大值

minHeap时间复杂度: O(nlogk)

TreeSet

  • 注意, 它的equals() 函数 依赖于comparator, 意味着, 修改着, 如果compare的数值一样, 意味着对象是相同的, 只会保留一个. 参考Trapping rain water
  • 主要函数
    • first() // 相当于peek(), O(1)
    • last() // O(1)
    • add()
    • contains()
    • pollFirst()
    • pollLast()
    • ceiling(E e) //Returns the least element in this set greater than or equal to the given element, ornullif there is no such element.
    • floor(E e) // Returns the greatest element in this set less than or equal to the given element, ornullif there is no such element.
    • higher(E e)
    • lower(E e) // comparator 顺序

Deque

results matching ""

    No results matching ""