Monthly Archives: August 2016

  1. LFU/All O one Data Structure

    Leave a comment

    August 31, 2016 by oneOokay

    LFU和All O`one Data Structure本质上都是一个double linkedlist和hashmap的结合体 Implement a data structure supporting the following operations: Inc(Key) – Inserts a new key with …
    Continue reading

  2. Largest Rectangle in Histogram

    Leave a comment

    August 25, 2016 by oneOokay

    类似:trapping-rain-water 以及相关应用: Maximal Rectangle 基本思想:对于一个heights[i],找出i向左的第一个小于它的数(heights[m])和i向右的第一个小于它的数(heights[n]),那么包含heights[i]这个点的最大的area是,height[m]之后一个数到heights[n]之前一个数的距离乘以heights[i] 需要了解一个叫做单调栈的概念:一个stack,里面的元素单调递增或者单调递减。 e.g: 构建一个单调递增栈:2,1,5,6,2,3 2=> 栈为空,push:2。    栈:[2 1=> 栈不为空,栈内peek=2,2 > 1,POP:2,push:1 。栈:[1  (area = 2 …
    Continue reading

  3. 544. 545.Top k Largest Numbers I II

    Leave a comment

    August 24, 2016 by oneOokay

    544. Top k largest numbers I Heap & Priority Queue 和quicksort的方法。 Heap & PriorityQueue:重点是:PriorityQueue/heap只能保证他的最顶点是整个结构的最小或最大值。除此以外的其他元素都是无序的,由于lintcode对输出有要求按从大到小排序,所以从heap里面取出来之后要重新排一下序。在求largest的问题的时候,需要用到minheap,最小堆。 public int[] topk(int[] nums, int k) …
    Continue reading

  4. 40. Implement Queue by 2 Stacks

    Leave a comment

    August 24, 2016 by oneOokay

      40. Implement Queue by 2 Stacks 2个stack:s1和s2:s1用来存正常的Queue.add(); s2用来存s1pop出来的数;s2若不为空,则当Queue.pop()时,应该从s2中pop;若s2为空,将s1中元素倒入s2中,再pop;

  5. Merge k sorted arrays

    Leave a comment

    August 23, 2016 by oneOokay

    Given k sorted integer arrays, merge them into one sorted array. 用一个size为k的PriorityQueue来解决: 把每一个array的第一个元素放入到PriorityQueue里面,放完之后要pop出一个数,加入到result array中,再到pop出的数属于的array中,放入第二个元素。所以这里怎么根据pop出来的数找到它原来的array呢?这里就需要构造一个自定义class了,里面需要包含row,col,val就可以了。 接着写好priorityQueue的comparator就可以了。 整个的时间复杂度是O(Nlogk)。空间复杂度是O(k)。 PriorityQueue:O(log n) performance for …
    Continue reading

  6. 129. Rehashing

    Leave a comment

    August 23, 2016 by oneOokay

    这题基本上是考linked list, 没有什么其他特别的。 public ListNode[] rehashing(ListNode[] hashTable) { // write your code here if (hashTable == null || hashTable.length <= …
    Continue reading

  7. k sum I II

    Leave a comment

    August 22, 2016 by oneOokay

    k sum: 基本看到了两种解法:2 sum的递归和dp 2 sum的递归见此:http://bangbingsyb.blogspot.com/2014/11/leetcode-4sum.html 好像不太适用与这个题目,因为引用参数以及返回参数都不一样。 (以后有空再研究一下吧,这个先放着做个参考) 所以还是先用dp from 九章:补充参考:http://www.cnblogs.com/yuzhangcmu/p/4279676.html 里面涉及了一个三维矩阵 int[][][],大概不用太去纠结它的具象吧。。。理解就好。 dp[i][j][t] 表示数组A的前i个数中,取j个数使其sum值为t的方案的个数 dp[i][0][0]: 数组A的前i个数,取0个数使其sum值为0的方案的个数为:1. (一个值都不取) public int kSum(int …
    Continue reading