Implement Stack using Queues leetcode

mplement the following operations of a stack using queues.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• empty() -- Return whether the stack is empty.

Notes:

• You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.
• Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
• You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

方法1: push() O(1), pop() O(n), peek() O(n) 用两个queue 来实现, 每次pop事后都把q1前边的都推入q2中, 最后一个出列, 然后q1, q2互换, top时候同理, 只是最后一个元素也入列q2.

class MyStack {
    Queue<Integer> q1 = new LinkedList<Integer>();
    Queue<Integer> q2 = new LinkedList<Integer>();
    public void push(int x) {
        q1.offer(x);
    }

    // Removes the element on top of the stack.
    public void pop() {
        while (q1.size() > 1) {
            q2.offer(q1.poll());
        }
        q1.poll();
        Queue tem = q1;
        q1 = q2;
        q2 = tem;
    }

    // Get the top element.
    public int top() {
        while (q1.size() > 1) {
            q2.offer(q1.poll());
        }
        int res = q1.peek();
        q2.offer(q1.poll());
        Queue tem = q1;
        q1 = q2;
        q2 = tem;
        return res;
    }

    // Return whether the stack is empty.
    public boolean empty() {
        return q1.isEmpty();
    }
}

方法2: push() O(n), pop() O(1), peek() O(1) 用两个queue 来实现, 每次push时候都入列q2, 然后再把q1的元素都一一入列q2直到q1空为止, 然后q1 q2互换. 这样q1内元素的出列顺序和stack中的顺序相同 所以pop 和 top功能就是q1的 poll() 和peek()

class MyStack {
    Queue<Integer> q1 = new LinkedList<Integer>();
    Queue<Integer> q2 = new LinkedList<Integer>();
    public void push(int x) {
        q2.offer(x);
        while (!q1.isEmpty()) {
            q2.offer(q1.poll());
        }
        Queue tem = q1;
        q1 = q2;
        q2 = tem;
    }

    // Removes the element on top of the stack.
    public void pop() {
        q1.poll();
    }

    // Get the top element.
    public int top() {
        
        return q1.peek();
    }

    // Return whether the stack is empty.
    public boolean empty() {
        return q1.isEmpty();
    }
}

Two Sum III - Data structure design leetcode

Design and implement a TwoSum class. It should support the following operations: add and find.

add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.

For example,

add(1); add(3); add(5);
find(4) -> true
find(7) -> false

public class TwoSum {
    private HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    // Add the number to an internal data structure.
 public void add(int number) {
     if (map.containsKey(number)) {
         map.put(number, map.get(number) + 1);
     } else {
         map.put(number, 1);
     }
 }

    // Find if there exists any pair of numbers which sum is equal to the value.
 public boolean find(int value) {
     for (Integer s : map.keySet()) {
         int tem = value - s;
         if (tem == s && map.get(tem) > 1) {
             return true;
         } 
         if ( tem != s && map.containsKey(tem)) {
                 return true;
         }
     }
     return false;
 }
}

Insert Interval leetcode

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

遍历整个interval组, 

如果cur.end > 给出interval.start 说明要merge的区间在后面 当前的interval可以入列

如果 cur.start > interval.end 说明merge去边在前边 注意这时候不是当前cur入列 而是interval入列 并且让当前的cur = interval

如果cur跟interval有重叠 只更新interval的范围 不入列

注意因为遍历完成之后1. interval的范围比较大 还没入列

2. interval已经入列了但是cur还没入列  但是此intval的值 = cur 

所以循环之后都要把interval入列 

因为遍历一遍 所以时间O(n)

public class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> res = new ArrayList<Interval>();
        for (Interval cur : intervals) {
            if (cur.start > newInterval.end) {
                res.add(newInterval);
                newInterval = cur;
            } else if (cur.end < newInterval.start) {
                res.add(cur);
            } else if (cur.start < newInterval.end || cur.end > newInterval.start) {
                newInterval.start = Math.min(cur.start, newInterval.start);
                newInterval.end = Math.max(cur.end, newInterval.end);
            }
        }
        res.add(newInterval);
        return res;
    }
}

Merge Intervals leetcode

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

 讲解转自http://codeganker.blogspot.com/2014/03/merge-intervals-leetcode.html

"这是一道关于interval数组结构的操作，在面试中也是一种比较常见的数据结构。假设这些interval是有序的（也就是说先按起始点排序，然后如果起始点相同就按结束点排序），那么要把它们合并就只需要按顺序读过来，如果当前一个和结果集中最后一个有重叠，那么就把结果集中最后一个元素设为当前元素的结束点（不用改变起始点因为起始点有序，因为结果集中最后一个元素起始点已经比当前元素小了）。那么剩下的问题就是如何给interval排序，在java实现中就是要给interval自定义一个Comparator，规则是按起始点排序，然后如果起始点相同就按结束点排序。整个算法是先排序，然后再做一次线性遍历，时间复杂度是O(nlogn+n)=O(nlogn)，空间复杂度是O(1)，因为不需要额外空间，只有结果集的空间。"

Comparable 和Comparator用法

Comparable

一个实现了comparable接口的对象的实例可以被用于和相同对象的不同实例做对比。它本身必须实现java.lang.Comparable的接口，这样它就拥有了对比的能力。

有一部分类实现了Comparable接口,如Integer Double和String等。 
Comparable接口有一个comparTo(Object o)方法,它返回整数类型。java.lang.Comparable: int compareTo(Object o1)

这个方法用于当前对象与o1对象做对比，返回int值，分别的意思是：

• positive – 当前对象大于o1
• zero – 当前对象等于o1
• negative – 当前对象小于o1

Comparator

