Merge k Sorted Lists
Merge k Sorted Lists @(算法)[算法, Divide and Conquer, Linked List, Priority Queue, Heap, Uber, Google,...
2016, Apr 16 — 1 minute readMerge k Sorted Lists @(算法)[算法, Divide and Conquer, Linked List, Priority Queue, Heap, Uber, Google,...
2016, Apr 16 — 1 minute readImplement Queue by Two Stacks @(算法)[算法, Stack, Queue] 这一题怎样用一句话描述？ 只用两个栈（FILO）实现一个队列（FIFO） 用到什么算法？什么数据结构？ 栈（Stack） 通过这题学到了什么？ 这一题非常有意思，用两个栈实现一个队列。想象一下一个栈装满了元素，而另一个栈为空，如下图： 通过图可以清楚的知道，左边栈的入栈序列是1->2->3，如果顺序出栈，出栈的序列就是3->2->1；如果把左边的栈元素依次出栈同时依次入右边的栈，那么右边的栈就会像这样被堆满：...
2016, Apr 15 — 1 minute readLongest Consecutive Sequence @(算法)[算法, Hash Table, Array] 这一题怎样用一句话描述？ 给出一个无序数组，找出最长的连续序列 用到什么算法？什么数据结构？ HashSet 通过这题学到了什么？ 这一题首先可以排序（O(nlogn)）然后再遍历一次排序后的数组（O(n)）。 不过题目的要求是O(n)的时间。 这里用到了hash表，不过可以不用HashMap类了，因为不需要Key-Value了，只需要知道hash表里有没有没有某个整数存在，所以直接使用HashSet。...
2016, Apr 14 — 1 minute readRehashing @(算法)[算法, Hash Table] 这一题怎样用一句话描述？ 这是一道模拟题，说的是hash表的长度是不定的，当有两个元素被hash函数map到同一个位置时，就要把hash表的长度加倍。这时候需要我们返回rehashing后的hash表 用到什么算法？什么数据结构？ 暴力，hash map 通过这题学到了什么？ hash map的迭代操作，有两种，第一种是可以同时拿到hash map中某一个位置的Key以及Value，参见Java官方文档，代码如下： for (Map.Entry<K,...
2016, Apr 13 — 1 minute readTop K Frequent Words @(算法)[算法, Hash Table, Heap, Priority Queue] 这一题怎样用一句话描述？ 给出一个字符串数组，以及一个整数K，返回出现次数前K多的字符串（从多到少，如果出现次数一样，则按字母顺序从小到大） 用到什么算法？什么数据结构？ HashMap，Priority Queue...
2016, Apr 12 — 1 minute read3Sum Closest @(算法)[算法, Two Pointers, Sort, Array] 这一题怎样用一句话描述？ 找出数组中三个不同的数字之和最接近给定值的组合 用到什么算法？什么数据结构？ 首先应该想到最暴力的解法，否则就是基本功不扎实了，所以O(n^3)的算法一定要会写 然后面试官肯能会问了，有没有办法优化呢？例如，优化成O(n^2)，这里是有方法的。也许我们第一个想到的会是动态规划，首先动归是用来找最优解的，契合这里的找最接近target的描述，不过动归主要是用来优化非线性时间的算法，假如暴力解已经是O(n^2)或者O(n^3)那么就不用考虑动归了。 这里的思路很简单，首先对数组排序，然后选定一个起点，再通过两个指针不断夹逼，举个例子： 给定数组和target S...
2016, Apr 12 — 1 minute read