之前在简书上初步总结过几个有关栈和队列的数据结构设计的题目。http://www.jianshu.com/p/d43f93661631
1.线性数据结构
2.非线性数据结构
Tree HashMap Heap/PriorityQueue
3.HashSet HashMap HashTable的区别：
hashMap的键就组成一个HashSet
HashTble实现是基于Dictionary类，而HashMap是基于Map接口
HashTable是线程安全的，HashMap不是线程安全的，效率更高
HashTable不允许空键值，HashMap允许空键值。
4.Hash Function
4.1对于给定键值，产生一个固定的无规律的介于 0 ~ capacity之间的一个值
4.2再好的HashFunction也可能存在冲突，解决冲突的方法:开放定址法和拉链法。
4.3当hash不够大时，就需要rehash
5.Heap 支持O(logn)的添加，O(logn)的删除堆顶元素，O(1)的max/min(最大堆 Vs 最小堆) PriorityQueue heap的java实现
6.TreeMap 支持O(logn)的任意位置的查找删除，比起Heap，只是在min/max的获取上时间复杂度为O(logn)。
7.LRU:最近最少使用页面置换算法，淘汰最长时间未被使用的页面，关键是页面最后一次内使用到发生页面调度的时间长短。
LFU:最近最不常用页面置换算法，淘汰一定时期内被访问次数最少的页面，关键是看一定时期内页面被使用的频率。
8. HashMap Hashtable TreeMap LinkedHashMap的区别于联系
这四个类都是Map接口的实现类。Map主要用于存取键值对，根据键得到值，因此不允许键重复（覆盖机制），但允许值重复。 HashMap: 1. 访问数据很快，一般用于获取键值和查找是否包含某个键值
2. HashMap 最多允许一条记录的键为null, 允许多条值记录为null
3. 不是线程同步的 HashTable: 1. 相对于hashMap速度较慢
2. 键和值都不能为null
3. 是线程同步的 LinkedHashMap ：1.HashMap的一个子类，保存了记录的插入顺序。
2.在用Iterator遍历 LinkedHashMap 时，先得到的记录肯定是先插入的。
也可以在构造时用带参数按照应用次数排序。
3. 在遍历的时候会比HashMap慢，不过有种情况例外，当 HashMap容量
很大，实际数据较少时，遍历起来可能会比 LinkedHashMap慢因为
LinkedHashMap的遍历速度只和实际数据有关，和容量无关，而
HashMap的遍历速度和他的容量有关
4. 按应用次数排序需要在构造函数中传入true。
5. 也可指定LinkedHashMap的大小，使得大于某个size的时候删除最早来
的数据。
LinkedHashMap<Integer, Integer> lm = new LinkedHashMap<Integer, Integer>(10, (float) 0.75, true) {
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > 3;
}
}; TreeMap: TreeMap实现sortMap接口，能够让保存的记录根据键排序，可以通过自定义
比较器以实现自定义排序方法。
实现猫狗队列，猫类型和狗类型都继承自Pet类型
Pet类型如下
要求如下：
思路：
如果使用一个队列来存储，那么无法区分猫和狗；如果使用两个队列，那么pollAll()中猫和狗的先后顺序无法区分；继续思考时候可以使用一个时间戳，相当于一个map,键为pet,值为其如队列的时间，但是这带来一个问题就是同一个宠物多次进队列的问题。所以，采用新建一个数据结构PetEnterQueue类型，对之前的宠物进行封装。这个类型包含Pet和count两个变量，然后猫狗队列中实际存放的是这个PetEnterQueue的实例，如队列的时候可以检测时猫还是狗然后封装进count之后进入各自的队列（猫和狗），然后pollDog pollPet的时候自个儿弹就行了，pollAll的时候先弹出两个队列头的count较小的。
Animal Shelter
在一个宠物避难所里，仅有狗和猫两种动物可供领养，且领养时严格执行“先进先出”的规则。如果有人想要从避难所领养动物，他只有两种选择：要么选择领养所有动物中最资深的一只（根据到达避难所的时间，越早到的越资深），要么选择领养猫或狗（同样，也只能领养最资深的一只）。也就是说，领养者不能随意选择某一指定动物。请建立一个数据结构，使得它可以运行以上规则，并可实现 enqueue, dequeueAny, dequeueDog， 和 dequeueCat 操作。
public static final int DOG = 1;
public static final int CAT = 2;
private int stamp;
private Queue<PetEnqueue> dogQueue;
private Queue<PetEnqueue> catQueue;
public AnimalShelter() {
// do initialize if necessary
stamp = 0;
dogQueue = new LinkedList<PetEnqueue>();
catQueue = new LinkedList<PetEnqueue>();
} /**
* @param name a string
* @param type an integer, 1 if Animal is dog or 0
* @return void
*/
void enqueue(String name, int type) {
// Write your code here
if (type == DOG) {
dogQueue.offer(new PetEnqueue(name, stamp++));
} else {
catQueue.offer(new PetEnqueue(name, stamp++));
}
} public String dequeueAny() {
// Write your code here
if (dogQueue.isEmpty() && catQueue.isEmpty()) {
return "";
}
if (dogQueue.isEmpty()) {
return catQueue.poll().pet;
}
if (catQueue.isEmpty()) {
return dogQueue.poll().pet;
}
int dog_stamp = dogQueue.peek().stamp;
int cat_stamp = catQueue.peek().stamp;
if (dog_stamp < cat_stamp) {
return dogQueue.poll().pet;
} else {
return catQueue.poll().pet;
}
} public String dequeueDog() {
// Write your code here
if (dogQueue.isEmpty()) {
return "";
}
return dogQueue.poll().pet;
} public String dequeueCat() {
// Write your code here
if (catQueue.isEmpty()) {
return "";
}
return catQueue.poll().pet;
}
}
class PetEnqueue {
String pet;
int stamp;
public PetEnqueue(String pet, int stamp) {
this.pet = pet;
this.stamp = stamp;
}
Min Stack
Implement a stack with min() function, which will return the smallest number in the stack.
It should support push, pop and min operation all in O(1) cost.
方法一：使用两个栈,内容栈和最小栈同入同出
Stack<Integer> contentStack;
Stack<Integer> minStack; public MinStack() {
// do initialize if necessary
contentStack = new Stack<Integer>();
minStack = new Stack<Integer>();
minStack.push(Integer.MAX_VALUE);
} public void push(int number) {
// write your code here
contentStack.push(number);
minStack.push(minStack.peek() < number ? minStack.peek() : number);
} public int pop() {
// write your code here
minStack.pop();
return contentStack.pop();
} public int min() {
// write your code here
return minStack.peek();
}
方法二：使用两个栈。入栈的时候，只有当前元素小于等于最小栈栈顶才入栈，出栈的时候只有内容栈等于最小栈栈顶，才弹出最小栈的栈顶元素。
注意最小栈压栈的时候是和最小站中的元素比较。
Stack<Integer> contentStack;
Stack<Integer> minStack; public MinStack() {
// do initialize if necessary
contentStack = new Stack<Integer>();
minStack = new Stack<Integer>();
} public void push(int number) {
// write your code here
contentStack.push(number);
if (minStack.isEmpty() || number <= minStack.peek()) {
minStack.push(number);
}
} public int pop() {
// write your code here
int temp = contentStack.pop();
if (temp == minStack.peek()) {
minStack.pop();
}
return temp;
} public int min() {
// write your code here
return minStack.peek();
}
Stack Sorting
Sort a stack in ascending order (with biggest terms on top).
You may use at most one additional stack to hold items, but you may not copy the elements into any other data structure (e.g. array).
public void stackSorting(Stack<Integer> stack) {
// Write your code here
Stack<Integer> help = new Stack<Integer>();
while (!stack.isEmpty()) {
int val = stack.pop();
if (help.isEmpty() || val <= help.peek()) {
help.push(val);
} else {
int num = 0;
while(!help.isEmpty() && help.peek() < val) {
stack.push(help.pop());
num++;
}
help.push(val);
for (int i = 0; i < num; i++) {
help.push(stack.pop());
}
}
}
while (!help.isEmpty()) {
stack.push(help.pop());
}
}
Largest Rectangle in Histogram
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
public int largestRectangleArea(int[] height) {
// write your code here
if (height == null || height.length == 0) {
return 0;
}
int max = 0;
Stack<Integer> stack = new Stack<Integer>();
stack.push(-1);
for (int i = 0; i <= height.length; i++) {
int val = i == height.length ? -1 : height[i];
while(stack.peek() != -1 && val <= height[stack.peek()]){
int cur = stack.pop();
max = Math.max(max, height[cur] * (i - stack.peek() - 1));
}
stack.push(i);
}
return max;
}
Maximal Rectangle
Given a 2D boolean matrix filled with False and True, find the largest rectangle containing all True and return its area.
public int maximalRectangle(boolean[][] matrix) {
// Write your code here
if (matrix == null || matrix.length == 0) {
return 0;
}
int max = 0;
int m = matrix.length;
int n = matrix[0].length;
int[] height = new int[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j]) {
height[j] += 1;
} else {
height[j] = 0;
}
}
max = Math.max(max, maxRectangle(height));
}
return max;
}
public int maxRectangle(int[] height) {
int max = 0;
Stack<Integer> stack = new Stack<Integer>();
stack.push(-1);
for (int i = 0; i <= height.length; i++) {
int val = i == height.length ? -1 : height[i];
while (stack.peek() != -1 && val <= height[stack.peek()]) {
int cur = stack.pop();
max = Math.max(max, height[cur] * (i - stack.peek() - 1));
}
stack.push(i);
}
return max;
}
Max Tree ***** --not bug free
Given an integer array with no duplicates. A max tree building on this array is defined as follow:
The root is the maximum number in the array
The left subtree and right subtree are the max trees of the subarray divided by the root number.
Construct the max tree by the given array.
使用一个栈来记录子树，遍历原数组，如果新来的数小于栈顶树根节点的值，那么新节点作为子树放入栈中，如果新来的数大，那么进行弹出操作，弹出栈顶元素，如果此时栈为空，表明栈顶元素就是新来的数的左二子，否则，考察弹出之后的栈顶left,弹出的middle和当前讨论的right。现在有left right的值时大于middle的值的，那么middle应该挂在哪呢？这由left和right的值的大小关系决定，如果left的值大，则right.left = middle，否则就是right的值大，left.right = middle。同样为了处理5 4 3 2 1的情况，最后需要传进来一个大数把栈中元素都弹出。
public TreeNode maxTree(int[] A) {
// write your code here
if (A == null || A.length == 0) {
return new TreeNode(0);
}
Stack<TreeNode> stack = new Stack<TreeNode>();
for (int i = 0; i <= A.length; i++) {
TreeNode right = i == A.length ? new TreeNode(Integer.MAX_VALUE)
: new TreeNode(A[i]);
while (!stack.isEmpty() && right.val > stack.peek().val) {
TreeNode middle = stack.pop();
if (stack.isEmpty()) {
right.left = middle;
} else {
TreeNode left = stack.peek();
if (left.val < right.val) {
left.right = middle;
} else {
right.left = middle;
}
}
}
stack.push(right);
}
return stack.peek().left;
}
Implement Queue by Two Stacks
private Stack<Integer> stack1;
private Stack<Integer> stack2; public Queue() {
// do initialization if necessary
stack1 = new Stack<Integer>();
stack2 = new Stack<Integer>();
} public void push(int element) {
// write your code here
stack1.push(element);
} public int pop() {
// write your code here
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
} public int top() {
// write your code here
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.peek();
}
Implement Stack by Two Queues
Queue<Integer> data = new LinkedList<Integer>();
Queue<Integer> help = new LinkedList<Integer>();
// Push a new item into the stack
public void push(int x) {
// Write your code here
data.offer(x);
} // Pop the top of the stack
public void pop() {
// Write your code here
while (data.size() != 1) {
help.offer(data.poll());
}
data.poll();
while (!help.isEmpty()) {
data.offer(help.poll());
}
} // Return the top of the stack
public int top() {
// Write your code here
while (data.size() != 1) {
help.offer(data.poll());
} int result = data.peek();
help.offer(data.poll()); while (!help.isEmpty()) {
data.offer(help.poll());
}
return result;
} // Check the stack is empty or not.
public boolean isEmpty() {
// Write your code here
return data.isEmpty();
}
优化，交换queue1 queue2的指针：
Queue<Integer> queue1;
Queue<Integer> queue2;
public MyStack() {
queue1 = new LinkedList<Integer>();
queue2 = new LinkedList<Integer>();
} public void moveItems() {
while (queue1.size() > 1) {
queue2.offer(queue1.poll());
}
} public void swapQueues() {
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
} // Push element x onto stack.
public void push(int x) {
queue1.offer(x);
} // Removes the element on top of the stack.
public void pop() {
moveItems();
queue1.poll();
swapQueues();
} // Get the top element.
public int top() {
moveItems();
int val = queue1.poll();
queue2.offer(val);
swapQueues();
return val;
} // Return whether the stack is empty.
public boolean empty() {
return queue1.isEmpty();
}
Implement Stack
Implement a stack. You can use any data structure inside a stack except stack itself to implement it.
Node dummyHead;
Node dummyEnd;
public Stack() {
dummyHead = new Node(0);
dummyEnd = new Node(0);
dummyHead.next = dummyEnd;
dummyEnd.prev = dummyHead;
}
// Push a new item into the stack
public void push(int x) {
// Write your code here
Node cur = new Node(x);
cur.next = dummyHead.next;
cur.next.prev = cur;
dummyHead.next = cur;
cur.prev = dummyHead;
} // Pop the top of the stack
public void pop() {
// Write your code here
dummyHead.next = dummyHead.next.next;
dummyHead.next.prev = dummyHead;
} // Return the top of the stack
public int top() {
// Write your code here
return dummyHead.next.val;
} // Check the stack is empty or not.
public boolean isEmpty() {
// Write your code here
return dummyHead.next == dummyEnd;
}
}
class Node {
int val;
Node prev;
Node next;
public Node(int val) {
this.val = val;
}
Implement Queue by Linked List
Node dummyHead;
Node dummyEnd;
public Queue() {
// do initialize if necessary
dummyHead = new Node(0);
dummyEnd = new Node(0);
dummyHead.prev = dummyEnd;
dummyEnd.next = dummyHead;
} public void enqueue(int item) {
// Write your code here
Node cur = new Node(item);
cur.next = dummyEnd.next;
dummyEnd.next.prev = cur;
dummyEnd.next = cur;
cur.prev = dummyEnd;
} public int dequeue() {
// Write your code here
if (dummyEnd.next == dummyHead) {
return Integer.MAX_VALUE;
}
Node top = dummyHead.prev;
top.prev.next = dummyHead;
dummyHead.prev = top.prev;
return top.val;
} class Node {
int val;
Node next;
Node prev;
public Node(int val) {
this.val = val;
}
}
Implement Queue by Linked List II
private LinkedList<Integer> list;
public Dequeue() {
// do initialize if necessary
list = new LinkedList<Integer>();
}
public void push_front(int item) {
// Write your code here
list.add(item);
}
public void push_back(int item) {
// Write your code here
list.addFirst(item);
}
public int pop_front() {
// Write your code here
return list.removeLast();
}
public int pop_back() {
// Write your code here
return list.removeFirst();
}
Hash Function --not bug free
public int hashCode(char[] key,int HASH_SIZE) {
// write your code here
long ans = 0;
for (int i = 0; i < key.length; i++) {
ans = (ans * 33 + (int)key[i]) % HASH_SIZE;
}
return (int)ans;
}
Rehashing
The size of the hash table is not determinate at the very beginning. If the total size of keys is too large (e.g. size >= capacity / 10), we should double the size of the hash table and rehash every keys.
public ListNode[] rehashing(ListNode[] hashTable) {
// write your code here
if (hashTable == null || hashTable.length == 0) {
return hashTable;
}
int oldCapacity = hashTable.length;
int newCapacity = oldCapacity * 2;
ListNode[] reHash = new ListNode[newCapacity];
for (int i = 0; i < oldCapacity; i++) {
ListNode cur = hashTable[i];
help(cur, reHash);
}
return reHash;
}
public void help(ListNode cur, ListNode[] reHash) {
if (cur == null) {
return;
}
int newCapacity = reHash.length;
help(cur.next, reHash);
int pos = (cur.val % newCapacity + newCapacity) % newCapacity;
ListNode next = reHash[pos];
reHash[pos] = new ListNode(cur.val);
reHash[pos].next = next;
}
LRU Cache **
注意访问过就要更新在后边
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
public class Solution {
HashMap<Integer, Node> hashMap;
int capacity;
int size;
Node dummyHead;
Node dummyEnd;
// @param capacity, an integer
public Solution(int capacity) {
// write your code here
hashMap = new HashMap<Integer, Node>();
this.capacity = capacity;
size = 0;
dummyHead = new Node(0,0);
dummyEnd = new Node(0,0);
dummyEnd.next = dummyHead;
dummyHead.prev = dummyEnd;
}
// @return an integer
public int get(int key) {
// write your code here
if (hashMap.containsKey(key)) {
set(key, hashMap.get(key).val);
return hashMap.get(key).val;
} else {
return -1;
}
}
// @param key, an integer
// @param value, an integer
// @return nothing
public void set(int key, int value) {
// write your code here
if (hashMap.containsKey(key)) {
Node oldNode = hashMap.get(key);
oldNode.prev.next = oldNode.next;
oldNode.next.prev = oldNode.prev;
} else {
if (size == capacity) {
Node realHead = dummyHead.prev;
realHead.prev.next = dummyHead;
dummyHead.prev = realHead.prev;
hashMap.remove(realHead.key);
} else {
size++;
}
}
Node newNode = new Node(key, value);
dummyEnd.next.prev = newNode;
newNode.next = dummyEnd.next;
newNode.prev = dummyEnd;
dummyEnd.next = newNode;
hashMap.put(key, newNode);
}
}
class Node {
int key;
int val;
Node prev;
Node next;
public Node(int key, int val) {
this.key = key;
this.val = val;
prev = null;
next = null;
}
}
LFU Cache
由于需要检测是有出现过某个键，所以需要一个hashMap，其对应的值为我们定义的Node。
这里主要有两种想法，其一使用一个PriorityQueue，按照出现次数建立一个minHeap，问题在于这里设立Pq的删除任意位置结点的操作，比较费时间。
另一种想法是直接使用TreeMap，这样本身就可以检测是否包含某个键，但是这里的问题在于TreeMap需要的是依照Value的大小顺序来排序，这是非常不方便的。
另外，这里假如frequency都相等的话，需要先拿走最先进入的，这里需要引入一个时间戳来记录这一个属性。
LFU (Least Frequently Used) is a famous cache eviction algorithm.
For a cache with capacity k, if the cache is full and need to evict a key in it, the key with the lease frequently used will be kicked out.
Implement set and get method for LFU cache.
方法一：PQ
long stamp;
int capacity;
int num;
PriorityQueue<Pair> minHeap;
HashMap<Integer, Pair> hashMap; // @param capacity, an integer
public LFUCache(int capacity) {
// Write your code here
this.capacity = capacity;
num = 0;
minHeap = new PriorityQueue<Pair>();
hashMap = new HashMap<Integer, Pair>();
stamp = 0;
} // @param key, an integer
// @param value, an integer
// @return nothing
public void set(int key, int value) {
// Write your code here
if (hashMap.containsKey(key)) {
Pair old = hashMap.get(key);
minHeap.remove(old); Pair newNode = new Pair(key, value, old.times + 1, stamp++); hashMap.put(key, newNode);
minHeap.offer(newNode);
} else if (num == capacity) {
Pair old = minHeap.poll();
hashMap.remove(old.key); Pair newNode = new Pair(key, value, 1, stamp++); hashMap.put(key, newNode);
minHeap.offer(newNode);
} else {
num++;
Pair pair = new Pair(key, value, 1, stamp++);
hashMap.put(key, pair);
minHeap.offer(pair);
}
} public int get(int key) {
// Write your code here
if (hashMap.containsKey(key)) {
Pair old = hashMap.get(key);
minHeap.remove(old); Pair newNode = new Pair(key, old.value, old.times + 1, stamp++); hashMap.put(key, newNode);
minHeap.offer(newNode);
return hashMap.get(key).value;
} else {
return -1;
}
} class Pair implements Comparable<Pair> {
long stamp;
int key;
int value;
int times;
public Pair(int key, int value, int times, long stamp) {
this.key = key;
this.value = value;
this.times = times;
this.stamp = stamp;
} public int compareTo(Pair that) {
if (this.times == that.times) {
return (int)(this.stamp - that.stamp);
} else {
return this.times - that.times;
}
}
}
方法二：TreeMap
今天重新使用treeMap来实现，treeMap的键就是我们自己定义的那个Pair
private int stamp;
private int capacity;
private TreeMap<Pair, Integer> treeMap;
private HashMap<Integer, Pair> hashMap;
// @param capacity, an integer
public LFUCache(int capacity) {
// Write your code here
stamp = 0;
this.capacity = capacity;
treeMap = new TreeMap<Pair, Integer>();
hashMap = new HashMap<Integer, Pair>();
} // @param key, an integer
// @param value, an integer
// @return nothing
public void set(int key, int value) {
// Write your code here
if (hashMap.containsKey(key)) {
Pair old = hashMap.get(key);
treeMap.remove(old);
Pair newPair = new Pair(value, old.times + 1, stamp++);
treeMap.put(newPair, key);
hashMap.put(key, newPair);
} else {
if (treeMap.size() == capacity) {
Map.Entry<Pair, Integer> min = treeMap.pollFirstEntry();
hashMap.remove(min.getValue());
}
Pair newPair = new Pair(value, 1, stamp++);
treeMap.put(newPair, key);
hashMap.put(key, newPair);
}
} public int get(int key) {
// Write your code here
if (!hashMap.containsKey(key)) {
return -1;
}
Pair old = hashMap.get(key);
treeMap.remove(old);
Pair newPair = new Pair(old.value, old.times + 1, stamp++);
treeMap.put(newPair, key);
hashMap.put(key, newPair);
return old.value;
} class Pair implements Comparable<Pair> {
int value;
int times;
int stamp;
public Pair(int value, int times, int stamp) {
this.value = value;
this.times = times;
this.stamp = stamp;
} public int compareTo(Pair that) {
if (this.times == that.times) {
return this.stamp - that.stamp;
} else {
return this.times - that.times;
}
}
}
Top K Frequent Words**
语法细节容易出错。
Given a list of words and an integer k, return the top k frequent words in the list.、
方法一：获取频数之后，进行排序之后取出前k大。O(n + mlogm)
方法二：保持一个大小为k的最小堆，比方法一效率更高。O(n + klog(k))
Top K Frequent Words II--not bug free
对比LFU,LFU是新来的有最大的优先级，而这里新来的并不具有最大的优先级，而是所有次数才具有最大的优先级。
方法一：PQ
方法二：TreeMap 和LFU不同的是，这里其实TreeMap的值已经不起作用了，因为我们并不需要根据删除的treeMap节点去更新hashMap节点。
int k;
HashMap<String, Pair> hashMap;
TreeMap<Pair, String> treeMap;
public TopK(int k) {
// initialize your data structure here
this.k = k;
hashMap = new HashMap<String, Pair>();
treeMap = new TreeMap<Pair, String>();
} public void add(String word) {
// Write your code here
if (!hashMap.containsKey(word)) {
Pair pair = new Pair(word, 1);
hashMap.put(word, pair);
treeMap.put(pair, word);
if (treeMap.size() > k) {
treeMap.pollFirstEntry();
}
} else {
Pair oldPair = hashMap.get(word);
treeMap.remove(oldPair);
Pair newPair = new Pair(word, oldPair.times + 1);
hashMap.put(word, newPair);
treeMap.put(newPair, word);
if (treeMap.size() > k) {
treeMap.pollFirstEntry();
}
}
} public List<String> topk() {
// Write your code here
List<Pair> temp = new ArrayList<Pair>(treeMap.keySet());
Collections.sort(temp);
LinkedList<String> results = new LinkedList<String>();
for (Pair pair : temp) {
results.addFirst(pair.val);
}
return results;
} class Pair implements Comparable<Pair> {
String val;
int times;
public Pair(String val, int times) {
this.val = val;
this.times = times;
}
public int compareTo(Pair that) {
if (this.times == that.times) {
return that.val.compareTo(this.val);
} else {
return this.times - that.times;
}
}
}
Anagrams
注意字符数组转字符串是用的String.ValueOf(), 并不是toString.
Given an array of strings, return all groups of strings that are anagrams.
方法一：字符串排序之后作为键
public List<String> anagrams(String[] strs) {
// write your code here
if (strs == null || strs.length < 2) {
return new ArrayList<String> ();
}
HashMap<String, List<String>> hashMap = new HashMap<String, List<String>>();
for (int i = 0; i < strs.length; i++) {
char[] chars = strs[i].toCharArray();
Arrays.sort(chars);
String temp = String.valueOf(chars);
if (!hashMap.containsKey(temp)) {
hashMap.put(temp, new ArrayList<String>());
}
hashMap.get(temp).add(strs[i]);
}
List<String> result = new ArrayList<String>();
for (String str : hashMap.keySet()) {
List<String> tmpList = hashMap.get(str);
if (tmpList.size() > 1) {
for (String str1 : tmpList) {
result.add(str1);
}
}
}
return result;
}
方法二：使用hash作为键
public int getHash(int[] count) {
int a = 378551;
int b = 63689;
int hash = 0;
for (int tmp : count) {
hash = hash * a + tmp;
a = a * b;
}
return hash;
}
public List<String> anagrams(String[] strs) {
// write your code here
if (strs == null || strs.length == 0) {
return new ArrayList<String>();
}
List<String> results = new ArrayList<String>();
HashMap<Integer, List<String>> hashMap = new HashMap<Integer, List<String>>();
for (int i = 0; i < strs.length; i++) {
int[] count = new int[26];
for (int j = 0; j < strs[i].length(); j++) {
count[strs[i].charAt(j) - 'a']++;
}
int hash = getHash(count);
if (!hashMap.containsKey(hash)) {
hashMap.put(hash, new ArrayList<String>());
}
hashMap.get(hash).add(strs[i]);
}
for (Integer tmp : hashMap.keySet()) {
if (hashMap.get(tmp).size() > 1) {
results.addAll(hashMap.get(tmp));
}
}
return results;
}
Longest Consecutive Sequence **
主要是思路。
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
public int longestConsecutive(int[] num) {
// write you code here
if (num == null || num.length == 0) {
return 0;
}
int result = 0;
HashSet<Integer> hashSet = new HashSet<Integer>();
for (int i = 0; i < num.length; i++) {
hashSet.add(num[i]);
}
for (int i = 0; i < num.length; i++) {
int down = num[i] - 1;
while (hashSet.contains(down)) {
hashSet.remove(down);
down--;
}
int up = num[i] + 1;
while (hashSet.contains(up)) {
hashSet.remove(up);
up++;
}
result = Math.max(result, up - down - 1);
if (result >= hashSet.size()) {
break;
}
}
return result;
}
Heapify***--not bug free
之前思路错误[1,7,4,8,9,5,6],不要试图去交换已经处理好了的两个孩子，这会引发问题。
Given an integer array, heapify it into a min-heap array.
For a heap array A, A[0] is the root of heap, and for each A[i], A[i * 2 + 1] is the left child of A[i] and A[i * 2 + 2] is the right child of A[i].
public void heapify(int[] A) {
// write your code here
if (A == null || A.length == 0) {
return ;
}
for (int i = A.length / 2; i >= 0; i--) {
siftDown(A, i);
}
}
private void siftDown(int[] A, int k) {
while (k < A.length) {
int smallest = k;
if (2 * k + 1 < A.length && A[2 * k + 1] < A[smallest]) {
smallest = 2 * k + 1;
}
if (2 * k + 2 < A.length && A[2 * k + 2] < A[smallest]) {
smallest = 2 * k + 2;
}
if (smallest == k) {
break ;
} else {
swap(A, k, smallest);
k = smallest;
}
}
}
private void swap(int[] A, int i, int j) {
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
Ugly Number II --not bug free
注意可能会出现 fact2, fact3, fact5不仅一个等于min的情况，这是相应的index都要增加,所以不能用else来分支判断。
Ugly number is a number that only have factors 2, 3 and 5.
Design an algorithm to find the nth ugly number. The first 10 ugly numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
public int nthUglyNumber(int n) {
// Write your code here
if (n <= 0) {
return 0;
}
int[] uglys = new int[n];
uglys[0] = 1;
int index2 = 0;
int index3 = 0;
int index5 = 0;
int fact2 = 2;
int fact3 = 3;
int fact5 = 5;
for (int i = 1; i < n; i++) {
int min = Math.min(fact2, Math.min(fact3, fact5));
uglys[i] = min;
if (min == fact2) {
fact2 = uglys[++index2] * 2;
}
if (min == fact3) {
fact3 = uglys[++index3] * 3;
}
if (min == fact5) {
fact5 = uglys[++index5] * 5;
}
}
return uglys[n - 1];
}
Top k Largest Numbers --not bug free
好几次都不能bug free。易错点：最后输出是从大到小；getPivo容易直接返回下标了。。；i <= j都要交换，不然导致死循环例如：54321，pivot选了1；quickSelect最后忘记递归的调用
。。。。我这都是在干啥。。。。
Given an integer array, find the top k largest numbers in it.
public int[] topk(int[] nums, int k) {
// Write your code here
if (nums == null || nums.length == 0 || nums.length < k) {
return new int[0];
}
quickSelect(nums, 0, nums.length - 1, k);
// ArrayList<Integer> list = new ArrayList<Integer>();
// for (int i = 0; i < k; i++) {
// list.add(nums[i]);
// }
// Collections.sort(list, Collections.reverseOrder());
int[] result = new int[k];
for (int i = 0; i < k; i++) {
// result[i] = list.get(i);
result[i] = nums[i];
}
return result;
}
private void quickSelect(int[] nums, int left, int right, int k) {
if (left >= right) {
return ;
}
int pivot = getPivot(nums, left, right);
int i = left;
int j = right;
while (i <= j) {
while (i <= j && nums[i] > pivot) {
i++;
}
while (i <= j && nums[j] < pivot) {
j--;
}
if (i <= j) {
swap(nums, i, j);
i++;
j--;
}
}
if (k <= i) {
quickSelect(nums, left, i - 1, k);
} else {
quickSelect(nums, left, i - 1, k);
quickSelect(nums, i, right, k);
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private int getPivot(int[] nums, int left, int right) {
Random random = new Random();
int index = random.nextInt(right - left + 1);
return nums[left + index];
}
Top k Largest Numbers II --not bug free
注意堆中只是保存了最大的k个数,而这些数并不是大小有序的。
Implement a data structure, provide two interfaces:
add(number). Add a new number in the data structure.topk(). Return the top k largest numbers in this data structure. k is given when we create the data structure.private int k;
PriorityQueue<Integer> minHeap; public Solution(int k) {
// initialize your data structure here.
this.k = k;
minHeap = new PriorityQueue<Integer>();
} public void add(int num) {
// Write your code here
minHeap.offer(num);
if (minHeap.size() > k) {
minHeap.poll();
}
} public List<Integer> topk() {
// Write your code here
List<Integer> result = new ArrayList<Integer>();
result.addAll(minHeap);
Collections.sort(result, Collections.reverseOrder());
return result;
}
Merge k Sorted Arrays
Given k sorted integer arrays, merge them into one sorted array.
三种方法：
分治
Heap
merge two by two
merge list给出了三种方法，这里只实现一种。
public List<Integer> mergekSortedArrays(int[][] arrays) {
// Write your code here
ArrayList<Integer> results = new ArrayList<Integer>();
if (arrays == null || arrays.length == 0) {
return results;
}
int m = arrays.length;
int n = arrays[0].length;
PriorityQueue<Element> minHeap = new PriorityQueue<Element>();
for (int i = 0; i < m; i++) {
if (arrays[i].length == 0) {
continue;
}
minHeap.offer(new Element(arrays[i][0], i, 0));
}
while (!minHeap.isEmpty()) {
Element top = minHeap.poll();
results.add(top.val);
if (top.col + 1 < arrays[top.row].length) {
minHeap.add(new Element(arrays[top.row][top.col + 1], top.row, top.col + 1));
}
}
return results;
}
}
class Element implements Comparable<Element> {
int val;
int row;
int col;
public Element(int val, int row, int col) {
this.val = val;
this.row = row;
this.col = col;
}
public int compareTo(Element eleB) {
return val - eleB.val;
}
Find Median from Data Stream ***
主要是思路。大堆存较小的数，小堆存较大的数。保证大堆 size 大于等于小堆 size。
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
PriorityQueue<Integer> maxHeap;
PriorityQueue<Integer> minHeap; public MedianFinder() {
maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder());
minHeap = new PriorityQueue<Integer>();
} // Adds a number into the data structure.
public void addNum(int num) {
maxHeap.offer(num);
minHeap.offer(maxHeap.poll());
if (maxHeap.size() < minHeap.size()) {
maxHeap.offer(minHeap.poll());
}
} // Returns the median of current data stream
public double findMedian() {
if (maxHeap.size() == 0) {
return 0;
}
if (maxHeap.size() == minHeap.size()) {
return (minHeap.peek() + maxHeap.peek()) * 0.5;
} else {
return maxHeap.peek();
}
}
Data Stream Median
同上题，要求稍微不同，接口不同。
Numbers keep coming, return the median of numbers at every time a new number added.
public int[] medianII(int[] nums) {
// write your code here
if(nums == null || nums.length == 0) {
return new int[0];
}
PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(nums.length, Collections.reverseOrder());//java 1.7
int[] result = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
maxHeap.offer(nums[i]);
minHeap.offer(maxHeap.poll());
if (maxHeap.size() < minHeap.size()) {
maxHeap.offer(minHeap.poll());
}
result[i] = maxHeap.peek();
}
return result;
}
Kth Smallest Number in Sorted Matrix**
Find the kth smallest number in at row and column sorted matrix.
public int kthSmallest(int[][] matrix, int k) {
// write your code here
if (matrix == null || matrix[0].length == 0) {
return -1;
}
int m = matrix.length;
int n = matrix[0].length;
PriorityQueue<Tuple> minHeap = new PriorityQueue<Tuple>();
for (int j = 0; j < n; j++) {
minHeap.offer(new Tuple(0, j, matrix[0][j]));
}
for (int i = 0; i < k - 1; i++) {
if (minHeap.size() == 0) {
return -1;
}
Tuple temp = minHeap.poll();
if (temp.x == m - 1) {
continue;
} else {
minHeap.offer(new Tuple(temp.x + 1, temp.y, matrix[temp.x + 1][temp.y]));
}
}
return minHeap.poll().val;
}
class Tuple implements Comparable<Tuple>{
int x;
int y;
int val;
public Tuple(int x, int y, int val) {
this.x = x;
this.y = y;
this.val = val;
}
public int compareTo(Tuple that) {
return this.val - that.val;
}
}
The Skyline Problem *****
大楼轮廓问题。之前不会解这个问题，在老师提示使用TreeMap之后，看了一个使用PriorityQueue的解法之后，改为使用TreeMap,效率得到了很大的提高。
解法思想：
首先对于每一个building,都提取处其左上角点和右上角点，提取的单位为一个大小为二的数组，height[0]为横坐标， height[1]位纵坐标或者纵坐标的负，这取决于是左上角点还是右上角点，放到height中。
然后根据横坐标的大小，对height进行排序。（横坐标相同的纵坐标小的排在前面 *1）
遍历height数组，如果遇到左上角点，就把这个点加入TreeMap，如果遇到右上角点，就把这个点对应的左上角点从TreeMap中弹出。TreeMap 键为height单元的高度，值为这个高度出现的次数（相比于PQ,这里记录次数的原因是treeMap不允许重复键值）。
使用变量key来记录之前的有效高度。每次弹出或者压入TreeMap之后，检测当前TreeMap的顶部（相当于最大堆，也就是最大高度）的高度，如果这个高度和prev不相等，往结果中加入一个新的点，更新prev。
*1这里是很关键的，相同的横坐标，纵坐标小的排在前边，不然的话，前边大的弹出的时候会往结果写入一个新点，后边小的压入的时候也会往结果写入一个新点。而其实这里顶多引入一个新点的。
*2之前对于以下这种情况还有点担心：[[1,2,2],[2,3,2]]
其实有了之前的规则，这种情况也是能够正确处理的。首先第二个左边由于是负数，所以他们的横坐标相同，按照纵坐标小的原则来排序的话，(2,-2) 是排在 (2,2) 的前面的，没有任何问题。
public List<int[]> getSkyline(int[][] buildings) {
List<int[]> result = new ArrayList<int[]>();
if (buildings == null || buildings.length == 0) {
return result;
}
List<int[]> height = new ArrayList<int[]>();
for (int i = 0; i < buildings.length; i++) {
height.add(new int[] {buildings[i][0], -buildings[i][2]});
height.add(new int[] {buildings[i][1], buildings[i][2]});
}
Collections.sort(height, new Comparator<int[]> () {
public int compare(int[] a, int[] b) {
if (a[0] == b[0]) {
return a[1] - b[1];
} else {
return a[0] - b[0];
}
}
});
TreeMap<Integer, Integer> treeMap = new TreeMap<Integer,Integer> (Collections.reverseOrder());
int prev = 0;
treeMap.put(0,1);
for (int[] h : height) {
if (h[1] < 0) {
Integer times = treeMap.get(-h[1]);
if (times == null) {
treeMap.put(-h[1], 1);
} else {
treeMap.put(-h[1], times + 1);
}
} else {
Integer times = treeMap.get(h[1]);
if (times == 1) {
treeMap.remove(h[1]);
} else {
treeMap.put(h[1], times - 1);
}
}
int cur = treeMap.firstKey();
if (cur != prev) {
result.add(new int[] {h[0], cur});
prev = cur;
}
}
return result;
}
Building Outline
lintcode上相似的题目,只是最后徐亚返回的结果稍微不同。
Given 3 buildings：
[
[1, 3, 3],
[2, 4, 4],
[5, 6, 1]
]
The outlines are：
[
[1, 2, 3],
[2, 4, 4],
[5, 6, 1]
]
public ArrayList<ArrayList<Integer>> buildingOutline(int[][] buildings) {
// write your code here
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
if (buildings == null || buildings.length == 0) {
return result;
}
List<int[]> height = new ArrayList<int[]>();
for (int i = 0; i < buildings.length; i++) {
height.add(new int[] {buildings[i][0], -buildings[i][2]});
height.add(new int[] {buildings[i][1], buildings[i][2]});
}
Collections.sort(height, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
if (a[0] != b[0]) {
return a[0] - b[0];
} else {
return a[1] - b[1];
}
}
});
List<int[]> points = new ArrayList<int[]>();
int prev = 0;
TreeMap<Integer, Integer> treeMap = new TreeMap<Integer, Integer>(
Collections.reverseOrder()
);
treeMap.put(0,1);
for (int[] h : height) {
if (h[1] < 0) {
Integer times = treeMap.get(-h[1]);
if (times == null) {
treeMap.put(-h[1], 1);
} else {
treeMap.put(-h[1], times + 1);
}
} else {
Integer times = treeMap.get(h[1]);
if (times == 1) {
treeMap.remove(h[1]);
} else {
treeMap.put(h[1], times - 1);
}
}
int cur = treeMap.firstKey();
if (cur != prev) {
points.add(new int[]{h[0], cur});
prev = cur;
}
}
for (int i = 0; i < points.size() - 1; i++) {
if (points.get(i)[1] != 0) {
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(points.get(i)[0]);
list.add(points.get(i + 1)[0]);
list.add(points.get(i)[1]);
result.add(list);
}
}
return result;
}
H-Index ***
https://leetcode.com/problems/h-index/
这个题还是有些绕的，主要是题意搞得有点晕了。最后题意应该是：h 为 h篇文章的引用至少为h，其余N-h篇文章的引用至多为h。（另外一种错误的理解是引用大于h的至少h篇）
方法一：hashtable
新建一个数组来存储每个引用分别有多少篇文章，由于h最多为文章总数len，所以对于那些引用大于文章总数len的，就把这些文章也加载引用为len次的元素位置。然后从这个数组末尾开始遍历。
使用一个tmp来存储文章数目，遍历到cur，首先更新tmp，表示引用大于等于cur的文章共有tmp篇。如果tmp>=cur,则可以返回cur.
class Solution(object):
def hIndex(self, citations):
"""
:type citations: List[int]
:rtype: int
"""
if not citations:
return 0
length = len(citations)
articleNum = [0]*(length + 1)
for i in range(length):
if citations[i] >= length:
articleNum[length] += 1
else:
articleNum[citations[i]] += 1
tmp = 0
for i in range(length, -1, -1):
tmp += articleNum[i]
if tmp >= i:
return i
return 0
方法二：sort
首先对原数组按升序排序，然后二分寻找。我们的目标是尽量往前走，length-cur为h因子。对于位置cur,可知引用大于等于cur的共有length-cur篇,如果citations[mid] ==length - cur,那么h=length-cur,因为你无法再往前走了（citations缩小而文章数增大）;如果citations[mid] < length - cur,表明mid这个位置已经不满足条件了;citations[mid]>length-cur,表明还可以继续往前走，多增加几篇文章，增大h。
def hIndex(self, citations):
"""
:type citations: List[int]
:rtype: int
"""
if not citations:
return 0
citations.sort()
length = len(citations)
start = 0
end = length - 1
while start + 1 < end:
mid = (start + end) / 2
if citations[mid] == length - mid:
return length - mid
elif citations[mid] < length - mid:
start = mid
else :
end = mid
if citations[start] >= length - start:
return length - start
elif citations[end] >= length - end:
return length - end
else:
return 0
GFS Client
Implement a simple client for GFS (Google File System, a distributed file system), it provides the following methods:
read(filename). Read the file with given filename from GFS.write(filename, content). Write a file with given filename & content to GFS.There are two private methods that already implemented in the base class:
readChunk(filename, chunkIndex). Read a chunk from GFS.writeChunk(filename, chunkIndex, chunkData). Write a chunk to GFS.To simplify this question, we can assume that the chunk size is chunkSizebytes. (In a real world system, it is 64M). The GFS Client's job is splitting a file into multiple chunks (if need) and save to the remote GFS server.chunkSize will be given in the constructor. You need to call these two private methods to implement read & write methods.
int chunkSize;
HashMap<String, Integer> chunkNum;
public GFSClient(int chunkSize) {
// initialize your data structure here
this.chunkSize = chunkSize;
chunkNum = new HashMap<String, Integer>();
} // @param filename a file name
// @return conetent of the file given from GFS
public String read(String filename) {
// Write your code here
if (!chunkNum.containsKey(filename)) {
return null;
}
int num = chunkNum.get(filename);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < num; i++) {
sb.append(readChunk(filename, i));
}
return sb.toString();
} // @param filename a file name
// @param content a string
// @return void
public void write(String filename, String content) {
// Write your code here
int length = content.length();
int num = (length - 1) / chunkSize + 1;
chunkNum.put(filename, num);
for (int i = 0; i < num; i++) {
int start = i * chunkSize;
int end = i == num - 1 ? length : (i + 1) * chunkSize;
String chunk = content.substring(start, end);
writeChunk(filename, i, chunk);
}
}
132 Pattern --not bug free***
Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.
方法一：检测每一个打头的是否满足。每一个的时候保留最大的大于它的。O(n^2)
public boolean find132pattern(int[] nums) {
if (nums == null || nums.length == 0) {
return false;
}
int n = nums.length;
int min = nums[0];
for (int i = 0; i < n - 2; i++) {
min = nums[i];
int max = Integer.MIN_VALUE;
for (int j = i + 1; j < n; j++) {
if (nums[j] > max) {
max = nums[j];
}
if (nums[j] < max && nums[j] > min) {
return true;
}
}
}
return false;
}
方法二：使用栈，记录最小最大区间。
画出一个图来就会比较好分析。
算法更新规则：
遍历数组，栈为空或者栈顶元素最小值大于新来的数的时候，压入栈。
新来元素素等于栈顶最小值不做任何操作
新来元素大于栈顶最小值，表明栈顶这个区间有机会了。看看新来的数是否小于栈顶最大值，如果是的，表明满足条件。如果新来的数大于等于栈顶最大值，此时画出图来就很明白，后面大的区间有可能有 满足条件的区间。弹出栈中元素如果栈不为空并且新来的数大于大于栈顶最大值。不用担心这些被弹出的区间带来什么问题，因为后边要压入一个大区间就包含了这些小区间。弹出完成之后检测如果新来的 数大于栈顶数的最小值则满足条件。最后把新来的数当最大值，最开始弹出的最小值为最小值压入栈。
public boolean find132pattern(int[] nums) {
if (nums == null || nums.length < 3) {
return false;
}
Stack<Pair> stack = new Stack<Pair>();
for (int i = 0; i < nums.length; i++) {
if (stack.isEmpty() || nums[i] < stack.peek().min) {
stack.push(new Pair(nums[i], nums[i]));
} else if (stack.peek().min == nums[i]) {
continue;
} else {
Pair top = stack.pop();
if (nums[i] < top.max) {
return true;
} else {
while (!stack.isEmpty() && stack.peek().max < nums[i]) {
stack.pop();
}
if (!stack.isEmpty() && stack.peek().min < nums[i]) {
return true;
}
top.max = nums[i];
stack.push(top);
}
}
}
return false;
}
class Pair {
int min;
int max;
public Pair(int min, int max) {
this.min = min;
this.max = max;
}
}