一个实现了comparator接口的对象能够对比不同的对象。它不能用于同一个类的不同实例的对比，但是可以用于其他的类的实例做对比。它必须实现java.util.Comparator的接口。

java.util.Comparator: int compare(Object o1, Objecto2)

这个方法用于o1与o2对象做对比，返回int值，分别的意思是：

• positive – o1大于o2
• zero – o1等于o2
• negative – o1小于o2



java.util.Collections.sort(List) 和 java.util.Arrays.sort(Object[]) 方法被用来排列使用内在排序（natural ordering）方式的对象
java.util.Collections.sort(List, Comparator) 和 java.util.Arrays.sort(Object[], Comparator)方法在Comparator如果可供比较的时候会被用到。
综上, 如果有comparable接口的排序就用Colletions.sort(list), 没有救用Colletion.sort(list, comparator)
所以这里要写一个comparator

class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals == null || intervals.size() <= 1) {
            return intervals;
        }
        ArrayList<Interval> res = new ArrayList<Interval>();
        Comparator<Interval> com= new Comparator<Interval>() {
            public int compare(Interval i1, Interval i2) {
                return i1.start - i2.start;
            }
        };
        Collections.sort(intervals, com);
        Interval prev = intervals.get(0);
        for (int i = 1; i < intervals.size(); i++) {
            Interval cur = intervals.get(i);
            if (prev.end >= cur.start) {
                prev = new Interval(prev.start, Math.max(prev.end, cur.end));
            } else {
                res.add(prev);
                prev = cur;
            }
        }
        res.add(prev);//把最后一个prev添加到结果里
        return res;
    }

}

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.

这道题可以用链表来实现 但是复杂度是O(n^2)

题解：

解决这道题的方法是：双向链表+HashMap。

“为了能够快速删除最久没有访问的数据项和插入最新的数据项，我们将双向链表连接Cache中的数据项，并且保证链表维持数据项从最近访问到最旧访问的顺序。 每次数据项被查询到时，都将此数据项移动到链表头部（O(1)的时间复杂度）。这样，在进行过多次查找操作后，最近被使用过的内容就向链表的头移动，而没 有被使用的内容就向链表的后面移动。当需要替换时，链表最后的位置就是最近最少被使用的数据项，我们只需要将最新的数据项放在链表头部，当Cache满 时，淘汰链表最后的位置就是了。 ”

解决了LRU的特性，现在考虑下算法的时间复杂度。为了能减少整个数据结构的时间复杂度，就要减少查找的时间复杂度，所以这里利用HashMap来做，这样时间苏咋读就是O(1)。

 所以对于本题来说：

get(key): 如果cache中不存在要get的值，返回-1；如果cache中存在要找的值，返回其值并将其在原链表中删除，然后将其作为头结点。

set(key,value)：当要set的key值已经存在，就更新其value， 将其在原链表中删除，然后将其作为头结点；当药set的key值不存在，就新建一个node，如果当前len<capacity,就将其加入hashmap中，并将其作为头结点，更新len长度，否则，删除链表最后一个node，再将其放入hashmap并作为头结点，但len不更新。

原则就是：对链表有访问，就要更新链表顺序。 

数据结构

LRU的典型实现是hash map + doubly linked list， 双向链表用于存储数据结点，并且它是按照结点最近被使用的时间来存储的。 如果一个结点被访问了， 我们有理由相信它在接下来的一段时间被访问的概率要大于其它结点。于是， 我们把它放到双向链表的头部。当我们往双向链表里插入一个结点， 我们也有可能很快就会使用到它，同样把它插入到头部。 我们使用这种方式不断地调整着双向链表，链表尾部的结点自然也就是最近一段时间， 最久没有使用到的结点。那么，当我们的Cache满了， 需要替换掉的就是双向链表中最后的那个结点(不是尾结点，头尾结点不存储实际内容)。

如下是双向链表示意图，注意头尾结点不存储实际内容：

头 --> 结 --> 结 --> 结 --> 尾
结     点     点     点     结
点 <-- 1  <-- 2 <-- 3  <-- 点

假如上图Cache已满了，我们要替换的就是结点3。

哈希表的作用是什么呢？如果没有哈希表，我们要访问某个结点，就需要顺序地一个个找， 时间复杂度是O(n)。使用哈希表可以让我们在O(1)的时间找到想要访问的结点， 或者返回未找到。
时间 Get O(1) Set O(1) 空间 O(N)

public class LRUCache {//
    public class ListNode {
        int key;
        int val;
        ListNode prev;
        ListNode next;
        public ListNode(int k, int v) {
            this.key = k;
            this.val = v;
        }
    }
    int size;
    int capacity;
    HashMap<Integer, ListNode> map;
    ListNode head;
    ListNode tail;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.map = new HashMap<Integer, ListNode>();
        this.head = new ListNode(0, 0);
        this.tail = new ListNode(0, 0);
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        ListNode n = map.get(key);
        if(n != null){
            movehead(n);
            return n.val;
        } else {
            return -1;
        }
    }
    
    public void set(int key, int value) {
        ListNode node = map.get(key);
        if (node == null) {
            node = new ListNode(key, value);
            puthead(node);
            size++;
        } else {
            node.val = value;
            movehead(node);
        }
        if (size > capacity) {
            removelast();
            size--;
        }
        map.put(key, node);
    }
    public void movehead(ListNode n) {
        n.next.prev = n.prev;
        n.prev.next = n.next;
        puthead(n);
    }
    public void puthead(ListNode n) {
        n.next = head.next;
        n.next.prev = n;
        head.next = n;
        n.prev = head;
    }
    public void removelast() {
        ListNode last = tail.prev;
        last.prev.next = tail;
        tail.prev = last.prev;
        map.remove(last.key);
    }
}